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