Mercurial > hg > nginx
annotate src/core/ngx_radix_tree.c @ 5438:f817f9d1cded
Configure: call "make clean" for OpenSSL only if Makefile exists.
This change allows to build nginx against git checkout of OpenSSL.
Signed-off-by: Piotr Sikora <piotr@cloudflare.com>
author | Piotr Sikora <piotr@cloudflare.com> |
---|---|
date | Mon, 04 Nov 2013 17:00:25 -0800 |
parents | 3be3de31d7dd |
children |
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 | 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 |
4976
6b416e3bdd26
Fixed return type of internal function that allocates radix tree nodes.
Ruslan Ermilov <ru@nginx.com>
parents:
4823
diff
changeset
|
12 static ngx_radix_node_t *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 | 15 ngx_radix_tree_t * |
489 | 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 | 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 | 21 tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)); |
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 | 31 tree->root = ngx_radix_alloc(tree); |
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 | 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 | 41 if (preallocate == 0) { |
42 return tree; | |
43 } | |
44 | |
487 | 45 /* |
2366 | 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 | |
489 | 50 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to |
51 * to preallocate more than one page, because further preallocation | |
2366 | 52 * distributes the only bit per page. Instead, a random insertion |
489 | 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) | |
487 | 60 */ |
61 | |
489 | 62 if (preallocate == -1) { |
4823
efa334556803
Radix tree preallocation fix.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
63 switch (ngx_pagesize / sizeof(ngx_radix_node_t)) { |
489 | 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 | |
487 | 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) | |
1130 | 92 != NGX_OK) |
487 | 93 { |
94 return NULL; | |
95 } | |
96 | |
97 key += inc; | |
98 | |
99 } while (key); | |
100 | |
101 inc >>= 1; | |
102 } | |
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 | 108 ngx_int_t |
109 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, | |
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 | 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 | 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 | 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 | 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 | 146 next = ngx_radix_alloc(tree); |
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 | 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 | 167 node->value = value; |
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 | 173 ngx_int_t |
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 | 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; | |
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 | 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 | 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) { | |
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 | 236 uintptr_t |
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 | 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 | 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 |
4992 | 266 #if (NGX_HAVE_INET6) |
267 | |
268 ngx_int_t | |
269 ngx_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 | |
351 ngx_int_t | |
352 ngx_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 | |
424 uintptr_t | |
425 ngx_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 | |
4976
6b416e3bdd26
Fixed return type of internal function that allocates radix tree nodes.
Ruslan Ermilov <ru@nginx.com>
parents:
4823
diff
changeset
|
463 static ngx_radix_node_t * |
487 | 464 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
|
465 { |
4976
6b416e3bdd26
Fixed return type of internal function that allocates radix tree nodes.
Ruslan Ermilov <ru@nginx.com>
parents:
4823
diff
changeset
|
466 ngx_radix_node_t *p; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
467 |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
468 if (tree->free) { |
4976
6b416e3bdd26
Fixed return type of internal function that allocates radix tree nodes.
Ruslan Ermilov <ru@nginx.com>
parents:
4823
diff
changeset
|
469 p = tree->free; |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
470 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
|
471 return p; |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
472 } |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
473 |
485 | 474 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
|
475 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize); |
501 | 476 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
|
477 return NULL; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
478 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
479 |
351
af4c6b45a687
nginx-0.0.4-2004-06-10-22:36:57 import
Igor Sysoev <igor@sysoev.ru>
parents:
342
diff
changeset
|
480 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
|
481 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
482 |
4976
6b416e3bdd26
Fixed return type of internal function that allocates radix tree nodes.
Ruslan Ermilov <ru@nginx.com>
parents:
4823
diff
changeset
|
483 p = (ngx_radix_node_t *) tree->start; |
485 | 484 tree->start += sizeof(ngx_radix_node_t); |
485 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
|
486 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
487 return p; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
488 } |