Mercurial > hg > nginx
annotate src/core/ngx_radix_tree.c @ 7736:a46fcf101cfc
Core: added format specifiers to output binary data as hex.
Now "s", "V", and "v" format specifiers may be prefixed with "x" (lowercase)
or "X" (uppercase) to output corresponding data in hexadecimal format.
In collaboration with Maxim Dounin.
| author | Vladimir Homutov <vl@nginx.com> |
|---|---|
| date | Wed, 28 Oct 2020 10:56:11 +0300 |
| 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 } |