Mercurial > hg > nginx-vendor-0-5

comparison src/core/ngx_hash.c @ 326:f70f2f565fe0 NGINX_0_5_33

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.5.33 *) Change: now by default the "echo" SSI command uses entity encoding. *) Feature: the "encoding" parameter in the "echo" SSI command. *) Change: mail proxy was split on three modules: pop3, imap and smtp. *) Feature: the --without-mail_pop3_module, --without-mail_imap_module, and --without-mail_smtp_module configuration parameters. *) Feature: the "smtp_greeting_delay" and "smtp_client_buffer" directives of the ngx_mail_smtp_module. *) Feature: the "server_name" and "valid_referers" directives support regular expressions. *) Feature: the "server_name", "map", and "valid_referers" directives support the "www.example.*" wildcards. *) Bugfix: sub_filter did not work with empty substitution. *) Bugfix: in sub_filter parsing. *) Bugfix: a worker process may got caught in an endless loop, if the memcached was used. *) Bugfix: nginx supported low case only "close" and "keep-alive" values in the "Connection" request header line; bug appeared in 0.5.32. *) Bugfix: nginx could not start on Solaris if the shared PCRE library located in non-standard place was used.
author Igor Sysoev <http://sysoev.ru>
date Wed, 07 Nov 2007 00:00:00 +0300
parents ff906029dd40
children
comparison
equal deleted inserted replaced
325:5bb1b28ddeaa 326:f70f2f565fe0
51 return NULL; 51 return NULL;
52 } 52 }
53 53
54 54
55 void * 55 void *
56 ngx_hash_find_wildcard(ngx_hash_wildcard_t *hwc, u_char *name, size_t len) 56 ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
57 { 57 {
58 void *value; 58 void *value;
59 ngx_uint_t i, n, key; 59 ngx_uint_t i, n, key;
60 60
61 #if 0 61 #if 0
62 ngx_str_t line; 62 ngx_str_t line;
63 63
64 line.len = len; 64 line.len = len;
65 line.data = name; 65 line.data = name;
66 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wc:\"%V\"", &line); 66 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wch:\"%V\"", &line);
67 #endif 67 #endif
68 68
69 n = len; 69 n = len;
70 70
71 while (n) { 71 while (n) {
110 } else { 110 } else {
111 return NULL; 111 return NULL;
112 } 112 }
113 } 113 }
114 114
115 value = ngx_hash_find_wildcard(hwc, name, n - 1); 115 value = ngx_hash_find_wc_head(hwc, name, n - 1);
116 116
117 if (value) { 117 if (value) {
118 return value; 118 return value;
119 } 119 }
120 120
123 123
124 return value; 124 return value;
125 } 125 }
126 126
127 return hwc->value; 127 return hwc->value;
128 }
129
130
131 void *
132 ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len)
133 {
134 void *value;
135 ngx_uint_t i, key;
136
137 #if 0
138 ngx_str_t line;
139
140 line.len = len;
141 line.data = name;
142 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "wct:\"%V\"", &line);
143 #endif
144
145 key = 0;
146
147 for (i = 0; i < len; i++) {
148 if (name[i] == '.') {
149 break;
150 }
151
152 key = ngx_hash(key, name[i]);
153 }
154
155 if (i == len) {
156 return NULL;
157 }
158
159 #if 0
160 ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "key:\"%ui\"", key);
161 #endif
162
163 value = ngx_hash_find(&hwc->hash, key, name, i);
164
165 if (value) {
166
167 /*
168 * the 2 low bits of value have the special meaning:
169 * 00 - value is data pointer,
170 * 01 - value is pointer to wildcard hash allowing "example.*".
171 */
172
173 if ((uintptr_t) value & 1) {
174
175 i++;
176
177 hwc = (ngx_hash_wildcard_t *) ((uintptr_t) value & (uintptr_t) ~3);
178
179 value = ngx_hash_find_wc_tail(hwc, &name[i], len - i);
180
181 if (value) {
182 return value;
183 }
184
185 return hwc->value;
186 }
187
188 return value;
189 }
190
191 return hwc->value;
192 }
193
194
195 void *
196 ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name,
197 size_t len)
198 {
199 void *value;
200
201 if (hash->hash.buckets) {
202 value = ngx_hash_find(&hash->hash, key, name, len);
203
204 if (value) {
205 return value;
206 }
207 }
208
209 if (hash->wc_head && hash->wc_head->hash.buckets) {
210 value = ngx_hash_find_wc_head(hash->wc_head, name, len);
211
212 if (value) {
213 return value;
214 }
215 }
216
217 if (hash->wc_tail && hash->wc_tail->hash.buckets) {
218 value = ngx_hash_find_wc_tail(hash->wc_tail, name, len);
219
220 if (value) {
221 return value;
222 }
223 }
224
225 return NULL;
128 } 226 }
129 227
130 228
131 #define NGX_HASH_ELT_SIZE(name) \ 229 #define NGX_HASH_ELT_SIZE(name) \
132 (sizeof(void *) + ngx_align((name)->key.len + 1, sizeof(void *))) 230 (sizeof(void *) + ngx_align((name)->key.len + 1, sizeof(void *)))
542 != NGX_OK) 640 != NGX_OK)
543 { 641 {
544 return NGX_ERROR; 642 return NGX_ERROR;
545 } 643 }
546 644
547 if (ngx_array_init(&ha->dns_wildcards, ha->temp_pool, asize, 645 if (ngx_array_init(&ha->dns_wc_head, ha->temp_pool, asize,
548 sizeof(ngx_hash_key_t)) 646 sizeof(ngx_hash_key_t))
549 != NGX_OK) 647 != NGX_OK)
550 { 648 {
551 return NGX_ERROR; 649 return NGX_ERROR;
552 } 650 }
553 651
652 if (ngx_array_init(&ha->dns_wc_tail, ha->temp_pool, asize,
653 sizeof(ngx_hash_key_t))
654 != NGX_OK)
655 {
656 return NGX_ERROR;
657 }
658
554 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize); 659 ha->keys_hash = ngx_pcalloc(ha->temp_pool, sizeof(ngx_array_t) * ha->hsize);
555 if (ha->keys_hash == NULL) { 660 if (ha->keys_hash == NULL) {
556 return NGX_ERROR; 661 return NGX_ERROR;
557 } 662 }
558 663
559 ha->dns_wildcards_hash = ngx_pcalloc(ha->temp_pool, 664 ha->dns_wc_head_hash = ngx_pcalloc(ha->temp_pool,
560 sizeof(ngx_array_t) * ha->hsize); 665 sizeof(ngx_array_t) * ha->hsize);
561 if (ha->dns_wildcards_hash == NULL) { 666 if (ha->dns_wc_head_hash == NULL) {
667 return NGX_ERROR;
668 }
669
670 ha->dns_wc_tail_hash = ngx_pcalloc(ha->temp_pool,
671 sizeof(ngx_array_t) * ha->hsize);
672 if (ha->dns_wc_tail_hash == NULL) {
562 return NGX_ERROR; 673 return NGX_ERROR;
563 } 674 }
564 675
565 return NGX_OK; 676 return NGX_OK;
566 } 677 }
569 ngx_int_t 680 ngx_int_t
570 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value, 681 ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value,
571 ngx_uint_t flags) 682 ngx_uint_t flags)
572 { 683 {
573 size_t len; 684 size_t len;
574 u_char *reverse; 685 u_char *p;
575 ngx_str_t *name; 686 ngx_str_t *name;
576 ngx_uint_t i, k, n, skip; 687 ngx_uint_t i, k, n, skip, last;
688 ngx_array_t *keys, *hwc;
577 ngx_hash_key_t *hk; 689 ngx_hash_key_t *hk;
578 690
579 if (!(flags & NGX_HASH_WILDCARD_KEY)) { 691 last = key->len;
580 692
581 /* exact hash */ 693 if (flags & NGX_HASH_WILDCARD_KEY) {
582 694
583 k = 0; 695 /*
696 * supported wildcards:
697 * "*.example.com", ".example.com", and "www.example.*"
698 */
699
700 n = 0;
584 701
585 for (i = 0; i < key->len; i++) { 702 for (i = 0; i < key->len; i++) {
586 if (!(flags & NGX_HASH_READONLY_KEY)) { 703
587 key->data[i] = ngx_tolower(key->data[i]); 704 if (key->data[i] == '*') {
588 } 705 if (++n > 1) {
589 k = ngx_hash(k, key->data[i]); 706 return NGX_DECLINED;
590 } 707 }
591 708 }
592 k %= ha->hsize; 709
593 710 if (key->data[i] == '.' && key->data[i + 1] == '.') {
594 /* check conflicts in exact hash */ 711 return NGX_DECLINED;
712 }
713 }
714
715 if (key->len > 1 && key->data[0] == '.') {
716 skip = 1;
717 goto wildcard;
718 }
719
720 if (key->len > 2) {
721
722 if (key->data[0] == '*' && key->data[1] == '.') {
723 skip = 2;
724 goto wildcard;
725 }
726
727 if (key->data[i - 2] == '.' && key->data[i - 1] == '*') {
728 skip = 0;
729 last -= 2;
730 goto wildcard;
731 }
732 }
733
734 if (n) {
735 return NGX_DECLINED;
736 }
737 }
738
739 /* exact hash */
740
741 k = 0;
742
743 for (i = 0; i < last; i++) {
744 if (!(flags & NGX_HASH_READONLY_KEY)) {
745 key->data[i] = ngx_tolower(key->data[i]);
746 }
747 k = ngx_hash(k, key->data[i]);
748 }
749
750 k %= ha->hsize;
751
752 /* check conflicts in exact hash */
753
754 name = ha->keys_hash[k].elts;
755
756 if (name) {
757 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
758 if (last != name[i].len) {
759 continue;
760 }
761
762 if (ngx_strncmp(key->data, name[i].data, last) == 0) {
763 return NGX_BUSY;
764 }
765 }
766
767 } else {
768 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
769 sizeof(ngx_str_t))
770 != NGX_OK)
771 {
772 return NGX_ERROR;
773 }
774 }
775
776 name = ngx_array_push(&ha->keys_hash[k]);
777 if (name == NULL) {
778 return NGX_ERROR;
779 }
780
781 *name = *key;
782
783 hk = ngx_array_push(&ha->keys);
784 if (hk == NULL) {
785 return NGX_ERROR;
786 }
787
788 hk->key = *key;
789 hk->key_hash = ngx_hash_key(key->data, last);
790 hk->value = value;
791
792 return NGX_OK;
793
794
795 wildcard:
796
797 /* wildcard hash */
798
799 k = 0;
800
801 for (i = skip; i < last; i++) {
802 key->data[i] = ngx_tolower(key->data[i]);
803 k = ngx_hash(k, key->data[i]);
804 }
805
806 k %= ha->hsize;
807
808 if (skip == 1) {
809
810 /* check conflicts in exact hash for ".example.com" */
595 811
596 name = ha->keys_hash[k].elts; 812 name = ha->keys_hash[k].elts;
597 813
598 if (name) { 814 if (name) {
815 len = last - skip;
816
599 for (i = 0; i < ha->keys_hash[k].nelts; i++) { 817 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
600 if (key->len != name[i].len) { 818 if (len != name[i].len) {
601 continue; 819 continue;
602 } 820 }
603 821
604 if (ngx_strncmp(key->data, name[i].data, key->len) == 0) { 822 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
605 return NGX_BUSY; 823 return NGX_BUSY;
606 } 824 }
607 } 825 }
608 826
609 } else { 827 } else {
618 name = ngx_array_push(&ha->keys_hash[k]); 836 name = ngx_array_push(&ha->keys_hash[k]);
619 if (name == NULL) { 837 if (name == NULL) {
620 return NGX_ERROR; 838 return NGX_ERROR;
621 } 839 }
622 840
623 *name = *key; 841 name->len = last - 1;
624 842 name->data = ngx_palloc(ha->temp_pool, name->len);
625 hk = ngx_array_push(&ha->keys); 843 if (name->data == NULL) {
626 if (hk == NULL) { 844 return NGX_ERROR;
627 return NGX_ERROR; 845 }
628 } 846
629 847 ngx_memcpy(name->data, &key->data[1], name->len);
630 hk->key = *key; 848 }
631 hk->key_hash = ngx_hash_key(key->data, key->len); 849
632 hk->value = value; 850
633 851 if (skip) {
634 } else {
635
636 /* wildcard hash */
637
638 skip = (key->data[0] == '*') ? 2 : 1;
639 k = 0;
640
641 for (i = skip; i < key->len; i++) {
642 key->data[i] = ngx_tolower(key->data[i]);
643 k = ngx_hash(k, key->data[i]);
644 }
645
646 k %= ha->hsize;
647
648 if (skip == 1) {
649
650 /* check conflicts in exact hash for ".example.com" */
651
652 name = ha->keys_hash[k].elts;
653
654 if (name) {
655 len = key->len - skip;
656
657 for (i = 0; i < ha->keys_hash[k].nelts; i++) {
658 if (len != name[i].len) {
659 continue;
660 }
661
662 if (ngx_strncmp(&key->data[1], name[i].data, len) == 0) {
663 return NGX_BUSY;
664 }
665 }
666
667 } else {
668 if (ngx_array_init(&ha->keys_hash[k], ha->temp_pool, 4,
669 sizeof(ngx_str_t))
670 != NGX_OK)
671 {
672 return NGX_ERROR;
673 }
674 }
675
676 name = ngx_array_push(&ha->keys_hash[k]);
677 if (name == NULL) {
678 return NGX_ERROR;
679 }
680
681 name->len = key->len - 1;
682 name->data = ngx_palloc(ha->temp_pool, name->len);
683 if (name->data == NULL) {
684 return NGX_ERROR;
685 }
686
687 ngx_memcpy(name->data, &key->data[1], name->len);
688 }
689
690 852
691 /* 853 /*
692 * convert "*.example.com" to "com.example.\0" 854 * convert "*.example.com" to "com.example.\0"
693 * and ".example.com" to "com.example\0" 855 * and ".example.com" to "com.example\0"
694 */ 856 */
695 857
696 reverse = ngx_palloc(ha->temp_pool, key->len); 858 p = ngx_palloc(ha->temp_pool, last);
697 if (reverse == NULL) { 859 if (p == NULL) {
698 return NGX_ERROR; 860 return NGX_ERROR;
699 } 861 }
700 862
701 len = 0; 863 len = 0;
702 n = 0; 864 n = 0;
703 865
704 for (i = key->len - 1; i; i--) { 866 for (i = last - 1; i; i--) {
705 if (key->data[i] == '.') { 867 if (key->data[i] == '.') {
706 ngx_memcpy(&reverse[n], &key->data[i + 1], len); 868 ngx_memcpy(&p[n], &key->data[i + 1], len);
707 n += len; 869 n += len;
708 reverse[n++] = '.'; 870 p[n++] = '.';
709 len = 0; 871 len = 0;
710 continue; 872 continue;
711 } 873 }
712 874
713 len++; 875 len++;
714 } 876 }
715 877
716 if (len) { 878 if (len) {
717 ngx_memcpy(&reverse[n], &key->data[1], len); 879 ngx_memcpy(&p[n], &key->data[1], len);
718 n += len; 880 n += len;
719 } 881 }
720 882
721 reverse[n] = '\0'; 883 p[n] = '\0';
722 884
723 885 hwc = &ha->dns_wc_head;
724 hk = ngx_array_push(&ha->dns_wildcards); 886 keys = &ha->dns_wc_head_hash[k];
725 if (hk == NULL) { 887
726 return NGX_ERROR; 888 } else {
727 } 889
728 890 /* convert "www.example.*" to "www.example\0" */
729 hk->key.len = key->len - 1; 891
730 hk->key.data = reverse; 892 last++;
731 hk->key_hash = 0; 893
732 hk->value = value; 894 p = ngx_palloc(ha->temp_pool, last);
733 895 if (p == NULL) {
734 896 return NGX_ERROR;
735 /* check conflicts in wildcard hash */ 897 }
736 898
737 name = ha->dns_wildcards_hash[k].elts; 899 ngx_cpystrn(p, key->data, last);
738 900
739 if (name) { 901 hwc = &ha->dns_wc_tail;
740 len = key->len - skip; 902 keys = &ha->dns_wc_tail_hash[k];
741 903 }
742 for (i = 0; i < ha->dns_wildcards_hash[k].nelts; i++) { 904
743 if (len != name[i].len) { 905
744 continue; 906 hk = ngx_array_push(hwc);
745 } 907 if (hk == NULL) {
746 908 return NGX_ERROR;
747 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) { 909 }
748 return NGX_BUSY; 910
749 } 911 hk->key.len = last - 1;
750 } 912 hk->key.data = p;
751 913 hk->key_hash = 0;
752 } else { 914 hk->value = value;
753 if (ngx_array_init(&ha->dns_wildcards_hash[k], ha->temp_pool, 4, 915
754 sizeof(ngx_str_t)) 916
755 != NGX_OK) 917 /* check conflicts in wildcard hash */
756 { 918
757 return NGX_ERROR; 919 name = keys->elts;
758 } 920
759 } 921 if (name) {
760 922 len = last - skip;
761 name = ngx_array_push(&ha->dns_wildcards_hash[k]); 923
762 if (name == NULL) { 924 for (i = 0; i < keys->nelts; i++) {
763 return NGX_ERROR; 925 if (len != name[i].len) {
764 } 926 continue;
765 927 }
766 name->len = key->len - skip; 928
767 name->data = ngx_palloc(ha->temp_pool, name->len); 929 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) {
768 if (name->data == NULL) { 930 return NGX_BUSY;
769 return NGX_ERROR; 931 }
770 } 932 }
771 933
772 ngx_memcpy(name->data, key->data + skip, name->len); 934 } else {
773 } 935 if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK)
936 {
937 return NGX_ERROR;
938 }
939 }
940
941 name = ngx_array_push(keys);
942 if (name == NULL) {
943 return NGX_ERROR;
944 }
945
946 name->len = last - skip;
947 name->data = ngx_palloc(ha->temp_pool, name->len);
948 if (name->data == NULL) {
949 return NGX_ERROR;
950 }
951
952 ngx_memcpy(name->data, key->data + skip, name->len);
774 953
775 return NGX_OK; 954 return NGX_OK;
776 } 955 }