nginx/src/core/ngx_hash.c

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