|
34
|
1
|
|
|
2 /*
|
|
|
3 * Copyright (C) Igor Sysoev
|
|
|
4 */
|
|
|
5
|
|
|
6
|
|
|
7 #include <ngx_config.h>
|
|
|
8 #include <ngx_core.h>
|
|
|
9
|
|
|
10
|
|
|
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
|
|
|
12
|
|
|
13
|
|
|
14 ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool)
|
|
|
15 {
|
|
|
16 ngx_radix_tree_t *tree;
|
|
|
17
|
|
|
18 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
|
|
|
19 return NULL;
|
|
|
20 }
|
|
|
21
|
|
|
22 tree->pool = pool;
|
|
|
23 tree->free = NULL;
|
|
|
24 tree->start = NULL;
|
|
|
25 tree->size = 0;
|
|
|
26
|
|
|
27 if (!(tree->root = ngx_radix_alloc(tree))) {
|
|
|
28 return NULL;
|
|
|
29 }
|
|
|
30
|
|
|
31 tree->root->right = NULL;
|
|
|
32 tree->root->left = NULL;
|
|
|
33 tree->root->parent = NULL;
|
|
|
34 tree->root->value = NGX_RADIX_NO_VALUE;
|
|
|
35
|
|
|
36 return tree;
|
|
|
37 }
|
|
|
38
|
|
|
39
|
|
|
40 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
|
|
|
41 uint32_t key, uint32_t mask, uintptr_t value)
|
|
|
42 {
|
|
|
43 uint32_t bit;
|
|
|
44 ngx_radix_node_t *node, *next;
|
|
|
45
|
|
|
46 bit = 0x80000000;
|
|
|
47
|
|
|
48 node = tree->root;
|
|
|
49 next = tree->root;
|
|
|
50
|
|
|
51 while (bit & mask) {
|
|
|
52 if (key & bit) {
|
|
|
53 next = node->right;
|
|
|
54
|
|
|
55 } else {
|
|
|
56 next = node->left;
|
|
|
57 }
|
|
|
58
|
|
|
59 if (next == NULL) {
|
|
|
60 break;
|
|
|
61 }
|
|
|
62
|
|
|
63 bit >>= 1;
|
|
|
64 node = next;
|
|
|
65 }
|
|
|
66
|
|
|
67 if (next) {
|
|
|
68 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
69 return NGX_BUSY;
|
|
|
70 }
|
|
|
71
|
|
|
72 node->value = value;
|
|
|
73 return NGX_OK;
|
|
|
74 }
|
|
|
75
|
|
|
76 while (bit & mask) {
|
|
|
77 if (!(next = ngx_radix_alloc(tree))) {
|
|
|
78 return NGX_ERROR;
|
|
|
79 }
|
|
|
80
|
|
|
81 next->right = NULL;
|
|
|
82 next->left = NULL;
|
|
|
83 next->parent = node;
|
|
|
84 next->value = NGX_RADIX_NO_VALUE;
|
|
|
85
|
|
|
86 if (key & bit) {
|
|
|
87 node->right = next;
|
|
|
88
|
|
|
89 } else {
|
|
|
90 node->left = next;
|
|
|
91 }
|
|
|
92
|
|
|
93 bit >>= 1;
|
|
|
94 node = next;
|
|
|
95 }
|
|
|
96
|
|
|
97 node->value = value;
|
|
|
98
|
|
|
99 return NGX_OK;
|
|
|
100 }
|
|
|
101
|
|
|
102
|
|
|
103 ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree,
|
|
|
104 uint32_t key, uint32_t mask)
|
|
|
105 {
|
|
|
106 uint32_t bit;
|
|
|
107 ngx_radix_node_t *node;
|
|
|
108
|
|
|
109 bit = 0x80000000;
|
|
|
110 node = tree->root;
|
|
|
111
|
|
|
112 while (node && (bit & mask)) {
|
|
|
113 if (key & bit) {
|
|
|
114 node = node->right;
|
|
|
115
|
|
|
116 } else {
|
|
|
117 node = node->left;
|
|
|
118 }
|
|
|
119
|
|
|
120 bit >>= 1;
|
|
|
121 }
|
|
|
122
|
|
|
123 if (node == NULL) {
|
|
|
124 return NGX_ERROR;
|
|
|
125 }
|
|
|
126
|
|
|
127 if (node->right || node->left) {
|
|
|
128 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
129 node->value = NGX_RADIX_NO_VALUE;
|
|
|
130 return NGX_OK;
|
|
|
131 }
|
|
|
132
|
|
|
133 return NGX_ERROR;
|
|
|
134 }
|
|
|
135
|
|
|
136 for ( ;; ) {
|
|
|
137 if (node->parent->right == node) {
|
|
|
138 node->parent->right = NULL;
|
|
|
139 } else {
|
|
|
140 node->parent->left = NULL;
|
|
|
141 }
|
|
|
142
|
|
|
143 node->right = tree->free;
|
|
|
144 tree->free = node;
|
|
|
145
|
|
|
146 node = node->parent;
|
|
|
147
|
|
|
148 if (node->right
|
|
|
149 || node->left
|
|
|
150 || node->value != NGX_RADIX_NO_VALUE
|
|
|
151 || node->parent == NULL)
|
|
|
152 {
|
|
|
153 break;
|
|
|
154 }
|
|
|
155 }
|
|
|
156
|
|
|
157 return NGX_OK;
|
|
|
158 }
|
|
|
159
|
|
|
160
|
|
|
161 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
|
|
|
162 {
|
|
|
163 uint32_t bit;
|
|
|
164 uintptr_t value;
|
|
|
165 ngx_radix_node_t *node;
|
|
|
166
|
|
|
167 bit = 0x80000000;
|
|
|
168 value = NGX_RADIX_NO_VALUE;
|
|
|
169 node = tree->root;
|
|
|
170
|
|
|
171 while (node) {
|
|
|
172 if (node->value != NGX_RADIX_NO_VALUE) {
|
|
|
173 value = node->value;
|
|
|
174 }
|
|
|
175
|
|
|
176 if (key & bit) {
|
|
|
177 node = node->right;
|
|
|
178
|
|
|
179 } else {
|
|
|
180 node = node->left;
|
|
|
181 }
|
|
|
182
|
|
|
183 bit >>= 1;
|
|
|
184 }
|
|
|
185
|
|
|
186 return value;
|
|
|
187 }
|
|
|
188
|
|
|
189
|
|
|
190 static void *ngx_radix_alloc(ngx_radix_tree_t *tree)
|
|
|
191 {
|
|
|
192 char *p;
|
|
|
193
|
|
|
194 if (tree->free) {
|
|
|
195 p = (char *) tree->free;
|
|
|
196 tree->free = tree->free->right;
|
|
|
197 return p;
|
|
|
198 }
|
|
|
199
|
|
|
200 if (tree->size < sizeof(ngx_radix_node_t)) {
|
|
|
201 if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) {
|
|
|
202 return NULL;
|
|
|
203 }
|
|
|
204
|
|
|
205 tree->size = ngx_pagesize;
|
|
|
206 }
|
|
|
207
|
|
|
208 p = tree->start;
|
|
|
209 tree->start += sizeof(ngx_radix_node_t);
|
|
|
210 tree->size -= sizeof(ngx_radix_node_t);
|
|
|
211
|
|
|
212 return p;
|
|
|
213 }
|
