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