aboutsummaryrefslogtreecommitdiffstats
path: root/app/nginx/src/core/ngx_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'app/nginx/src/core/ngx_hash.c')
-rw-r--r--app/nginx/src/core/ngx_hash.c988
1 files changed, 988 insertions, 0 deletions
diff --git a/app/nginx/src/core/ngx_hash.c b/app/nginx/src/core/ngx_hash.c
new file mode 100644
index 0000000..1944c7a
--- /dev/null
+++ b/app/nginx/src/core/ngx_hash.c
@@ -0,0 +1,988 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) Nginx, Inc.
+ */
+
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+void *
+ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
+{
+ ngx_uint_t i;
+ ngx_hash_elt_t *elt;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
+#endif
+
+ elt = hash->buckets[key % hash->size];
+
+ if (elt == NULL) {
+ return NULL;
+ }
+
+ while (elt->value) {
+ if (len != (size_t) elt->len) {
+ goto next;
+ }
+
+ for (i = 0; i < len; i++) {
+ if (name[i] != elt->name[i]) {
+ goto next;
+ }
+ }
+
+ return elt->value;
+
+ next:
+
+ elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
+ sizeof(void *));
+ continue;
+ }
+
+ return NULL;
+}
+
+
+void *
+ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
+{
+ void *value;
+ ngx_uint_t i, n, key;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%*s\"", len, name);
+#endif
+
+ n = len;
+
+ while (n) {
+ if (name[n - 1] == '.') {
+ break;
+ }
+
+ n--;
+ }
+
+ key = 0;
+
+ for (i = n; i < len; i++) {
+ key = ngx_hash(key, name[i]);
+ }
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
+#endif
+
+ value = ngx_hash_find(&hwc->hash, key, &name[n], len - n);
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
+#endif
+
+ if (value) {
+
+ /*
+ * the 2 low bits of value have the special meaning:
+ * 00 - value is data pointer for both "example.com"
+ * and "*.example.com";
+ * 01 - value is data pointer for "*.example.com" only;
+ * 10 - value is pointer to wildcard hash allowing
+ * both "example.com" and "*.example.com";
+ * 11 - value is pointer to wildcard hash allowing
+ * "*.example.com" only.
+ */
+
+ if ((uintptr_t) value & 2) {
+
+ if (n == 0) {
+
+ /* "example.com" */
+
+ if ((uintptr_t) value & 1) {
+ return NULL;
+ }
+
+ hwc = (ngx_hash_wildcard_t *)
+ ((uintptr_t) value & (uintptr_t) ~3);
+ return hwc->value;
+ }
+
+ hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
+
+ value = ngx_hash_find_wc_head(hwc, name, n - 1);
+
+ if (value) {
+ return value;
+ }
+
+ return hwc->value;
+ }
+
+ if ((uintptr_t) value & 1) {
+
+ if (n == 0) {
+
+ /* "example.com" */
+
+ return NULL;
+ }
+
+ return (void *) ((uintptr_t) value & (uintptr_t) ~3);
+ }
+
+ return value;
+ }
+
+ return hwc->value;
+}
+
+
+void *
+ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
+{
+ void *value;
+ ngx_uint_t i, key;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%*s\"", len, name);
+#endif
+
+ key = 0;
+
+ for (i = 0; i < len; i++) {
+ if (name[i] == '.') {
+ break;
+ }
+
+ key = ngx_hash(key, name[i]);
+ }
+
+ if (i == len) {
+ return NULL;
+ }
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
+#endif
+
+ value = ngx_hash_find(&hwc->hash, key, name, i);
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "value:\"%p\"", value);
+#endif
+
+ if (value) {
+
+ /*
+ * the 2 low bits of value have the special meaning:
+ * 00 - value is data pointer;
+ * 11 - value is pointer to wildcard hash allowing "example.*".
+ */
+
+ if ((uintptr_t) value & 2) {
+
+ i++;
+
+ hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
+
+ value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);
+
+ if (value) {
+ return value;
+ }
+
+ return hwc->value;
+ }
+
+ return value;
+ }
+
+ return hwc->value;
+}
+
+
+void *
+ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name,
+ size_t len)
+{
+ void *value;
+
+ if (hash->hash.buckets) {
+ value = ngx_hash_find(&hash->hash, key, name, len);
+
+ if (value) {
+ return value;
+ }
+ }
+
+ if (len == 0) {
+ return NULL;
+ }
+
+ if (hash->wc_head && hash->wc_head->hash.buckets) {
+ value = ngx_hash_find_wc_head(hash->wc_head, name, len);
+
+ if (value) {
+ return value;
+ }
+ }
+
+ if (hash->wc_tail && hash->wc_tail->hash.buckets) {
+ value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);
+
+ if (value) {
+ return value;
+ }
+ }
+
+ return NULL;
+}
+
+
+#define NGX_HASH_ELT_SIZE(name) \
+ (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
+
+ngx_int_t
+ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
+{
+ u_char *elts;
+ size_t len;
+ u_short *test;
+ ngx_uint_t i, n, key, size, start, bucket_size;
+ ngx_hash_elt_t *elt, **buckets;
+
+ if (hinit->max_size == 0) {
+ ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
+ "could not build %s, you should "
+ "increase %s_max_size: %i",
+ hinit->name, hinit->name, hinit->max_size);
+ return NGX_ERROR;
+ }
+
+ for (n = 0; n < nelts; n++) {
+ if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
+ {
+ ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
+ "could not build %s, you should "
+ "increase %s_bucket_size: %i",
+ hinit->name, hinit->name, hinit->bucket_size);
+ return NGX_ERROR;
+ }
+ }
+
+ test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
+ if (test == NULL) {
+ return NGX_ERROR;
+ }
+
+ bucket_size = hinit->bucket_size - sizeof(void *);
+
+ start = nelts / (bucket_size / (2 * sizeof(void *)));
+ start = start ? start : 1;
+
+ if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
+ start = hinit->max_size - 1000;
+ }
+
+ for (size = start; size <= hinit->max_size; size++) {
+
+ ngx_memzero(test, size * sizeof(u_short));
+
+ for (n = 0; n < nelts; n++) {
+ if (names[n].key.data == NULL) {
+ continue;
+ }
+
+ key = names[n].key_hash % size;
+ test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "%ui: %ui %ui \"%V\"",
+ size, key, test[key], &names[n].key);
+#endif
+
+ if (test[key] > (u_short) bucket_size) {
+ goto next;
+ }
+ }
+
+ goto found;
+
+ next:
+
+ continue;
+ }
+
+ size = hinit->max_size;
+
+ ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
+ "could not build optimal %s, you should increase "
+ "either %s_max_size: %i or %s_bucket_size: %i; "
+ "ignoring %s_bucket_size",
+ hinit->name, hinit->name, hinit->max_size,
+ hinit->name, hinit->bucket_size, hinit->name);
+
+found:
+
+ for (i = 0; i < size; i++) {
+ test[i] = sizeof(void *);
+ }
+
+ for (n = 0; n < nelts; n++) {
+ if (names[n].key.data == NULL) {
+ continue;
+ }
+
+ key = names[n].key_hash % size;
+ test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
+ }
+
+ len = 0;
+
+ for (i = 0; i < size; i++) {
+ if (test[i] == sizeof(void *)) {
+ continue;
+ }
+
+ test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
+
+ len += test[i];
+ }
+
+ if (hinit->hash == NULL) {
+ hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
+ + size * sizeof(ngx_hash_elt_t *));
+ if (hinit->hash == NULL) {
+ ngx_free(test);
+ return NGX_ERROR;
+ }
+
+ buckets = (ngx_hash_elt_t **)
+ ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
+
+ } else {
+ buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
+ if (buckets == NULL) {
+ ngx_free(test);
+ return NGX_ERROR;
+ }
+ }
+
+ elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
+ if (elts == NULL) {
+ ngx_free(test);
+ return NGX_ERROR;
+ }
+
+ elts = ngx_align_ptr(elts, ngx_cacheline_size);
+
+ for (i = 0; i < size; i++) {
+ if (test[i] == sizeof(void *)) {
+ continue;
+ }
+
+ buckets[i] = (ngx_hash_elt_t *) elts;
+ elts += test[i];
+ }
+
+ for (i = 0; i < size; i++) {
+ test[i] = 0;
+ }
+
+ for (n = 0; n < nelts; n++) {
+ if (names[n].key.data == NULL) {
+ continue;
+ }
+
+ key = names[n].key_hash % size;
+ elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
+
+ elt->value = names[n].value;
+ elt->len = (u_short) names[n].key.len;
+
+ ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
+
+ test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
+ }
+
+ for (i = 0; i < size; i++) {
+ if (buckets[i] == NULL) {
+ continue;
+ }
+
+ elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
+
+ elt->value = NULL;
+ }
+
+ ngx_free(test);
+
+ hinit->hash->buckets = buckets;
+ hinit->hash->size = size;
+
+#if 0
+
+ for (i = 0; i < size; i++) {
+ ngx_str_t val;
+ ngx_uint_t key;
+
+ elt = buckets[i];
+
+ if (elt == NULL) {
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "%ui: NULL", i);
+ continue;
+ }
+
+ while (elt->value) {
+ val.len = elt->len;
+ val.data = &elt->name[0];
+
+ key = hinit->key(val.data, val.len);
+
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "%ui: %p \"%V\" %ui", i, elt, &val, key);
+
+ elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
+ sizeof(void *));
+ }
+ }
+
+#endif
+
+ return NGX_OK;
+}
+
+
+ngx_int_t
+ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
+ ngx_uint_t nelts)
+{
+ size_t len, dot_len;
+ ngx_uint_t i, n, dot;
+ ngx_array_t curr_names, next_names;
+ ngx_hash_key_t *name, *next_name;
+ ngx_hash_init_t h;
+ ngx_hash_wildcard_t *wdc;
+
+ if (ngx_array_init(&curr_names, hinit->temp_pool, nelts,
+ sizeof(ngx_hash_key_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ if (ngx_array_init(&next_names, hinit->temp_pool, nelts,
+ sizeof(ngx_hash_key_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ for (n = 0; n < nelts; n = i) {
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "wc0: \"%V\"", &names[n].key);
+#endif
+
+ dot = 0;
+
+ for (len = 0; len < names[n].key.len; len++) {
+ if (names[n].key.data[len] == '.') {
+ dot = 1;
+ break;
+ }
+ }
+
+ name = ngx_array_push(&curr_names);
+ if (name == NULL) {
+ return NGX_ERROR;
+ }
+
+ name->key.len = len;
+ name->key.data = names[n].key.data;
+ name->key_hash = hinit->key(name->key.data, name->key.len);
+ name->value = names[n].value;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "wc1: \"%V\" %ui", &name->key, dot);
+#endif
+
+ dot_len = len + 1;
+
+ if (dot) {
+ len++;
+ }
+
+ next_names.nelts = 0;
+
+ if (names[n].key.len != len) {
+ next_name = ngx_array_push(&next_names);
+ if (next_name == NULL) {
+ return NGX_ERROR;
+ }
+
+ next_name->key.len = names[n].key.len - len;
+ next_name->key.data = names[n].key.data + len;
+ next_name->key_hash = 0;
+ next_name->value = names[n].value;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "wc2: \"%V\"", &next_name->key);
+#endif
+ }
+
+ for (i = n + 1; i < nelts; i++) {
+ if (ngx_strncmp(names[n].key.data, names[i].key.data, len) != 0) {
+ break;
+ }
+
+ if (!dot
+ && names[i].key.len > len
+ && names[i].key.data[len] != '.')
+ {
+ break;
+ }
+
+ next_name = ngx_array_push(&next_names);
+ if (next_name == NULL) {
+ return NGX_ERROR;
+ }
+
+ next_name->key.len = names[i].key.len - dot_len;
+ next_name->key.data = names[i].key.data + dot_len;
+ next_name->key_hash = 0;
+ next_name->value = names[i].value;
+
+#if 0
+ ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
+ "wc3: \"%V\"", &next_name->key);
+#endif
+ }
+
+ if (next_names.nelts) {
+
+ h = *hinit;
+ h.hash = NULL;
+
+ if (ngx_hash_wildcard_init(&h, (ngx_hash_key_t *) next_names.elts,
+ next_names.nelts)
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ wdc = (ngx_hash_wildcard_t *) h.hash;
+
+ if (names[n].key.len == len) {
+ wdc->value = names[n].value;
+ }
+
+ name->value = (void *) ((uintptr_t) wdc | (dot ? 3 : 2));
+
+ } else if (dot) {
+ name->value = (void *) ((uintptr_t) name->value | 1);
+ }
+ }
+
+ if (ngx_hash_init(hinit, (ngx_hash_key_t *) curr_names.elts,
+ curr_names.nelts)
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ return NGX_OK;
+}
+
+
+ngx_uint_t
+ngx_hash_key(u_char *data, size_t len)
+{
+ ngx_uint_t i, key;
+
+ key = 0;
+
+ for (i = 0; i < len; i++) {
+ key = ngx_hash(key, data[i]);
+ }
+
+ return key;
+}
+
+
+ngx_uint_t
+ngx_hash_key_lc(u_char *data, size_t len)
+{
+ ngx_uint_t i, key;
+
+ key = 0;
+
+ for (i = 0; i < len; i++) {
+ key = ngx_hash(key, ngx_tolower(data[i]));
+ }
+
+ return key;
+}
+
+
+ngx_uint_t
+ngx_hash_strlow(u_char *dst, u_char *src, size_t n)
+{
+ ngx_uint_t key;
+
+ key = 0;
+
+ while (n--) {
+ *dst = ngx_tolower(*src);
+ key = ngx_hash(key, *dst);
+ dst++;
+ src++;
+ }
+
+ return key;
+}
+
+
+ngx_int_t
+ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type)
+{
+ ngx_uint_t asize;
+
+ if (type == NGX_HASH_SMALL) {
+ asize = 4;
+ ha->hsize = 107;
+
+ } else {
+ asize = NGX_HASH_LARGE_ASIZE;
+ ha->hsize = NGX_HASH_LARGE_HSIZE;
+ }
+
+ if (ngx_array_init(&ha->keys, ha->temp_pool, asize, sizeof(ngx_hash_key_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
+ sizeof(ngx_hash_key_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
+ sizeof(ngx_hash_key_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
+ if (ha->keys_hash == NULL) {
+ return NGX_ERROR;
+ }
+
+ ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
+ sizeof(ngx_array_t) * ha->hsize);
+ if (ha->dns_wc_head_hash == NULL) {
+ return NGX_ERROR;
+ }
+
+ ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
+ sizeof(ngx_array_t) * ha->hsize);
+ if (ha->dns_wc_tail_hash == NULL) {
+ return NGX_ERROR;
+ }
+
+ return NGX_OK;
+}
+
+
+ngx_int_t
+ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
+ ngx_uint_t flags)
+{
+ size_t len;
+ u_char *p;
+ ngx_str_t *name;
+ ngx_uint_t i, k, n, skip, last;
+ ngx_array_t *keys, *hwc;
+ ngx_hash_key_t *hk;
+
+ last = key->len;
+
+ if (flags & NGX_HASH_WILDCARD_KEY) {
+
+ /*
+ * supported wildcards:
+ * "*.example.com", ".example.com", and "www.example.*"
+ */
+
+ n = 0;
+
+ for (i = 0; i < key->len; i++) {
+
+ if (key->data[i] == '*') {
+ if (++n > 1) {
+ return NGX_DECLINED;
+ }
+ }
+
+ if (key->data[i] == '.' && key->data[i + 1] == '.') {
+ return NGX_DECLINED;
+ }
+
+ if (key->data[i] == '\0') {
+ return NGX_DECLINED;
+ }
+ }
+
+ if (key->len > 1 && key->data[0] == '.') {
+ skip = 1;
+ goto wildcard;
+ }
+
+ if (key->len > 2) {
+
+ if (key->data[0] == '*' && key->data[1] == '.') {
+ skip = 2;
+ goto wildcard;
+ }
+
+ if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
+ skip = 0;
+ last -= 2;
+ goto wildcard;
+ }
+ }
+
+ if (n) {
+ return NGX_DECLINED;
+ }
+ }
+
+ /* exact hash */
+
+ k = 0;
+
+ for (i = 0; i < last; i++) {
+ if (!(flags & NGX_HASH_READONLY_KEY)) {
+ key->data[i] = ngx_tolower(key->data[i]);
+ }
+ k = ngx_hash(k, key->data[i]);
+ }
+
+ k %= ha->hsize;
+
+ /* check conflicts in exact hash */
+
+ name = ha->keys_hash[k].elts;
+
+ if (name) {
+ for (i = 0; i < ha->keys_hash[k].nelts; i++) {
+ if (last != name[i].len) {
+ continue;
+ }
+
+ if (ngx_strncmp(key->data, name[i].data, last) == 0) {
+ return NGX_BUSY;
+ }
+ }
+
+ } else {
+ if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
+ sizeof(ngx_str_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+ }
+
+ name = ngx_array_push(&ha->keys_hash[k]);
+ if (name == NULL) {
+ return NGX_ERROR;
+ }
+
+ *name = *key;
+
+ hk = ngx_array_push(&ha->keys);
+ if (hk == NULL) {
+ return NGX_ERROR;
+ }
+
+ hk->key = *key;
+ hk->key_hash = ngx_hash_key(key->data, last);
+ hk->value = value;
+
+ return NGX_OK;
+
+
+wildcard:
+
+ /* wildcard hash */
+
+ k = ngx_hash_strlow(&key->data[skip], &key->data[skip], last - skip);
+
+ k %= ha->hsize;
+
+ if (skip == 1) {
+
+ /* check conflicts in exact hash for ".example.com" */
+
+ name = ha->keys_hash[k].elts;
+
+ if (name) {
+ len = last - skip;
+
+ for (i = 0; i < ha->keys_hash[k].nelts; i++) {
+ if (len != name[i].len) {
+ continue;
+ }
+
+ if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
+ return NGX_BUSY;
+ }
+ }
+
+ } else {
+ if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
+ sizeof(ngx_str_t))
+ != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+ }
+
+ name = ngx_array_push(&ha->keys_hash[k]);
+ if (name == NULL) {
+ return NGX_ERROR;
+ }
+
+ name->len = last - 1;
+ name->data = ngx_pnalloc(ha->temp_pool, name->len);
+ if (name->data == NULL) {
+ return NGX_ERROR;
+ }
+
+ ngx_memcpy(name->data, &key->data[1], name->len);
+ }
+
+
+ if (skip) {
+
+ /*
+ * convert "*.example.com" to "com.example.\0"
+ * and ".example.com" to "com.example\0"
+ */
+
+ p = ngx_pnalloc(ha->temp_pool, last);
+ if (p == NULL) {
+ return NGX_ERROR;
+ }
+
+ len = 0;
+ n = 0;
+
+ for (i = last - 1; i; i--) {
+ if (key->data[i] == '.') {
+ ngx_memcpy(&p[n], &key->data[i + 1], len);
+ n += len;
+ p[n++] = '.';
+ len = 0;
+ continue;
+ }
+
+ len++;
+ }
+
+ if (len) {
+ ngx_memcpy(&p[n], &key->data[1], len);
+ n += len;
+ }
+
+ p[n] = '\0';
+
+ hwc = &ha->dns_wc_head;
+ keys = &ha->dns_wc_head_hash[k];
+
+ } else {
+
+ /* convert "www.example.*" to "www.example\0" */
+
+ last++;
+
+ p = ngx_pnalloc(ha->temp_pool, last);
+ if (p == NULL) {
+ return NGX_ERROR;
+ }
+
+ ngx_cpystrn(p, key->data, last);
+
+ hwc = &ha->dns_wc_tail;
+ keys = &ha->dns_wc_tail_hash[k];
+ }
+
+
+ /* check conflicts in wildcard hash */
+
+ name = keys->elts;
+
+ if (name) {
+ len = last - skip;
+
+ for (i = 0; i < keys->nelts; i++) {
+ if (len != name[i].len) {
+ continue;
+ }
+
+ if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
+ return NGX_BUSY;
+ }
+ }
+
+ } else {
+ if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+ }
+
+ name = ngx_array_push(keys);
+ if (name == NULL) {
+ return NGX_ERROR;
+ }
+
+ name->len = last - skip;
+ name->data = ngx_pnalloc(ha->temp_pool, name->len);
+ if (name->data == NULL) {
+ return NGX_ERROR;
+ }
+
+ ngx_memcpy(name->data, key->data + skip, name->len);
+
+
+ /* add to wildcard hash */
+
+ hk = ngx_array_push(hwc);
+ if (hk == NULL) {
+ return NGX_ERROR;
+ }
+
+ hk->key.len = last - 1;
+ hk->key.data = p;
+ hk->key_hash = 0;
+ hk->value = value;
+
+ return NGX_OK;
+}