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