Mercurial > hg > nginx
annotate src/core/ngx_radix_tree.c @ 2369:12e8e0045096 radix_with_skip
add radix tree skip node
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Wed, 03 Dec 2008 13:26:02 +0000 |
parents | 62be1c4edfba |
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 |
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 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
11 static ngx_int_t ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
12 uint32_t key, uint32_t mask, ngx_radix_node_t **pnode, uint32_t bit); |
2369 | 13 void ngx_radix32tree_compress_node(ngx_radix_tree_t *tree, |
14 ngx_radix_node_t *node); | |
485 | 15 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
|
16 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
17 |
487 | 18 ngx_radix_tree_t * |
489 | 19 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
|
20 { |
487 | 21 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
|
22 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
|
23 |
501 | 24 tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)); |
25 if (tree == NULL) { | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
26 return NULL; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
27 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
28 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
29 tree->pool = pool; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
30 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
|
31 tree->start = NULL; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
32 tree->size = 0; |
2369 | 33 tree->count = 0; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
34 |
501 | 35 tree->root = ngx_radix_alloc(tree); |
36 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
|
37 return NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
38 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
39 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
40 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
|
41 tree->root->left = NULL; |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
42 tree->root->skip = 0; |
485 | 43 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
|
44 |
489 | 45 if (preallocate == 0) { |
46 return tree; | |
47 } | |
48 | |
487 | 49 /* |
2366 | 50 * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc. |
51 * increases TLB hits even if for first lookup iterations. | |
52 * On 32-bit platforms the 7 preallocated bits takes continuous 4K, | |
53 * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits | |
489 | 54 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to |
55 * to preallocate more than one page, because further preallocation | |
2366 | 56 * distributes the only bit per page. Instead, a random insertion |
489 | 57 * may distribute several bits per page. |
58 * | |
59 * Thus, by default we preallocate maximum | |
60 * 6 bits on amd64 (64-bit platform and 4K pages) | |
61 * 7 bits on i386 (32-bit platform and 4K pages) | |
62 * 7 bits on sparc64 in 64-bit mode (8K pages) | |
63 * 8 bits on sparc64 in 32-bit mode (8K pages) | |
487 | 64 */ |
65 | |
489 | 66 if (preallocate == -1) { |
67 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) { | |
68 | |
69 /* amd64 */ | |
70 case 128: | |
71 preallocate = 6; | |
72 break; | |
73 | |
74 /* i386, sparc64 */ | |
75 case 256: | |
76 preallocate = 7; | |
77 break; | |
78 | |
79 /* sparc64 in 32-bit mode */ | |
80 default: | |
81 preallocate = 8; | |
82 } | |
83 } | |
84 | |
487 | 85 mask = 0; |
86 inc = 0x80000000; | |
87 | |
88 while (preallocate--) { | |
89 | |
90 key = 0; | |
91 mask >>= 1; | |
92 mask |= 0x80000000; | |
93 | |
94 do { | |
95 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE) | |
1130 | 96 != NGX_OK) |
487 | 97 { |
98 return NULL; | |
99 } | |
100 | |
101 key += inc; | |
102 | |
103 } while (key); | |
104 | |
105 inc >>= 1; | |
106 } | |
107 | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
108 return tree; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
109 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
110 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
111 |
487 | 112 ngx_int_t |
113 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, | |
114 uintptr_t value) | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
115 { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
116 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
|
117 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
|
118 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
119 bit = 0x80000000; |
485 | 120 |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
121 node = tree->root; |
485 | 122 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
|
123 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
124 while (bit & mask) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
125 if (key & bit) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
126 next = node->right; |
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 } else { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
129 next = node->left; |
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 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
132 if (next == NULL) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
133 break; |
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 |
485 | 136 bit >>= 1; |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
137 node = next; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
138 } |
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 if (next) { |
485 | 141 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
|
142 return NGX_BUSY; |
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 node->value = value; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
146 return NGX_OK; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
147 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
148 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
149 while (bit & mask) { |
501 | 150 next = ngx_radix_alloc(tree); |
151 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
|
152 return NGX_ERROR; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
153 } |
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 next->right = NULL; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
156 next->left = NULL; |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
157 next->skip = 0; |
485 | 158 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
|
159 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
160 if (key & bit) { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
161 node->right = next; |
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 } else { |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
164 node->left = 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 |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
167 bit >>= 1; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
168 node = next; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
169 } |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
170 |
485 | 171 node->value = value; |
172 | |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
173 return NGX_OK; |
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
174 } |
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 |
487 | 177 ngx_int_t |
178 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
|
179 { |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
180 return ngx_radix32tree_delete_node(tree, key, mask, &tree->root, |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
181 0x80000000); |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
182 } |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
183 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
184 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
185 static ngx_int_t |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
186 ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
187 ngx_radix_node_t **pnode, uint32_t bit) |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
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 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
|
190 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
191 node = *pnode; |
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 == 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 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
197 if ((bit & mask) == 0) { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
198 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
199 if (node->right || node->left) { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
200 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
201 if (node->value != NGX_RADIX_NO_VALUE) { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
202 node->value = NGX_RADIX_NO_VALUE; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
203 return NGX_OK; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
204 } |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
205 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
206 return NGX_ERROR; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
207 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
208 } else { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
209 node->right = tree->free; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
210 tree->free = node; |
2369 | 211 tree->count--; |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
212 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
213 *pnode = NULL; |
485 | 214 } |
215 | |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
216 return NGX_OK; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
217 } |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
218 |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
219 if (ngx_radix32tree_delete_node(tree, key, mask, |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
220 (key & bit) ? &node->right : &node->left, |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
221 bit >> 1) |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
222 != NGX_OK) |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
223 { |
485 | 224 return NGX_ERROR; |
340
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 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
227 if (node->right || node->left) { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
228 return NGX_OK; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
229 } |
342
0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
Igor Sysoev <igor@sysoev.ru>
parents:
341
diff
changeset
|
230 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
231 if (node->value != NGX_RADIX_NO_VALUE) { |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
232 return NGX_OK; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
233 } |
563 | 234 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
235 node->right = tree->free; |
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
236 tree->free = node; |
2369 | 237 tree->count--; |
563 | 238 |
2368
62be1c4edfba
remove parent from radix tree node to add skip field
Igor Sysoev <igor@sysoev.ru>
parents:
2366
diff
changeset
|
239 *pnode = NULL; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
240 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
241 return NGX_OK; |
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 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
244 |
2369 | 245 void |
246 ngx_radix32tree_compress(ngx_radix_tree_t *tree) | |
247 { | |
248 if (tree->root) { | |
249 ngx_radix32tree_compress_node(tree, tree->root); | |
250 } | |
251 } | |
252 | |
253 | |
254 void | |
255 ngx_radix32tree_compress_node(ngx_radix_tree_t *tree, ngx_radix_node_t *node) | |
256 { | |
257 uintptr_t skip; | |
258 ngx_radix_node_t *n; | |
259 | |
260 if (node->right) { | |
261 | |
262 skip = 0; | |
263 | |
264 for (n = node->right; | |
265 n->right && n->left == NULL && n->value == NGX_RADIX_NO_VALUE; | |
266 n = node->right) | |
267 { | |
268 node->right = n->right; | |
269 | |
270 n->right = tree->free; | |
271 tree->free = n; | |
272 tree->count--; | |
273 | |
274 skip++; | |
275 } | |
276 | |
277 node->right->skip = skip; | |
278 | |
279 ngx_radix32tree_compress_node(tree, node->right); | |
280 } | |
281 | |
282 if (node->left) { | |
283 | |
284 skip = 0; | |
285 | |
286 for (n = node->left; | |
287 n->left && n->right == NULL && n->value == NGX_RADIX_NO_VALUE; | |
288 n = node->left) | |
289 { | |
290 node->left = n->left; | |
291 | |
292 n->right = tree->free; | |
293 tree->free = n; | |
294 tree->count--; | |
295 | |
296 skip++; | |
297 } | |
298 | |
299 node->left->skip = skip; | |
300 | |
301 ngx_radix32tree_compress_node(tree, node->left); | |
302 } | |
303 } | |
304 | |
305 | |
487 | 306 uintptr_t |
307 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
|
308 { |
2369 | 309 uint32_t bit, test; |
310 uintptr_t value, skip; | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
311 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
|
312 |
485 | 313 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
|
314 node = tree->root; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
315 |
2369 | 316 if (node == NULL) { |
317 return NGX_RADIX_NO_VALUE; | |
318 } | |
319 | |
320 bit = 0x80000000; | |
321 | |
322 for ( ;; ) { | |
323 | |
485 | 324 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
|
325 value = node->value; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
326 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
327 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
328 if (key & bit) { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
329 node = node->right; |
2369 | 330 test = 0; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
331 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
332 } else { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
333 node = node->left; |
2369 | 334 test = bit >> 1; |
335 } | |
336 | |
337 if (node == NULL) { | |
338 return value; | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
339 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
340 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
341 bit >>= 1; |
2369 | 342 |
343 for (skip = node->skip; skip; skip--) { | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
344 |
2369 | 345 if ((key & bit) == test) { |
346 return value; | |
347 } | |
348 | |
349 bit >>= 1; | |
350 test >>= 1; | |
351 } | |
352 } | |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
353 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
354 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
355 |
487 | 356 static void * |
357 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
|
358 { |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
359 char *p; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
360 |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
361 if (tree->free) { |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
362 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
|
363 tree->free = tree->free->right; |
2369 | 364 tree->count++; |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
365 return p; |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
366 } |
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
367 |
485 | 368 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
|
369 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize); |
501 | 370 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
|
371 return NULL; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
372 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
373 |
351
af4c6b45a687
nginx-0.0.4-2004-06-10-22:36:57 import
Igor Sysoev <igor@sysoev.ru>
parents:
342
diff
changeset
|
374 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
|
375 } |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
376 |
341
41e552841296
nginx-0.0.3-2004-05-26-19:30:12 import
Igor Sysoev <igor@sysoev.ru>
parents:
340
diff
changeset
|
377 p = tree->start; |
485 | 378 tree->start += sizeof(ngx_radix_node_t); |
379 tree->size -= sizeof(ngx_radix_node_t); | |
2369 | 380 tree->count++; |
340
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
381 |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
382 return p; |
0bf903191ceb
nginx-0.0.3-2004-05-25-19:28:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
383 } |