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