1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
5 */
6
7
8 #include <ngx_config.h>
9 #include <ngx_core.h>
10
11
12 void *
ngx_hash_find(ngx_hash_t * hash,ngx_uint_t key,u_char * name,size_t len)13 ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
14 {
15 ngx_uint_t i;
16 ngx_hash_elt_t *elt;
17
18 #if 0
19 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
20 #endif
21
22 elt = hash->buckets[key % hash->size];
23
24 if (elt == NULL) {
25 return NULL;
26 }
27
28 while (elt->value) {
29 if (len != (size_t) elt->len) {
30 goto next;
31 }
32
33 for (i = 0; i < len; i++) {
34 if (name[i] != elt->name[i]) {
35 goto next;
36 }
37 }
38
39 return elt->value;
40
41 next:
42
43 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
44 sizeof(void *));
45 continue;
46 }
47
48 return NULL;
49 }
50
51
52 void *
ngx_hash_find_wc_head(ngx_hash_wildcard_t * hwc,u_char * name,size_t len)53 ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
54 {
55 void *value;
56 ngx_uint_t i, n, key;
57
58 #if 0
59 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name);
60 #endif
61
62 n = len;
63
64 while (n) {
65 if (name[n - 1] == '.') {
66 break;
67 }
68
69 n--;
70 }
71
72 key = 0;
73
74 for (i = n; i < len; i++) {
75 key = ngx_hash(key, name[i]);
76 }
77
78 #if 0
79 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
80 #endif
81
82 value = ngx_hash_find(&hwc->hash, key, &name[n], len - n);
83
84 #if 0
85 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
86 #endif
87
88 if (value) {
89
90 /*
91 * the 2 low bits of value have the special meaning:
92 * 00 - value is data pointer for both "example.com"
93 * and "*.example.com";
94 * 01 - value is data pointer for "*.example.com" only;
95 * 10 - value is pointer to wildcard hash allowing
96 * both "example.com" and "*.example.com";
97 * 11 - value is pointer to wildcard hash allowing
98 * "*.example.com" only.
99 */
100
101 if ((uintptr_t) value & 2) {
102
103 if (n == 0) {
104
105 /* "example.com" */
106
107 if ((uintptr_t) value & 1) {
108 return NULL;
109 }
110
111 hwc = (ngx_hash_wildcard_t *)
112 ((uintptr_t) value & (uintptr_t) ~3);
113 return hwc->value;
114 }
115
116 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
117
118 value = ngx_hash_find_wc_head(hwc, name, n - 1);
119
120 if (value) {
121 return value;
122 }
123
124 return hwc->value;
125 }
126
127 if ((uintptr_t) value & 1) {
128
129 if (n == 0) {
130
131 /* "example.com" */
132
133 return NULL;
134 }
135
136 return (void *) ((uintptr_t) value & (uintptr_t) ~3);
137 }
138
139 return value;
140 }
141
142 return hwc->value;
143 }
144
145
146 void *
ngx_hash_find_wc_tail(ngx_hash_wildcard_t * hwc,u_char * name,size_t len)147 ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
148 {
149 void *value;
150 ngx_uint_t i, key;
151
152 #if 0
153 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name);
154 #endif
155
156 key = 0;
157
158 for (i = 0; i < len; i++) {
159 if (name[i] == '.') {
160 break;
161 }
162
163 key = ngx_hash(key, name[i]);
164 }
165
166 if (i == len) {
167 return NULL;
168 }
169
170 #if 0
171 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
172 #endif
173
174 value = ngx_hash_find(&hwc->hash, key, name, i);
175
176 #if 0
177 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
178 #endif
179
180 if (value) {
181
182 /*
183 * the 2 low bits of value have the special meaning:
184 * 00 - value is data pointer;
185 * 11 - value is pointer to wildcard hash allowing "example.*".
186 */
187
188 if ((uintptr_t) value & 2) {
189
190 i++;
191
192 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
193
194 value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);
195
196 if (value) {
197 return value;
198 }
199
200 return hwc->value;
201 }
202
203 return value;
204 }
205
206 return hwc->value;
207 }
208
209
210 void *
ngx_hash_find_combined(ngx_hash_combined_t * hash,ngx_uint_t key,u_char * name,size_t len)211 ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name,
212 size_t len)
213 {
214 void *value;
215
216 if (hash->hash.buckets) {
217 value = ngx_hash_find(&hash->hash, key, name, len);
218
219 if (value) {
220 return value;
221 }
222 }
223
224 if (len == 0) {
225 return NULL;
226 }
227
228 if (hash->wc_head && hash->wc_head->hash.buckets) {
229 value = ngx_hash_find_wc_head(hash->wc_head, name, len);
230
231 if (value) {
232 return value;
233 }
234 }
235
236 if (hash->wc_tail && hash->wc_tail->hash.buckets) {
237 value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);
238
239 if (value) {
240 return value;
241 }
242 }
243
244 return NULL;
245 }
246
247
248 #define NGX_HASH_ELT_SIZE(name) \
249 (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
250
251 ngx_int_t
ngx_hash_init(ngx_hash_init_t * hinit,ngx_hash_key_t * names,ngx_uint_t nelts)252 ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
253 {
254 u_char *elts;
255 size_t len;
256 u_short *test;
257 ngx_uint_t i, n, key, size, start, bucket_size;
258 ngx_hash_elt_t *elt, **buckets;
259
260 if (hinit->max_size == 0) {
261 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
262 "could not build %s, you should "
263 "increase %s_max_size: %i",
264 hinit->name, hinit->name, hinit->max_size);
265 return NGX_ERROR;
266 }
267
268 if (hinit->bucket_size > 65536 - ngx_cacheline_size) {
269 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
270 "could not build %s, too large "
271 "%s_bucket_size: %i",
272 hinit->name, hinit->name, hinit->bucket_size);
273 return NGX_ERROR;
274 }
275
276 for (n = 0; n < nelts; n++) {
277 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
278 {
279 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
280 "could not build %s, you should "
281 "increase %s_bucket_size: %i",
282 hinit->name, hinit->name, hinit->bucket_size);
283 return NGX_ERROR;
284 }
285 }
286
287 test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
288 if (test == NULL) {
289 return NGX_ERROR;
290 }
291
292 bucket_size = hinit->bucket_size - sizeof(void *);
293
294 start = nelts / (bucket_size / (2 * sizeof(void *)));
295 start = start ? start : 1;
296
297 if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
298 start = hinit->max_size - 1000;
299 }
300
301 for (size = start; size <= hinit->max_size; size++) {
302
303 ngx_memzero(test, size * sizeof(u_short));
304
305 for (n = 0; n < nelts; n++) {
306 if (names[n].key.data == NULL) {
307 continue;
308 }
309
310 key = names[n].key_hash % size;
311 len = test[key] + NGX_HASH_ELT_SIZE(&names[n]);
312
313 #if 0
314 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
315 "%ui: %ui %uz \"%V\"",
316 size, key, len, &names[n].key);
317 #endif
318
319 if (len > bucket_size) {
320 goto next;
321 }
322
323 test[key] = (u_short) len;
324 }
325
326 goto found;
327
328 next:
329
330 continue;
331 }
332
333 size = hinit->max_size;
334
335 ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
336 "could not build optimal %s, you should increase "
337 "either %s_max_size: %i or %s_bucket_size: %i; "
338 "ignoring %s_bucket_size",
339 hinit->name, hinit->name, hinit->max_size,
340 hinit->name, hinit->bucket_size, hinit->name);
341
342 found:
343
344 for (i = 0; i < size; i++) {
345 test[i] = sizeof(void *);
346 }
347
348 for (n = 0; n < nelts; n++) {
349 if (names[n].key.data == NULL) {
350 continue;
351 }
352
353 key = names[n].key_hash % size;
354 len = test[key] + NGX_HASH_ELT_SIZE(&names[n]);
355
356 if (len > 65536 - ngx_cacheline_size) {
357 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
358 "could not build %s, you should "
359 "increase %s_max_size: %i",
360 hinit->name, hinit->name, hinit->max_size);
361 ngx_free(test);
362 return NGX_ERROR;
363 }
364
365 test[key] = (u_short) len;
366 }
367
368 len = 0;
369
370 for (i = 0; i < size; i++) {
371 if (test[i] == sizeof(void *)) {
372 continue;
373 }
374
375 test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
376
377 len += test[i];
378 }
379
380 if (hinit->hash == NULL) {
381 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
382 + size * sizeof(ngx_hash_elt_t *));
383 if (hinit->hash == NULL) {
384 ngx_free(test);
385 return NGX_ERROR;
386 }
387
388 buckets = (ngx_hash_elt_t **)
389 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
390
391 } else {
392 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
393 if (buckets == NULL) {
394 ngx_free(test);
395 return NGX_ERROR;
396 }
397 }
398
399 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
400 if (elts == NULL) {
401 ngx_free(test);
402 return NGX_ERROR;
403 }
404
405 elts = ngx_align_ptr(elts, ngx_cacheline_size);
406
407 for (i = 0; i < size; i++) {
408 if (test[i] == sizeof(void *)) {
409 continue;
410 }
411
412 buckets[i] = (ngx_hash_elt_t *) elts;
413 elts += test[i];
414 }
415
416 for (i = 0; i < size; i++) {
417 test[i] = 0;
418 }
419
420 for (n = 0; n < nelts; n++) {
421 if (names[n].key.data == NULL) {
422 continue;
423 }
424
425 key = names[n].key_hash % size;
426 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
427
428 elt->value = names[n].value;
429 elt->len = (u_short) names[n].key.len;
430
431 ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
432
433 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
434 }
435
436 for (i = 0; i < size; i++) {
437 if (buckets[i] == NULL) {
438 continue;
439 }
440
441 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
442
443 elt->value = NULL;
444 }
445
446 ngx_free(test);
447
448 hinit->hash->buckets = buckets;
449 hinit->hash->size = size;
450
451 #if 0
452
453 for (i = 0; i < size; i++) {
454 ngx_str_t val;
455 ngx_uint_t key;
456
457 elt = buckets[i];
458
459 if (elt == NULL) {
460 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
461 "%ui: NULL", i);
462 continue;
463 }
464
465 while (elt->value) {
466 val.len = elt->len;
467 val.data = &elt->name[0];
468
469 key = hinit->key(val.data, val.len);
470
471 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
472 "%ui: %p \"%V\" %ui", i, elt, &val, key);
473
474 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
475 sizeof(void *));
476 }
477 }
478
479 #endif
480
481 return NGX_OK;
482 }
483
484
485 ngx_int_t
ngx_hash_wildcard_init(ngx_hash_init_t * hinit,ngx_hash_key_t * names,ngx_uint_t nelts)486 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
487 ngx_uint_t nelts)
488 {
489 size_t len, dot_len;
490 ngx_uint_t i, n, dot;
491 ngx_array_t curr_names, next_names;
492 ngx_hash_key_t *name, *next_name;
493 ngx_hash_init_t h;
494 ngx_hash_wildcard_t *wdc;
495
496 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
497 sizeof(ngx_hash_key_t))
498 != NGX_OK)
499 {
500 return NGX_ERROR;
501 }
502
503 if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
504 sizeof(ngx_hash_key_t))
505 != NGX_OK)
506 {
507 return NGX_ERROR;
508 }
509
510 for (n = 0; n < nelts; n = i) {
511
512 #if 0
513 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
514 "wc0: \"%V\"", &names[n].key);
515 #endif
516
517 dot = 0;
518
519 for (len = 0; len < names[n].key.len; len++) {
520 if (names[n].key.data[len] == '.') {
521 dot = 1;
522 break;
523 }
524 }
525
526 name = ngx_array_push(&curr_names);
527 if (name == NULL) {
528 return NGX_ERROR;
529 }
530
531 name->key.len = len;
532 name->key.data = names[n].key.data;
533 name->key_hash = hinit->key(name->key.data, name->key.len);
534 name->value = names[n].value;
535
536 #if 0
537 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
538 "wc1: \"%V\" %ui", &name->key, dot);
539 #endif
540
541 dot_len = len + 1;
542
543 if (dot) {
544 len++;
545 }
546
547 next_names.nelts = 0;
548
549 if (names[n].key.len != len) {
550 next_name = ngx_array_push(&next_names);
551 if (next_name == NULL) {
552 return NGX_ERROR;
553 }
554
555 next_name->key.len = names[n].key.len - len;
556 next_name->key.data = names[n].key.data + len;
557 next_name->key_hash = 0;
558 next_name->value = names[n].value;
559
560 #if 0
561 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
562 "wc2: \"%V\"", &next_name->key);
563 #endif
564 }
565
566 for (i = n + 1; i < nelts; i++) {
567 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
568 break;
569 }
570
571 if (!dot
572 && names[i].key.len > len
573 && names[i].key.data[len] != '.')
574 {
575 break;
576 }
577
578 next_name = ngx_array_push(&next_names);
579 if (next_name == NULL) {
580 return NGX_ERROR;
581 }
582
583 next_name->key.len = names[i].key.len - dot_len;
584 next_name->key.data = names[i].key.data + dot_len;
585 next_name->key_hash = 0;
586 next_name->value = names[i].value;
587
588 #if 0
589 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
590 "wc3: \"%V\"", &next_name->key);
591 #endif
592 }
593
594 if (next_names.nelts) {
595
596 h = *hinit;
597 h.hash = NULL;
598
599 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
600 next_names.nelts)
601 != NGX_OK)
602 {
603 return NGX_ERROR;
604 }
605
606 wdc = (ngx_hash_wildcard_t *) h.hash;
607
608 if (names[n].key.len == len) {
609 wdc->value = names[n].value;
610 }
611
612 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
613
614 } else if (dot) {
615 name->value = (void *) ((uintptr_t) name->value | 1);
616 }
617 }
618
619 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
620 curr_names.nelts)
621 != NGX_OK)
622 {
623 return NGX_ERROR;
624 }
625
626 return NGX_OK;
627 }
628
629
630 ngx_uint_t
ngx_hash_key(u_char * data,size_t len)631 ngx_hash_key(u_char *data, size_t len)
632 {
633 ngx_uint_t i, key;
634
635 key = 0;
636
637 for (i = 0; i < len; i++) {
638 key = ngx_hash(key, data[i]);
639 }
640
641 return key;
642 }
643
644
645 ngx_uint_t
ngx_hash_key_lc(u_char * data,size_t len)646 ngx_hash_key_lc(u_char *data, size_t len)
647 {
648 ngx_uint_t i, key;
649
650 key = 0;
651
652 for (i = 0; i < len; i++) {
653 key = ngx_hash(key, ngx_tolower(data[i]));
654 }
655
656 return key;
657 }
658
659
660 ngx_uint_t
ngx_hash_strlow(u_char * dst,u_char * src,size_t n)661 ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
662 {
663 ngx_uint_t key;
664
665 key = 0;
666
667 while (n--) {
668 *dst = ngx_tolower(*src);
669 key = ngx_hash(key, *dst);
670 dst++;
671 src++;
672 }
673
674 return key;
675 }
676
677
678 ngx_int_t
ngx_hash_keys_array_init(ngx_hash_keys_arrays_t * ha,ngx_uint_t type)679 ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
680 {
681 ngx_uint_t asize;
682
683 if (type == NGX_HASH_SMALL) {
684 asize = 4;
685 ha->hsize = 107;
686
687 } else {
688 asize = NGX_HASH_LARGE_ASIZE;
689 ha->hsize = NGX_HASH_LARGE_HSIZE;
690 }
691
692 if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
693 != NGX_OK)
694 {
695 return NGX_ERROR;
696 }
697
698 if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
699 sizeof(ngx_hash_key_t))
700 != NGX_OK)
701 {
702 return NGX_ERROR;
703 }
704
705 if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
706 sizeof(ngx_hash_key_t))
707 != NGX_OK)
708 {
709 return NGX_ERROR;
710 }
711
712 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
713 if (ha->keys_hash == NULL) {
714 return NGX_ERROR;
715 }
716
717 ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
718 sizeof(ngx_array_t) * ha->hsize);
719 if (ha->dns_wc_head_hash == NULL) {
720 return NGX_ERROR;
721 }
722
723 ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
724 sizeof(ngx_array_t) * ha->hsize);
725 if (ha->dns_wc_tail_hash == NULL) {
726 return NGX_ERROR;
727 }
728
729 return NGX_OK;
730 }
731
732
733 ngx_int_t
ngx_hash_add_key(ngx_hash_keys_arrays_t * ha,ngx_str_t * key,void * value,ngx_uint_t flags)734 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
735 ngx_uint_t flags)
736 {
737 size_t len;
738 u_char *p;
739 ngx_str_t *name;
740 ngx_uint_t i, k, n, skip, last;
741 ngx_array_t *keys, *hwc;
742 ngx_hash_key_t *hk;
743
744 last = key->len;
745
746 if (flags & NGX_HASH_WILDCARD_KEY) {
747
748 /*
749 * supported wildcards:
750 * "*.example.com", ".example.com", and "www.example.*"
751 */
752
753 n = 0;
754
755 for (i = 0; i < key->len; i++) {
756
757 if (key->data[i] == '*') {
758 if (++n > 1) {
759 return NGX_DECLINED;
760 }
761 }
762
763 if (key->data[i] == '.' && key->data[i + 1] == '.') {
764 return NGX_DECLINED;
765 }
766
767 if (key->data[i] == '\0') {
768 return NGX_DECLINED;
769 }
770 }
771
772 if (key->len > 1 && key->data[0] == '.') {
773 skip = 1;
774 goto wildcard;
775 }
776
777 if (key->len > 2) {
778
779 if (key->data[0] == '*' && key->data[1] == '.') {
780 skip = 2;
781 goto wildcard;
782 }
783
784 if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
785 skip = 0;
786 last -= 2;
787 goto wildcard;
788 }
789 }
790
791 if (n) {
792 return NGX_DECLINED;
793 }
794 }
795
796 /* exact hash */
797
798 k = 0;
799
800 for (i = 0; i < last; i++) {
801 if (!(flags & NGX_HASH_READONLY_KEY)) {
802 key->data[i] = ngx_tolower(key->data[i]);
803 }
804 k = ngx_hash(k, key->data[i]);
805 }
806
807 k %= ha->hsize;
808
809 /* check conflicts in exact hash */
810
811 name = ha->keys_hash[k].elts;
812
813 if (name) {
814 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
815 if (last != name[i].len) {
816 continue;
817 }
818
819 if (ngx_strncmp(key->data, name[i].data, last) == 0) {
820 return NGX_BUSY;
821 }
822 }
823
824 } else {
825 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
826 sizeof(ngx_str_t))
827 != NGX_OK)
828 {
829 return NGX_ERROR;
830 }
831 }
832
833 name = ngx_array_push(&ha->keys_hash[k]);
834 if (name == NULL) {
835 return NGX_ERROR;
836 }
837
838 *name = *key;
839
840 hk = ngx_array_push(&ha->keys);
841 if (hk == NULL) {
842 return NGX_ERROR;
843 }
844
845 hk->key = *key;
846 hk->key_hash = ngx_hash_key(key->data, last);
847 hk->value = value;
848
849 return NGX_OK;
850
851
852 wildcard:
853
854 /* wildcard hash */
855
856 k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);
857
858 k %= ha->hsize;
859
860 if (skip == 1) {
861
862 /* check conflicts in exact hash for ".example.com" */
863
864 name = ha->keys_hash[k].elts;
865
866 if (name) {
867 len = last - skip;
868
869 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
870 if (len != name[i].len) {
871 continue;
872 }
873
874 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
875 return NGX_BUSY;
876 }
877 }
878
879 } else {
880 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
881 sizeof(ngx_str_t))
882 != NGX_OK)
883 {
884 return NGX_ERROR;
885 }
886 }
887
888 name = ngx_array_push(&ha->keys_hash[k]);
889 if (name == NULL) {
890 return NGX_ERROR;
891 }
892
893 name->len = last - 1;
894 name->data = ngx_pnalloc(ha->temp_pool, name->len);
895 if (name->data == NULL) {
896 return NGX_ERROR;
897 }
898
899 ngx_memcpy(name->data, &key->data[1], name->len);
900 }
901
902
903 if (skip) {
904
905 /*
906 * convert "*.example.com" to "com.example.\0"
907 * and ".example.com" to "com.example\0"
908 */
909
910 p = ngx_pnalloc(ha->temp_pool, last);
911 if (p == NULL) {
912 return NGX_ERROR;
913 }
914
915 len = 0;
916 n = 0;
917
918 for (i = last - 1; i; i--) {
919 if (key->data[i] == '.') {
920 ngx_memcpy(&p[n], &key->data[i + 1], len);
921 n += len;
922 p[n++] = '.';
923 len = 0;
924 continue;
925 }
926
927 len++;
928 }
929
930 if (len) {
931 ngx_memcpy(&p[n], &key->data[1], len);
932 n += len;
933 }
934
935 p[n] = '\0';
936
937 hwc = &ha->dns_wc_head;
938 keys = &ha->dns_wc_head_hash[k];
939
940 } else {
941
942 /* convert "www.example.*" to "www.example\0" */
943
944 last++;
945
946 p = ngx_pnalloc(ha->temp_pool, last);
947 if (p == NULL) {
948 return NGX_ERROR;
949 }
950
951 ngx_cpystrn(p, key->data, last);
952
953 hwc = &ha->dns_wc_tail;
954 keys = &ha->dns_wc_tail_hash[k];
955 }
956
957
958 /* check conflicts in wildcard hash */
959
960 name = keys->elts;
961
962 if (name) {
963 len = last - skip;
964
965 for (i = 0; i < keys->nelts; i++) {
966 if (len != name[i].len) {
967 continue;
968 }
969
970 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
971 return NGX_BUSY;
972 }
973 }
974
975 } else {
976 if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
977 {
978 return NGX_ERROR;
979 }
980 }
981
982 name = ngx_array_push(keys);
983 if (name == NULL) {
984 return NGX_ERROR;
985 }
986
987 name->len = last - skip;
988 name->data = ngx_pnalloc(ha->temp_pool, name->len);
989 if (name->data == NULL) {
990 return NGX_ERROR;
991 }
992
993 ngx_memcpy(name->data, key->data + skip, name->len);
994
995
996 /* add to wildcard hash */
997
998 hk = ngx_array_push(hwc);
999 if (hk == NULL) {
1000 return NGX_ERROR;
1001 }
1002
1003 hk->key.len = last - 1;
1004 hk->key.data = p;
1005 hk->key_hash = 0;
1006 hk->value = value;
1007
1008 return NGX_OK;
1009 }
1010