xref: /unit/src/nxt_rbtree.h (revision 23:600903c98957)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #ifndef _NXT_RBTREE_H_INCLUDED_
80Sigor@sysoev.ru #define _NXT_RBTREE_H_INCLUDED_
90Sigor@sysoev.ru 
100Sigor@sysoev.ru 
110Sigor@sysoev.ru typedef struct nxt_rbtree_node_s  nxt_rbtree_node_t;
120Sigor@sysoev.ru 
130Sigor@sysoev.ru struct nxt_rbtree_node_s {
145Sigor@sysoev.ru     nxt_rbtree_node_t         *left;
155Sigor@sysoev.ru     nxt_rbtree_node_t         *right;
165Sigor@sysoev.ru     nxt_rbtree_node_t         *parent;
170Sigor@sysoev.ru 
185Sigor@sysoev.ru     uint8_t                   color;
190Sigor@sysoev.ru };
200Sigor@sysoev.ru 
210Sigor@sysoev.ru 
220Sigor@sysoev.ru typedef struct {
235Sigor@sysoev.ru     nxt_rbtree_node_t         *left;
245Sigor@sysoev.ru     nxt_rbtree_node_t         *right;
255Sigor@sysoev.ru     nxt_rbtree_node_t         *parent;
260Sigor@sysoev.ru } nxt_rbtree_part_t;
270Sigor@sysoev.ru 
280Sigor@sysoev.ru 
290Sigor@sysoev.ru #define NXT_RBTREE_NODE(node)                                                 \
305Sigor@sysoev.ru     nxt_rbtree_part_t         node;                                           \
315Sigor@sysoev.ru     uint8_t                   node##_color
320Sigor@sysoev.ru 
330Sigor@sysoev.ru 
340Sigor@sysoev.ru #define NXT_RBTREE_NODE_INIT  { NULL, NULL, NULL }, 0
350Sigor@sysoev.ru 
360Sigor@sysoev.ru 
370Sigor@sysoev.ru typedef struct {
385Sigor@sysoev.ru     nxt_rbtree_node_t         sentinel;
390Sigor@sysoev.ru } nxt_rbtree_t;
400Sigor@sysoev.ru 
410Sigor@sysoev.ru 
425Sigor@sysoev.ru /*
435Sigor@sysoev.ru  * A comparison function should return intptr_t result because
445Sigor@sysoev.ru  * this eliminates overhead required to implement correct addresses
455Sigor@sysoev.ru  * comparison without result truncation.
465Sigor@sysoev.ru  */
475Sigor@sysoev.ru typedef intptr_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
480Sigor@sysoev.ru     nxt_rbtree_node_t *node2);
490Sigor@sysoev.ru 
500Sigor@sysoev.ru 
515Sigor@sysoev.ru #define nxt_rbtree_root(tree)                                                 \
520Sigor@sysoev.ru     ((tree)->sentinel.left)
530Sigor@sysoev.ru 
540Sigor@sysoev.ru 
550Sigor@sysoev.ru #define nxt_rbtree_sentinel(tree)                                             \
560Sigor@sysoev.ru     (&(tree)->sentinel)
570Sigor@sysoev.ru 
580Sigor@sysoev.ru 
590Sigor@sysoev.ru #define nxt_rbtree_is_empty(tree)                                             \
600Sigor@sysoev.ru     (nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree))
610Sigor@sysoev.ru 
620Sigor@sysoev.ru 
630Sigor@sysoev.ru #define nxt_rbtree_min(tree)                                                  \
640Sigor@sysoev.ru     nxt_rbtree_branch_min(tree, &(tree)->sentinel)
650Sigor@sysoev.ru 
660Sigor@sysoev.ru 
670Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t *
nxt_rbtree_branch_min(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)680Sigor@sysoev.ru nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
690Sigor@sysoev.ru {
700Sigor@sysoev.ru     while (node->left != nxt_rbtree_sentinel(tree)) {
710Sigor@sysoev.ru         node = node->left;
720Sigor@sysoev.ru     }
730Sigor@sysoev.ru 
740Sigor@sysoev.ru     return node;
750Sigor@sysoev.ru }
760Sigor@sysoev.ru 
770Sigor@sysoev.ru 
780Sigor@sysoev.ru #define nxt_rbtree_is_there_successor(tree, node)                             \
790Sigor@sysoev.ru     ((node) != nxt_rbtree_sentinel(tree))
800Sigor@sysoev.ru 
810Sigor@sysoev.ru 
820Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t *
nxt_rbtree_node_successor(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)830Sigor@sysoev.ru nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
840Sigor@sysoev.ru {
850Sigor@sysoev.ru     nxt_rbtree_node_t  *parent;
860Sigor@sysoev.ru 
870Sigor@sysoev.ru     if (node->right != nxt_rbtree_sentinel(tree)) {
880Sigor@sysoev.ru         return nxt_rbtree_branch_min(tree, node->right);
890Sigor@sysoev.ru     }
900Sigor@sysoev.ru 
910Sigor@sysoev.ru     for ( ;; ) {
920Sigor@sysoev.ru         parent = node->parent;
930Sigor@sysoev.ru 
940Sigor@sysoev.ru         /*
950Sigor@sysoev.ru          * Explicit test for a root node is not required here, because
960Sigor@sysoev.ru          * the root node is always the left child of the sentinel.
970Sigor@sysoev.ru          */
980Sigor@sysoev.ru         if (node == parent->left) {
990Sigor@sysoev.ru             return parent;
1000Sigor@sysoev.ru         }
1010Sigor@sysoev.ru 
1020Sigor@sysoev.ru         node = parent;
1030Sigor@sysoev.ru     }
1040Sigor@sysoev.ru }
1050Sigor@sysoev.ru 
1060Sigor@sysoev.ru 
1070Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree,
1085Sigor@sysoev.ru     nxt_rbtree_compare_t compare);
1090Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
1100Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree,
1110Sigor@sysoev.ru     nxt_rbtree_part_t *node);
1120Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree,
1130Sigor@sysoev.ru     nxt_rbtree_part_t *node);
1145Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t
1155Sigor@sysoev.ru     *nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
1160Sigor@sysoev.ru     nxt_rbtree_part_t *node);
1170Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
1180Sigor@sysoev.ru 
119*23Sigor@sysoev.ru /*
120*23Sigor@sysoev.ru  * nxt_rbtree_destroy_next() is iterator to use only while rbtree destruction.
121*23Sigor@sysoev.ru  * It deletes a node from rbtree and returns the node.  The rbtree is not
122*23Sigor@sysoev.ru  * rebalanced after deletion.  At the beginning the "next" parameter should
123*23Sigor@sysoev.ru  * be equal to rbtree root.  The iterator should be called in loop until
124*23Sigor@sysoev.ru  * the "next" parameter will be equal to the rbtree sentinel.  No other
125*23Sigor@sysoev.ru  * operations must be performed on the rbtree while destruction.
126*23Sigor@sysoev.ru  */
127*23Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_destroy_next(nxt_rbtree_t *tree,
128*23Sigor@sysoev.ru     nxt_rbtree_node_t **next);
129*23Sigor@sysoev.ru 
1300Sigor@sysoev.ru 
1310Sigor@sysoev.ru #endif /* _NXT_RBTREE_H_INCLUDED_ */
132