Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_radix_tree.c @ 34:aab2ea7c0458 NGINX_0_1_17

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.1.17 *) Change: the ngx_http_rewrite_module was rewritten from the scratch. Now it is possible to redirect, to return the error codes, to check the variables and referrers. The directives can be used inside locations. The redirect directive was canceled. *) Feature: the ngx_http_geo_module. *) Feature: the proxy_set_x_var and fastcgi_set_var directives. *) Bugfix: the location configuration with "=" modifier may be used in another location. *) Bugfix: the correct content type was set only for requests that use small caps letters in extension. *) Bugfix: if the proxy_pass or fastcgi_pass directives were set in the location, and access was denied, and the error was redirected to a static page, then the segmentation fault occurred. *) Bugfix: if in a proxied "Location" header was a relative URL, then a host name and a slash were added to them; bug appeared in 0.1.14. *) Bugfix: the system error message was not logged on Linux.
author Igor Sysoev <http://sysoev.ru>
date Thu, 03 Feb 2005 00:00:00 +0300
parents
children a39d1b793287
comparison
equal deleted inserted replaced
33:27f09a550803 34:aab2ea7c0458
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 }