|
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 *
|
|
38
|
15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
|
|
34
|
16 {
|
|
36
|
17 uint32_t key, mask, inc;
|
|
34
|
18 ngx_radix_tree_t *tree;
|
|
|
19
|
|
50
|
20 tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
|
|
|
21 if (tree == NULL) {
|
|
34
|
22 return NULL;
|
|
|
23 }
|
|
|
24
|
|
|
25 tree->pool = pool;
|
|
|
26 tree->free = NULL;
|
|
|
27 tree->start = NULL;
|
|
|
28 tree->size = 0;
|
|
|
29
|
|
50
|
30 tree->root = ngx_radix_alloc(tree);
|
|
|
31 if (tree->root == NULL) {
|
|
34
|
32 return NULL;
|
|
|
33 }
|
|
|
34
|
|
|
35 tree->root->right = NULL;
|
|
|
36 tree->root->left = NULL;
|
|
|
37 tree->root->parent = NULL;
|
|
|
38 tree->root->value = NGX_RADIX_NO_VALUE;
|
|
|
39
|
|
38
|
40 if (preallocate == 0) {
|
|
|
41 return tree;
|
|
|
42 }
|
|
|
43
|
|
36
|
44 /*
|
|
42
|
45 * The preallocation the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc.
|
|
|
46 * increases the TLB hits even if for the first lookup iterations.
|
|
36
|
47 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K,
|
|
38
|
48 * 8 - 8K, 9 - 16K, etc. On the 64-bit platforms the 6 preallocated bits
|
|
|
49 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
|
|
|
50 * to preallocate more than one page, because further preallocation
|
|
48
|
51 * distributes the only bit per page. Instead, the random insertion
|
|
38
|
52 * may distribute several bits per page.
|
|
|
53 *
|
|
|
54 * Thus, by default we preallocate maximum
|
|
|
55 * 6 bits on amd64 (64-bit platform and 4K pages)
|
|
|
56 * 7 bits on i386 (32-bit platform and 4K pages)
|
|
|
57 * 7 bits on sparc64 in 64-bit mode (8K pages)
|
|
|
58 * 8 bits on sparc64 in 32-bit mode (8K pages)
|
|
36
|
59 */
|
|
|
60
|
|
38
|
61 if (preallocate == -1) {
|
|
|
62 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
|
|
|
63
|
|
|
64 /* amd64 */
|
|
|
65 case 128:
|
|
|
66 preallocate = 6;
|
|
|
67 break;
|
|
|
68
|
|
|
69 /* i386, sparc64 */
|
|
|
70 case 256:
|
|
|
71 preallocate = 7;
|
|
|
72 break;
|
|
|
73
|
|
|
74 /* sparc64 in 32-bit mode */
|
|
|
75 default:
|
|
|
76 preallocate = 8;
|
|
|
77 }
|
|
|
78 }
|
|
|
79
|
|
36
|
80 mask = 0;
|
|
|
81 inc = 0x80000000;
|
|
|
82
|
|
|
83 while (preallocate--) {
|
|
|
84
|
|
|
85 key = 0;
|
|
|
86 mask >>= 1;
|
|
|
87 mask |= 0x80000000;
|
|
|
88
|
|
|
89 do {
|
|
|
90 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
|
|
|
91 != NGX_OK)
|
|
|
92 {
|
|
|
93 return NULL;
|
|
|
94 }
|
|
|
95
|
|
|
96 key += inc;
|
|
|
97
|
|
|
98 } while (key);
|
|
|
99
|
|
|
100 inc >>= 1;
|
|
|
101 }
|
|
|
102
|
|
34
|
103 return tree;
|
|
|
104 }
|
|
|
105
|
|
|
106
|
|
36
|
107 ngx_int_t
|
|
|
108 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
|
|
|
109 uintptr_t value)
|
|
34
|
110 {
|
|
|
111 uint32_t bit;
|
|
|
112 ngx_radix_node_t *node, *next;
|
|
|
113
|
|
|
114 bit = 0x80000000;
|
|
|
115
|
|
|
116 node = tree->root;
|
|
|
117 next = tree->root;
|
|
|
118
|
|
|
119 while (bit & mask) {
|
|
|
120 if (key & bit) {
|
|
|
121 next = node->right;
|
|
|
122
|
|
|
123 } else {
|
|
|
124 next = node->left;
|
|
|
125 }
|
|
|
126
|
|
|
127 if (next == NULL) {
|
|
|
128 break;
|
|
|
129 }
|
|
|
130
|
|
|
131 bit >>= 1;
|
|
|
132 node = next;
|
|
|
133 }
|
|
|
134
|
|
|
135 if (next) {
|
|
|
136 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
137 return NGX_BUSY;
|
|
|
138 }
|
|
|
139
|
|
|
140 node->value = value;
|
|
|
141 return NGX_OK;
|
|
|
142 }
|
|
|
143
|
|
|
144 while (bit & mask) {
|
|
50
|
145 next = ngx_radix_alloc(tree);
|
|
|
146 if (next == NULL) {
|
|
34
|
147 return NGX_ERROR;
|
|
|
148 }
|
|
|
149
|
|
|
150 next->right = NULL;
|
|
|
151 next->left = NULL;
|
|
|
152 next->parent = node;
|
|
|
153 next->value = NGX_RADIX_NO_VALUE;
|
|
|
154
|
|
|
155 if (key & bit) {
|
|
|
156 node->right = next;
|
|
|
157
|
|
|
158 } else {
|
|
|
159 node->left = next;
|
|
|
160 }
|
|
|
161
|
|
|
162 bit >>= 1;
|
|
|
163 node = next;
|
|
|
164 }
|
|
|
165
|
|
|
166 node->value = value;
|
|
|
167
|
|
|
168 return NGX_OK;
|
|
|
169 }
|
|
|
170
|
|
|
171
|
|
36
|
172 ngx_int_t
|
|
|
173 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
|
|
34
|
174 {
|
|
|
175 uint32_t bit;
|
|
|
176 ngx_radix_node_t *node;
|
|
|
177
|
|
|
178 bit = 0x80000000;
|
|
|
179 node = tree->root;
|
|
|
180
|
|
|
181 while (node && (bit & mask)) {
|
|
|
182 if (key & bit) {
|
|
|
183 node = node->right;
|
|
|
184
|
|
|
185 } else {
|
|
|
186 node = node->left;
|
|
|
187 }
|
|
|
188
|
|
|
189 bit >>= 1;
|
|
|
190 }
|
|
|
191
|
|
|
192 if (node == NULL) {
|
|
|
193 return NGX_ERROR;
|
|
|
194 }
|
|
|
195
|
|
|
196 if (node->right || node->left) {
|
|
|
197 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
198 node->value = NGX_RADIX_NO_VALUE;
|
|
|
199 return NGX_OK;
|
|
|
200 }
|
|
|
201
|
|
|
202 return NGX_ERROR;
|
|
|
203 }
|
|
|
204
|
|
|
205 for ( ;; ) {
|
|
|
206 if (node->parent->right == node) {
|
|
|
207 node->parent->right = NULL;
|
|
112
|
208
|
|
34
|
209 } else {
|
|
|
210 node->parent->left = NULL;
|
|
|
211 }
|
|
|
212
|
|
|
213 node->right = tree->free;
|
|
|
214 tree->free = node;
|
|
|
215
|
|
|
216 node = node->parent;
|
|
|
217
|
|
112
|
218 if (node->right || node->left) {
|
|
|
219 break;
|
|
|
220 }
|
|
|
221
|
|
|
222 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
223 break;
|
|
|
224 }
|
|
|
225
|
|
|
226 if (node->parent == NULL) {
|
|
34
|
227 break;
|
|
|
228 }
|
|
|
229 }
|
|
|
230
|
|
|
231 return NGX_OK;
|
|
|
232 }
|
|
|
233
|
|
|
234
|
|
36
|
235 uintptr_t
|
|
|
236 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
|
|
34
|
237 {
|
|
|
238 uint32_t bit;
|
|
|
239 uintptr_t value;
|
|
|
240 ngx_radix_node_t *node;
|
|
|
241
|
|
|
242 bit = 0x80000000;
|
|
|
243 value = NGX_RADIX_NO_VALUE;
|
|
|
244 node = tree->root;
|
|
|
245
|
|
|
246 while (node) {
|
|
|
247 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
248 value = node->value;
|
|
|
249 }
|
|
|
250
|
|
|
251 if (key & bit) {
|
|
|
252 node = node->right;
|
|
|
253
|
|
|
254 } else {
|
|
|
255 node = node->left;
|
|
|
256 }
|
|
|
257
|
|
|
258 bit >>= 1;
|
|
|
259 }
|
|
|
260
|
|
|
261 return value;
|
|
|
262 }
|
|
|
263
|
|
|
264
|
|
36
|
265 static void *
|
|
|
266 ngx_radix_alloc(ngx_radix_tree_t *tree)
|
|
34
|
267 {
|
|
|
268 char *p;
|
|
|
269
|
|
|
270 if (tree->free) {
|
|
|
271 p = (char *) tree->free;
|
|
|
272 tree->free = tree->free->right;
|
|
|
273 return p;
|
|
|
274 }
|
|
|
275
|
|
|
276 if (tree->size < sizeof(ngx_radix_node_t)) {
|
|
50
|
277 tree->start = ngx_palloc(tree->pool, ngx_pagesize);
|
|
|
278 if (tree->start == NULL) {
|
|
34
|
279 return NULL;
|
|
|
280 }
|
|
|
281
|
|
|
282 tree->size = ngx_pagesize;
|
|
|
283 }
|
|
|
284
|
|
|
285 p = tree->start;
|
|
|
286 tree->start += sizeof(ngx_radix_node_t);
|
|
|
287 tree->size -= sizeof(ngx_radix_node_t);
|
|
|
288
|
|
|
289 return p;
|
|
|
290 }
|
