One Level Up Top Level

src/core/ngx_hash.c - nginx-1.7.10

Functions defined

Macros defined

Source code


  2. /*
  3. * Copyright (C) Igor Sysoev
  4. * Copyright (C) Nginx, Inc.
  5. */


  8. #include <ngx_config.h>
  9. #include <ngx_core.h>


  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;

  18. #if 0
  19.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
  20. #endif

  22.     elt = hash->buckets[key % hash->size];

  24.     if (elt == NULL) {
  25.         return NULL;
  26.     }

  28.     while (elt->value) {
  29.         if (len != (size_t) elt->len) {
  30.             goto next;
  31.         }

  33.         for (i = 0; i < len; i++) {
  34.             if (name[i] != elt->name[i]) {
  35.                 goto next;
  36.             }
  37.         }

  39.         return elt->value;

  41.     next:

  43.         elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
  44.                                                sizeof(void *));
  45.         continue;
  46.     }

  48.     return NULL;
  49. }


  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;

  58. #if 0
  59.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name);
  60. #endif

  62.     n = len;

  64.     while (n) {
  65.         if (name[n - 1] == '.') {
  66.             break;
  67.         }

  69.         n--;
  70.     }

  72.     key = 0;

  74.     for (i = n; i < len; i++) {
  75.         key = ngx_hash(key, name[i]);
  76.     }

  78. #if 0
  79.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
  80. #endif

  82.     value = ngx_hash_find(&hwc->hash, key, &name[n], len - n);

  84. #if 0
  85.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
  86. #endif

  88.     if (value) {

  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.          */

  101.         if ((uintptr_t) value & 2) {

  103.             if (n == 0) {

  105.                 /* "example.com" */

  107.                 if ((uintptr_t) value & 1) {
  108.                     return NULL;
  109.                 }

  111.                 hwc = (ngx_hash_wildcard_t *)
  112.                                           ((uintptr_t) value & (uintptr_t) ~3);
  113.                 return hwc->value;
  114.             }

  116.             hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);

  118.             value = ngx_hash_find_wc_head(hwc, name, n - 1);

  120.             if (value) {
  121.                 return value;
  122.             }

  124.             return hwc->value;
  125.         }

  127.         if ((uintptr_t) value & 1) {

  129.             if (n == 0) {

  131.                 /* "example.com" */

  133.                 return NULL;
  134.             }

  136.             return (void *) ((uintptr_t) value & (uintptr_t) ~3);
  137.         }

  139.         return value;
  140.     }

  142.     return hwc->value;
  143. }


  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;

  152. #if 0
  153.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name);
  154. #endif

  156.     key = 0;

  158.     for (i = 0; i < len; i++) {
  159.         if (name[i] == '.') {
  160.             break;
  161.         }

  163.         key = ngx_hash(key, name[i]);
  164.     }

  166.     if (i == len) {
  167.         return NULL;
  168.     }

  170. #if 0
  171.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
  172. #endif

  174.     value = ngx_hash_find(&hwc->hash, key, name, i);

  176. #if 0
  177.     ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
  178. #endif

  180.     if (value) {

  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.          */

  188.         if ((uintptr_t) value & 2) {

  190.             i++;

  192.             hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);

  194.             value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);

  196.             if (value) {
  197.                 return value;
  198.             }

  200.             return hwc->value;
  201.         }

  203.         return value;
  204.     }

  206.     return hwc->value;
  207. }


  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;

  216.     if (hash->hash.buckets) {
  217.         value = ngx_hash_find(&hash->hash, key, name, len);

  219.         if (value) {
  220.             return value;
  221.         }
  222.     }

  224.     if (len == 0) {
  225.         return NULL;
  226.     }

  228.     if (hash->wc_head && hash->wc_head->hash.buckets) {
  229.         value = ngx_hash_find_wc_head(hash->wc_head, name, len);

  231.         if (value) {
  232.             return value;
  233.         }
  234.     }

  236.     if (hash->wc_tail && hash->wc_tail->hash.buckets) {
  237.         value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);

  239.         if (value) {
  240.             return value;
  241.         }
  242.     }

  244.     return NULL;
  245. }


  248. ‌#define NGX_HASH_ELT_SIZE(name)                                               \
  249.     (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))

  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;

  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.     }

  271.     test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
  272.     if (test == NULL) {
  273.         return NGX_ERROR;
  274.     }

  276.     bucket_size = hinit->bucket_size - sizeof(void *);

  278.     start = nelts / (bucket_size / (2 * sizeof(void *)));
  279.     start = start ? start : 1;

  281.     if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
  282.         start = hinit->max_size - 1000;
  283.     }

  285.     for (size = start; size <= hinit->max_size; size++) {

  287.         ngx_memzero(test, size * sizeof(u_short));

  289.         for (n = 0; n < nelts; n++) {
  290.             if (names[n].key.data == NULL) {
  291.                 continue;
  292.             }

  294.             key = names[n].key_hash % size;
  295.             test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));

  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

  303.             if (test[key] > (u_short) bucket_size) {
  304.                 goto next;
  305.             }
  306.         }

  308.         goto found;

  310.     next:

  312.         continue;
  313.     }

  315.     size--;

  317.     ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
  318.                   "could not build optimal %s, you should increase "
  319.                   "either %s_max_size: %i or %s_bucket_size: %i; "
  320.                   "ignoring %s_bucket_size",
  321.                   hinit->name, hinit->name, hinit->max_size,
  322.                   hinit->name, hinit->bucket_size, hinit->name);

  324. found:

  326.     for (i = 0; i < size; i++) {
  327.         test[i] = sizeof(void *);
  328.     }

  330.     for (n = 0; n < nelts; n++) {
  331.         if (names[n].key.data == NULL) {
  332.             continue;
  333.         }

  335.         key = names[n].key_hash % size;
  336.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
  337.     }

  339.     len = 0;

  341.     for (i = 0; i < size; i++) {
  342.         if (test[i] == sizeof(void *)) {
  343.             continue;
  344.         }

  346.         test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));

  348.         len += test[i];
  349.     }

  351.     if (hinit->hash == NULL) {
  352.         hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
  353.                                              + size * sizeof(ngx_hash_elt_t *));
  354.         if (hinit->hash == NULL) {
  355.             ngx_free(test);
  356.             return NGX_ERROR;
  357.         }

  359.         buckets = (ngx_hash_elt_t **)
  360.                       ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));

  362.     } else {
  363.         buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
  364.         if (buckets == NULL) {
  365.             ngx_free(test);
  366.             return NGX_ERROR;
  367.         }
  368.     }

  370.     elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
  371.     if (elts == NULL) {
  372.         ngx_free(test);
  373.         return NGX_ERROR;
  374.     }

  376.     elts = ngx_align_ptr(elts, ngx_cacheline_size);

  378.     for (i = 0; i < size; i++) {
  379.         if (test[i] == sizeof(void *)) {
  380.             continue;
  381.         }

  383.         buckets[i] = (ngx_hash_elt_t *) elts;
  384.         elts += test[i];

  386.     }

  388.     for (i = 0; i < size; i++) {
  389.         test[i] = 0;
  390.     }

  392.     for (n = 0; n < nelts; n++) {
  393.         if (names[n].key.data == NULL) {
  394.             continue;
  395.         }

  397.         key = names[n].key_hash % size;
  398.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);

  400.         elt->value = names[n].value;
  401.         elt->len = (u_short) names[n].key.len;

  403.         ngx_strlow(elt->name, names[n].key.data, names[n].key.len);

  405.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
  406.     }

  408.     for (i = 0; i < size; i++) {
  409.         if (buckets[i] == NULL) {
  410.             continue;
  411.         }

  413.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);

  415.         elt->value = NULL;
  416.     }

  418.     ngx_free(test);

  420.     hinit->hash->buckets = buckets;
  421.     hinit->hash->size = size;

  423. #if 0

  425.     for (i = 0; i < size; i++) {
  426.         ngx_str_t   val;
  427.         ngx_uint_t  key;

  429.         elt = buckets[i];

  431.         if (elt == NULL) {
  432.             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  433.                           "%ui: NULL", i);
  434.             continue;
  435.         }

  437.         while (elt->value) {
  438.             val.len = elt->len;
  439.             val.data = &elt->name[0];

  441.             key = hinit->key(val.data, val.len);

  443.             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  444.                           "%ui: %p \"%V\" %ui", i, elt, &val, key);

  446.             elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
  447.                                                    sizeof(void *));
  448.         }
  449.     }

  451. #endif

  453.     return NGX_OK;
  454. }


  457. ngx_int_t
  458. ‌ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
  459.     ngx_uint_t nelts)
  460. {
  461.     size_t                len, dot_len;
  462.     ngx_uint_t            i, n, dot;
  463.     ngx_array_t           curr_names, next_names;
  464.     ngx_hash_key_t       *name, *next_name;
  465.     ngx_hash_init_t       h;
  466.     ngx_hash_wildcard_t  *wdc;

  468.     if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
  469.                        sizeof(ngx_hash_key_t))
  470.         != NGX_OK)
  471.     {
  472.         return NGX_ERROR;
  473.     }

  475.     if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
  476.                        sizeof(ngx_hash_key_t))
  477.         != NGX_OK)
  478.     {
  479.         return NGX_ERROR;
  480.     }

  482.     for (n = 0; n < nelts; n = i) {

  484. #if 0
  485.         ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  486.                       "wc0: \"%V\"", &names[n].key);
  487. #endif

  489.         dot = 0;

  491.         for (len = 0; len < names[n].key.len; len++) {
  492.             if (names[n].key.data[len] == '.') {
  493.                 dot = 1;
  494.                 break;
  495.             }
  496.         }

  498.         name = ngx_array_push(&curr_names);
  499.         if (name == NULL) {
  500.             return NGX_ERROR;
  501.         }

  503.         name->key.len = len;
  504.         name->key.data = names[n].key.data;
  505.         name->key_hash = hinit->key(name->key.data, name->key.len);
  506.         name->value = names[n].value;

  508. #if 0
  509.         ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  510.                       "wc1: \"%V\" %ui", &name->key, dot);
  511. #endif

  513.         dot_len = len + 1;

  515.         if (dot) {
  516.             len++;
  517.         }

  519.         next_names.nelts = 0;

  521.         if (names[n].key.len != len) {
  522.             next_name = ngx_array_push(&next_names);
  523.             if (next_name == NULL) {
  524.                 return NGX_ERROR;
  525.             }

  527.             next_name->key.len = names[n].key.len - len;
  528.             next_name->key.data = names[n].key.data + len;
  529.             next_name->key_hash = 0;
  530.             next_name->value = names[n].value;

  532. #if 0
  533.             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  534.                           "wc2: \"%V\"", &next_name->key);
  535. #endif
  536.         }

  538.         for (i = n + 1; i < nelts; i++) {
  539.             if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
  540.                 break;
  541.             }

  543.             if (!dot
  544.                 && names[i].key.len > len
  545.                 && names[i].key.data[len] != '.')
  546.             {
  547.                 break;
  548.             }

  550.             next_name = ngx_array_push(&next_names);
  551.             if (next_name == NULL) {
  552.                 return NGX_ERROR;
  553.             }

  555.             next_name->key.len = names[i].key.len - dot_len;
  556.             next_name->key.data = names[i].key.data + dot_len;
  557.             next_name->key_hash = 0;
  558.             next_name->value = names[i].value;

  560. #if 0
  561.             ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
  562.                           "wc3: \"%V\"", &next_name->key);
  563. #endif
  564.         }

  566.         if (next_names.nelts) {

  568.             h = *hinit;
  569.             h.hash = NULL;

  571.             if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
  572.                                        next_names.nelts)
  573.                 != NGX_OK)
  574.             {
  575.                 return NGX_ERROR;
  576.             }

  578.             wdc = (ngx_hash_wildcard_t *) h.hash;

  580.             if (names[n].key.len == len) {
  581.                 wdc->value = names[n].value;
  582.             }

  584.             name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));

  586.         } else if (dot) {
  587.             name->value = (void *) ((uintptr_t) name->value | 1);
  588.         }
  589.     }

  591.     if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
  592.                       curr_names.nelts)
  593.         != NGX_OK)
  594.     {
  595.         return NGX_ERROR;
  596.     }

  598.     return NGX_OK;
  599. }


  602. ngx_uint_t
  603. ‌ngx_hash_key(u_char *data, size_t len)
  604. {
  605.     ngx_uint_t  i, key;

  607.     key = 0;

  609.     for (i = 0; i < len; i++) {
  610.         key = ngx_hash(key, data[i]);
  611.     }

  613.     return key;
  614. }


  617. ngx_uint_t
  618. ‌ngx_hash_key_lc(u_char *data, size_t len)
  619. {
  620.     ngx_uint_t  i, key;

  622.     key = 0;

  624.     for (i = 0; i < len; i++) {
  625.         key = ngx_hash(key, ngx_tolower(data[i]));
  626.     }

  628.     return key;
  629. }


  632. ngx_uint_t
  633. ‌ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
  634. {
  635.     ngx_uint_t  key;

  637.     key = 0;

  639.     while (n--) {
  640.         *dst = ngx_tolower(*src);
  641.         key = ngx_hash(key, *dst);
  642.         dst++;
  643.         src++;
  644.     }

  646.     return key;
  647. }


  650. ngx_int_t
  651. ‌ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
  652. {
  653.     ngx_uint_t  asize;

  655.     if (type == NGX_HASH_SMALL) {
  656.         asize = 4;
  657.         ha->hsize = 107;

  659.     } else {
  660.         asize = NGX_HASH_LARGE_ASIZE;
  661.         ha->hsize = NGX_HASH_LARGE_HSIZE;
  662.     }

  664.     if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
  665.         != NGX_OK)
  666.     {
  667.         return NGX_ERROR;
  668.     }

  670.     if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
  671.                        sizeof(ngx_hash_key_t))
  672.         != NGX_OK)
  673.     {
  674.         return NGX_ERROR;
  675.     }

  677.     if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
  678.                        sizeof(ngx_hash_key_t))
  679.         != NGX_OK)
  680.     {
  681.         return NGX_ERROR;
  682.     }

  684.     ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
  685.     if (ha->keys_hash == NULL) {
  686.         return NGX_ERROR;
  687.     }

  689.     ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
  690.                                        sizeof(ngx_array_t) * ha->hsize);
  691.     if (ha->dns_wc_head_hash == NULL) {
  692.         return NGX_ERROR;
  693.     }

  695.     ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
  696.                                        sizeof(ngx_array_t) * ha->hsize);
  697.     if (ha->dns_wc_tail_hash == NULL) {
  698.         return NGX_ERROR;
  699.     }

  701.     return NGX_OK;
  702. }


  705. ngx_int_t
  706. ‌ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
  707.     ngx_uint_t flags)
  708. {
  709.     size_t           len;
  710.     u_char          *p;
  711.     ngx_str_t       *name;
  712.     ngx_uint_t       i, k, n, skip, last;
  713.     ngx_array_t     *keys, *hwc;
  714.     ngx_hash_key_t  *hk;

  716.     last = key->len;

  718.     if (flags & NGX_HASH_WILDCARD_KEY) {

  720.         /*
  721.          * supported wildcards:
  722.          *     "*.example.com", ".example.com", and "www.example.*"
  723.          */

  725.         n = 0;

  727.         for (i = 0; i < key->len; i++) {

  729.             if (key->data[i] == '*') {
  730.                 if (++n > 1) {
  731.                     return NGX_DECLINED;
  732.                 }
  733.             }

  735.             if (key->data[i] == '.' && key->data[i + 1] == '.') {
  736.                 return NGX_DECLINED;
  737.             }
  738.         }

  740.         if (key->len > 1 && key->data[0] == '.') {
  741.             skip = 1;
  742.             goto wildcard;
  743.         }

  745.         if (key->len > 2) {

  747.             if (key->data[0] == '*' && key->data[1] == '.') {
  748.                 skip = 2;
  749.                 goto wildcard;
  750.             }

  752.             if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
  753.                 skip = 0;
  754.                 last -= 2;
  755.                 goto wildcard;
  756.             }
  757.         }

  759.         if (n) {
  760.             return NGX_DECLINED;
  761.         }
  762.     }

  764.     /* exact hash */

  766.     k = 0;

  768.     for (i = 0; i < last; i++) {
  769.         if (!(flags & NGX_HASH_READONLY_KEY)) {
  770.             key->data[i] = ngx_tolower(key->data[i]);
  771.         }
  772.         k = ngx_hash(k, key->data[i]);
  773.     }

  775.     k %= ha->hsize;

  777.     /* check conflicts in exact hash */

  779.     name = ha->keys_hash[k].elts;

  781.     if (name) {
  782.         for (i = 0; i < ha->keys_hash[k].nelts; i++) {
  783.             if (last != name[i].len) {
  784.                 continue;
  785.             }

  787.             if (ngx_strncmp(key->data, name[i].data, last) == 0) {
  788.                 return NGX_BUSY;
  789.             }
  790.         }

  792.     } else {
  793.         if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
  794.                            sizeof(ngx_str_t))
  795.             != NGX_OK)
  796.         {
  797.             return NGX_ERROR;
  798.         }
  799.     }

  801.     name = ngx_array_push(&ha->keys_hash[k]);
  802.     if (name == NULL) {
  803.         return NGX_ERROR;
  804.     }

  806.     *name = *key;

  808.     hk = ngx_array_push(&ha->keys);
  809.     if (hk == NULL) {
  810.         return NGX_ERROR;
  811.     }

  813.     hk->key = *key;
  814.     hk->key_hash = ngx_hash_key(key->data, last);
  815.     hk->value = value;

  817.     return NGX_OK;


  820. wildcard:

  822.     /* wildcard hash */

  824.     k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);

  826.     k %= ha->hsize;

  828.     if (skip == 1) {

  830.         /* check conflicts in exact hash for ".example.com" */

  832.         name = ha->keys_hash[k].elts;

  834.         if (name) {
  835.             len = last - skip;

  837.             for (i = 0; i < ha->keys_hash[k].nelts; i++) {
  838.                 if (len != name[i].len) {
  839.                     continue;
  840.                 }

  842.                 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
  843.                     return NGX_BUSY;
  844.                 }
  845.             }

  847.         } else {
  848.             if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
  849.                                sizeof(ngx_str_t))
  850.                 != NGX_OK)
  851.             {
  852.                 return NGX_ERROR;
  853.             }
  854.         }

  856.         name = ngx_array_push(&ha->keys_hash[k]);
  857.         if (name == NULL) {
  858.             return NGX_ERROR;
  859.         }

  861.         name->len = last - 1;
  862.         name->data = ngx_pnalloc(ha->temp_pool, name->len);
  863.         if (name->data == NULL) {
  864.             return NGX_ERROR;
  865.         }

  867.         ngx_memcpy(name->data, &key->data[1], name->len);
  868.     }


  871.     if (skip) {

  873.         /*
  874.          * convert "*.example.com" to "com.example.\0"
  875.          *      and ".example.com" to "com.example\0"
  876.          */

  878.         p = ngx_pnalloc(ha->temp_pool, last);
  879.         if (p == NULL) {
  880.             return NGX_ERROR;
  881.         }

  883.         len = 0;
  884.         n = 0;

  886.         for (i = last - 1; i; i--) {
  887.             if (key->data[i] == '.') {
  888.                 ngx_memcpy(&p[n], &key->data[i + 1], len);
  889.                 n += len;
  890.                 p[n++] = '.';
  891.                 len = 0;
  892.                 continue;
  893.             }

  895.             len++;
  896.         }

  898.         if (len) {
  899.             ngx_memcpy(&p[n], &key->data[1], len);
  900.             n += len;
  901.         }

  903.         p[n] = '\0';

  905.         hwc = &ha->dns_wc_head;
  906.         keys = &ha->dns_wc_head_hash[k];

  908.     } else {

  910.         /* convert "www.example.*" to "www.example\0" */

  912.         last++;

  914.         p = ngx_pnalloc(ha->temp_pool, last);
  915.         if (p == NULL) {
  916.             return NGX_ERROR;
  917.         }

  919.         ngx_cpystrn(p, key->data, last);

  921.         hwc = &ha->dns_wc_tail;
  922.         keys = &ha->dns_wc_tail_hash[k];
  923.     }


  926.     /* check conflicts in wildcard hash */

  928.     name = keys->elts;

  930.     if (name) {
  931.         len = last - skip;

  933.         for (i = 0; i < keys->nelts; i++) {
  934.             if (len != name[i].len) {
  935.                 continue;
  936.             }

  938.             if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
  939.                 return NGX_BUSY;
  940.             }
  941.         }

  943.     } else {
  944.         if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
  945.         {
  946.             return NGX_ERROR;
  947.         }
  948.     }

  950.     name = ngx_array_push(keys);
  951.     if (name == NULL) {
  952.         return NGX_ERROR;
  953.     }

  955.     name->len = last - skip;
  956.     name->data = ngx_pnalloc(ha->temp_pool, name->len);
  957.     if (name->data == NULL) {
  958.         return NGX_ERROR;
  959.     }

  961.     ngx_memcpy(name->data, key->data + skip, name->len);


  964.     /* add to wildcard hash */

  966.     hk = ngx_array_push(hwc);
  967.     if (hk == NULL) {
  968.         return NGX_ERROR;
  969.     }

  971.     hk->key.len = last - 1;
  972.     hk->key.data = p;
  973.     hk->key_hash = 0;
  974.     hk->value = value;

  976.     return NGX_OK;
  977. }

One Level Up Top Level