Mercurial > hg > nginx-vendor-0-7
comparison src/core/ngx_hash.c @ 138:8e6d4d96ec4c NGINX_0_3_16
nginx 0.3.16
*) Feature: the ngx_http_map_module.
*) Feature: the "types_hash_max_size" and "types_hash_bucket_size"
directives.
*) Feature: the "ssi_value_length" directive.
*) Feature: the "worker_rlimit_core" directive.
*) Workaround: the connection number in logs was always 1 if nginx was
built by the icc 8.1 or 9.0 compilers with optimization for
Pentium 4.
*) Bugfix: the "config timefmt" SSI command set incorrect time format.
*) Bugfix: nginx did not close connection to IMAP/POP3 backend for the
SSL connections; bug appeared in 0.3.13.
Thanks to Rob Mueller.
*) Bugfix: segmentation fault may occurred in at SSL shutdown; bug
appeared in 0.3.13.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Fri, 16 Dec 2005 00:00:00 +0300 |
parents | 91372f004adf |
children | 55a211e5eeb7 |
comparison
equal
deleted
inserted
replaced
137:768f51dd150b | 138:8e6d4d96ec4c |
---|---|
6 | 6 |
7 #include <ngx_config.h> | 7 #include <ngx_config.h> |
8 #include <ngx_core.h> | 8 #include <ngx_core.h> |
9 | 9 |
10 | 10 |
11 void * | |
12 ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) | |
13 { | |
14 ngx_uint_t i; | |
15 ngx_hash_elt_t *elt; | |
16 | |
17 #if 0 | |
18 ngx_str_t line; | |
19 | |
20 line.len = len; | |
21 line.data = name; | |
22 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%V\"", &line); | |
23 #endif | |
24 | |
25 elt = hash->buckets[key % hash->size]; | |
26 | |
27 if (elt == NULL) { | |
28 return NULL; | |
29 } | |
30 | |
31 while (elt->value) { | |
32 if (len != (size_t) elt->len) { | |
33 goto next; | |
34 } | |
35 | |
36 for (i = 0; i < len; i++) { | |
37 if (name[i] != elt->name[i]) { | |
38 goto next; | |
39 } | |
40 } | |
41 | |
42 return elt->value; | |
43 | |
44 next: | |
45 | |
46 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, | |
47 sizeof(void *)); | |
48 continue; | |
49 } | |
50 | |
51 return NULL; | |
52 } | |
53 | |
54 | |
55 void * | |
56 ngx_hash_find_wildcard(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) | |
57 { | |
58 void *value; | |
59 ngx_uint_t i, n, key; | |
60 | |
61 #if 0 | |
62 ngx_str_t line; | |
63 | |
64 line.len = len; | |
65 line.data = name; | |
66 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wc:\"%V\"", &line); | |
67 #endif | |
68 | |
69 n = len; | |
70 | |
71 while (n) { | |
72 if (name[n - 1] == '.') { | |
73 break; | |
74 } | |
75 | |
76 n--; | |
77 } | |
78 | |
79 if (n == 0) { | |
80 return NULL; | |
81 } | |
82 | |
83 key = 0; | |
84 | |
85 for (i = n; i < len; i++) { | |
86 key = ngx_hash(key, name[i]); | |
87 } | |
88 | |
89 #if 0 | |
90 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key); | |
91 #endif | |
92 | |
93 value = ngx_hash_find(&hwc->hash, key, &name[n], len - n); | |
94 | |
95 if (value) { | |
96 if ((uintptr_t) value & 1) { | |
97 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~1); | |
98 | |
99 value = ngx_hash_find_wildcard(hwc, name, n - 1); | |
100 | |
101 if (value) { | |
102 return value; | |
103 } | |
104 | |
105 return hwc->value; | |
106 } | |
107 | |
108 return value; | |
109 } | |
110 | |
111 return hwc->value; | |
112 } | |
113 | |
114 | |
115 #define NGX_HASH_ELT_SIZE(name) \ | |
116 sizeof(void *) + ngx_align((name)->key.len + 1, sizeof(void *)) | |
117 | |
11 ngx_int_t | 118 ngx_int_t |
12 ngx_hash_init(ngx_hash_t *hash, ngx_pool_t *pool, void *names, ngx_uint_t nelts) | 119 ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) |
120 { | |
121 u_char *elts; | |
122 size_t *test, len; | |
123 ngx_uint_t i, n, key, size, start, bucket_size; | |
124 ngx_hash_elt_t *elt, **buckets; | |
125 | |
126 for (n = 0; n < nelts; n++) { | |
127 if (names[n].key.len >= 255) { | |
128 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, | |
129 "the \"%V\" value to hash is to long: %uz bytes, " | |
130 "the maximum length can be 255 bytes only", | |
131 &names[n].key, names[n].key.len); | |
132 return NGX_ERROR; | |
133 } | |
134 | |
135 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) | |
136 { | |
137 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, | |
138 "could not build the %s hash, you should " | |
139 "increase %s_bucket_size: %i", | |
140 hinit->name, hinit->name, hinit->bucket_size); | |
141 return NGX_ERROR; | |
142 } | |
143 } | |
144 | |
145 test = ngx_alloc(hinit->max_size * sizeof(ngx_uint_t), hinit->pool->log); | |
146 if (test == NULL) { | |
147 return NGX_ERROR; | |
148 } | |
149 | |
150 start = nelts / (ngx_cacheline_size / (2 * sizeof(void *)) - 1); | |
151 start = start ? start : 1; | |
152 | |
153 bucket_size = hinit->bucket_size - sizeof(void *); | |
154 | |
155 for (size = start; size < hinit->max_size; size++) { | |
156 | |
157 ngx_memzero(test, size * sizeof(ngx_uint_t)); | |
158 | |
159 for (n = 0; n < nelts; n++) { | |
160 if (names[n].key.data == NULL) { | |
161 continue; | |
162 } | |
163 | |
164 key = names[n].key_hash % size; | |
165 test[key] += NGX_HASH_ELT_SIZE(&names[n]); | |
166 | |
167 #if 0 | |
168 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
169 "%ui: %ui %ui \"%V\"", | |
170 size, key, test[key], &names[n].key); | |
171 #endif | |
172 | |
173 if (test[key] > bucket_size) { | |
174 goto next; | |
175 } | |
176 } | |
177 | |
178 goto found; | |
179 | |
180 next: | |
181 | |
182 continue; | |
183 } | |
184 | |
185 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0, | |
186 "could not build the %s hash, you should increase " | |
187 "either %s_max_size: %i or %s_bucket_size: %i", | |
188 hinit->name, hinit->name, hinit->max_size, | |
189 hinit->name, hinit->bucket_size); | |
190 | |
191 ngx_free(test); | |
192 | |
193 return NGX_ERROR; | |
194 | |
195 found: | |
196 | |
197 for (i = 0; i < size; i++) { | |
198 test[i] = sizeof(void *); | |
199 } | |
200 | |
201 for (n = 0; n < nelts; n++) { | |
202 if (names[n].key.data == NULL) { | |
203 continue; | |
204 } | |
205 | |
206 key = names[n].key_hash % size; | |
207 test[key] += NGX_HASH_ELT_SIZE(&names[n]); | |
208 } | |
209 | |
210 len = 0; | |
211 | |
212 for (i = 0; i < size; i++) { | |
213 if (test[i] == sizeof(void *)) { | |
214 continue; | |
215 } | |
216 | |
217 test[i] = ngx_align(test[i], ngx_cacheline_size); | |
218 | |
219 len += test[i]; | |
220 } | |
221 | |
222 if (hinit->hash == NULL) { | |
223 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t) | |
224 + size * sizeof(ngx_hash_elt_t *)); | |
225 if (hinit->hash == NULL) { | |
226 ngx_free(test); | |
227 return NGX_ERROR; | |
228 } | |
229 | |
230 buckets = (ngx_hash_elt_t **) | |
231 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t)); | |
232 | |
233 } else { | |
234 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *)); | |
235 if (buckets == NULL) { | |
236 ngx_free(test); | |
237 return NGX_ERROR; | |
238 } | |
239 } | |
240 | |
241 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size); | |
242 if (elts == NULL) { | |
243 ngx_free(test); | |
244 return NGX_ERROR; | |
245 } | |
246 | |
247 elts = ngx_align_ptr(elts, ngx_cacheline_size); | |
248 | |
249 for (i = 0; i < size; i++) { | |
250 if (test[i] == sizeof(void *)) { | |
251 continue; | |
252 } | |
253 | |
254 buckets[i] = (ngx_hash_elt_t *) elts; | |
255 elts += test[i]; | |
256 | |
257 } | |
258 | |
259 for (i = 0; i < size; i++) { | |
260 test[i] = 0; | |
261 } | |
262 | |
263 for (n = 0; n < nelts; n++) { | |
264 if (names[n].key.data == NULL) { | |
265 continue; | |
266 } | |
267 | |
268 key = names[n].key_hash % size; | |
269 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]); | |
270 | |
271 elt->value = names[n].value; | |
272 elt->len = (u_char) names[n].key.len; | |
273 | |
274 for (i = 0; i < names[n].key.len; i++) { | |
275 elt->name[i] = ngx_tolower(names[n].key.data[i]); | |
276 } | |
277 | |
278 test[key] += NGX_HASH_ELT_SIZE(&names[n]); | |
279 } | |
280 | |
281 for (i = 0; i < size; i++) { | |
282 if (buckets[i] == NULL) { | |
283 continue; | |
284 } | |
285 | |
286 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]); | |
287 | |
288 elt->value = NULL; | |
289 } | |
290 | |
291 ngx_free(test); | |
292 | |
293 hinit->hash->buckets = buckets; | |
294 hinit->hash->size = size; | |
295 | |
296 #if 0 | |
297 | |
298 for (i = 0; i < size; i++) { | |
299 ngx_str_t val; | |
300 ngx_uint_t key; | |
301 | |
302 elt = buckets[i]; | |
303 | |
304 if (elt == NULL) { | |
305 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
306 "%ui: NULL", i); | |
307 continue; | |
308 } | |
309 | |
310 while (elt->value) { | |
311 val.len = elt->len; | |
312 val.data = &elt->name[0]; | |
313 | |
314 key = hinit->key(val.data, val.len); | |
315 | |
316 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
317 "%ui: %p \"%V\" %ui", i, elt, &val, key); | |
318 | |
319 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len, | |
320 sizeof(void *)); | |
321 } | |
322 } | |
323 | |
324 #endif | |
325 | |
326 return NGX_OK; | |
327 } | |
328 | |
329 | |
330 ngx_int_t | |
331 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, | |
332 ngx_uint_t nelts) | |
333 { | |
334 size_t len; | |
335 ngx_uint_t i, n; | |
336 ngx_array_t curr_names, next_names; | |
337 ngx_hash_key_t *name, *next_name; | |
338 ngx_hash_init_t h; | |
339 ngx_hash_wildcard_t *wdc; | |
340 | |
341 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts, | |
342 sizeof(ngx_hash_key_t)) | |
343 != NGX_OK) | |
344 { | |
345 return NGX_ERROR; | |
346 } | |
347 | |
348 if (ngx_array_init(&next_names, hinit->temp_pool, nelts, | |
349 sizeof(ngx_hash_key_t)) | |
350 != NGX_OK) | |
351 { | |
352 return NGX_ERROR; | |
353 } | |
354 | |
355 for (n = 0; n < nelts; n = i) { | |
356 | |
357 #if 0 | |
358 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
359 "wc0: \"%V\"", &names[n].key); | |
360 #endif | |
361 | |
362 for (len = 0; len < names[n].key.len; len++) { | |
363 if (names[n].key.data[len] == '.') { | |
364 len++; | |
365 break; | |
366 } | |
367 } | |
368 | |
369 name = ngx_array_push(&curr_names); | |
370 if (name == NULL) { | |
371 return NGX_ERROR; | |
372 } | |
373 | |
374 name->key.len = len - 1; | |
375 name->key.data = names[n].key.data; | |
376 name->key_hash = hinit->key(name->key.data, name->key.len); | |
377 name->value = names[n].value; | |
378 | |
379 #if 0 | |
380 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
381 "wc1: \"%V\"", &name->key); | |
382 #endif | |
383 | |
384 next_names.nelts = 0; | |
385 | |
386 if (names[n].key.len != len) { | |
387 next_name = ngx_array_push(&next_names); | |
388 if (next_name == NULL) { | |
389 return NGX_ERROR; | |
390 } | |
391 | |
392 next_name->key.len = names[n].key.len - len; | |
393 next_name->key.data = names[n].key.data + len; | |
394 next_name->key_hash= 0; | |
395 next_name->value = names[n].value; | |
396 | |
397 #if 0 | |
398 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
399 "wc2: \"%V\"", &next_name->key); | |
400 #endif | |
401 } | |
402 | |
403 for (i = n + 1; i < nelts; i++) { | |
404 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) { | |
405 break; | |
406 } | |
407 | |
408 next_name = ngx_array_push(&next_names); | |
409 if (next_name == NULL) { | |
410 return NGX_ERROR; | |
411 } | |
412 | |
413 next_name->key.len = names[i].key.len - len; | |
414 next_name->key.data = names[i].key.data + len; | |
415 next_name->key_hash= 0; | |
416 next_name->value = names[i].value; | |
417 | |
418 #if 0 | |
419 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
420 "wc2: \"%V\"", &next_name->key); | |
421 #endif | |
422 } | |
423 | |
424 if (next_names.nelts) { | |
425 h = *hinit; | |
426 h.hash = NULL; | |
427 | |
428 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts, | |
429 next_names.nelts) | |
430 != NGX_OK) | |
431 { | |
432 return NGX_ERROR; | |
433 } | |
434 | |
435 wdc = (ngx_hash_wildcard_t *) h.hash; | |
436 | |
437 if (names[n].key.len == len) { | |
438 wdc->value = names[n].value; | |
439 #if 0 | |
440 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0, | |
441 "wdc: \"%V\"", wdc->value); | |
442 #endif | |
443 } | |
444 | |
445 name->value = (void *) ((uintptr_t) wdc | 1); | |
446 } | |
447 } | |
448 | |
449 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts, | |
450 curr_names.nelts) | |
451 != NGX_OK) | |
452 { | |
453 return NGX_ERROR; | |
454 } | |
455 | |
456 return NGX_OK; | |
457 } | |
458 | |
459 | |
460 ngx_uint_t | |
461 ngx_hash_key(u_char *data, size_t len) | |
462 { | |
463 ngx_uint_t i, key; | |
464 | |
465 key = 0; | |
466 | |
467 for (i = 0; i < len; i++) { | |
468 key = ngx_hash(key, data[i]); | |
469 } | |
470 | |
471 return key; | |
472 } | |
473 | |
474 | |
475 ngx_uint_t | |
476 ngx_hash_key_lc(u_char *data, size_t len) | |
477 { | |
478 ngx_uint_t i, key; | |
479 | |
480 key = 0; | |
481 | |
482 for (i = 0; i < len; i++) { | |
483 key = ngx_hash(key, ngx_tolower(data[i])); | |
484 } | |
485 | |
486 return key; | |
487 } | |
488 | |
489 | |
490 ngx_int_t | |
491 ngx_hash0_init(ngx_hash0_t *hash, ngx_pool_t *pool, void *names, | |
492 ngx_uint_t nelts) | |
13 { | 493 { |
14 u_char *p; | 494 u_char *p; |
15 ngx_str_t *name, *bucket; | 495 ngx_str_t *name, *bucket; |
16 ngx_uint_t i, n, key, size, best, *test, buckets, min_buckets; | 496 ngx_uint_t i, n, key, size, best, *test, buckets, min_buckets; |
17 | 497 |