|
34
|
1
|
|
|
2 /*
|
|
|
3 * Copyright (C) Igor Sysoev
|
|
|
4 */
|
|
|
5
|
|
|
6
|
|
|
7 #include <ngx_config.h>
|
|
|
8 #include <ngx_core.h>
|
|
|
9
|
|
|
10
|
|
|
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
|
|
|
12
|
|
|
13
|
|
36
|
14 ngx_radix_tree_t *
|
|
|
15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_uint_t preallocate)
|
|
34
|
16 {
|
|
36
|
17 uint32_t key, mask, inc;
|
|
34
|
18 ngx_radix_tree_t *tree;
|
|
|
19
|
|
|
20 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
|
|
|
21 return NULL;
|
|
|
22 }
|
|
|
23
|
|
|
24 tree->pool = pool;
|
|
|
25 tree->free = NULL;
|
|
|
26 tree->start = NULL;
|
|
|
27 tree->size = 0;
|
|
|
28
|
|
|
29 if (!(tree->root = ngx_radix_alloc(tree))) {
|
|
|
30 return NULL;
|
|
|
31 }
|
|
|
32
|
|
|
33 tree->root->right = NULL;
|
|
|
34 tree->root->left = NULL;
|
|
|
35 tree->root->parent = NULL;
|
|
|
36 tree->root->value = NGX_RADIX_NO_VALUE;
|
|
|
37
|
|
36
|
38 /*
|
|
|
39 * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc.,
|
|
|
40 * to increase the TLB hits even if for the first lookup iterations.
|
|
|
41 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K,
|
|
|
42 * 8 - 8K, 9 - 16K, etc.
|
|
|
43 */
|
|
|
44
|
|
|
45 mask = 0;
|
|
|
46 inc = 0x80000000;
|
|
|
47
|
|
|
48 while (preallocate--) {
|
|
|
49
|
|
|
50 key = 0;
|
|
|
51 mask >>= 1;
|
|
|
52 mask |= 0x80000000;
|
|
|
53
|
|
|
54 do {
|
|
|
55 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
|
|
|
56 != NGX_OK)
|
|
|
57 {
|
|
|
58 return NULL;
|
|
|
59 }
|
|
|
60
|
|
|
61 key += inc;
|
|
|
62
|
|
|
63 } while (key);
|
|
|
64
|
|
|
65 inc >>= 1;
|
|
|
66 }
|
|
|
67
|
|
34
|
68 return tree;
|
|
|
69 }
|
|
|
70
|
|
|
71
|
|
36
|
72 ngx_int_t
|
|
|
73 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
|
|
|
74 uintptr_t value)
|
|
34
|
75 {
|
|
|
76 uint32_t bit;
|
|
|
77 ngx_radix_node_t *node, *next;
|
|
|
78
|
|
|
79 bit = 0x80000000;
|
|
|
80
|
|
|
81 node = tree->root;
|
|
|
82 next = tree->root;
|
|
|
83
|
|
|
84 while (bit & mask) {
|
|
|
85 if (key & bit) {
|
|
|
86 next = node->right;
|
|
|
87
|
|
|
88 } else {
|
|
|
89 next = node->left;
|
|
|
90 }
|
|
|
91
|
|
|
92 if (next == NULL) {
|
|
|
93 break;
|
|
|
94 }
|
|
|
95
|
|
|
96 bit >>= 1;
|
|
|
97 node = next;
|
|
|
98 }
|
|
|
99
|
|
|
100 if (next) {
|
|
|
101 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
102 return NGX_BUSY;
|
|
|
103 }
|
|
|
104
|
|
|
105 node->value = value;
|
|
|
106 return NGX_OK;
|
|
|
107 }
|
|
|
108
|
|
|
109 while (bit & mask) {
|
|
|
110 if (!(next = ngx_radix_alloc(tree))) {
|
|
|
111 return NGX_ERROR;
|
|
|
112 }
|
|
|
113
|
|
|
114 next->right = NULL;
|
|
|
115 next->left = NULL;
|
|
|
116 next->parent = node;
|
|
|
117 next->value = NGX_RADIX_NO_VALUE;
|
|
|
118
|
|
|
119 if (key & bit) {
|
|
|
120 node->right = next;
|
|
|
121
|
|
|
122 } else {
|
|
|
123 node->left = next;
|
|
|
124 }
|
|
|
125
|
|
|
126 bit >>= 1;
|
|
|
127 node = next;
|
|
|
128 }
|
|
|
129
|
|
|
130 node->value = value;
|
|
|
131
|
|
|
132 return NGX_OK;
|
|
|
133 }
|
|
|
134
|
|
|
135
|
|
36
|
136 ngx_int_t
|
|
|
137 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
|
|
34
|
138 {
|
|
|
139 uint32_t bit;
|
|
|
140 ngx_radix_node_t *node;
|
|
|
141
|
|
|
142 bit = 0x80000000;
|
|
|
143 node = tree->root;
|
|
|
144
|
|
|
145 while (node && (bit & mask)) {
|
|
|
146 if (key & bit) {
|
|
|
147 node = node->right;
|
|
|
148
|
|
|
149 } else {
|
|
|
150 node = node->left;
|
|
|
151 }
|
|
|
152
|
|
|
153 bit >>= 1;
|
|
|
154 }
|
|
|
155
|
|
|
156 if (node == NULL) {
|
|
|
157 return NGX_ERROR;
|
|
|
158 }
|
|
|
159
|
|
|
160 if (node->right || node->left) {
|
|
|
161 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
162 node->value = NGX_RADIX_NO_VALUE;
|
|
|
163 return NGX_OK;
|
|
|
164 }
|
|
|
165
|
|
|
166 return NGX_ERROR;
|
|
|
167 }
|
|
|
168
|
|
|
169 for ( ;; ) {
|
|
|
170 if (node->parent->right == node) {
|
|
|
171 node->parent->right = NULL;
|
|
|
172 } else {
|
|
|
173 node->parent->left = NULL;
|
|
|
174 }
|
|
|
175
|
|
|
176 node->right = tree->free;
|
|
|
177 tree->free = node;
|
|
|
178
|
|
|
179 node = node->parent;
|
|
|
180
|
|
|
181 if (node->right
|
|
|
182 || node->left
|
|
|
183 || node->value != NGX_RADIX_NO_VALUE
|
|
|
184 || node->parent == NULL)
|
|
|
185 {
|
|
|
186 break;
|
|
|
187 }
|
|
|
188 }
|
|
|
189
|
|
|
190 return NGX_OK;
|
|
|
191 }
|
|
|
192
|
|
|
193
|
|
36
|
194 uintptr_t
|
|
|
195 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
|
|
34
|
196 {
|
|
|
197 uint32_t bit;
|
|
|
198 uintptr_t value;
|
|
|
199 ngx_radix_node_t *node;
|
|
|
200
|
|
|
201 bit = 0x80000000;
|
|
|
202 value = NGX_RADIX_NO_VALUE;
|
|
|
203 node = tree->root;
|
|
|
204
|
|
|
205 while (node) {
|
|
|
206 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
207 value = node->value;
|
|
|
208 }
|
|
|
209
|
|
|
210 if (key & bit) {
|
|
|
211 node = node->right;
|
|
|
212
|
|
|
213 } else {
|
|
|
214 node = node->left;
|
|
|
215 }
|
|
|
216
|
|
|
217 bit >>= 1;
|
|
|
218 }
|
|
|
219
|
|
|
220 return value;
|
|
|
221 }
|
|
|
222
|
|
|
223
|
|
36
|
224 static void *
|
|
|
225 ngx_radix_alloc(ngx_radix_tree_t *tree)
|
|
34
|
226 {
|
|
|
227 char *p;
|
|
|
228
|
|
|
229 if (tree->free) {
|
|
|
230 p = (char *) tree->free;
|
|
|
231 tree->free = tree->free->right;
|
|
|
232 return p;
|
|
|
233 }
|
|
|
234
|
|
|
235 if (tree->size < sizeof(ngx_radix_node_t)) {
|
|
|
236 if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) {
|
|
|
237 return NULL;
|
|
|
238 }
|
|
|
239
|
|
|
240 tree->size = ngx_pagesize;
|
|
|
241 }
|
|
|
242
|
|
|
243 p = tree->start;
|
|
|
244 tree->start += sizeof(ngx_radix_node_t);
|
|
|
245 tree->size -= sizeof(ngx_radix_node_t);
|
|
|
246
|
|
|
247 return p;
|
|
|
248 }
|
