1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/*
* Copyright (C) Igor Sysoev
* Copyright (C) NGINX, Inc.
*/
#ifndef _NXT_RBTREE_H_INCLUDED_
#define _NXT_RBTREE_H_INCLUDED_
typedef struct nxt_rbtree_node_s nxt_rbtree_node_t;
struct nxt_rbtree_node_s {
nxt_rbtree_node_t *left;
nxt_rbtree_node_t *right;
nxt_rbtree_node_t *parent;
uint8_t color;
};
typedef struct {
nxt_rbtree_node_t *left;
nxt_rbtree_node_t *right;
nxt_rbtree_node_t *parent;
} nxt_rbtree_part_t;
#define NXT_RBTREE_NODE(node) \
nxt_rbtree_part_t node; \
uint8_t node##_color
#define NXT_RBTREE_NODE_INIT { NULL, NULL, NULL }, 0
typedef struct {
nxt_rbtree_node_t sentinel;
} nxt_rbtree_t;
/*
* A comparison function should return intptr_t result because
* this eliminates overhead required to implement correct addresses
* comparison without result truncation.
*/
typedef intptr_t (*nxt_rbtree_compare_t)(nxt_rbtree_node_t *node1,
nxt_rbtree_node_t *node2);
#define nxt_rbtree_root(tree) \
((tree)->sentinel.left)
#define nxt_rbtree_sentinel(tree) \
(&(tree)->sentinel)
#define nxt_rbtree_is_empty(tree) \
(nxt_rbtree_root(tree) == nxt_rbtree_sentinel(tree))
#define nxt_rbtree_min(tree) \
nxt_rbtree_branch_min(tree, &(tree)->sentinel)
nxt_inline nxt_rbtree_node_t *
nxt_rbtree_branch_min(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
{
while (node->left != nxt_rbtree_sentinel(tree)) {
node = node->left;
}
return node;
}
#define nxt_rbtree_is_there_successor(tree, node) \
((node) != nxt_rbtree_sentinel(tree))
nxt_inline nxt_rbtree_node_t *
nxt_rbtree_node_successor(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
{
nxt_rbtree_node_t *parent;
if (node->right != nxt_rbtree_sentinel(tree)) {
return nxt_rbtree_branch_min(tree, node->right);
}
for ( ;; ) {
parent = node->parent;
/*
* Explicit test for a root node is not required here, because
* the root node is always the left child of the sentinel.
*/
if (node == parent->left) {
return parent;
}
node = parent;
}
}
NXT_EXPORT void nxt_rbtree_init(nxt_rbtree_t *tree,
nxt_rbtree_compare_t compare);
NXT_EXPORT void nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find(nxt_rbtree_t *tree,
nxt_rbtree_part_t *node);
NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree,
nxt_rbtree_part_t *node);
NXT_EXPORT nxt_rbtree_node_t
*nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree,
nxt_rbtree_part_t *node);
NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
/*
* nxt_rbtree_destroy_next() is iterator to use only while rbtree destruction.
* It deletes a node from rbtree and returns the node. The rbtree is not
* rebalanced after deletion. At the beginning the "next" parameter should
* be equal to rbtree root. The iterator should be called in loop until
* the "next" parameter will be equal to the rbtree sentinel. No other
* operations must be performed on the rbtree while destruction.
*/
NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_destroy_next(nxt_rbtree_t *tree,
nxt_rbtree_node_t **next);
#endif /* _NXT_RBTREE_H_INCLUDED_ */
|
