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