Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.15.11 ]​[ nginx-1.14.2 ]​

0001 
0002 /*
0003  * Copyright (C) Igor Sysoev
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 
0011 
0012 void *
0013 ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
0014 {
0015     ngx_uint_t       i;
0016     ngx_hash_elt_t  *elt;
0017 
0018 #if 0
0019     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
0020 #endif
0021 
0022     elt = hash->buckets[key % hash->size];
0023 
0024     if (elt == NULL) {
0025         return NULL;
0026     }
0027 
0028     while (elt->value) {
0029         if (len != (size_t) elt->len) {
0030             goto next;
0031         }
0032 
0033         for (i = 0; i < len; i++) {
0034             if (name[i] != elt->name[i]) {
0035                 goto next;
0036             }
0037         }
0038 
0039         return elt->value;
0040 
0041     next:
0042 
0043         elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
0044                                                sizeof(void *));
0045         continue;
0046     }
0047 
0048     return NULL;
0049 }
0050 
0051 
0052 void *
0053 ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
0054 {
0055     void        *value;
0056     ngx_uint_t   i, n, key;
0057 
0058 #if 0
0059     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name);
0060 #endif
0061 
0062     n = len;
0063 
0064     while (n) {
0065         if (name[n - 1] == '.') {
0066             break;
0067         }
0068 
0069         n--;
0070     }
0071 
0072     key = 0;
0073 
0074     for (i = n; i < len; i++) {
0075         key = ngx_hash(key, name[i]);
0076     }
0077 
0078 #if 0
0079     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
0080 #endif
0081 
0082     value = ngx_hash_find(&hwc->hash, key, &name[n], len - n);
0083 
0084 #if 0
0085     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
0086 #endif
0087 
0088     if (value) {
0089 
0090         /*
0091          * the 2 low bits of value have the special meaning:
0092          *     00 - value is data pointer for both "example.com"
0093          *          and "*.example.com";
0094          *     01 - value is data pointer for "*.example.com" only;
0095          *     10 - value is pointer to wildcard hash allowing
0096          *          both "example.com" and "*.example.com";
0097          *     11 - value is pointer to wildcard hash allowing
0098          *          "*.example.com" only.
0099          */
0100 
0101         if ((uintptr_t) value & 2) {
0102 
0103             if (n == 0) {
0104 
0105                 /* "example.com" */
0106 
0107                 if ((uintptr_t) value & 1) {
0108                     return NULL;
0109                 }
0110 
0111                 hwc = (ngx_hash_wildcard_t *)
0112                                           ((uintptr_t) value & (uintptr_t) ~3);
0113                 return hwc->value;
0114             }
0115 
0116             hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
0117 
0118             value = ngx_hash_find_wc_head(hwc, name, n - 1);
0119 
0120             if (value) {
0121                 return value;
0122             }
0123 
0124             return hwc->value;
0125         }
0126 
0127         if ((uintptr_t) value & 1) {
0128 
0129             if (n == 0) {
0130 
0131                 /* "example.com" */
0132 
0133                 return NULL;
0134             }
0135 
0136             return (void *) ((uintptr_t) value & (uintptr_t) ~3);
0137         }
0138 
0139         return value;
0140     }
0141 
0142     return hwc->value;
0143 }
0144 
0145 
0146 void *
0147 ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
0148 {
0149     void        *value;
0150     ngx_uint_t   i, key;
0151 
0152 #if 0
0153     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name);
0154 #endif
0155 
0156     key = 0;
0157 
0158     for (i = 0; i < len; i++) {
0159         if (name[i] == '.') {
0160             break;
0161         }
0162 
0163         key = ngx_hash(key, name[i]);
0164     }
0165 
0166     if (i == len) {
0167         return NULL;
0168     }
0169 
0170 #if 0
0171     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
0172 #endif
0173 
0174     value = ngx_hash_find(&hwc->hash, key, name, i);
0175 
0176 #if 0
0177     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
0178 #endif
0179 
0180     if (value) {
0181 
0182         /*
0183          * the 2 low bits of value have the special meaning:
0184          *     00 - value is data pointer;
0185          *     11 - value is pointer to wildcard hash allowing "example.*".
0186          */
0187 
0188         if ((uintptr_t) value & 2) {
0189 
0190             i++;
0191 
0192             hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
0193 
0194             value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);
0195 
0196             if (value) {
0197                 return value;
0198             }
0199 
0200             return hwc->value;
0201         }
0202 
0203         return value;
0204     }
0205 
0206     return hwc->value;
0207 }
0208 
0209 
0210 void *
0211 ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name,
0212     size_t len)
0213 {
0214     void  *value;
0215 
0216     if (hash->hash.buckets) {
0217         value = ngx_hash_find(&hash->hash, key, name, len);
0218 
0219         if (value) {
0220             return value;
0221         }
0222     }
0223 
0224     if (len == 0) {
0225         return NULL;
0226     }
0227 
0228     if (hash->wc_head && hash->wc_head->hash.buckets) {
0229         value = ngx_hash_find_wc_head(hash->wc_head, name, len);
0230 
0231         if (value) {
0232             return value;
0233         }
0234     }
0235 
0236     if (hash->wc_tail && hash->wc_tail->hash.buckets) {
0237         value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);
0238 
0239         if (value) {
0240             return value;
0241         }
0242     }
0243 
0244     return NULL;
0245 }
0246 
0247 
0248 #define NGX_HASH_ELT_SIZE(name)                                               \
0249     (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
0250 
0251 ngx_int_t
0252 ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
0253 {
0254     u_char          *elts;
0255     size_t           len;
0256     u_short         *test;
0257     ngx_uint_t       i, n, key, size, start, bucket_size;
0258     ngx_hash_elt_t  *elt, **buckets;
0259 
0260     if (hinit->max_size == 0) {
0261         ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
0262                       "could not build %s, you should "
0263                       "increase %s_max_size: %i",
0264                       hinit->name, hinit->name, hinit->max_size);
0265         return NGX_ERROR;
0266     }
0267 
0268     for (n = 0; n < nelts; n++) {
0269         if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
0270         {
0271             ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
0272                           "could not build %s, you should "
0273                           "increase %s_bucket_size: %i",
0274                           hinit->name, hinit->name, hinit->bucket_size);
0275             return NGX_ERROR;
0276         }
0277     }
0278 
0279     test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
0280     if (test == NULL) {
0281         return NGX_ERROR;
0282     }
0283 
0284     bucket_size = hinit->bucket_size - sizeof(void *);
0285 
0286     start = nelts / (bucket_size / (2 * sizeof(void *)));
0287     start = start ? start : 1;
0288 
0289     if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
0290         start = hinit->max_size - 1000;
0291     }
0292 
0293     for (size = start; size <= hinit->max_size; size++) {
0294 
0295         ngx_memzero(test, size * sizeof(u_short));
0296 
0297         for (n = 0; n < nelts; n++) {
0298             if (names[n].key.data == NULL) {
0299                 continue;
0300             }
0301 
0302             key = names[n].key_hash % size;
0303             test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
0304 
0305 #if 0
0306             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0307                           "%ui: %ui %ui \"%V\"",
0308                           size, key, test[key], &names[n].key);
0309 #endif
0310 
0311             if (test[key] > (u_short) bucket_size) {
0312                 goto next;
0313             }
0314         }
0315 
0316         goto found;
0317 
0318     next:
0319 
0320         continue;
0321     }
0322 
0323     size = hinit->max_size;
0324 
0325     ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
0326                   "could not build optimal %s, you should increase "
0327                   "either %s_max_size: %i or %s_bucket_size: %i; "
0328                   "ignoring %s_bucket_size",
0329                   hinit->name, hinit->name, hinit->max_size,
0330                   hinit->name, hinit->bucket_size, hinit->name);
0331 
0332 found:
0333 
0334     for (i = 0; i < size; i++) {
0335         test[i] = sizeof(void *);
0336     }
0337 
0338     for (n = 0; n < nelts; n++) {
0339         if (names[n].key.data == NULL) {
0340             continue;
0341         }
0342 
0343         key = names[n].key_hash % size;
0344         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
0345     }
0346 
0347     len = 0;
0348 
0349     for (i = 0; i < size; i++) {
0350         if (test[i] == sizeof(void *)) {
0351             continue;
0352         }
0353 
0354         test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
0355 
0356         len += test[i];
0357     }
0358 
0359     if (hinit->hash == NULL) {
0360         hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
0361                                              + size * sizeof(ngx_hash_elt_t *));
0362         if (hinit->hash == NULL) {
0363             ngx_free(test);
0364             return NGX_ERROR;
0365         }
0366 
0367         buckets = (ngx_hash_elt_t **)
0368                       ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
0369 
0370     } else {
0371         buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
0372         if (buckets == NULL) {
0373             ngx_free(test);
0374             return NGX_ERROR;
0375         }
0376     }
0377 
0378     elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
0379     if (elts == NULL) {
0380         ngx_free(test);
0381         return NGX_ERROR;
0382     }
0383 
0384     elts = ngx_align_ptr(elts, ngx_cacheline_size);
0385 
0386     for (i = 0; i < size; i++) {
0387         if (test[i] == sizeof(void *)) {
0388             continue;
0389         }
0390 
0391         buckets[i] = (ngx_hash_elt_t *) elts;
0392         elts += test[i];
0393     }
0394 
0395     for (i = 0; i < size; i++) {
0396         test[i] = 0;
0397     }
0398 
0399     for (n = 0; n < nelts; n++) {
0400         if (names[n].key.data == NULL) {
0401             continue;
0402         }
0403 
0404         key = names[n].key_hash % size;
0405         elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
0406 
0407         elt->value = names[n].value;
0408         elt->len = (u_short) names[n].key.len;
0409 
0410         ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
0411 
0412         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
0413     }
0414 
0415     for (i = 0; i < size; i++) {
0416         if (buckets[i] == NULL) {
0417             continue;
0418         }
0419 
0420         elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
0421 
0422         elt->value = NULL;
0423     }
0424 
0425     ngx_free(test);
0426 
0427     hinit->hash->buckets = buckets;
0428     hinit->hash->size = size;
0429 
0430 #if 0
0431 
0432     for (i = 0; i < size; i++) {
0433         ngx_str_t   val;
0434         ngx_uint_t  key;
0435 
0436         elt = buckets[i];
0437 
0438         if (elt == NULL) {
0439             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0440                           "%ui: NULL", i);
0441             continue;
0442         }
0443 
0444         while (elt->value) {
0445             val.len = elt->len;
0446             val.data = &elt->name[0];
0447 
0448             key = hinit->key(val.data, val.len);
0449 
0450             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0451                           "%ui: %p \"%V\" %ui", i, elt, &val, key);
0452 
0453             elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
0454                                                    sizeof(void *));
0455         }
0456     }
0457 
0458 #endif
0459 
0460     return NGX_OK;
0461 }
0462 
0463 
0464 ngx_int_t
0465 ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
0466     ngx_uint_t nelts)
0467 {
0468     size_t                len, dot_len;
0469     ngx_uint_t            i, n, dot;
0470     ngx_array_t           curr_names, next_names;
0471     ngx_hash_key_t       *name, *next_name;
0472     ngx_hash_init_t       h;
0473     ngx_hash_wildcard_t  *wdc;
0474 
0475     if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
0476                        sizeof(ngx_hash_key_t))
0477         != NGX_OK)
0478     {
0479         return NGX_ERROR;
0480     }
0481 
0482     if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
0483                        sizeof(ngx_hash_key_t))
0484         != NGX_OK)
0485     {
0486         return NGX_ERROR;
0487     }
0488 
0489     for (n = 0; n < nelts; n = i) {
0490 
0491 #if 0
0492         ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0493                       "wc0: \"%V\"", &names[n].key);
0494 #endif
0495 
0496         dot = 0;
0497 
0498         for (len = 0; len < names[n].key.len; len++) {
0499             if (names[n].key.data[len] == '.') {
0500                 dot = 1;
0501                 break;
0502             }
0503         }
0504 
0505         name = ngx_array_push(&curr_names);
0506         if (name == NULL) {
0507             return NGX_ERROR;
0508         }
0509 
0510         name->key.len = len;
0511         name->key.data = names[n].key.data;
0512         name->key_hash = hinit->key(name->key.data, name->key.len);
0513         name->value = names[n].value;
0514 
0515 #if 0
0516         ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0517                       "wc1: \"%V\" %ui", &name->key, dot);
0518 #endif
0519 
0520         dot_len = len + 1;
0521 
0522         if (dot) {
0523             len++;
0524         }
0525 
0526         next_names.nelts = 0;
0527 
0528         if (names[n].key.len != len) {
0529             next_name = ngx_array_push(&next_names);
0530             if (next_name == NULL) {
0531                 return NGX_ERROR;
0532             }
0533 
0534             next_name->key.len = names[n].key.len - len;
0535             next_name->key.data = names[n].key.data + len;
0536             next_name->key_hash = 0;
0537             next_name->value = names[n].value;
0538 
0539 #if 0
0540             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0541                           "wc2: \"%V\"", &next_name->key);
0542 #endif
0543         }
0544 
0545         for (i = n + 1; i < nelts; i++) {
0546             if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
0547                 break;
0548             }
0549 
0550             if (!dot
0551                 && names[i].key.len > len
0552                 && names[i].key.data[len] != '.')
0553             {
0554                 break;
0555             }
0556 
0557             next_name = ngx_array_push(&next_names);
0558             if (next_name == NULL) {
0559                 return NGX_ERROR;
0560             }
0561 
0562             next_name->key.len = names[i].key.len - dot_len;
0563             next_name->key.data = names[i].key.data + dot_len;
0564             next_name->key_hash = 0;
0565             next_name->value = names[i].value;
0566 
0567 #if 0
0568             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
0569                           "wc3: \"%V\"", &next_name->key);
0570 #endif
0571         }
0572 
0573         if (next_names.nelts) {
0574 
0575             h = *hinit;
0576             h.hash = NULL;
0577 
0578             if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
0579                                        next_names.nelts)
0580                 != NGX_OK)
0581             {
0582                 return NGX_ERROR;
0583             }
0584 
0585             wdc = (ngx_hash_wildcard_t *) h.hash;
0586 
0587             if (names[n].key.len == len) {
0588                 wdc->value = names[n].value;
0589             }
0590 
0591             name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
0592 
0593         } else if (dot) {
0594             name->value = (void *) ((uintptr_t) name->value | 1);
0595         }
0596     }
0597 
0598     if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
0599                       curr_names.nelts)
0600         != NGX_OK)
0601     {
0602         return NGX_ERROR;
0603     }
0604 
0605     return NGX_OK;
0606 }
0607 
0608 
0609 ngx_uint_t
0610 ngx_hash_key(u_char *data, size_t len)
0611 {
0612     ngx_uint_t  i, key;
0613 
0614     key = 0;
0615 
0616     for (i = 0; i < len; i++) {
0617         key = ngx_hash(key, data[i]);
0618     }
0619 
0620     return key;
0621 }
0622 
0623 
0624 ngx_uint_t
0625 ngx_hash_key_lc(u_char *data, size_t len)
0626 {
0627     ngx_uint_t  i, key;
0628 
0629     key = 0;
0630 
0631     for (i = 0; i < len; i++) {
0632         key = ngx_hash(key, ngx_tolower(data[i]));
0633     }
0634 
0635     return key;
0636 }
0637 
0638 
0639 ngx_uint_t
0640 ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
0641 {
0642     ngx_uint_t  key;
0643 
0644     key = 0;
0645 
0646     while (n--) {
0647         *dst = ngx_tolower(*src);
0648         key = ngx_hash(key, *dst);
0649         dst++;
0650         src++;
0651     }
0652 
0653     return key;
0654 }
0655 
0656 
0657 ngx_int_t
0658 ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
0659 {
0660     ngx_uint_t  asize;
0661 
0662     if (type == NGX_HASH_SMALL) {
0663         asize = 4;
0664         ha->hsize = 107;
0665 
0666     } else {
0667         asize = NGX_HASH_LARGE_ASIZE;
0668         ha->hsize = NGX_HASH_LARGE_HSIZE;
0669     }
0670 
0671     if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
0672         != NGX_OK)
0673     {
0674         return NGX_ERROR;
0675     }
0676 
0677     if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
0678                        sizeof(ngx_hash_key_t))
0679         != NGX_OK)
0680     {
0681         return NGX_ERROR;
0682     }
0683 
0684     if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
0685                        sizeof(ngx_hash_key_t))
0686         != NGX_OK)
0687     {
0688         return NGX_ERROR;
0689     }
0690 
0691     ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
0692     if (ha->keys_hash == NULL) {
0693         return NGX_ERROR;
0694     }
0695 
0696     ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
0697                                        sizeof(ngx_array_t) * ha->hsize);
0698     if (ha->dns_wc_head_hash == NULL) {
0699         return NGX_ERROR;
0700     }
0701 
0702     ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
0703                                        sizeof(ngx_array_t) * ha->hsize);
0704     if (ha->dns_wc_tail_hash == NULL) {
0705         return NGX_ERROR;
0706     }
0707 
0708     return NGX_OK;
0709 }
0710 
0711 
0712 ngx_int_t
0713 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
0714     ngx_uint_t flags)
0715 {
0716     size_t           len;
0717     u_char          *p;
0718     ngx_str_t       *name;
0719     ngx_uint_t       i, k, n, skip, last;
0720     ngx_array_t     *keys, *hwc;
0721     ngx_hash_key_t  *hk;
0722 
0723     last = key->len;
0724 
0725     if (flags & NGX_HASH_WILDCARD_KEY) {
0726 
0727         /*
0728          * supported wildcards:
0729          *     "*.example.com", ".example.com", and "www.example.*"
0730          */
0731 
0732         n = 0;
0733 
0734         for (i = 0; i < key->len; i++) {
0735 
0736             if (key->data[i] == '*') {
0737                 if (++n > 1) {
0738                     return NGX_DECLINED;
0739                 }
0740             }
0741 
0742             if (key->data[i] == '.' && key->data[i + 1] == '.') {
0743                 return NGX_DECLINED;
0744             }
0745 
0746             if (key->data[i] == '\0') {
0747                 return NGX_DECLINED;
0748             }
0749         }
0750 
0751         if (key->len > 1 && key->data[0] == '.') {
0752             skip = 1;
0753             goto wildcard;
0754         }
0755 
0756         if (key->len > 2) {
0757 
0758             if (key->data[0] == '*' && key->data[1] == '.') {
0759                 skip = 2;
0760                 goto wildcard;
0761             }
0762 
0763             if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
0764                 skip = 0;
0765                 last -= 2;
0766                 goto wildcard;
0767             }
0768         }
0769 
0770         if (n) {
0771             return NGX_DECLINED;
0772         }
0773     }
0774 
0775     /* exact hash */
0776 
0777     k = 0;
0778 
0779     for (i = 0; i < last; i++) {
0780         if (!(flags & NGX_HASH_READONLY_KEY)) {
0781             key->data[i] = ngx_tolower(key->data[i]);
0782         }
0783         k = ngx_hash(k, key->data[i]);
0784     }
0785 
0786     k %= ha->hsize;
0787 
0788     /* check conflicts in exact hash */
0789 
0790     name = ha->keys_hash[k].elts;
0791 
0792     if (name) {
0793         for (i = 0; i < ha->keys_hash[k].nelts; i++) {
0794             if (last != name[i].len) {
0795                 continue;
0796             }
0797 
0798             if (ngx_strncmp(key->data, name[i].data, last) == 0) {
0799                 return NGX_BUSY;
0800             }
0801         }
0802 
0803     } else {
0804         if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
0805                            sizeof(ngx_str_t))
0806             != NGX_OK)
0807         {
0808             return NGX_ERROR;
0809         }
0810     }
0811 
0812     name = ngx_array_push(&ha->keys_hash[k]);
0813     if (name == NULL) {
0814         return NGX_ERROR;
0815     }
0816 
0817     *name = *key;
0818 
0819     hk = ngx_array_push(&ha->keys);
0820     if (hk == NULL) {
0821         return NGX_ERROR;
0822     }
0823 
0824     hk->key = *key;
0825     hk->key_hash = ngx_hash_key(key->data, last);
0826     hk->value = value;
0827 
0828     return NGX_OK;
0829 
0830 
0831 wildcard:
0832 
0833     /* wildcard hash */
0834 
0835     k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);
0836 
0837     k %= ha->hsize;
0838 
0839     if (skip == 1) {
0840 
0841         /* check conflicts in exact hash for ".example.com" */
0842 
0843         name = ha->keys_hash[k].elts;
0844 
0845         if (name) {
0846             len = last - skip;
0847 
0848             for (i = 0; i < ha->keys_hash[k].nelts; i++) {
0849                 if (len != name[i].len) {
0850                     continue;
0851                 }
0852 
0853                 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
0854                     return NGX_BUSY;
0855                 }
0856             }
0857 
0858         } else {
0859             if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
0860                                sizeof(ngx_str_t))
0861                 != NGX_OK)
0862             {
0863                 return NGX_ERROR;
0864             }
0865         }
0866 
0867         name = ngx_array_push(&ha->keys_hash[k]);
0868         if (name == NULL) {
0869             return NGX_ERROR;
0870         }
0871 
0872         name->len = last - 1;
0873         name->data = ngx_pnalloc(ha->temp_pool, name->len);
0874         if (name->data == NULL) {
0875             return NGX_ERROR;
0876         }
0877 
0878         ngx_memcpy(name->data, &key->data[1], name->len);
0879     }
0880 
0881 
0882     if (skip) {
0883 
0884         /*
0885          * convert "*.example.com" to "com.example.\0"
0886          *      and ".example.com" to "com.example\0"
0887          */
0888 
0889         p = ngx_pnalloc(ha->temp_pool, last);
0890         if (p == NULL) {
0891             return NGX_ERROR;
0892         }
0893 
0894         len = 0;
0895         n = 0;
0896 
0897         for (i = last - 1; i; i--) {
0898             if (key->data[i] == '.') {
0899                 ngx_memcpy(&p[n], &key->data[i + 1], len);
0900                 n += len;
0901                 p[n++] = '.';
0902                 len = 0;
0903                 continue;
0904             }
0905 
0906             len++;
0907         }
0908 
0909         if (len) {
0910             ngx_memcpy(&p[n], &key->data[1], len);
0911             n += len;
0912         }
0913 
0914         p[n] = '\0';
0915 
0916         hwc = &ha->dns_wc_head;
0917         keys = &ha->dns_wc_head_hash[k];
0918 
0919     } else {
0920 
0921         /* convert "www.example.*" to "www.example\0" */
0922 
0923         last++;
0924 
0925         p = ngx_pnalloc(ha->temp_pool, last);
0926         if (p == NULL) {
0927             return NGX_ERROR;
0928         }
0929 
0930         ngx_cpystrn(p, key->data, last);
0931 
0932         hwc = &ha->dns_wc_tail;
0933         keys = &ha->dns_wc_tail_hash[k];
0934     }
0935 
0936 
0937     /* check conflicts in wildcard hash */
0938 
0939     name = keys->elts;
0940 
0941     if (name) {
0942         len = last - skip;
0943 
0944         for (i = 0; i < keys->nelts; i++) {
0945             if (len != name[i].len) {
0946                 continue;
0947             }
0948 
0949             if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
0950                 return NGX_BUSY;
0951             }
0952         }
0953 
0954     } else {
0955         if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
0956         {
0957             return NGX_ERROR;
0958         }
0959     }
0960 
0961     name = ngx_array_push(keys);
0962     if (name == NULL) {
0963         return NGX_ERROR;
0964     }
0965 
0966     name->len = last - skip;
0967     name->data = ngx_pnalloc(ha->temp_pool, name->len);
0968     if (name->data == NULL) {
0969         return NGX_ERROR;
0970     }
0971 
0972     ngx_memcpy(name->data, key->data + skip, name->len);
0973 
0974 
0975     /* add to wildcard hash */
0976 
0977     hk = ngx_array_push(hwc);
0978     if (hk == NULL) {
0979         return NGX_ERROR;
0980     }
0981 
0982     hk->key.len = last - 1;
0983     hk->key.data = p;
0984     hk->key_hash = 0;
0985     hk->value = value;
0986 
0987     return NGX_OK;
0988 }