xref: /unit/src/nxt_rbtree.h (revision 23:600903c98957)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #ifndef _NXT_RBTREE_H_INCLUDED_
8 #define _NXT_RBTREE_H_INCLUDED_
9 
10 
11 typedef struct nxt_rbtree_node_s  nxt_rbtree_node_t;
12 
13 struct nxt_rbtree_node_s {
14     nxt_rbtree_node_t         *left;
15     nxt_rbtree_node_t         *right;
16     nxt_rbtree_node_t         *parent;
17 
18     uint8_t                   color;
19 };
20 
21 
22 typedef struct {
23     nxt_rbtree_node_t         *left;
24     nxt_rbtree_node_t         *right;
25     nxt_rbtree_node_t         *parent;
26 } nxt_rbtree_part_t;
27 
28 
29 #define NXT_RBTREE_NODE(node)                                                 \
30     nxt_rbtree_part_t         node;                                           \
31     uint8_t                   node##_color
32 
33 
34 #define NXT_RBTREE_NODE_INIT  { NULL, NULL, NULL }, 0
35 
36 
37 typedef struct {
38     nxt_rbtree_node_t         sentinel;
39 } nxt_rbtree_t;
40 
41 
42 /*
43  * A comparison function should return intptr_t result because
44  * this eliminates overhead required to implement correct addresses
45  * comparison without result truncation.
46  */
47 typedef intptr_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
48     nxt_rbtree_node_t *node2);
49 
50 
51 #define nxt_rbtree_root(tree)                                                 \
52     ((tree)->sentinel.left)
53 
54 
55 #define nxt_rbtree_sentinel(tree)                                             \
56     (&(tree)->sentinel)
57 
58 
59 #define nxt_rbtree_is_empty(tree)                                             \
60     (nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree))
61 
62 
63 #define nxt_rbtree_min(tree)                                                  \
64     nxt_rbtree_branch_min(tree, &(tree)->sentinel)
65 
66 
67 nxt_inline nxt_rbtree_node_t *
nxt_rbtree_branch_min(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)68 nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
69 {
70     while (node->left != nxt_rbtree_sentinel(tree)) {
71         node = node->left;
72     }
73 
74     return node;
75 }
76 
77 
78 #define nxt_rbtree_is_there_successor(tree, node)                             \
79     ((node) != nxt_rbtree_sentinel(tree))
80 
81 
82 nxt_inline nxt_rbtree_node_t *
nxt_rbtree_node_successor(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)83 nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
84 {
85     nxt_rbtree_node_t  *parent;
86 
87     if (node->right != nxt_rbtree_sentinel(tree)) {
88         return nxt_rbtree_branch_min(tree, node->right);
89     }
90 
91     for ( ;; ) {
92         parent = node->parent;
93 
94         /*
95          * Explicit test for a root node is not required here, because
96          * the root node is always the left child of the sentinel.
97          */
98         if (node == parent->left) {
99             return parent;
100         }
101 
102         node = parent;
103     }
104 }
105 
106 
107 NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree,
108     nxt_rbtree_compare_t compare);
109 NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
110 NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree,
111     nxt_rbtree_part_t *node);
112 NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree,
113     nxt_rbtree_part_t *node);
114 NXT_EXPORT nxt_rbtree_node_t
115     *nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
116     nxt_rbtree_part_t *node);
117 NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
118 
119 /*
120  * nxt_rbtree_destroy_next() is iterator to use only while rbtree destruction.
121  * It deletes a node from rbtree and returns the node.  The rbtree is not
122  * rebalanced after deletion.  At the beginning the "next" parameter should
123  * be equal to rbtree root.  The iterator should be called in loop until
124  * the "next" parameter will be equal to the rbtree sentinel.  No other
125  * operations must be performed on the rbtree while destruction.
126  */
127 NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_destroy_next(nxt_rbtree_t *tree,
128     nxt_rbtree_node_t **next);
129 
130 
131 #endif /* _NXT_RBTREE_H_INCLUDED_ */
132