Mercurial > hg > nginx

annotate src/core/ngx_radix_tree.c @ 4580:ae60a1085c82

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Access module: fixed inheritance of allow/deny ipv6 rules. Previous (incorrect) behaviour was to inherit ipv6 rules separately from ipv4 ones. Now all rules are either inherited (if there are no rules defined at current level) or not (if there are any rules defined).
author Maxim Dounin <mdounin@mdounin.ru>
date Tue, 10 Apr 2012 13:25:53 +0000
parents d620f497c50f
children efa334556803
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 351
diff changeset
1
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 351
diff changeset
2 /*
444
42d11f017717 nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents: 441
diff changeset
3 * Copyright (C) Igor Sysoev
4412
d620f497c50f Copyright updated.
Maxim Konovalov <maxim@nginx.com>
parents: 2366
diff changeset
4 * Copyright (C) Nginx, Inc.
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 351
diff changeset
5 */
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 351
diff changeset
6
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
7
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
8 #include <ngx_config.h>
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
9 #include <ngx_core.h>
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
10
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
11
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
12 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
13
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
14
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
15 ngx_radix_tree_t *
489
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
16 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
17 {
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
18 uint32_t key, mask, inc;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
19 ngx_radix_tree_t *tree;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
20
501
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
21 tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
22 if (tree == NULL) {
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
23 return NULL;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
24 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
25
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
26 tree->pool = pool;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
27 tree->free = NULL;
341
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
28 tree->start = NULL;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29 tree->size = 0;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
30
501
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
31 tree->root = ngx_radix_alloc(tree);
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
32 if (tree->root == NULL) {
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
33 return NULL;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
34 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
35
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
36 tree->root->right = NULL;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
37 tree->root->left = NULL;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
38 tree->root->parent = NULL;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
39 tree->root->value = NGX_RADIX_NO_VALUE;
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
40
489
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
41 if (preallocate == 0) {
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
42 return tree;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
43 }
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
44
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
45 /*
2366
3aa4fd0e7dc5 fix comment
Igor Sysoev <igor@sysoev.ru>
parents: 2221
diff changeset
46 * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
3aa4fd0e7dc5 fix comment
Igor Sysoev <igor@sysoev.ru>
parents: 2221
diff changeset
47 * increases TLB hits even if for first lookup iterations.
3aa4fd0e7dc5 fix comment
Igor Sysoev <igor@sysoev.ru>
parents: 2221
diff changeset
48 * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
3aa4fd0e7dc5 fix comment
Igor Sysoev <igor@sysoev.ru>
parents: 2221
diff changeset
49 * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits
489
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
50 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
51 * to preallocate more than one page, because further preallocation
2366
3aa4fd0e7dc5 fix comment
Igor Sysoev <igor@sysoev.ru>
parents: 2221
diff changeset
52 * distributes the only bit per page. Instead, a random insertion
489
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
53 * may distribute several bits per page.
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
54 *
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
55 * Thus, by default we preallocate maximum
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
56 * 6 bits on amd64 (64-bit platform and 4K pages)
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
57 * 7 bits on i386 (32-bit platform and 4K pages)
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
58 * 7 bits on sparc64 in 64-bit mode (8K pages)
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
59 * 8 bits on sparc64 in 32-bit mode (8K pages)
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
60 */
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
61
489
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
62 if (preallocate == -1) {
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
63 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
64
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
65 /* amd64 */
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
66 case 128:
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
67 preallocate = 6;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
68 break;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
69
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
70 /* i386, sparc64 */
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
71 case 256:
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
72 preallocate = 7;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
73 break;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
74
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
75 /* sparc64 in 32-bit mode */
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
76 default:
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
77 preallocate = 8;
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
78 }
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
79 }
45a460f82aec nginx-0.1.19-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 487
diff changeset
80
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
81 mask = 0;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
82 inc = 0x80000000;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
83
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
84 while (preallocate--) {
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
85
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
86 key = 0;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
87 mask >>= 1;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
88 mask |= 0x80000000;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
89
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
90 do {
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
91 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
1130
119605405c4b style fix
Igor Sysoev <igor@sysoev.ru>
parents: 563
diff changeset
92 != NGX_OK)
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
93 {
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
94 return NULL;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
95 }
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
96
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
97 key += inc;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
98
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
99 } while (key);
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
100
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
101 inc >>= 1;
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
102 }
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
103
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
104 return tree;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
105 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
106
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
107
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
108 ngx_int_t
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
109 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
110 uintptr_t value)
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
111 {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
112 uint32_t bit;
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
113 ngx_radix_node_t *node, *next;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
114
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
115 bit = 0x80000000;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
116
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
117 node = tree->root;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
118 next = tree->root;
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
119
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
120 while (bit & mask) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
121 if (key & bit) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
122 next = node->right;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
123
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
124 } else {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
125 next = node->left;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
126 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
127
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
128 if (next == NULL) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
129 break;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
130 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
131
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
132 bit >>= 1;
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
133 node = next;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
134 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
135
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
136 if (next) {
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
137 if (node->value != NGX_RADIX_NO_VALUE) {
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
138 return NGX_BUSY;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
139 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
140
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
141 node->value = value;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
142 return NGX_OK;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
143 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
144
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
145 while (bit & mask) {
501
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
146 next = ngx_radix_alloc(tree);
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
147 if (next == NULL) {
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
148 return NGX_ERROR;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
149 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
150
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
151 next->right = NULL;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
152 next->left = NULL;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
153 next->parent = node;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
154 next->value = NGX_RADIX_NO_VALUE;
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
155
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
156 if (key & bit) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
157 node->right = next;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
158
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
159 } else {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
160 node->left = next;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
161 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
162
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
163 bit >>= 1;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
164 node = next;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
165 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
166
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
167 node->value = value;
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
168
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
169 return NGX_OK;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
170 }
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
171
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
172
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
173 ngx_int_t
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
174 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
175 {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
176 uint32_t bit;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
177 ngx_radix_node_t *node;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
178
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
179 bit = 0x80000000;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
180 node = tree->root;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
181
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
182 while (node && (bit & mask)) {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
183 if (key & bit) {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
184 node = node->right;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
185
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
186 } else {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
187 node = node->left;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
188 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
189
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
190 bit >>= 1;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
191 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
192
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
193 if (node == NULL) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
194 return NGX_ERROR;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
195 }
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
196
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
197 if (node->right || node->left) {
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
198 if (node->value != NGX_RADIX_NO_VALUE) {
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
199 node->value = NGX_RADIX_NO_VALUE;
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
200 return NGX_OK;
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
201 }
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
202
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
203 return NGX_ERROR;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
204 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
205
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
206 for ( ;; ) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
207 if (node->parent->right == node) {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
208 node->parent->right = NULL;
563
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
209
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
210 } else {
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
211 node->parent->left = NULL;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
212 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
213
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
214 node->right = tree->free;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
215 tree->free = node;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
216
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
217 node = node->parent;
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
218
563
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
219 if (node->right || node->left) {
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
220 break;
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
221 }
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
222
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
223 if (node->value != NGX_RADIX_NO_VALUE) {
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
224 break;
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
225 }
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
226
9c2f3ed7a247 nginx-0.3.3-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 501
diff changeset
227 if (node->parent == NULL) {
342
0ee0642af5f1 nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents: 341
diff changeset
228 break;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
229 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
230 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
231
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
232 return NGX_OK;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
233 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
234
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
235
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
236 uintptr_t
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
237 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
238 {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
239 uint32_t bit;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
240 uintptr_t value;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
241 ngx_radix_node_t *node;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
242
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
243 bit = 0x80000000;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
244 value = NGX_RADIX_NO_VALUE;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
245 node = tree->root;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
246
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
247 while (node) {
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
248 if (node->value != NGX_RADIX_NO_VALUE) {
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
249 value = node->value;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
250 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
251
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
252 if (key & bit) {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
253 node = node->right;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
254
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
255 } else {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
256 node = node->left;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
257 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
258
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
259 bit >>= 1;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
260 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
261
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
262 return value;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
263 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
264
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
265
487
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
266 static void *
31ff3e943e16 nginx-0.1.18-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 485
diff changeset
267 ngx_radix_alloc(ngx_radix_tree_t *tree)
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
268 {
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
269 char *p;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
270
341
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
271 if (tree->free) {
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
272 p = (char *) tree->free;
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
273 tree->free = tree->free->right;
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
274 return p;
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
275 }
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
276
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
277 if (tree->size < sizeof(ngx_radix_node_t)) {
2221
78415b0469bc use ngx_pmemalign() to allocate radix pages
Igor Sysoev <igor@sysoev.ru>
parents: 1130
diff changeset
278 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
501
d4ea69372b94 nginx-0.1.25-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 499
diff changeset
279 if (tree->start == NULL) {
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
280 return NULL;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
281 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
282
351
af4c6b45a687 nginx-0.0.4-2004-06-10-22:36:57 import
Igor Sysoev <igor@sysoev.ru>
parents: 342
diff changeset
283 tree->size = ngx_pagesize;
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
284 }
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
285
341
41e552841296 nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents: 340
diff changeset
286 p = tree->start;
485
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
287 tree->start += sizeof(ngx_radix_node_t);
4ebe09b07e30 nginx-0.1.17-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 444
diff changeset
288 tree->size -= sizeof(ngx_radix_node_t);
340
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
289
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
290 return p;
0bf903191ceb nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
291 }