xref: /unit/src/test/nxt_rbtree1.h (revision 2673:08b48a5ad55d)
1384Szelenkov@nginx.com 
2384Szelenkov@nginx.com /*
3384Szelenkov@nginx.com  * Copyright (C) Igor Sysoev
4*2673Szelenkov@nginx.com  * Copyright (C) NGINX, Inc.
5384Szelenkov@nginx.com  */
6384Szelenkov@nginx.com 
7384Szelenkov@nginx.com 
8384Szelenkov@nginx.com typedef nxt_uint_t  nxt_rbtree1_key_t;
9384Szelenkov@nginx.com typedef nxt_int_t   nxt_rbtree1_key_int_t;
10384Szelenkov@nginx.com 
11384Szelenkov@nginx.com 
12384Szelenkov@nginx.com typedef struct nxt_rbtree1_node_s  nxt_rbtree1_node_t;
13384Szelenkov@nginx.com 
14384Szelenkov@nginx.com struct nxt_rbtree1_node_s {
15384Szelenkov@nginx.com     nxt_rbtree1_key_t       key;
16384Szelenkov@nginx.com     nxt_rbtree1_node_t     *left;
17384Szelenkov@nginx.com     nxt_rbtree1_node_t     *right;
18384Szelenkov@nginx.com     nxt_rbtree1_node_t     *parent;
19384Szelenkov@nginx.com     u_char                  color;
20384Szelenkov@nginx.com     u_char                  data;
21384Szelenkov@nginx.com };
22384Szelenkov@nginx.com 
23384Szelenkov@nginx.com 
24384Szelenkov@nginx.com typedef struct nxt_rbtree1_s  nxt_rbtree1_t;
25384Szelenkov@nginx.com 
26384Szelenkov@nginx.com typedef void (*nxt_rbtree1_insert_pt) (nxt_rbtree1_node_t *root,
27384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
28384Szelenkov@nginx.com 
29384Szelenkov@nginx.com struct nxt_rbtree1_s {
30384Szelenkov@nginx.com     nxt_rbtree1_node_t     *root;
31384Szelenkov@nginx.com     nxt_rbtree1_node_t     *sentinel;
32384Szelenkov@nginx.com     nxt_rbtree1_insert_pt   insert;
33384Szelenkov@nginx.com };
34384Szelenkov@nginx.com 
35384Szelenkov@nginx.com 
36384Szelenkov@nginx.com #define nxt_rbtree1_init(tree, s, i)                                          \
37384Szelenkov@nginx.com     nxt_rbtree1_sentinel_init(s);                                             \
38384Szelenkov@nginx.com     (tree)->root = s;                                                         \
39384Szelenkov@nginx.com     (tree)->sentinel = s;                                                     \
40384Szelenkov@nginx.com     (tree)->insert = i
41384Szelenkov@nginx.com 
42384Szelenkov@nginx.com 
43384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert(nxt_rbtree1_t *tree,
44384Szelenkov@nginx.com     nxt_rbtree1_node_t *node);
45384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_delete(nxt_rbtree1_t *tree,
46384Szelenkov@nginx.com     nxt_rbtree1_node_t *node);
47384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert_value(nxt_rbtree1_node_t *root,
48384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
49384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t *root,
50384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
51384Szelenkov@nginx.com 
52384Szelenkov@nginx.com 
53384Szelenkov@nginx.com #define nxt_rbtree1_red(node)               ((node)->color = 1)
54384Szelenkov@nginx.com #define nxt_rbtree1_black(node)             ((node)->color = 0)
55384Szelenkov@nginx.com #define nxt_rbtree1_is_red(node)            ((node)->color)
56384Szelenkov@nginx.com #define nxt_rbtree1_is_black(node)          (!nxt_rbtree1_is_red(node))
57384Szelenkov@nginx.com #define nxt_rbtree1_copy_color(n1, n2)      (n1->color = n2->color)
58384Szelenkov@nginx.com 
59384Szelenkov@nginx.com 
60384Szelenkov@nginx.com /* a sentinel must be black */
61384Szelenkov@nginx.com 
62384Szelenkov@nginx.com #define nxt_rbtree1_sentinel_init(node)  nxt_rbtree1_black(node)
63384Szelenkov@nginx.com 
64384Szelenkov@nginx.com 
65384Szelenkov@nginx.com nxt_inline nxt_rbtree1_node_t *
nxt_rbtree1_min(nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)66384Szelenkov@nginx.com nxt_rbtree1_min(nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel)
67384Szelenkov@nginx.com {
68384Szelenkov@nginx.com     while (node->left != sentinel) {
69384Szelenkov@nginx.com         node = node->left;
70384Szelenkov@nginx.com     }
71384Szelenkov@nginx.com 
72384Szelenkov@nginx.com     return node;
73384Szelenkov@nginx.com }
74