nxt_http_parse.c (410:35d3565882ac) nxt_http_parse.c (417:47366bb40f2c)
1
2/*
3 * Copyright (C) NGINX, Inc.
4 * Copyright (C) Valentin V. Bartenev
5 */
6
7#include <nxt_main.h>
8
9
1
2/*
3 * Copyright (C) NGINX, Inc.
4 * Copyright (C) Valentin V. Bartenev
5 */
6
7#include <nxt_main.h>
8
9
10typedef struct {
11 nxt_http_field_handler_t handler;
12 uintptr_t data;
13
14 union {
15 uint8_t str[8];
16 uint64_t ui64;
17 } key[];
18} nxt_http_fields_hash_elt_t;
19
20
21struct nxt_http_fields_hash_s {
22 size_t min_length;
23 size_t max_length;
24 void *long_fields;
25 nxt_http_fields_hash_elt_t *elts[];
26};
27
28
29#define nxt_http_fields_hash_next_elt(elt, n) \
30 ((nxt_http_fields_hash_elt_t *) ((u_char *) (elt) \
31 + sizeof(nxt_http_fields_hash_elt_t) \
32 + n * 8))
33
34
35static nxt_int_t nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp,
36 u_char **pos, u_char *end);
37static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp,
38 u_char **pos, u_char *end);
39static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp,
40 u_char **pos, u_char *end);
41static nxt_int_t nxt_http_parse_field_value(nxt_http_request_parse_t *rp,
42 u_char **pos, u_char *end);
43static u_char *nxt_http_lookup_field_end(u_char *p, u_char *end);
44static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp,
45 u_char **pos, u_char *end);
46
10static nxt_int_t nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp,
11 u_char **pos, u_char *end);
12static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp,
13 u_char **pos, u_char *end);
14static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp,
15 u_char **pos, u_char *end);
16static nxt_int_t nxt_http_parse_field_value(nxt_http_request_parse_t *rp,
17 u_char **pos, u_char *end);
18static u_char *nxt_http_lookup_field_end(u_char *p, u_char *end);
19static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp,
20 u_char **pos, u_char *end);
21
47static void nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *hash,
48 uint64_t key[4], nxt_http_field_t *field);
49static void nxt_http_fields_hash_lookup_long(nxt_http_fields_hash_t *hash,
50 nxt_http_field_t *field);
51
52static nxt_int_t nxt_http_parse_complex_target(nxt_http_request_parse_t *rp);
53
22static nxt_int_t nxt_http_parse_complex_target(nxt_http_request_parse_t *rp);
23
24static nxt_int_t nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data);
25static void *nxt_http_field_hash_alloc(void *pool, size_t size);
26static void nxt_http_field_hash_free(void *pool, void *p);
54
27
28static nxt_int_t nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq,
29 void *data);
30
31
32#define NXT_HTTP_MAX_FIELD_NAME 0xff
33#define NXT_HTTP_MAX_FIELD_VALUE NXT_INT32_T_MAX
34
35#define NXT_HTTP_FIELD_LVLHSH_SHIFT 5
36
37#define NXT_HTTP_FIELD_HASH_INIT 159406
38#define nxt_http_field_hash_char(h, c) (((h) << 4) + (h) + (c))
39#define nxt_http_field_hash_end(h) (((h) >> 16) ^ (h))
40
41
55typedef enum {
56 NXT_HTTP_TARGET_SPACE = 1, /* \s */
57 NXT_HTTP_TARGET_HASH, /* # */
58 NXT_HTTP_TARGET_AGAIN,
59 NXT_HTTP_TARGET_BAD, /* \0\r\n */
60
61 /* traps below are used for extended check only */
62

--- 59 unchanged lines hidden (view full) ---

122 nxt_target_test_char(*p); p++;
123 }
124
125 return NXT_HTTP_TARGET_AGAIN;
126}
127
128
129nxt_int_t
42typedef enum {
43 NXT_HTTP_TARGET_SPACE = 1, /* \s */
44 NXT_HTTP_TARGET_HASH, /* # */
45 NXT_HTTP_TARGET_AGAIN,
46 NXT_HTTP_TARGET_BAD, /* \0\r\n */
47
48 /* traps below are used for extended check only */
49

--- 59 unchanged lines hidden (view full) ---

109 nxt_target_test_char(*p); p++;
110 }
111
112 return NXT_HTTP_TARGET_AGAIN;
113}
114
115
116nxt_int_t
117nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp)
118{
119 rp->mem_pool = mp;
120
121 rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t));
122 if (nxt_slow_path(rp->fields == NULL)){
123 return NXT_ERROR;
124 }
125
126 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
127
128 return NXT_OK;
129}
130
131
132nxt_int_t
130nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
131{
132 nxt_int_t rc;
133
134 if (rp->handler == NULL) {
135 rp->handler = &nxt_http_parse_request_line;
136 }
137

--- 337 unchanged lines hidden (view full) ---

475 return NXT_ERROR;
476}
477
478
479static nxt_int_t
480nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
481 u_char *end)
482{
133nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
134{
135 nxt_int_t rc;
136
137 if (rp->handler == NULL) {
138 rp->handler = &nxt_http_parse_request_line;
139 }
140

--- 337 unchanged lines hidden (view full) ---

478 return NXT_ERROR;
479}
480
481
482static nxt_int_t
483nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
484 u_char *end)
485{
483 u_char *p, ch, c;
484 size_t i, size;
486 u_char *p, c;
487 size_t len;
488 uint32_t hash;
485
486 static const u_char normal[256] nxt_aligned(64) =
487 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
488 "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0"
489
490 /* These 64 bytes should reside in one cache line. */
491 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
492 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
493
494 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
495 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
496 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
497 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
498
489
490 static const u_char normal[256] nxt_aligned(64) =
491 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
492 "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0"
493
494 /* These 64 bytes should reside in one cache line. */
495 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
496 "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
497
498 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
499 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
500 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
501 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
502
499 p = *pos;
503 p = *pos + rp->field_name.length;
504 hash = rp->field_hash;
500
505
501 size = end - p;
502 i = rp->field_name.length;
506 while (nxt_fast_path(end - p >= 8)) {
503
507
504 while (nxt_fast_path(size - i >= 8)) {
505
506#define nxt_field_name_test_char(i) \
508#define nxt_field_name_test_char(ch) \
507 \
509 \
508 ch = p[i]; \
509 c = normal[ch]; \
510 \
511 if (nxt_slow_path(c == '\0')) { \
510 c = normal[ch]; \
511 \
512 if (nxt_slow_path(c == '\0')) { \
513 p = &(ch); \
512 goto name_end; \
513 } \
514 \
514 goto name_end; \
515 } \
516 \
515 rp->field_key.str[i % 32] = c;
517 hash = nxt_http_field_hash_char(hash, c);
516
517/* enddef */
518
518
519/* enddef */
520
519 nxt_field_name_test_char(i); i++;
520 nxt_field_name_test_char(i); i++;
521 nxt_field_name_test_char(i); i++;
522 nxt_field_name_test_char(i); i++;
521 nxt_field_name_test_char(p[0]);
522 nxt_field_name_test_char(p[1]);
523 nxt_field_name_test_char(p[2]);
524 nxt_field_name_test_char(p[3]);
523
525
524 nxt_field_name_test_char(i); i++;
525 nxt_field_name_test_char(i); i++;
526 nxt_field_name_test_char(i); i++;
527 nxt_field_name_test_char(i); i++;
526 nxt_field_name_test_char(p[4]);
527 nxt_field_name_test_char(p[5]);
528 nxt_field_name_test_char(p[6]);
529 nxt_field_name_test_char(p[7]);
530
531 p += 8;
528 }
529
532 }
533
530 while (nxt_fast_path(i != size)) {
531 nxt_field_name_test_char(i); i++;
534 while (nxt_fast_path(p != end)) {
535 nxt_field_name_test_char(*p); p++;
532 }
533
536 }
537
534 rp->field_name.length = i;
538 len = p - *pos;
539
540 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
541 return NXT_ERROR;
542 }
543
544 rp->field_hash = hash;
545 rp->field_name.length = len;
546
535 rp->handler = &nxt_http_parse_field_name;
536
537 return NXT_AGAIN;
538
539name_end:
540
547 rp->handler = &nxt_http_parse_field_name;
548
549 return NXT_AGAIN;
550
551name_end:
552
541 if (nxt_fast_path(ch == ':')) {
542 if (nxt_slow_path(i == 0)) {
553 if (nxt_fast_path(*p == ':')) {
554 if (nxt_slow_path(p == *pos)) {
543 return NXT_ERROR;
544 }
545
555 return NXT_ERROR;
556 }
557
546 *pos = &p[i] + 1;
558 len = p - *pos;
547
559
548 rp->field_name.length = i;
549 rp->field_name.start = p;
560 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
561 return NXT_ERROR;
562 }
550
563
564 rp->field_hash = hash;
565
566 rp->field_name.length = len;
567 rp->field_name.start = *pos;
568
569 *pos = p + 1;
570
551 return nxt_http_parse_field_value(rp, pos, end);
552 }
553
571 return nxt_http_parse_field_value(rp, pos, end);
572 }
573
554 if (nxt_slow_path(i != 0)) {
574 if (nxt_slow_path(p != *pos)) {
555 return NXT_ERROR;
556 }
557
558 return nxt_http_parse_field_end(rp, pos, end);
559}
560
561
562static nxt_int_t
563nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
564 u_char *end)
565{
566 u_char *p, ch;
575 return NXT_ERROR;
576 }
577
578 return nxt_http_parse_field_end(rp, pos, end);
579}
580
581
582static nxt_int_t
583nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
584 u_char *end)
585{
586 u_char *p, ch;
587 size_t len;
567
568 p = *pos;
569
570 for ( ;; ) {
571 if (nxt_slow_path(p == end)) {
572 *pos = p;
573 rp->handler = &nxt_http_parse_field_value;
574 return NXT_AGAIN;

--- 9 unchanged lines hidden (view full) ---

584 *pos = p;
585
586 p += rp->field_value.length;
587
588 for ( ;; ) {
589 p = nxt_http_lookup_field_end(p, end);
590
591 if (nxt_slow_path(p == end)) {
588
589 p = *pos;
590
591 for ( ;; ) {
592 if (nxt_slow_path(p == end)) {
593 *pos = p;
594 rp->handler = &nxt_http_parse_field_value;
595 return NXT_AGAIN;

--- 9 unchanged lines hidden (view full) ---

605 *pos = p;
606
607 p += rp->field_value.length;
608
609 for ( ;; ) {
610 p = nxt_http_lookup_field_end(p, end);
611
612 if (nxt_slow_path(p == end)) {
592 rp->field_value.length = p - *pos;
613 len = p - *pos;
614
615 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
616 return NXT_ERROR;
617 }
618
619 rp->field_value.length = len;
593 rp->handler = &nxt_http_parse_field_value;
594 return NXT_AGAIN;
595 }
596
597 ch = *p;
598
599 if (nxt_fast_path(ch == '\r' || ch == '\n')) {
600 break;

--- 5 unchanged lines hidden (view full) ---

606 }
607
608 if (nxt_fast_path(p != *pos)) {
609 while (p[-1] == ' ') {
610 p--;
611 }
612 }
613
620 rp->handler = &nxt_http_parse_field_value;
621 return NXT_AGAIN;
622 }
623
624 ch = *p;
625
626 if (nxt_fast_path(ch == '\r' || ch == '\n')) {
627 break;

--- 5 unchanged lines hidden (view full) ---

633 }
634
635 if (nxt_fast_path(p != *pos)) {
636 while (p[-1] == ' ') {
637 p--;
638 }
639 }
640
614 rp->field_value.length = p - *pos;
641 len = p - *pos;
642
643 if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
644 return NXT_ERROR;
645 }
646
647 rp->field_value.length = len;
615 rp->field_value.start = *pos;
616
617 *pos = p;
618
619 return nxt_http_parse_field_end(rp, pos, end);
620}
621
622

--- 86 unchanged lines hidden (view full) ---

709
710 if (rp->field_name.length != 0) {
711 field = nxt_list_add(rp->fields);
712
713 if (nxt_slow_path(field == NULL)) {
714 return NXT_ERROR;
715 }
716
648 rp->field_value.start = *pos;
649
650 *pos = p;
651
652 return nxt_http_parse_field_end(rp, pos, end);
653}
654
655

--- 86 unchanged lines hidden (view full) ---

742
743 if (rp->field_name.length != 0) {
744 field = nxt_list_add(rp->fields);
745
746 if (nxt_slow_path(field == NULL)) {
747 return NXT_ERROR;
748 }
749
717 field->name = rp->field_name;
718 field->value = rp->field_value;
750 field->hash = nxt_http_field_hash_end(rp->field_hash);
751 field->skip = 0;
719
752
720 nxt_http_fields_hash_lookup(rp->fields_hash, rp->field_key.ui64,
721 field);
753 field->name_length = rp->field_name.length;
754 field->value_length = rp->field_value.length;
755 field->name = rp->field_name.start;
756 field->value = rp->field_value.start;
722
757
723 nxt_memzero(rp->field_key.str, 32);
758 rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
724
725 rp->field_name.length = 0;
726 rp->field_value.length = 0;
727
728 rp->handler = &nxt_http_parse_field_name;
729 return NXT_OK;
730 }
731
732 return NXT_DONE;
733 }
734
735 return NXT_ERROR;
736}
737
738
759
760 rp->field_name.length = 0;
761 rp->field_value.length = 0;
762
763 rp->handler = &nxt_http_parse_field_name;
764 return NXT_OK;
765 }
766
767 return NXT_DONE;
768 }
769
770 return NXT_ERROR;
771}
772
773
739nxt_http_fields_hash_t *
740nxt_http_fields_hash_create(nxt_http_fields_hash_entry_t *entries,
741 nxt_mp_t *mp)
742{
743 size_t min_length, max_length, length, size;
744 nxt_uint_t i, j, n;
745 nxt_http_fields_hash_t *hash;
746 nxt_http_fields_hash_elt_t *elt;
747
748 min_length = 32 + 1;
749 max_length = 0;
750
751 for (i = 0; entries[i].handler != NULL; i++) {
752 length = entries[i].name.length;
753
754 if (length > 32) {
755 /* TODO */
756 return NULL;
757 }
758
759 min_length = nxt_min(length, min_length);
760 max_length = nxt_max(length, max_length);
761 }
762
763 size = sizeof(nxt_http_fields_hash_t);
764
765 if (min_length <= 32) {
766 size += (max_length - min_length + 1)
767 * sizeof(nxt_http_fields_hash_elt_t *);
768 }
769
770 hash = nxt_mp_zget(mp, size);
771 if (nxt_slow_path(hash == NULL)) {
772 return NULL;
773 }
774
775 hash->min_length = min_length;
776 hash->max_length = max_length;
777
778 for (i = 0; entries[i].handler != NULL; i++) {
779 length = entries[i].name.length;
780 elt = hash->elts[length - min_length];
781
782 if (elt != NULL) {
783 continue;
784 }
785
786 n = 1;
787
788 for (j = i + 1; entries[j].handler != NULL; j++) {
789 if (length == entries[j].name.length) {
790 n++;
791 }
792 }
793
794 size = sizeof(nxt_http_fields_hash_elt_t) + nxt_align_size(length, 8);
795
796 elt = nxt_mp_zget(mp, n * size + sizeof(nxt_http_fields_hash_elt_t));
797
798 if (nxt_slow_path(elt == NULL)) {
799 return NULL;
800 }
801
802 hash->elts[length - min_length] = elt;
803
804 for (j = i; entries[j].handler != NULL; j++) {
805 if (length != entries[j].name.length) {
806 continue;
807 }
808
809 elt->handler = entries[j].handler;
810 elt->data = entries[j].data;
811
812 nxt_memcpy_lowcase(elt->key->str, entries[j].name.start, length);
813
814 n--;
815
816 if (n == 0) {
817 break;
818 }
819
820 elt = nxt_pointer_to(elt, size);
821 }
822 }
823
824 return hash;
825}
826
827
828static void
829nxt_http_fields_hash_lookup(nxt_http_fields_hash_t *hash, uint64_t key[4],
830 nxt_http_field_t *field)
831{
832 nxt_http_fields_hash_elt_t *elt;
833
834 if (hash == NULL || field->name.length < hash->min_length) {
835 goto not_found;
836 }
837
838 if (field->name.length > hash->max_length) {
839
840 if (field->name.length > 32 && hash->long_fields != NULL) {
841 nxt_http_fields_hash_lookup_long(hash, field);
842 return;
843 }
844
845 goto not_found;
846 }
847
848 elt = hash->elts[field->name.length - hash->min_length];
849
850 if (elt == NULL) {
851 goto not_found;
852 }
853
854 switch ((field->name.length + 7) / 8) {
855 case 1:
856 do {
857 if (elt->key[0].ui64 == key[0]) {
858 break;
859 }
860
861 elt = nxt_http_fields_hash_next_elt(elt, 1);
862
863 } while (elt->handler != NULL);
864
865 break;
866
867 case 2:
868 do {
869 if (elt->key[0].ui64 == key[0]
870 && elt->key[1].ui64 == key[1])
871 {
872 break;
873 }
874
875 elt = nxt_http_fields_hash_next_elt(elt, 2);
876
877 } while (elt->handler != NULL);
878
879 break;
880
881 case 3:
882 do {
883 if (elt->key[0].ui64 == key[0]
884 && elt->key[1].ui64 == key[1]
885 && elt->key[2].ui64 == key[2])
886 {
887 break;
888 }
889
890 elt = nxt_http_fields_hash_next_elt(elt, 3);
891
892 } while (elt->handler != NULL);
893
894 break;
895
896 case 4:
897 do {
898 if (elt->key[0].ui64 == key[0]
899 && elt->key[1].ui64 == key[1]
900 && elt->key[2].ui64 == key[2]
901 && elt->key[3].ui64 == key[3])
902 {
903 break;
904 }
905
906 elt = nxt_http_fields_hash_next_elt(elt, 4);
907
908 } while (elt->handler != NULL);
909
910 break;
911
912 default:
913 nxt_unreachable();
914 }
915
916 field->handler = elt->handler;
917 field->data = elt->data;
918
919 return;
920
921not_found:
922
923 field->handler = NULL;
924 field->data = 0;
925}
926
927
928static void
929nxt_http_fields_hash_lookup_long(nxt_http_fields_hash_t *hash,
930 nxt_http_field_t *field)
931{
932 /* TODO */
933
934 field->handler = NULL;
935 field->data = 0;
936}
937
938
939nxt_int_t
940nxt_http_fields_process(nxt_list_t *fields, void *ctx, nxt_log_t *log)
941{
942 nxt_int_t rc;
943 nxt_http_field_t *field;
944
945 nxt_list_each(field, fields) {
946
947 if (field->handler != NULL) {
948 rc = field->handler(ctx, field, log);
949
950 if (rc != NXT_OK) {
951 return rc;
952 }
953 }
954
955 } nxt_list_loop;
956
957 return NXT_OK;
958}
959
960
961#define \
962nxt_http_is_normal(c) \
963 (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
964
965
966static const uint8_t nxt_http_normal[32] nxt_aligned(32) = {
967
968 /* \0 \r \n */

--- 286 unchanged lines hidden (view full) ---

1255
1256 if (rp->exten_start) {
1257 rp->exten.length = u - rp->exten_start;
1258 rp->exten.start = rp->exten_start;
1259 }
1260
1261 return NXT_OK;
1262}
774#define \
775nxt_http_is_normal(c) \
776 (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
777
778
779static const uint8_t nxt_http_normal[32] nxt_aligned(32) = {
780
781 /* \0 \r \n */

--- 286 unchanged lines hidden (view full) ---

1068
1069 if (rp->exten_start) {
1070 rp->exten.length = u - rp->exten_start;
1071 rp->exten.start = rp->exten_start;
1072 }
1073
1074 return NXT_OK;
1075}
1076
1077
1078static const nxt_lvlhsh_proto_t nxt_http_fields_hash_proto nxt_aligned(64) = {
1079 NXT_LVLHSH_BUCKET_SIZE(64),
1080 { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 },
1081 nxt_http_field_hash_test,
1082 nxt_http_field_hash_alloc,
1083 nxt_http_field_hash_free,
1084};
1085
1086
1087static nxt_int_t
1088nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data)
1089{
1090 nxt_http_field_proc_t *field;
1091
1092 field = data;
1093
1094 if (nxt_strcasestr_eq(&lhq->key, &field->name)) {
1095 return NXT_OK;
1096 }
1097
1098 return NXT_DECLINED;
1099}
1100
1101
1102static void *
1103nxt_http_field_hash_alloc(void *pool, size_t size)
1104{
1105 return nxt_mp_align(pool, size, size);
1106}
1107
1108
1109static void
1110nxt_http_field_hash_free(void *pool, void *p)
1111{
1112 nxt_mp_free(pool, p);
1113}
1114
1115
1116static nxt_int_t
1117nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data)
1118{
1119 return NXT_OK;
1120}
1121
1122
1123nxt_int_t
1124nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1125 nxt_http_field_proc_t items[], nxt_uint_t count)
1126{
1127 u_char ch;
1128 uint32_t key;
1129 nxt_str_t *name;
1130 nxt_int_t ret;
1131 nxt_uint_t i, j;
1132 nxt_lvlhsh_query_t lhq;
1133
1134 lhq.replace = 0;
1135 lhq.proto = &nxt_http_fields_hash_proto;
1136 lhq.pool = mp;
1137
1138 for (i = 0; i < count; i++) {
1139 key = NXT_HTTP_FIELD_HASH_INIT;
1140 name = &items[i].name;
1141
1142 for (j = 0; j < name->length; j++) {
1143 ch = nxt_lowcase(name->start[j]);
1144 key = nxt_http_field_hash_char(key, ch);
1145 }
1146
1147 lhq.key_hash = nxt_http_field_hash_end(key) & 0xffff;
1148 lhq.key = *name;
1149 lhq.value = &items[i];
1150
1151 ret = nxt_lvlhsh_insert(hash, &lhq);
1152
1153 if (nxt_slow_path(ret != NXT_OK)) {
1154 return NXT_ERROR;
1155 }
1156 }
1157
1158 return NXT_OK;
1159}
1160
1161
1162nxt_uint_t
1163nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1164 nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level)
1165{
1166 u_char ch;
1167 uint32_t key, mask;
1168 nxt_str_t *name;
1169 nxt_uint_t colls, i, j;
1170 nxt_lvlhsh_proto_t proto;
1171 nxt_lvlhsh_query_t lhq;
1172
1173 proto = nxt_http_fields_hash_proto;
1174 proto.test = nxt_http_field_hash_collision;
1175
1176 lhq.replace = 0;
1177 lhq.proto = &proto;
1178 lhq.pool = mp;
1179
1180 mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xffff;
1181
1182 colls = 0;
1183
1184 for (i = 0; i < count; i++) {
1185 key = NXT_HTTP_FIELD_HASH_INIT;
1186 name = &items[i].name;
1187
1188 for (j = 0; j < name->length; j++) {
1189 ch = nxt_lowcase(name->start[j]);
1190 key = nxt_http_field_hash_char(key, ch);
1191 }
1192
1193 lhq.key_hash = nxt_http_field_hash_end(key) & mask;
1194
1195 if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) {
1196 colls++;
1197 }
1198 }
1199
1200 return colls;
1201}
1202
1203
1204nxt_int_t
1205nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx)
1206{
1207 nxt_int_t ret;
1208 nxt_http_field_t *field;
1209 nxt_lvlhsh_query_t lhq;
1210 nxt_http_field_proc_t *proc;
1211
1212 lhq.proto = &nxt_http_fields_hash_proto;
1213
1214 nxt_list_each(field, fields) {
1215
1216 lhq.key_hash = field->hash;
1217 lhq.key.length = field->name_length;
1218 lhq.key.start = field->name;
1219
1220 if (nxt_lvlhsh_find(hash, &lhq) != NXT_OK) {
1221 continue;
1222 }
1223
1224 proc = lhq.value;
1225
1226 ret = proc->handler(ctx, field, proc->data);
1227
1228 if (nxt_slow_path(ret != NXT_OK)) {
1229 return ret;
1230 }
1231
1232 } nxt_list_loop;
1233
1234 return NXT_OK;
1235}