xref: /unit/src/nxt_rbtree.h (revision 0)
1*0Sigor@sysoev.ru 
2*0Sigor@sysoev.ru /*
3*0Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
4*0Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
5*0Sigor@sysoev.ru  */
6*0Sigor@sysoev.ru 
7*0Sigor@sysoev.ru #ifndef _NXT_RBTREE_H_INCLUDED_
8*0Sigor@sysoev.ru #define _NXT_RBTREE_H_INCLUDED_
9*0Sigor@sysoev.ru 
10*0Sigor@sysoev.ru 
11*0Sigor@sysoev.ru typedef struct nxt_rbtree_node_s  nxt_rbtree_node_t;
12*0Sigor@sysoev.ru 
13*0Sigor@sysoev.ru struct nxt_rbtree_node_s {
14*0Sigor@sysoev.ru     nxt_rbtree_node_t  *left;
15*0Sigor@sysoev.ru     nxt_rbtree_node_t  *right;
16*0Sigor@sysoev.ru     nxt_rbtree_node_t  *parent;
17*0Sigor@sysoev.ru 
18*0Sigor@sysoev.ru     uint8_t            color;
19*0Sigor@sysoev.ru     uint8_t            spare;
20*0Sigor@sysoev.ru };
21*0Sigor@sysoev.ru 
22*0Sigor@sysoev.ru 
23*0Sigor@sysoev.ru typedef struct {
24*0Sigor@sysoev.ru     nxt_rbtree_node_t  *left;
25*0Sigor@sysoev.ru     nxt_rbtree_node_t  *right;
26*0Sigor@sysoev.ru     nxt_rbtree_node_t  *parent;
27*0Sigor@sysoev.ru } nxt_rbtree_part_t;
28*0Sigor@sysoev.ru 
29*0Sigor@sysoev.ru 
30*0Sigor@sysoev.ru #define NXT_RBTREE_NODE(node)                                                 \
31*0Sigor@sysoev.ru     nxt_rbtree_part_t  node;                                                  \
32*0Sigor@sysoev.ru     uint8_t            color
33*0Sigor@sysoev.ru 
34*0Sigor@sysoev.ru 
35*0Sigor@sysoev.ru #define NXT_RBTREE_NODE_INIT  { NULL, NULL, NULL }, 0
36*0Sigor@sysoev.ru 
37*0Sigor@sysoev.ru 
38*0Sigor@sysoev.ru typedef struct {
39*0Sigor@sysoev.ru     nxt_rbtree_node_t  sentinel;
40*0Sigor@sysoev.ru } nxt_rbtree_t;
41*0Sigor@sysoev.ru 
42*0Sigor@sysoev.ru 
43*0Sigor@sysoev.ru typedef void (*nxt_rbtree_insert_t)(nxt_rbtree_node_t *root,
44*0Sigor@sysoev.ru     nxt_rbtree_node_t *node, nxt_rbtree_node_t *sentinel);
45*0Sigor@sysoev.ru 
46*0Sigor@sysoev.ru typedef nxt_int_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
47*0Sigor@sysoev.ru     nxt_rbtree_node_t *node2);
48*0Sigor@sysoev.ru 
49*0Sigor@sysoev.ru 
50*0Sigor@sysoev.ru #define                                                                       \
51*0Sigor@sysoev.ru nxt_rbtree_root(tree)                                                         \
52*0Sigor@sysoev.ru     ((tree)->sentinel.left)
53*0Sigor@sysoev.ru 
54*0Sigor@sysoev.ru 
55*0Sigor@sysoev.ru #define nxt_rbtree_sentinel(tree)                                             \
56*0Sigor@sysoev.ru     (&(tree)->sentinel)
57*0Sigor@sysoev.ru 
58*0Sigor@sysoev.ru 
59*0Sigor@sysoev.ru #define nxt_rbtree_is_empty(tree)                                             \
60*0Sigor@sysoev.ru     (nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree))
61*0Sigor@sysoev.ru 
62*0Sigor@sysoev.ru 
63*0Sigor@sysoev.ru #define nxt_rbtree_min(tree)                                                  \
64*0Sigor@sysoev.ru     nxt_rbtree_branch_min(tree, &(tree)->sentinel)
65*0Sigor@sysoev.ru 
66*0Sigor@sysoev.ru 
67*0Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t *
68*0Sigor@sysoev.ru nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
69*0Sigor@sysoev.ru {
70*0Sigor@sysoev.ru     while (node->left != nxt_rbtree_sentinel(tree)) {
71*0Sigor@sysoev.ru         node = node->left;
72*0Sigor@sysoev.ru     }
73*0Sigor@sysoev.ru 
74*0Sigor@sysoev.ru     return node;
75*0Sigor@sysoev.ru }
76*0Sigor@sysoev.ru 
77*0Sigor@sysoev.ru 
78*0Sigor@sysoev.ru #define nxt_rbtree_is_there_successor(tree, node)                             \
79*0Sigor@sysoev.ru     ((node) != nxt_rbtree_sentinel(tree))
80*0Sigor@sysoev.ru 
81*0Sigor@sysoev.ru 
82*0Sigor@sysoev.ru nxt_inline nxt_rbtree_node_t *
83*0Sigor@sysoev.ru nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
84*0Sigor@sysoev.ru {
85*0Sigor@sysoev.ru     nxt_rbtree_node_t  *parent;
86*0Sigor@sysoev.ru 
87*0Sigor@sysoev.ru     if (node->right != nxt_rbtree_sentinel(tree)) {
88*0Sigor@sysoev.ru         return nxt_rbtree_branch_min(tree, node->right);
89*0Sigor@sysoev.ru     }
90*0Sigor@sysoev.ru 
91*0Sigor@sysoev.ru     for ( ;; ) {
92*0Sigor@sysoev.ru         parent = node->parent;
93*0Sigor@sysoev.ru 
94*0Sigor@sysoev.ru         /*
95*0Sigor@sysoev.ru          * Explicit test for a root node is not required here, because
96*0Sigor@sysoev.ru          * the root node is always the left child of the sentinel.
97*0Sigor@sysoev.ru          */
98*0Sigor@sysoev.ru         if (node == parent->left) {
99*0Sigor@sysoev.ru             return parent;
100*0Sigor@sysoev.ru         }
101*0Sigor@sysoev.ru 
102*0Sigor@sysoev.ru         node = parent;
103*0Sigor@sysoev.ru     }
104*0Sigor@sysoev.ru }
105*0Sigor@sysoev.ru 
106*0Sigor@sysoev.ru 
107*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree,
108*0Sigor@sysoev.ru     nxt_rbtree_compare_t compare, nxt_rbtree_insert_t insert);
109*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
110*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree,
111*0Sigor@sysoev.ru     nxt_rbtree_part_t *node);
112*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree,
113*0Sigor@sysoev.ru     nxt_rbtree_part_t *node);
114*0Sigor@sysoev.ru NXT_EXPORT nxt_rbtree_node_t *
115*0Sigor@sysoev.ru     nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
116*0Sigor@sysoev.ru     nxt_rbtree_part_t *node);
117*0Sigor@sysoev.ru NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
118*0Sigor@sysoev.ru 
119*0Sigor@sysoev.ru 
120*0Sigor@sysoev.ru #endif /* _NXT_RBTREE_H_INCLUDED_ */
121