Using glibc tree search library

On 2017/12/11 at 00:11

When doing C programming, I found C POSIX library provides both tree library(tsearch) and hash table library(hsearch) to help C development. I look into the glibc's tree library implementation and surprisely found out that it is implemented using a red/black tree!

glibc misc/tsearch.c

So I did a little experiment as following to check if the tree is really balanced and the output show the tree is balanced as expected.

When reading the manpage of tsearch, the most interesting part is the const VISIT which argument in the action callback function for twalk. The manpage says:

preorder, postorder, and endorder are known as preorder, inorder, and postorder

So I had to use postorder to print the inorder traversal for the tree. You might be mislead by the postorder symbol as I did if you are using tsearch for the first time :)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <search.h>

int cmp(const void *a, const void *b)
    return *(int*)a - *(int*)b;

void walk_cb(const void *nodep, const VISIT which, const int depth)
    int *val = *(int **)nodep;
    if (leaf == which || postorder == which) {
        printf("val=%d, depth=%d\n", *val, depth);

int main()
    void *root = NULL;
    int val[10];


    for (int i = 0; i < 10; i++) {
        val[i] = i;
        tsearch(&val[i], &root, cmp);
    twalk(root, walk_cb);