ngx_hash.c revision e18a033b
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
12void *
13ngx_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
52void *
53ngx_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
146void *
147ngx_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
210void *
211ngx_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
251ngx_int_t
252ngx_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
332found:
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
464ngx_int_t
465ngx_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
609ngx_uint_t
610ngx_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
624ngx_uint_t
625ngx_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
639ngx_uint_t
640ngx_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
657ngx_int_t
658ngx_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
712ngx_int_t
713ngx_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
831wildcard:
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