Mercurial > hg > nginx
annotate src/core/ngx_radix_tree.c @ 493:975f62e77f02 release-0.1.21
nginx-0.1.21-RELEASE import
*) Bugfix: the ngx_http_stub_status_module showed incorrect statistics
if "rtsig" method was used or if several worker process ran on SMP.
*) Bugfix: nginx could not be built by the icc compiler on Linux or if
the zlib-1.2.x library was building from sources.
*) Bugfix: nginx could not be built on NetBSD 2.0.
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Tue, 22 Feb 2005 14:40:13 +0000 |
parents | 45a460f82aec |
children | 64d9afb209da |
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 |
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
|
4 */ |
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 |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
6 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
7 #include <ngx_config.h> |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
8 #include <ngx_core.h> |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
9 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
10 |
485 | 11 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
|
12 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
13 |
487 | 14 ngx_radix_tree_t * |
489 | 15 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
|
16 { |
487 | 17 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
|
18 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
|
19 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
20 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
21 return NULL; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
22 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
23 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
24 tree->pool = pool; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
25 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
|
26 tree->start = NULL; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
27 tree->size = 0; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
28 |
485 | 29 if (!(tree->root = ngx_radix_alloc(tree))) { |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
30 return NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
31 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
32 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
33 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
|
34 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
|
35 tree->root->parent = NULL; |
485 | 36 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
|
37 |
489 | 38 if (preallocate == 0) { |
39 return tree; | |
40 } | |
41 | |
487 | 42 /* |
493 | 43 * The preallocation the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc. |
44 * increases the TLB hits even if for the first lookup iterations. | |
487 | 45 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K, |
489 | 46 * 8 - 8K, 9 - 16K, etc. On the 64-bit platforms the 6 preallocated bits |
47 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to | |
48 * to preallocate more than one page, because further preallocation | |
49 * distribute the only bit per page. Instead, the random insertion | |
50 * may distribute several bits per page. | |
51 * | |
52 * Thus, by default we preallocate maximum | |
53 * 6 bits on amd64 (64-bit platform and 4K pages) | |
54 * 7 bits on i386 (32-bit platform and 4K pages) | |
55 * 7 bits on sparc64 in 64-bit mode (8K pages) | |
56 * 8 bits on sparc64 in 32-bit mode (8K pages) | |
487 | 57 */ |
58 | |
489 | 59 if (preallocate == -1) { |
60 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) { | |
61 | |
62 /* amd64 */ | |
63 case 128: | |
64 preallocate = 6; | |
65 break; | |
66 | |
67 /* i386, sparc64 */ | |
68 case 256: | |
69 preallocate = 7; | |
70 break; | |
71 | |
72 /* sparc64 in 32-bit mode */ | |
73 default: | |
74 preallocate = 8; | |
75 } | |
76 } | |
77 | |
487 | 78 mask = 0; |
79 inc = 0x80000000; | |
80 | |
81 while (preallocate--) { | |
82 | |
83 key = 0; | |
84 mask >>= 1; | |
85 mask |= 0x80000000; | |
86 | |
87 do { | |
88 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE) | |
89 != NGX_OK) | |
90 { | |
91 return NULL; | |
92 } | |
93 | |
94 key += inc; | |
95 | |
96 } while (key); | |
97 | |
98 inc >>= 1; | |
99 } | |
100 | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
101 return tree; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
102 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
103 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
104 |
487 | 105 ngx_int_t |
106 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, | |
107 uintptr_t value) | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
108 { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
109 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
|
110 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
|
111 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
112 bit = 0x80000000; |
485 | 113 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
114 node = tree->root; |
485 | 115 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
|
116 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
117 while (bit & mask) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
118 if (key & bit) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
119 next = node->right; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
120 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
121 } else { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
122 next = node->left; |
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 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
125 if (next == NULL) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
126 break; |
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 |
485 | 129 bit >>= 1; |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
130 node = next; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
131 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
132 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
133 if (next) { |
485 | 134 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
|
135 return NGX_BUSY; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
136 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
137 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
138 node->value = value; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
139 return NGX_OK; |
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 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
142 while (bit & mask) { |
485 | 143 if (!(next = ngx_radix_alloc(tree))) { |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
144 return NGX_ERROR; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
145 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
146 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
147 next->right = NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
148 next->left = NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
149 next->parent = node; |
485 | 150 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
|
151 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
152 if (key & bit) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
153 node->right = next; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
154 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
155 } else { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
156 node->left = next; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
157 } |
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 bit >>= 1; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
160 node = 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 |
485 | 163 node->value = value; |
164 | |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
165 return NGX_OK; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
166 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
167 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
168 |
487 | 169 ngx_int_t |
170 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
|
171 { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
172 uint32_t bit; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
173 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
|
174 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
175 bit = 0x80000000; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
176 node = tree->root; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
177 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
178 while (node && (bit & mask)) { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
179 if (key & bit) { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
180 node = node->right; |
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 } else { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
183 node = node->left; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
184 } |
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 bit >>= 1; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
187 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
188 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
189 if (node == NULL) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
190 return NGX_ERROR; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
191 } |
340
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->right || node->left) { |
485 | 194 if (node->value != NGX_RADIX_NO_VALUE) { |
195 node->value = NGX_RADIX_NO_VALUE; | |
196 return NGX_OK; | |
197 } | |
198 | |
199 return NGX_ERROR; | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
200 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
201 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
202 for ( ;; ) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
203 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
|
204 node->parent->right = NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
205 } else { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
206 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
|
207 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
208 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
209 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
|
210 tree->free = node; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
211 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
212 node = node->parent; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
213 |
485 | 214 if (node->right |
215 || node->left | |
216 || node->value != NGX_RADIX_NO_VALUE | |
217 || node->parent == NULL) | |
218 { | |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
219 break; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
220 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
221 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
222 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
223 return NGX_OK; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
224 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
225 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
226 |
487 | 227 uintptr_t |
228 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
|
229 { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
230 uint32_t bit; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
231 uintptr_t value; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
232 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
|
233 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
234 bit = 0x80000000; |
485 | 235 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
|
236 node = tree->root; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
237 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
238 while (node) { |
485 | 239 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
|
240 value = node->value; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
241 } |
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 if (key & bit) { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
244 node = node->right; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
245 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
246 } else { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
247 node = node->left; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
248 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
249 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
250 bit >>= 1; |
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 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
253 return value; |
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 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
256 |
487 | 257 static void * |
258 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
|
259 { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
260 char *p; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
261 |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
262 if (tree->free) { |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
263 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
|
264 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
|
265 return p; |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
266 } |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
267 |
485 | 268 if (tree->size < sizeof(ngx_radix_node_t)) { |
351
af4c6b45a687
nginx-0.0.4-2004-06-10-22:36:57 import
Igor Sysoev <igor@sysoev.ru>
parents:
342
diff
changeset
|
269 if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) { |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
270 return NULL; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
271 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
272 |
351
af4c6b45a687
nginx-0.0.4-2004-06-10-22:36:57 import
Igor Sysoev <igor@sysoev.ru>
parents:
342
diff
changeset
|
273 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
|
274 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
275 |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
276 p = tree->start; |
485 | 277 tree->start += sizeof(ngx_radix_node_t); |
278 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
|
279 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
280 return p; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
281 } |