release/src/router/nginx/src/core/ngx_hash.c

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