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