xref: /unit/src/test/nxt_rbtree1.h (revision 384:8f86d3ff3e29)
1*384Szelenkov@nginx.com 
2*384Szelenkov@nginx.com /*
3*384Szelenkov@nginx.com  * Copyright (C) Igor Sysoev
4*384Szelenkov@nginx.com  * Copyright (C) Nginx, Inc.
5*384Szelenkov@nginx.com  */
6*384Szelenkov@nginx.com 
7*384Szelenkov@nginx.com 
8*384Szelenkov@nginx.com typedef nxt_uint_t  nxt_rbtree1_key_t;
9*384Szelenkov@nginx.com typedef nxt_int_t   nxt_rbtree1_key_int_t;
10*384Szelenkov@nginx.com 
11*384Szelenkov@nginx.com 
12*384Szelenkov@nginx.com typedef struct nxt_rbtree1_node_s  nxt_rbtree1_node_t;
13*384Szelenkov@nginx.com 
14*384Szelenkov@nginx.com struct nxt_rbtree1_node_s {
15*384Szelenkov@nginx.com     nxt_rbtree1_key_t       key;
16*384Szelenkov@nginx.com     nxt_rbtree1_node_t     *left;
17*384Szelenkov@nginx.com     nxt_rbtree1_node_t     *right;
18*384Szelenkov@nginx.com     nxt_rbtree1_node_t     *parent;
19*384Szelenkov@nginx.com     u_char                  color;
20*384Szelenkov@nginx.com     u_char                  data;
21*384Szelenkov@nginx.com };
22*384Szelenkov@nginx.com 
23*384Szelenkov@nginx.com 
24*384Szelenkov@nginx.com typedef struct nxt_rbtree1_s  nxt_rbtree1_t;
25*384Szelenkov@nginx.com 
26*384Szelenkov@nginx.com typedef void (*nxt_rbtree1_insert_pt) (nxt_rbtree1_node_t *root,
27*384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
28*384Szelenkov@nginx.com 
29*384Szelenkov@nginx.com struct nxt_rbtree1_s {
30*384Szelenkov@nginx.com     nxt_rbtree1_node_t     *root;
31*384Szelenkov@nginx.com     nxt_rbtree1_node_t     *sentinel;
32*384Szelenkov@nginx.com     nxt_rbtree1_insert_pt   insert;
33*384Szelenkov@nginx.com };
34*384Szelenkov@nginx.com 
35*384Szelenkov@nginx.com 
36*384Szelenkov@nginx.com #define nxt_rbtree1_init(tree, s, i)                                          \
37*384Szelenkov@nginx.com     nxt_rbtree1_sentinel_init(s);                                             \
38*384Szelenkov@nginx.com     (tree)->root = s;                                                         \
39*384Szelenkov@nginx.com     (tree)->sentinel = s;                                                     \
40*384Szelenkov@nginx.com     (tree)->insert = i
41*384Szelenkov@nginx.com 
42*384Szelenkov@nginx.com 
43*384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert(nxt_rbtree1_t *tree,
44*384Szelenkov@nginx.com     nxt_rbtree1_node_t *node);
45*384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_delete(nxt_rbtree1_t *tree,
46*384Szelenkov@nginx.com     nxt_rbtree1_node_t *node);
47*384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert_value(nxt_rbtree1_node_t *root,
48*384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
49*384Szelenkov@nginx.com NXT_EXPORT void nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t *root,
50*384Szelenkov@nginx.com     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel);
51*384Szelenkov@nginx.com 
52*384Szelenkov@nginx.com 
53*384Szelenkov@nginx.com #define nxt_rbtree1_red(node)               ((node)->color = 1)
54*384Szelenkov@nginx.com #define nxt_rbtree1_black(node)             ((node)->color = 0)
55*384Szelenkov@nginx.com #define nxt_rbtree1_is_red(node)            ((node)->color)
56*384Szelenkov@nginx.com #define nxt_rbtree1_is_black(node)          (!nxt_rbtree1_is_red(node))
57*384Szelenkov@nginx.com #define nxt_rbtree1_copy_color(n1, n2)      (n1->color = n2->color)
58*384Szelenkov@nginx.com 
59*384Szelenkov@nginx.com 
60*384Szelenkov@nginx.com /* a sentinel must be black */
61*384Szelenkov@nginx.com 
62*384Szelenkov@nginx.com #define nxt_rbtree1_sentinel_init(node)  nxt_rbtree1_black(node)
63*384Szelenkov@nginx.com 
64*384Szelenkov@nginx.com 
65*384Szelenkov@nginx.com nxt_inline nxt_rbtree1_node_t *
nxt_rbtree1_min(nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)66*384Szelenkov@nginx.com nxt_rbtree1_min(nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel)
67*384Szelenkov@nginx.com {
68*384Szelenkov@nginx.com     while (node->left != sentinel) {
69*384Szelenkov@nginx.com         node = node->left;
70*384Szelenkov@nginx.com     }
71*384Szelenkov@nginx.com 
72*384Szelenkov@nginx.com     return node;
73*384Szelenkov@nginx.com }
74