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