Annotation of embedaddon/nginx/src/core/ngx_hash.c, revision 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ngx_hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core