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