Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_hash.c @ 138:8e6d4d96ec4c NGINX_0_3_16

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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