1
2/*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
5 */
6
7
8#include <ngx_config.h>
9#include <ngx_core.h>
10
11
12static ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree);
13
14
15ngx_radix_tree_t *
16ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
17{
18    uint32_t           key, mask, inc;
19    ngx_radix_tree_t  *tree;
20
21    tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
22    if (tree == NULL) {
23        return NULL;
24    }
25
26    tree->pool = pool;
27    tree->free = NULL;
28    tree->start = NULL;
29    tree->size = 0;
30
31    tree->root = ngx_radix_alloc(tree);
32    if (tree->root == NULL) {
33        return NULL;
34    }
35
36    tree->root->right = NULL;
37    tree->root->left = NULL;
38    tree->root->parent = NULL;
39    tree->root->value = NGX_RADIX_NO_VALUE;
40
41    if (preallocate == 0) {
42        return tree;
43    }
44
45    /*
46     * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
47     * increases TLB hits even if for first lookup iterations.
48     * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
49     * 8 - 8K, 9 - 16K, etc.  On 64-bit platforms the 6 preallocated bits
50     * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
51     * to preallocate more than one page, because further preallocation
52     * distributes the only bit per page.  Instead, a random insertion
53     * may distribute several bits per page.
54     *
55     * Thus, by default we preallocate maximum
56     *     6 bits on amd64 (64-bit platform and 4K pages)
57     *     7 bits on i386 (32-bit platform and 4K pages)
58     *     7 bits on sparc64 in 64-bit mode (8K pages)
59     *     8 bits on sparc64 in 32-bit mode (8K pages)
60     */
61
62    if (preallocate == -1) {
63        switch (ngx_pagesize / sizeof(ngx_radix_node_t)) {
64
65        /* amd64 */
66        case 128:
67            preallocate = 6;
68            break;
69
70        /* i386, sparc64 */
71        case 256:
72            preallocate = 7;
73            break;
74
75        /* sparc64 in 32-bit mode */
76        default:
77            preallocate = 8;
78        }
79    }
80
81    mask = 0;
82    inc = 0x80000000;
83
84    while (preallocate--) {
85
86        key = 0;
87        mask >>= 1;
88        mask |= 0x80000000;
89
90        do {
91            if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
92                != NGX_OK)
93            {
94                return NULL;
95            }
96
97            key += inc;
98
99        } while (key);
100
101        inc >>= 1;
102    }
103
104    return tree;
105}
106
107
108ngx_int_t
109ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
110    uintptr_t value)
111{
112    uint32_t           bit;
113    ngx_radix_node_t  *node, *next;
114
115    bit = 0x80000000;
116
117    node = tree->root;
118    next = tree->root;
119
120    while (bit & mask) {
121        if (key & bit) {
122            next = node->right;
123
124        } else {
125            next = node->left;
126        }
127
128        if (next == NULL) {
129            break;
130        }
131
132        bit >>= 1;
133        node = next;
134    }
135
136    if (next) {
137        if (node->value != NGX_RADIX_NO_VALUE) {
138            return NGX_BUSY;
139        }
140
141        node->value = value;
142        return NGX_OK;
143    }
144
145    while (bit & mask) {
146        next = ngx_radix_alloc(tree);
147        if (next == NULL) {
148            return NGX_ERROR;
149        }
150
151        next->right = NULL;
152        next->left = NULL;
153        next->parent = node;
154        next->value = NGX_RADIX_NO_VALUE;
155
156        if (key & bit) {
157            node->right = next;
158
159        } else {
160            node->left = next;
161        }
162
163        bit >>= 1;
164        node = next;
165    }
166
167    node->value = value;
168
169    return NGX_OK;
170}
171
172
173ngx_int_t
174ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
175{
176    uint32_t           bit;
177    ngx_radix_node_t  *node;
178
179    bit = 0x80000000;
180    node = tree->root;
181
182    while (node && (bit & mask)) {
183        if (key & bit) {
184            node = node->right;
185
186        } else {
187            node = node->left;
188        }
189
190        bit >>= 1;
191    }
192
193    if (node == NULL) {
194        return NGX_ERROR;
195    }
196
197    if (node->right || node->left) {
198        if (node->value != NGX_RADIX_NO_VALUE) {
199            node->value = NGX_RADIX_NO_VALUE;
200            return NGX_OK;
201        }
202
203        return NGX_ERROR;
204    }
205
206    for ( ;; ) {
207        if (node->parent->right == node) {
208            node->parent->right = NULL;
209
210        } else {
211            node->parent->left = NULL;
212        }
213
214        node->right = tree->free;
215        tree->free = node;
216
217        node = node->parent;
218
219        if (node->right || node->left) {
220            break;
221        }
222
223        if (node->value != NGX_RADIX_NO_VALUE) {
224            break;
225        }
226
227        if (node->parent == NULL) {
228            break;
229        }
230    }
231
232    return NGX_OK;
233}
234
235
236uintptr_t
237ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
238{
239    uint32_t           bit;
240    uintptr_t          value;
241    ngx_radix_node_t  *node;
242
243    bit = 0x80000000;
244    value = NGX_RADIX_NO_VALUE;
245    node = tree->root;
246
247    while (node) {
248        if (node->value != NGX_RADIX_NO_VALUE) {
249            value = node->value;
250        }
251
252        if (key & bit) {
253            node = node->right;
254
255        } else {
256            node = node->left;
257        }
258
259        bit >>= 1;
260    }
261
262    return value;
263}
264
265
266#if (NGX_HAVE_INET6)
267
268ngx_int_t
269ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
270    uintptr_t value)
271{
272    u_char             bit;
273    ngx_uint_t         i;
274    ngx_radix_node_t  *node, *next;
275
276    i = 0;
277    bit = 0x80;
278
279    node = tree->root;
280    next = tree->root;
281
282    while (bit & mask[i]) {
283        if (key[i] & bit) {
284            next = node->right;
285
286        } else {
287            next = node->left;
288        }
289
290        if (next == NULL) {
291            break;
292        }
293
294        bit >>= 1;
295        node = next;
296
297        if (bit == 0) {
298            if (++i == 16) {
299                break;
300            }
301
302            bit = 0x80;
303        }
304    }
305
306    if (next) {
307        if (node->value != NGX_RADIX_NO_VALUE) {
308            return NGX_BUSY;
309        }
310
311        node->value = value;
312        return NGX_OK;
313    }
314
315    while (bit & mask[i]) {
316        next = ngx_radix_alloc(tree);
317        if (next == NULL) {
318            return NGX_ERROR;
319        }
320
321        next->right = NULL;
322        next->left = NULL;
323        next->parent = node;
324        next->value = NGX_RADIX_NO_VALUE;
325
326        if (key[i] & bit) {
327            node->right = next;
328
329        } else {
330            node->left = next;
331        }
332
333        bit >>= 1;
334        node = next;
335
336        if (bit == 0) {
337            if (++i == 16) {
338                break;
339            }
340
341            bit = 0x80;
342        }
343    }
344
345    node->value = value;
346
347    return NGX_OK;
348}
349
350
351ngx_int_t
352ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
353{
354    u_char             bit;
355    ngx_uint_t         i;
356    ngx_radix_node_t  *node;
357
358    i = 0;
359    bit = 0x80;
360    node = tree->root;
361
362    while (node && (bit & mask[i])) {
363        if (key[i] & bit) {
364            node = node->right;
365
366        } else {
367            node = node->left;
368        }
369
370        bit >>= 1;
371
372        if (bit == 0) {
373            if (++i == 16) {
374                break;
375            }
376
377            bit = 0x80;
378        }
379    }
380
381    if (node == NULL) {
382        return NGX_ERROR;
383    }
384
385    if (node->right || node->left) {
386        if (node->value != NGX_RADIX_NO_VALUE) {
387            node->value = NGX_RADIX_NO_VALUE;
388            return NGX_OK;
389        }
390
391        return NGX_ERROR;
392    }
393
394    for ( ;; ) {
395        if (node->parent->right == node) {
396            node->parent->right = NULL;
397
398        } else {
399            node->parent->left = NULL;
400        }
401
402        node->right = tree->free;
403        tree->free = node;
404
405        node = node->parent;
406
407        if (node->right || node->left) {
408            break;
409        }
410
411        if (node->value != NGX_RADIX_NO_VALUE) {
412            break;
413        }
414
415        if (node->parent == NULL) {
416            break;
417        }
418    }
419
420    return NGX_OK;
421}
422
423
424uintptr_t
425ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key)
426{
427    u_char             bit;
428    uintptr_t          value;
429    ngx_uint_t         i;
430    ngx_radix_node_t  *node;
431
432    i = 0;
433    bit = 0x80;
434    value = NGX_RADIX_NO_VALUE;
435    node = tree->root;
436
437    while (node) {
438        if (node->value != NGX_RADIX_NO_VALUE) {
439            value = node->value;
440        }
441
442        if (key[i] & bit) {
443            node = node->right;
444
445        } else {
446            node = node->left;
447        }
448
449        bit >>= 1;
450
451        if (bit == 0) {
452            i++;
453            bit = 0x80;
454        }
455    }
456
457    return value;
458}
459
460#endif
461
462
463static ngx_radix_node_t *
464ngx_radix_alloc(ngx_radix_tree_t *tree)
465{
466    ngx_radix_node_t  *p;
467
468    if (tree->free) {
469        p = tree->free;
470        tree->free = tree->free->right;
471        return p;
472    }
473
474    if (tree->size < sizeof(ngx_radix_node_t)) {
475        tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
476        if (tree->start == NULL) {
477            return NULL;
478        }
479
480        tree->size = ngx_pagesize;
481    }
482
483    p = (ngx_radix_node_t *) tree->start;
484    tree->start += sizeof(ngx_radix_node_t);
485    tree->size -= sizeof(ngx_radix_node_t);
486
487    return p;
488}
489