|
507
|
1
|
|
|
2 /*
|
|
|
3 * Copyright (C) Igor Sysoev
|
|
|
4 */
|
|
|
5
|
|
|
6
|
|
|
7 #include <ngx_config.h>
|
|
|
8 #include <ngx_core.h>
|
|
|
9
|
|
|
10
|
|
589
|
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
|
|
507
|
118 ngx_int_t
|
|
589
|
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)
|
|
507
|
493 {
|
|
|
494 u_char *p;
|
|
509
|
495 ngx_str_t *name, *bucket;
|
|
|
496 ngx_uint_t i, n, key, size, best, *test, buckets, min_buckets;
|
|
|
497
|
|
|
498 if (nelts == 0) {
|
|
|
499 for (name = (ngx_str_t *) names;
|
|
|
500 name->len;
|
|
|
501 name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
|
502 {
|
|
|
503 nelts++;
|
|
|
504 }
|
|
|
505 }
|
|
507
|
506
|
|
|
507 test = ngx_alloc(hash->max_size * sizeof(ngx_uint_t), pool->log);
|
|
|
508 if (test == NULL) {
|
|
|
509 return NGX_ERROR;
|
|
|
510 }
|
|
|
511
|
|
|
512 min_buckets = hash->bucket_limit + 1;
|
|
|
513
|
|
|
514 #if (NGX_SUPPRESS_WARN)
|
|
|
515 best = 0;
|
|
|
516 #endif
|
|
|
517
|
|
|
518 for (size = 1; size < hash->max_size; size++) {
|
|
|
519
|
|
|
520 buckets = 0;
|
|
|
521
|
|
|
522 for (i = 0; i < size; i++) {
|
|
|
523 test[i] = 0;
|
|
|
524 }
|
|
|
525
|
|
509
|
526 for (n = 0, name = (ngx_str_t *) names;
|
|
|
527 n < nelts;
|
|
|
528 n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
507
|
529 {
|
|
583
|
530 if (name->data == NULL) {
|
|
|
531 continue;
|
|
|
532 }
|
|
|
533
|
|
507
|
534 key = 0;
|
|
|
535
|
|
509
|
536 for (i = 0; i < name->len; i++) {
|
|
|
537 key += ngx_tolower(name->data[i]);
|
|
507
|
538 }
|
|
|
539
|
|
|
540 key %= size;
|
|
|
541
|
|
|
542 if (test[key] == hash->bucket_limit) {
|
|
|
543 break;
|
|
|
544 }
|
|
|
545
|
|
|
546 test[key]++;
|
|
|
547
|
|
|
548 if (buckets < test[key]) {
|
|
|
549 buckets = test[key];
|
|
|
550 }
|
|
|
551 }
|
|
|
552
|
|
509
|
553 if (n == nelts) {
|
|
507
|
554 if (min_buckets > buckets) {
|
|
|
555 min_buckets = buckets;
|
|
|
556 best = size;
|
|
|
557 }
|
|
|
558
|
|
|
559 if (hash->bucket_limit == 1) {
|
|
|
560 break;
|
|
|
561 }
|
|
|
562 }
|
|
|
563 }
|
|
|
564
|
|
|
565 if (min_buckets == hash->bucket_limit + 1) {
|
|
|
566 ngx_log_error(NGX_LOG_EMERG, pool->log, 0,
|
|
|
567 "could not build the %s hash, you should increase "
|
|
|
568 "either %s_size: %i or %s_bucket_limit: %i",
|
|
|
569 hash->name, hash->name, hash->max_size,
|
|
|
570 hash->name, hash->bucket_limit);
|
|
|
571 ngx_free(test);
|
|
|
572 return NGX_ERROR;
|
|
|
573 }
|
|
|
574
|
|
|
575 hash->buckets = ngx_pcalloc(pool, best * hash->bucket_size);
|
|
|
576 if (hash->buckets == NULL) {
|
|
|
577 ngx_free(test);
|
|
|
578 return NGX_ERROR;
|
|
|
579 }
|
|
|
580
|
|
|
581 if (hash->bucket_limit != 1) {
|
|
|
582
|
|
|
583 for (i = 0; i < best; i++) {
|
|
|
584 test[i] = 0;
|
|
|
585 }
|
|
|
586
|
|
509
|
587 for (n = 0, name = (ngx_str_t *) names;
|
|
|
588 n < nelts;
|
|
|
589 n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
507
|
590 {
|
|
583
|
591 if (name->data == NULL) {
|
|
|
592 continue;
|
|
|
593 }
|
|
|
594
|
|
507
|
595 key = 0;
|
|
|
596
|
|
509
|
597 for (i = 0; i < name->len; i++) {
|
|
|
598 key += ngx_tolower(name->data[i]);
|
|
507
|
599 }
|
|
|
600
|
|
|
601 key %= best;
|
|
|
602
|
|
|
603 test[key]++;
|
|
|
604 }
|
|
|
605
|
|
|
606 for (i = 0; i < best; i++) {
|
|
|
607 if (test[i] == 0) {
|
|
|
608 continue;
|
|
|
609 }
|
|
|
610
|
|
|
611 bucket = ngx_palloc(pool, test[i] * hash->bucket_size);
|
|
|
612 if (bucket == NULL) {
|
|
|
613 ngx_free(test);
|
|
|
614 return NGX_ERROR;
|
|
|
615 }
|
|
|
616
|
|
|
617 hash->buckets[i] = bucket;
|
|
|
618 bucket->len = 0;
|
|
|
619 }
|
|
|
620 }
|
|
|
621
|
|
509
|
622 for (n = 0, name = (ngx_str_t *) names;
|
|
|
623 n < nelts;
|
|
|
624 n++, name = (ngx_str_t *) ((char *) name + hash->bucket_size))
|
|
507
|
625 {
|
|
583
|
626 if (name->data == NULL) {
|
|
|
627 continue;
|
|
|
628 }
|
|
|
629
|
|
507
|
630 key = 0;
|
|
|
631
|
|
509
|
632 for (i = 0; i < name->len; i++) {
|
|
|
633 key += ngx_tolower(name->data[i]);
|
|
507
|
634 }
|
|
|
635
|
|
|
636 key %= best;
|
|
|
637
|
|
|
638 if (hash->bucket_limit == 1) {
|
|
|
639 p = (u_char *) hash->buckets + key * hash->bucket_size;
|
|
509
|
640 ngx_memcpy(p, name, hash->bucket_size);
|
|
507
|
641 continue;
|
|
|
642 }
|
|
|
643
|
|
|
644 for (bucket = hash->buckets[key];
|
|
|
645 bucket->len;
|
|
|
646 bucket = (ngx_str_t *) ((char *) bucket + hash->bucket_size))
|
|
|
647 {
|
|
|
648 bucket->len &= 0x7fffffff;
|
|
|
649 }
|
|
|
650
|
|
509
|
651 ngx_memcpy(bucket, name, hash->bucket_size);
|
|
507
|
652 bucket->len |= 0x80000000;
|
|
|
653 }
|
|
|
654
|
|
|
655 ngx_free(test);
|
|
|
656
|
|
|
657 hash->hash_size = best;
|
|
|
658 hash->min_buckets = min_buckets;
|
|
|
659
|
|
|
660 return NGX_OK;
|
|
|
661 }
|
