Mercurial > hg > nginx-vendor-0-7
comparison src/core/ngx_hash.c @ 312:429900ca25ee NGINX_0_6_0
nginx 0.6.0
*) Feature: the "server_name", "map", and "valid_referers" directives
support the "www.example.*" wildcards.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Thu, 14 Jun 2007 00:00:00 +0400 |
parents | ff906029dd40 |
children | 5e3b425174f6 |
comparison
equal
deleted
inserted
replaced
311:fcb663e92663 | 312:429900ca25ee |
---|---|
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) { | |
627 return NGX_ERROR; | 844 return NGX_ERROR; |
628 } | 845 } |
629 | 846 |
630 hk->key = *key; | 847 ngx_memcpy(name->data, &key->data[1], name->len); |
631 hk->key_hash = ngx_hash_key(key->data, key->len); | 848 } |
632 hk->value = value; | 849 |
633 | 850 |
634 } else { | 851 if (skip) { |
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 |
888 } else { | |
889 | |
890 /* convert "www.example.*" to "www.example\0" */ | |
891 | |
892 p = key->data; | |
893 key->data[last] = '\0'; | |
894 last++; | |
895 | |
896 hwc = &ha->dns_wc_tail; | |
897 keys = &ha->dns_wc_tail_hash[k]; | |
898 } | |
899 | |
900 | |
901 hk = ngx_array_push(hwc); | |
902 if (hk == NULL) { | |
903 return NGX_ERROR; | |
904 } | |
905 | |
906 hk->key.len = last - 1; | |
907 hk->key.data = p; | |
908 hk->key_hash = 0; | |
909 hk->value = value; | |
910 | |
911 | |
912 /* check conflicts in wildcard hash */ | |
913 | |
914 name = keys->elts; | |
915 | |
916 if (name) { | |
917 len = last - skip; | |
918 | |
919 for (i = 0; i < keys->nelts; i++) { | |
920 if (len != name[i].len) { | |
921 continue; | |
922 } | |
923 | |
924 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) { | |
925 return NGX_BUSY; | |
926 } | |
927 } | |
928 | |
929 } else { | |
930 if (ngx_array_init(keys, ha->temp_pool, 4, sizeof(ngx_str_t)) != NGX_OK) | |
931 { | |
726 return NGX_ERROR; | 932 return NGX_ERROR; |
727 } | 933 } |
728 | 934 } |
729 hk->key.len = key->len - 1; | 935 |
730 hk->key.data = reverse; | 936 name = ngx_array_push(keys); |
731 hk->key_hash = 0; | 937 if (name == NULL) { |
732 hk->value = value; | 938 return NGX_ERROR; |
733 | 939 } |
734 | 940 |
735 /* check conflicts in wildcard hash */ | 941 name->len = last - skip; |
736 | 942 name->data = ngx_palloc(ha->temp_pool, name->len); |
737 name = ha->dns_wildcards_hash[k].elts; | 943 if (name->data == NULL) { |
738 | 944 return NGX_ERROR; |
739 if (name) { | 945 } |
740 len = key->len - skip; | 946 |
741 | 947 ngx_memcpy(name->data, key->data + skip, name->len); |
742 for (i = 0; i < ha->dns_wildcards_hash[k].nelts; i++) { | |
743 if (len != name[i].len) { | |
744 continue; | |
745 } | |
746 | |
747 if (ngx_strncmp(key->data + skip, name[i].data, len) == 0) { | |
748 return NGX_BUSY; | |
749 } | |
750 } | |
751 | |
752 } else { | |
753 if (ngx_array_init(&ha->dns_wildcards_hash[k], ha->temp_pool, 4, | |
754 sizeof(ngx_str_t)) | |
755 != NGX_OK) | |
756 { | |
757 return NGX_ERROR; | |
758 } | |
759 } | |
760 | |
761 name = ngx_array_push(&ha->dns_wildcards_hash[k]); | |
762 if (name == NULL) { | |
763 return NGX_ERROR; | |
764 } | |
765 | |
766 name->len = key->len - skip; | |
767 name->data = ngx_palloc(ha->temp_pool, name->len); | |
768 if (name->data == NULL) { | |
769 return NGX_ERROR; | |
770 } | |
771 | |
772 ngx_memcpy(name->data, key->data + skip, name->len); | |
773 } | |
774 | 948 |
775 return NGX_OK; | 949 return NGX_OK; |
776 } | 950 } |