Day 48 - ngx_rbtree_t

I told you so much about red-black trees over the last few days that I cannot pass on the pleasure of looking at the nginx version of those beasts, namely the ngx_rbtree_t structure.

From core/ngx_rbtree.h, you get the following definition of a tree:

struct {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};

A red-black tree is a root node, a sentinel node (for those of you who didn't pay attention to the part about ngx_queue_t in my previous post about locations and ngx_queue_t, here is what wikipedia defines as a sentinel node) and a ngx_rbtree_insert_pt, also known by its friends as a void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel), also known as a pointer to a function that will be invoked to insert a node in the tree.

A node is something like that:

struct {
    ngx_rbtree_key_t       key;
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};

• left and right are the usual names for the children nodes that all nodes of a binary search tree have (yes, a red-black tree is a special kind of binary search tree but you should really read my other posts...).
• parent is easy to figure out.
• color can be red or black (I won't get into the details of the red-black algorithm, but roughly you have one node out of two red and the other black.
• I left the best fields out: key and data because they really depend on what the red-black tree is like. The best way to explain how this works is probably to look at an example. I picked up the DNS resolver. Well, one might wonder why nginx needs its own DNS resolver. This is probably a good topic for exploration in the future. For now, all I know is that sometimes nginx cannot figure out at configuration time what is the backend (or upstream) server it needs to talk to. And when it does, it needs to resolve the name. And it resolves it asynchronously (just like everything it does) and puts the result in a cache (which happens to be a red-black tree).

But be fore we move to the example, I would like to give you a brief list of the interesting functions/macros defined by core/ngx_rbtree.h:

void ngx_rbtree_init(ngx_rbtree_t* tree, ngx_rbtree_node_t* s,
                     ngx_rbtree_insert_pt ins_func);
void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);

Hold on, something must be missing. There is no search/find/whatever you want to call it function that will retrieve the node I'm looking for. I thought red-black trees were binary search trees... ;) Well, they are! But Igor doesn't know what we are searching, so he can't help. It's also why we have to provide our own insertion function: this function has to figure out where to insert the node in the tree. But, hold on, there is a ngx_rbtree_insert. At this point (two levels of "hold on"), pretty much everybody should be lost and we should use the ultimate clarification tool: bullet-points. ;)

• About finding:
  • nginx doesn't know what you are storing in the tree.
  • Therefore, it cannot figure out by itself if node A is before node B (or after).
  • This could be solved by using a "comparator" function. For whatever reason, Igor did not go this way. Instead he left this task to the user of the red-black tree. This is usually a simple loop. So, most people trying to use a red-black tree should be able to write it.
• About inserting:
  • The first step of an insertion is a red-black tree is to find where to insert the node.
  • To do so, you need to know how to compare two nodes.
  • For the reasons mentioned above (in "About finding"), you (developer using ngx_rbtree) have to provide this infamous insertion function.
  • The second step is rebalancing the tree. This is a fairly complex algorithm (the one that makes use of the color of a node).
  • Therefore, it makes perfect sense to let Igor implement this algorithm (with some help from "Introduction to Algorithms" by Cormen, Leiserson and Rivest - or so he claims in the comments).
  • As a consequence, we end up with a ngx_rbtree_insert function provided by nginx that delegates the work in step 1 to ngx_rbtree_t.insert and does the heavy lifting of step 2.

Now, since I promised an example, let's look at how core/ngx_resolver.c uses this red-black tree. It all starts with the ngx_resolver_node_t structure:

typedef struct {
    ngx_rbtree_node_t         node;
    ngx_queue_t               queue;

    /* PTR: resolved name, A: name to resolve */
    u_char                   *name;
    [...]
}

Same trick as with ngx_queue_t: do some object inheritance by "glueing" your data after the structure you inherit from. And this also explains why the last element of the ngx_rbtree is named data (and why it has such a meaningless type): it is just a marker to show where the actual data (as opposed to the overhead due to the red-black tree) starts.

Function ngx_resolver_lookup_name does the lookup to retrieve the "resolver context" (a structure holding all the info needed to perform and track name resolution) based on the name to resolve. An interesting point is that it takes as argument a hash of the name on 32 bits (you'll see why very soon). And the code is so simple, I can paste it here:

    while (node != sentinel) {
        if (hash < node->key) {
            node = node->left;
            continue;
        }
        if (hash > node->key) {
            node = node->right;
            continue;
        }

        /* hash == node->key */
        do {
            rn = (ngx_resolver_node_t *) node;
            rc = ngx_memn2cmp(name->data, rn->name, name->len, rn->nlen);
            if (rc == 0) {
                return rn;
            }

            node = (rc < 0) ? node->left : node->right;
        } while (node != sentinel && hash == node->key);
        break;
    }

Yes, this red-black tree structure uses a hash of the string to index its elements and, once this is not enough (after all it's just a hash), it uses the string comparison. The main benefit is obviously speed as you don't have to perform a string comparison for each node you traverse.

And last, the function ngx_resolver_rbtree_insert_value is provided to insert the node and its code is very similar to the one from ngx_resolver_lookup_name because it first searches where to insert the node. Then, all it does is to attach it and paint it red (something mandatory for the balancing algorithm to work).

One last thing: I lied. ;) There are a couple of insert functions provided by nginx for "standard" nodes:

• ngx_rbtree_insert_value if what you are indexing is an unsigned int and you put it in key.
• ngx_rbtree_insert_timer_value for timers.
• ngx_str_rbtree_insert_value and ngx_str_rbtree_lookup (look in core/ngx_string.cif you index strings and use key to store a 32-bit hash of your string. If you look at the code you'll also notice that the string should be stored starting at data. Does that ring a bell?

There might be others but this should be enough for most uses and if it's not, that gives you plenty of examples to work with.