Red black tree library - nginx

See wikipedia link on rb tree description.  Red black tree provides improvement over binary trees that makes it faster to search and also faster to insert/delete nodes.  It applies four principles as described in wiki link to balance the tree after every addition and deletion.  These principles make it search performance predictable.  These rebalancing principles are not expensive and hence insert and delete operations are also faster.

Nginx web server uses rb trees to cache SSL sessions across threads, to store the open file cache entries and for many other purposes.

Nginx rbtree implementation does not include all  binary tree operations. It leaves the binary tree insertion to the applications.  It does rebalancing of the tree and also it provides delete operation API function. It lets the application to do the 'search' on binary tree.  Note that search operation on rbtree is same as search operation on binary tree.

Though implementation of 'rbtree' implementation looks complicated (mainly if you have not gone through the algorithm before),   its usage by application is simple.  Applications need to define the root and put the node in the structure elements which it wants to put in the rbtree.

Following type definition of the rbtree root is defined by 'rbtree' implementation:

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

root :  This is root of the binary tree.
setinel:  This node is created to empty node for leaves. See wikilink to understand the usage of this. This is really dummy node memory.
insert:  This is function pointer to application function which does insertion into the binary tree.

struct ngx_rbtree_node_s {
    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;
};

ngx_rbtree_node_s is expected to be defined in each element that application needs to make it part of rbtree.

Key:  This is the key.  Applications typically put the hash value of the actual application key in here.  This is used to traverse to left and right based on key value. If two nodes have same key value, then the entire application key is used to make decision.   I guess this is done to improve performance.  Application key can be long.  Integer based comparisons are faster.

left, right, parent:  Are used to maintain the node in the tree.  left and right point to the children and parent point to the parent node.

color:  Color of the node - Red or black.

data:  Start of application data. It is not used by rbtree.

API functions:

•  ngx_rbtree_init(tree, s, i) : This macro initialize the rbtree instance.  'tree' is pointer to the 'rbtree' instance of type ngx_rbtree_t.   's' is pointer to sentinel node and 'i' is pointer to the insert function. This is the first macro that needs to be called by application to initialize the rbtree instance.
• void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,     ngx_rbtree_node_t *node) : This function is called by application to put a new node in the rbtree. This function internally calls the insert function provided to ngx_rbtree_init before to insert the node as per application key in the binary tree. Then ngx_rbtree_insert function continues to do the rebalancing of the tree.
• void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,     ngx_rbtree_node_t *node):  This function is called to remove 'node' from the rbtree 'tree'.  It removes the node from the binary tree and reblances it as per rbtree principles.