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.c`

if 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.

## No comments:

## Post a Comment