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 for (n = 0; n < nelts; n++) {
269 if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
270 {
271 ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
272 "could not build %s, you should "
273 "increase %s_bucket_size: %i",
274 hinit->name, hinit->name, hinit->bucket_size);
275 return NGX_ERROR;
276 }
277 }
278
279 test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
280 if (test == NULL) {
281 return NGX_ERROR;
282 }
283
284 bucket_size = hinit->bucket_size - sizeof(void *);
285
286 start = nelts / (bucket_size / (2 * sizeof(void *)));
287 start = start ? start : 1;
288
289 if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
290 start = hinit->max_size - 1000;
291 }
292
293 for (size = start; size <= hinit->max_size; size++) {
294
295 ngx_memzero(test, size * sizeof(u_short));
296
297 for (n = 0; n < nelts; n++) {
298 if (names[n].key.data == NULL) {
299 continue;
300 }
301
302 key = names[n].key_hash % size;
303 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
304
305 #if 0
306 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
307 "%ui: %ui %ui \"%V\"",
308 size, key, test[key], &names[n].key);
309 #endif
310
311 if (test[key] > (u_short) bucket_size) {
312 goto next;
313 }
314 }
315
316 goto found;
317
318 next:
319
320 continue;
321 }
322
323 size = hinit->max_size;
324
325 ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
326 "could not build optimal %s, you should increase "
327 "either %s_max_size: %i or %s_bucket_size: %i; "
328 "ignoring %s_bucket_size",
329 hinit->name, hinit->name, hinit->max_size,
330 hinit->name, hinit->bucket_size, hinit->name);
331
332 found:
333
334 for (i = 0; i < size; i++) {
335 test[i] = sizeof(void *);
336 }
337
338 for (n = 0; n < nelts; n++) {
339 if (names[n].key.data == NULL) {
340 continue;
341 }
342
343 key = names[n].key_hash % size;
344 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
345 }
346
347 len = 0;
348
349 for (i = 0; i < size; i++) {
350 if (test[i] == sizeof(void *)) {
351 continue;
352 }
353
354 test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
355
356 len += test[i];
357 }
358
359 if (hinit->hash == NULL) {
360 hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
361 + size * sizeof(ngx_hash_elt_t *));
362 if (hinit->hash == NULL) {
363 ngx_free(test);
364 return NGX_ERROR;
365 }
366
367 buckets = (ngx_hash_elt_t **)
368 ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
369
370 } else {
371 buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
372 if (buckets == NULL) {
373 ngx_free(test);
374 return NGX_ERROR;
375 }
376 }
377
378 elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
379 if (elts == NULL) {
380 ngx_free(test);
381 return NGX_ERROR;
382 }
383
384 elts = ngx_align_ptr(elts, ngx_cacheline_size);
385
386 for (i = 0; i < size; i++) {
387 if (test[i] == sizeof(void *)) {
388 continue;
389 }
390
391 buckets[i] = (ngx_hash_elt_t *) elts;
392 elts += test[i];
393 }
394
395 for (i = 0; i < size; i++) {
396 test[i] = 0;
397 }
398
399 for (n = 0; n < nelts; n++) {
400 if (names[n].key.data == NULL) {
401 continue;
402 }
403
404 key = names[n].key_hash % size;
405 elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
406
407 elt->value = names[n].value;
408 elt->len = (u_short) names[n].key.len;
409
410 ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
411
412 test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
413 }
414
415 for (i = 0; i < size; i++) {
416 if (buckets[i] == NULL) {
417 continue;
418 }
419
420 elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
421
422 elt->value = NULL;
423 }
424
425 ngx_free(test);
426
427 hinit->hash->buckets = buckets;
428 hinit->hash->size = size;
429
430 #if 0
431
432 for (i = 0; i < size; i++) {
433 ngx_str_t val;
434 ngx_uint_t key;
435
436 elt = buckets[i];
437
438 if (elt == NULL) {
439 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
440 "%ui: NULL", i);
441 continue;
442 }
443
444 while (elt->value) {
445 val.len = elt->len;
446 val.data = &elt->name[0];
447
448 key = hinit->key(val.data, val.len);
449
450 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
451 "%ui: %p \"%V\" %ui", i, elt, &val, key);
452
453 elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
454 sizeof(void *));
455 }
456 }
457
458 #endif
459
460 return NGX_OK;
461 }
462
463
464 ngx_int_t
ngx_hash_wildcard_init(ngx_hash_init_t * hinit,ngx_hash_key_t * names,ngx_uint_t nelts)465 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
466 ngx_uint_t nelts)
467 {
468 size_t len, dot_len;
469 ngx_uint_t i, n, dot;
470 ngx_array_t curr_names, next_names;
471 ngx_hash_key_t *name, *next_name;
472 ngx_hash_init_t h;
473 ngx_hash_wildcard_t *wdc;
474
475 if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
476 sizeof(ngx_hash_key_t))
477 != NGX_OK)
478 {
479 return NGX_ERROR;
480 }
481
482 if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
483 sizeof(ngx_hash_key_t))
484 != NGX_OK)
485 {
486 return NGX_ERROR;
487 }
488
489 for (n = 0; n < nelts; n = i) {
490
491 #if 0
492 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
493 "wc0: \"%V\"", &names[n].key);
494 #endif
495
496 dot = 0;
497
498 for (len = 0; len < names[n].key.len; len++) {
499 if (names[n].key.data[len] == '.') {
500 dot = 1;
501 break;
502 }
503 }
504
505 name = ngx_array_push(&curr_names);
506 if (name == NULL) {
507 return NGX_ERROR;
508 }
509
510 name->key.len = len;
511 name->key.data = names[n].key.data;
512 name->key_hash = hinit->key(name->key.data, name->key.len);
513 name->value = names[n].value;
514
515 #if 0
516 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
517 "wc1: \"%V\" %ui", &name->key, dot);
518 #endif
519
520 dot_len = len + 1;
521
522 if (dot) {
523 len++;
524 }
525
526 next_names.nelts = 0;
527
528 if (names[n].key.len != len) {
529 next_name = ngx_array_push(&next_names);
530 if (next_name == NULL) {
531 return NGX_ERROR;
532 }
533
534 next_name->key.len = names[n].key.len - len;
535 next_name->key.data = names[n].key.data + len;
536 next_name->key_hash = 0;
537 next_name->value = names[n].value;
538
539 #if 0
540 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
541 "wc2: \"%V\"", &next_name->key);
542 #endif
543 }
544
545 for (i = n + 1; i < nelts; i++) {
546 if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
547 break;
548 }
549
550 if (!dot
551 && names[i].key.len > len
552 && names[i].key.data[len] != '.')
553 {
554 break;
555 }
556
557 next_name = ngx_array_push(&next_names);
558 if (next_name == NULL) {
559 return NGX_ERROR;
560 }
561
562 next_name->key.len = names[i].key.len - dot_len;
563 next_name->key.data = names[i].key.data + dot_len;
564 next_name->key_hash = 0;
565 next_name->value = names[i].value;
566
567 #if 0
568 ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
569 "wc3: \"%V\"", &next_name->key);
570 #endif
571 }
572
573 if (next_names.nelts) {
574
575 h = *hinit;
576 h.hash = NULL;
577
578 if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
579 next_names.nelts)
580 != NGX_OK)
581 {
582 return NGX_ERROR;
583 }
584
585 wdc = (ngx_hash_wildcard_t *) h.hash;
586
587 if (names[n].key.len == len) {
588 wdc->value = names[n].value;
589 }
590
591 name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
592
593 } else if (dot) {
594 name->value = (void *) ((uintptr_t) name->value | 1);
595 }
596 }
597
598 if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
599 curr_names.nelts)
600 != NGX_OK)
601 {
602 return NGX_ERROR;
603 }
604
605 return NGX_OK;
606 }
607
608
609 ngx_uint_t
ngx_hash_key(u_char * data,size_t len)610 ngx_hash_key(u_char *data, size_t len)
611 {
612 ngx_uint_t i, key;
613
614 key = 0;
615
616 for (i = 0; i < len; i++) {
617 key = ngx_hash(key, data[i]);
618 }
619
620 return key;
621 }
622
623
624 ngx_uint_t
ngx_hash_key_lc(u_char * data,size_t len)625 ngx_hash_key_lc(u_char *data, size_t len)
626 {
627 ngx_uint_t i, key;
628
629 key = 0;
630
631 for (i = 0; i < len; i++) {
632 key = ngx_hash(key, ngx_tolower(data[i]));
633 }
634
635 return key;
636 }
637
638
639 ngx_uint_t
ngx_hash_strlow(u_char * dst,u_char * src,size_t n)640 ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
641 {
642 ngx_uint_t key;
643
644 key = 0;
645
646 while (n--) {
647 *dst = ngx_tolower(*src);
648 key = ngx_hash(key, *dst);
649 dst++;
650 src++;
651 }
652
653 return key;
654 }
655
656
657 ngx_int_t
ngx_hash_keys_array_init(ngx_hash_keys_arrays_t * ha,ngx_uint_t type)658 ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
659 {
660 ngx_uint_t asize;
661
662 if (type == NGX_HASH_SMALL) {
663 asize = 4;
664 ha->hsize = 107;
665
666 } else {
667 asize = NGX_HASH_LARGE_ASIZE;
668 ha->hsize = NGX_HASH_LARGE_HSIZE;
669 }
670
671 if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
672 != NGX_OK)
673 {
674 return NGX_ERROR;
675 }
676
677 if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
678 sizeof(ngx_hash_key_t))
679 != NGX_OK)
680 {
681 return NGX_ERROR;
682 }
683
684 if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
685 sizeof(ngx_hash_key_t))
686 != NGX_OK)
687 {
688 return NGX_ERROR;
689 }
690
691 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
692 if (ha->keys_hash == NULL) {
693 return NGX_ERROR;
694 }
695
696 ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
697 sizeof(ngx_array_t) * ha->hsize);
698 if (ha->dns_wc_head_hash == NULL) {
699 return NGX_ERROR;
700 }
701
702 ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
703 sizeof(ngx_array_t) * ha->hsize);
704 if (ha->dns_wc_tail_hash == NULL) {
705 return NGX_ERROR;
706 }
707
708 return NGX_OK;
709 }
710
711
712 ngx_int_t
ngx_hash_add_key(ngx_hash_keys_arrays_t * ha,ngx_str_t * key,void * value,ngx_uint_t flags)713 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
714 ngx_uint_t flags)
715 {
716 size_t len;
717 u_char *p;
718 ngx_str_t *name;
719 ngx_uint_t i, k, n, skip, last;
720 ngx_array_t *keys, *hwc;
721 ngx_hash_key_t *hk;
722
723 last = key->len;
724
725 if (flags & NGX_HASH_WILDCARD_KEY) {
726
727 /*
728 * supported wildcards:
729 * "*.example.com", ".example.com", and "www.example.*"
730 */
731
732 n = 0;
733
734 for (i = 0; i < key->len; i++) {
735
736 if (key->data[i] == '*') {
737 if (++n > 1) {
738 return NGX_DECLINED;
739 }
740 }
741
742 if (key->data[i] == '.' && key->data[i + 1] == '.') {
743 return NGX_DECLINED;
744 }
745
746 if (key->data[i] == '\0') {
747 return NGX_DECLINED;
748 }
749 }
750
751 if (key->len > 1 && key->data[0] == '.') {
752 skip = 1;
753 goto wildcard;
754 }
755
756 if (key->len > 2) {
757
758 if (key->data[0] == '*' && key->data[1] == '.') {
759 skip = 2;
760 goto wildcard;
761 }
762
763 if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
764 skip = 0;
765 last -= 2;
766 goto wildcard;
767 }
768 }
769
770 if (n) {
771 return NGX_DECLINED;
772 }
773 }
774
775 /* exact hash */
776
777 k = 0;
778
779 for (i = 0; i < last; i++) {
780 if (!(flags & NGX_HASH_READONLY_KEY)) {
781 key->data[i] = ngx_tolower(key->data[i]);
782 }
783 k = ngx_hash(k, key->data[i]);
784 }
785
786 k %= ha->hsize;
787
788 /* check conflicts in exact hash */
789
790 name = ha->keys_hash[k].elts;
791
792 if (name) {
793 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
794 if (last != name[i].len) {
795 continue;
796 }
797
798 if (ngx_strncmp(key->data, name[i].data, last) == 0) {
799 return NGX_BUSY;
800 }
801 }
802
803 } else {
804 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
805 sizeof(ngx_str_t))
806 != NGX_OK)
807 {
808 return NGX_ERROR;
809 }
810 }
811
812 name = ngx_array_push(&ha->keys_hash[k]);
813 if (name == NULL) {
814 return NGX_ERROR;
815 }
816
817 *name = *key;
818
819 hk = ngx_array_push(&ha->keys);
820 if (hk == NULL) {
821 return NGX_ERROR;
822 }
823
824 hk->key = *key;
825 hk->key_hash = ngx_hash_key(key->data, last);
826 hk->value = value;
827
828 return NGX_OK;
829
830
831 wildcard:
832
833 /* wildcard hash */
834
835 k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);
836
837 k %= ha->hsize;
838
839 if (skip == 1) {
840
841 /* check conflicts in exact hash for ".example.com" */
842
843 name = ha->keys_hash[k].elts;
844
845 if (name) {
846 len = last - skip;
847
848 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
849 if (len != name[i].len) {
850 continue;
851 }
852
853 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
854 return NGX_BUSY;
855 }
856 }
857
858 } else {
859 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
860 sizeof(ngx_str_t))
861 != NGX_OK)
862 {
863 return NGX_ERROR;
864 }
865 }
866
867 name = ngx_array_push(&ha->keys_hash[k]);
868 if (name == NULL) {
869 return NGX_ERROR;
870 }
871
872 name->len = last - 1;
873 name->data = ngx_pnalloc(ha->temp_pool, name->len);
874 if (name->data == NULL) {
875 return NGX_ERROR;
876 }
877
878 ngx_memcpy(name->data, &key->data[1], name->len);
879 }
880
881
882 if (skip) {
883
884 /*
885 * convert "*.example.com" to "com.example.\0"
886 * and ".example.com" to "com.example\0"
887 */
888
889 p = ngx_pnalloc(ha->temp_pool, last);
890 if (p == NULL) {
891 return NGX_ERROR;
892 }
893
894 len = 0;
895 n = 0;
896
897 for (i = last - 1; i; i--) {
898 if (key->data[i] == '.') {
899 ngx_memcpy(&p[n], &key->data[i + 1], len);
900 n += len;
901 p[n++] = '.';
902 len = 0;
903 continue;
904 }
905
906 len++;
907 }
908
909 if (len) {
910 ngx_memcpy(&p[n], &key->data[1], len);
911 n += len;
912 }
913
914 p[n] = '\0';
915
916 hwc = &ha->dns_wc_head;
917 keys = &ha->dns_wc_head_hash[k];
918
919 } else {
920
921 /* convert "www.example.*" to "www.example\0" */
922
923 last++;
924
925 p = ngx_pnalloc(ha->temp_pool, last);
926 if (p == NULL) {
927 return NGX_ERROR;
928 }
929
930 ngx_cpystrn(p, key->data, last);
931
932 hwc = &ha->dns_wc_tail;
933 keys = &ha->dns_wc_tail_hash[k];
934 }
935
936
937 /* check conflicts in wildcard hash */
938
939 name = keys->elts;
940
941 if (name) {
942 len = last - skip;
943
944 for (i = 0; i < keys->nelts; i++) {
945 if (len != name[i].len) {
946 continue;
947 }
948
949 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
950 return NGX_BUSY;
951 }
952 }
953
954 } else {
955 if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
956 {
957 return NGX_ERROR;
958 }
959 }
960
961 name = ngx_array_push(keys);
962 if (name == NULL) {
963 return NGX_ERROR;
964 }
965
966 name->len = last - skip;
967 name->data = ngx_pnalloc(ha->temp_pool, name->len);
968 if (name->data == NULL) {
969 return NGX_ERROR;
970 }
971
972 ngx_memcpy(name->data, key->data + skip, name->len);
973
974
975 /* add to wildcard hash */
976
977 hk = ngx_array_push(hwc);
978 if (hk == NULL) {
979 return NGX_ERROR;
980 }
981
982 hk->key.len = last - 1;
983 hk->key.data = p;
984 hk->key_hash = 0;
985 hk->value = value;
986
987 return NGX_OK;
988 }
989