1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package io.netty5.handler.codec;
16
17 import io.netty5.util.HashingStrategy;
18
19 import java.util.Arrays;
20 import java.util.Collections;
21 import java.util.Iterator;
22 import java.util.LinkedHashSet;
23 import java.util.LinkedList;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.Map.Entry;
27 import java.util.NoSuchElementException;
28 import java.util.Set;
29
30 import static io.netty5.util.HashingStrategy.JAVA_HASHER;
31 import static io.netty5.util.internal.MathUtil.findNextPositivePowerOfTwo;
32 import static java.lang.Math.max;
33 import static java.lang.Math.min;
34 import static java.util.Objects.requireNonNull;
35
36
37
38
39
40
41
42
43 public class DefaultHeaders<K, V, T extends Headers<K, V, T>> implements Headers<K, V, T> {
44
45
46
47 static final int HASH_CODE_SEED = 0xc2b2ae35;
48
49 private final HeaderEntry<K, V>[] entries;
50 protected final HeaderEntry<K, V> head;
51
52 private final byte hashMask;
53 private final ValueConverter<V> valueConverter;
54 private final NameValidator<K> nameValidator;
55 private final HashingStrategy<K> hashingStrategy;
56 int size;
57
58 public interface NameValidator<K> {
59
60
61
62
63
64 void validateName(K name);
65
66 @SuppressWarnings("rawtypes")
67 NameValidator NOT_NULL = name -> requireNonNull(name, "name");
68 }
69
70 @SuppressWarnings("unchecked")
71 public DefaultHeaders(ValueConverter<V> valueConverter) {
72 this(JAVA_HASHER, valueConverter);
73 }
74
75 @SuppressWarnings("unchecked")
76 public DefaultHeaders(ValueConverter<V> valueConverter, NameValidator<K> nameValidator) {
77 this(JAVA_HASHER, valueConverter, nameValidator);
78 }
79
80 @SuppressWarnings("unchecked")
81 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy, ValueConverter<V> valueConverter) {
82 this(nameHashingStrategy, valueConverter, NameValidator.NOT_NULL);
83 }
84
85 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy,
86 ValueConverter<V> valueConverter, NameValidator<K> nameValidator) {
87 this(nameHashingStrategy, valueConverter, nameValidator, 16);
88 }
89
90
91
92
93
94
95
96
97
98 @SuppressWarnings("unchecked")
99 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy,
100 ValueConverter<V> valueConverter, NameValidator<K> nameValidator, int arraySizeHint) {
101 this.valueConverter = requireNonNull(valueConverter, "valueConverter");
102 this.nameValidator = requireNonNull(nameValidator, "nameValidator");
103 this.hashingStrategy = requireNonNull(nameHashingStrategy, "nameHashingStrategy");
104
105
106 entries = new DefaultHeaders.HeaderEntry[findNextPositivePowerOfTwo(max(2, min(arraySizeHint, 128)))];
107 hashMask = (byte) (entries.length - 1);
108 head = new HeaderEntry<>();
109 }
110
111 @Override
112 public V get(K name) {
113 requireNonNull(name, "name");
114
115 int h = hashingStrategy.hashCode(name);
116 int i = index(h);
117 HeaderEntry<K, V> e = entries[i];
118 V value = null;
119
120 while (e != null) {
121 if (e.hash == h && hashingStrategy.equals(name, e.key)) {
122 value = e.value;
123 }
124
125 e = e.next;
126 }
127 return value;
128 }
129
130 @Override
131 public V get(K name, V defaultValue) {
132 V value = get(name);
133 if (value == null) {
134 return defaultValue;
135 }
136 return value;
137 }
138
139 @Override
140 public V getAndRemove(K name) {
141 int h = hashingStrategy.hashCode(name);
142 return remove0(h, index(h), requireNonNull(name, "name"));
143 }
144
145 @Override
146 public V getAndRemove(K name, V defaultValue) {
147 V value = getAndRemove(name);
148 if (value == null) {
149 return defaultValue;
150 }
151 return value;
152 }
153
154 @Override
155 public List<V> getAll(K name) {
156 requireNonNull(name, "name");
157
158 int h = hashingStrategy.hashCode(name);
159 int i = index(h);
160 HeaderEntry<K, V> e = entries[i];
161
162 if (e == null) {
163 return Collections.emptyList();
164 }
165
166 LinkedList<V> values = new LinkedList<>();
167
168 do {
169 if (e.hash == h && hashingStrategy.equals(name, e.key)) {
170 values.addFirst(e.getValue());
171 }
172 e = e.next;
173 } while (e != null);
174 return values;
175 }
176
177
178
179
180
181
182 public Iterator<V> valueIterator(K name) {
183 return new ValueIterator(name);
184 }
185
186 @Override
187 public List<V> getAllAndRemove(K name) {
188 List<V> all = getAll(name);
189 remove(name);
190 return all;
191 }
192
193 @Override
194 public boolean contains(K name) {
195 return get(name) != null;
196 }
197
198 @Override
199 public boolean containsObject(K name, Object value) {
200 return contains(name, valueConverter.convertObject(requireNonNull(value, "value")));
201 }
202
203 @Override
204 public boolean containsBoolean(K name, boolean value) {
205 return contains(name, valueConverter.convertBoolean(value));
206 }
207
208 @Override
209 public boolean containsByte(K name, byte value) {
210 return contains(name, valueConverter.convertByte(value));
211 }
212
213 @Override
214 public boolean containsChar(K name, char value) {
215 return contains(name, valueConverter.convertChar(value));
216 }
217
218 @Override
219 public boolean containsShort(K name, short value) {
220 return contains(name, valueConverter.convertShort(value));
221 }
222
223 @Override
224 public boolean containsInt(K name, int value) {
225 return contains(name, valueConverter.convertInt(value));
226 }
227
228 @Override
229 public boolean containsLong(K name, long value) {
230 return contains(name, valueConverter.convertLong(value));
231 }
232
233 @Override
234 public boolean containsFloat(K name, float value) {
235 return contains(name, valueConverter.convertFloat(value));
236 }
237
238 @Override
239 public boolean containsDouble(K name, double value) {
240 return contains(name, valueConverter.convertDouble(value));
241 }
242
243 @Override
244 public boolean containsTimeMillis(K name, long value) {
245 return contains(name, valueConverter.convertTimeMillis(value));
246 }
247
248 @SuppressWarnings("unchecked")
249 @Override
250 public boolean contains(K name, V value) {
251 return contains(name, value, JAVA_HASHER);
252 }
253
254 public final boolean contains(K name, V value, HashingStrategy<? super V> valueHashingStrategy) {
255 requireNonNull(name, "name");
256
257 int h = hashingStrategy.hashCode(name);
258 int i = index(h);
259 HeaderEntry<K, V> e = entries[i];
260 while (e != null) {
261 if (e.hash == h && hashingStrategy.equals(name, e.key) && valueHashingStrategy.equals(value, e.value)) {
262 return true;
263 }
264 e = e.next;
265 }
266 return false;
267 }
268
269 @Override
270 public int size() {
271 return size;
272 }
273
274 @Override
275 public boolean isEmpty() {
276 return head == head.after;
277 }
278
279 @Override
280 public Set<K> names() {
281 if (isEmpty()) {
282 return Collections.emptySet();
283 }
284 Set<K> names = new LinkedHashSet<>(size());
285 HeaderEntry<K, V> e = head.after;
286 while (e != head) {
287 names.add(e.getKey());
288 e = e.after;
289 }
290 return names;
291 }
292
293 @Override
294 public T add(K name, V value) {
295 nameValidator.validateName(name);
296 requireNonNull(value, "value");
297 int h = hashingStrategy.hashCode(name);
298 int i = index(h);
299 add0(h, i, name, value);
300 return thisT();
301 }
302
303 @Override
304 public T add(K name, Iterable<? extends V> values) {
305 nameValidator.validateName(name);
306 int h = hashingStrategy.hashCode(name);
307 int i = index(h);
308 for (V v: values) {
309 add0(h, i, name, v);
310 }
311 return thisT();
312 }
313
314 @Override
315 public T add(K name, V... values) {
316 nameValidator.validateName(name);
317 int h = hashingStrategy.hashCode(name);
318 int i = index(h);
319 for (V v: values) {
320 add0(h, i, name, v);
321 }
322 return thisT();
323 }
324
325 @Override
326 public T addObject(K name, Object value) {
327 return add(name, valueConverter.convertObject(requireNonNull(value, "value")));
328 }
329
330 @Override
331 public T addObject(K name, Iterable<?> values) {
332 for (Object value : values) {
333 addObject(name, value);
334 }
335 return thisT();
336 }
337
338 @Override
339 public T addObject(K name, Object... values) {
340 for (Object value: values) {
341 addObject(name, value);
342 }
343 return thisT();
344 }
345
346 @Override
347 public T addInt(K name, int value) {
348 return add(name, valueConverter.convertInt(value));
349 }
350
351 @Override
352 public T addLong(K name, long value) {
353 return add(name, valueConverter.convertLong(value));
354 }
355
356 @Override
357 public T addDouble(K name, double value) {
358 return add(name, valueConverter.convertDouble(value));
359 }
360
361 @Override
362 public T addTimeMillis(K name, long value) {
363 return add(name, valueConverter.convertTimeMillis(value));
364 }
365
366 @Override
367 public T addChar(K name, char value) {
368 return add(name, valueConverter.convertChar(value));
369 }
370
371 @Override
372 public T addBoolean(K name, boolean value) {
373 return add(name, valueConverter.convertBoolean(value));
374 }
375
376 @Override
377 public T addFloat(K name, float value) {
378 return add(name, valueConverter.convertFloat(value));
379 }
380
381 @Override
382 public T addByte(K name, byte value) {
383 return add(name, valueConverter.convertByte(value));
384 }
385
386 @Override
387 public T addShort(K name, short value) {
388 return add(name, valueConverter.convertShort(value));
389 }
390
391 @Override
392 public T add(Headers<? extends K, ? extends V, ?> headers) {
393 if (headers == this) {
394 throw new IllegalArgumentException("can't add to itself.");
395 }
396 addImpl(headers);
397 return thisT();
398 }
399
400 protected void addImpl(Headers<? extends K, ? extends V, ?> headers) {
401 if (headers instanceof DefaultHeaders) {
402 @SuppressWarnings("unchecked")
403 final DefaultHeaders<? extends K, ? extends V, T> defaultHeaders =
404 (DefaultHeaders<? extends K, ? extends V, T>) headers;
405 HeaderEntry<? extends K, ? extends V> e = defaultHeaders.head.after;
406 if (defaultHeaders.hashingStrategy == hashingStrategy &&
407 defaultHeaders.nameValidator == nameValidator) {
408
409 while (e != defaultHeaders.head) {
410 add0(e.hash, index(e.hash), e.key, e.value);
411 e = e.after;
412 }
413 } else {
414
415 while (e != defaultHeaders.head) {
416 add(e.key, e.value);
417 e = e.after;
418 }
419 }
420 } else {
421
422 for (Entry<? extends K, ? extends V> header : headers) {
423 add(header.getKey(), header.getValue());
424 }
425 }
426 }
427
428 @Override
429 public T set(K name, V value) {
430 nameValidator.validateName(name);
431 requireNonNull(value, "value");
432 int h = hashingStrategy.hashCode(name);
433 int i = index(h);
434 remove0(h, i, name);
435 add0(h, i, name, value);
436 return thisT();
437 }
438
439 @Override
440 public T set(K name, Iterable<? extends V> values) {
441 nameValidator.validateName(name);
442 requireNonNull(values, "values");
443
444 int h = hashingStrategy.hashCode(name);
445 int i = index(h);
446
447 remove0(h, i, name);
448 for (V v: values) {
449 if (v == null) {
450 break;
451 }
452 add0(h, i, name, v);
453 }
454
455 return thisT();
456 }
457
458 @Override
459 public T set(K name, V... values) {
460 nameValidator.validateName(name);
461 requireNonNull(values, "values");
462
463 int h = hashingStrategy.hashCode(name);
464 int i = index(h);
465
466 remove0(h, i, name);
467 for (V v: values) {
468 if (v == null) {
469 break;
470 }
471 add0(h, i, name, v);
472 }
473
474 return thisT();
475 }
476
477 @Override
478 public T setObject(K name, Object value) {
479 requireNonNull(value, "value");
480 V convertedValue = requireNonNull(valueConverter.convertObject(value), "convertedValue");
481 return set(name, convertedValue);
482 }
483
484 @Override
485 public T setObject(K name, Iterable<?> values) {
486 nameValidator.validateName(name);
487
488 int h = hashingStrategy.hashCode(name);
489 int i = index(h);
490
491 remove0(h, i, name);
492 for (Object v: values) {
493 if (v == null) {
494 break;
495 }
496 add0(h, i, name, valueConverter.convertObject(v));
497 }
498
499 return thisT();
500 }
501
502 @Override
503 public T setObject(K name, Object... values) {
504 nameValidator.validateName(name);
505
506 int h = hashingStrategy.hashCode(name);
507 int i = index(h);
508
509 remove0(h, i, name);
510 for (Object v: values) {
511 if (v == null) {
512 break;
513 }
514 add0(h, i, name, valueConverter.convertObject(v));
515 }
516
517 return thisT();
518 }
519
520 @Override
521 public T setInt(K name, int value) {
522 return set(name, valueConverter.convertInt(value));
523 }
524
525 @Override
526 public T setLong(K name, long value) {
527 return set(name, valueConverter.convertLong(value));
528 }
529
530 @Override
531 public T setDouble(K name, double value) {
532 return set(name, valueConverter.convertDouble(value));
533 }
534
535 @Override
536 public T setTimeMillis(K name, long value) {
537 return set(name, valueConverter.convertTimeMillis(value));
538 }
539
540 @Override
541 public T setFloat(K name, float value) {
542 return set(name, valueConverter.convertFloat(value));
543 }
544
545 @Override
546 public T setChar(K name, char value) {
547 return set(name, valueConverter.convertChar(value));
548 }
549
550 @Override
551 public T setBoolean(K name, boolean value) {
552 return set(name, valueConverter.convertBoolean(value));
553 }
554
555 @Override
556 public T setByte(K name, byte value) {
557 return set(name, valueConverter.convertByte(value));
558 }
559
560 @Override
561 public T setShort(K name, short value) {
562 return set(name, valueConverter.convertShort(value));
563 }
564
565 @Override
566 public T set(Headers<? extends K, ? extends V, ?> headers) {
567 if (headers != this) {
568 clear();
569 addImpl(headers);
570 }
571 return thisT();
572 }
573
574 @Override
575 public T setAll(Headers<? extends K, ? extends V, ?> headers) {
576 if (headers != this) {
577 for (K key : headers.names()) {
578 remove(key);
579 }
580 addImpl(headers);
581 }
582 return thisT();
583 }
584
585 @Override
586 public boolean remove(K name) {
587 return getAndRemove(name) != null;
588 }
589
590 @Override
591 public T clear() {
592 Arrays.fill(entries, null);
593 head.before = head.after = head;
594 size = 0;
595 return thisT();
596 }
597
598 @Override
599 public Iterator<Entry<K, V>> iterator() {
600 return new HeaderIterator();
601 }
602
603 @Override
604 public Boolean getBoolean(K name) {
605 V v = get(name);
606 try {
607 return v != null ? valueConverter.convertToBoolean(v) : null;
608 } catch (RuntimeException ignore) {
609 return null;
610 }
611 }
612
613 @Override
614 public boolean getBoolean(K name, boolean defaultValue) {
615 Boolean v = getBoolean(name);
616 return v != null ? v : defaultValue;
617 }
618
619 @Override
620 public Byte getByte(K name) {
621 V v = get(name);
622 try {
623 return v != null ? valueConverter.convertToByte(v) : null;
624 } catch (RuntimeException ignore) {
625 return null;
626 }
627 }
628
629 @Override
630 public byte getByte(K name, byte defaultValue) {
631 Byte v = getByte(name);
632 return v != null ? v : defaultValue;
633 }
634
635 @Override
636 public Character getChar(K name) {
637 V v = get(name);
638 try {
639 return v != null ? valueConverter.convertToChar(v) : null;
640 } catch (RuntimeException ignore) {
641 return null;
642 }
643 }
644
645 @Override
646 public char getChar(K name, char defaultValue) {
647 Character v = getChar(name);
648 return v != null ? v : defaultValue;
649 }
650
651 @Override
652 public Short getShort(K name) {
653 V v = get(name);
654 try {
655 return v != null ? valueConverter.convertToShort(v) : null;
656 } catch (RuntimeException ignore) {
657 return null;
658 }
659 }
660
661 @Override
662 public short getShort(K name, short defaultValue) {
663 Short v = getShort(name);
664 return v != null ? v : defaultValue;
665 }
666
667 @Override
668 public Integer getInt(K name) {
669 V v = get(name);
670 try {
671 return v != null ? valueConverter.convertToInt(v) : null;
672 } catch (RuntimeException ignore) {
673 return null;
674 }
675 }
676
677 @Override
678 public int getInt(K name, int defaultValue) {
679 Integer v = getInt(name);
680 return v != null ? v : defaultValue;
681 }
682
683 @Override
684 public Long getLong(K name) {
685 V v = get(name);
686 try {
687 return v != null ? valueConverter.convertToLong(v) : null;
688 } catch (RuntimeException ignore) {
689 return null;
690 }
691 }
692
693 @Override
694 public long getLong(K name, long defaultValue) {
695 Long v = getLong(name);
696 return v != null ? v : defaultValue;
697 }
698
699 @Override
700 public Float getFloat(K name) {
701 V v = get(name);
702 try {
703 return v != null ? valueConverter.convertToFloat(v) : null;
704 } catch (RuntimeException ignore) {
705 return null;
706 }
707 }
708
709 @Override
710 public float getFloat(K name, float defaultValue) {
711 Float v = getFloat(name);
712 return v != null ? v : defaultValue;
713 }
714
715 @Override
716 public Double getDouble(K name) {
717 V v = get(name);
718 try {
719 return v != null ? valueConverter.convertToDouble(v) : null;
720 } catch (RuntimeException ignore) {
721 return null;
722 }
723 }
724
725 @Override
726 public double getDouble(K name, double defaultValue) {
727 Double v = getDouble(name);
728 return v != null ? v : defaultValue;
729 }
730
731 @Override
732 public Long getTimeMillis(K name) {
733 V v = get(name);
734 try {
735 return v != null ? valueConverter.convertToTimeMillis(v) : null;
736 } catch (RuntimeException ignore) {
737 return null;
738 }
739 }
740
741 @Override
742 public long getTimeMillis(K name, long defaultValue) {
743 Long v = getTimeMillis(name);
744 return v != null ? v : defaultValue;
745 }
746
747 @Override
748 public Boolean getBooleanAndRemove(K name) {
749 V v = getAndRemove(name);
750 try {
751 return v != null ? valueConverter.convertToBoolean(v) : null;
752 } catch (RuntimeException ignore) {
753 return null;
754 }
755 }
756
757 @Override
758 public boolean getBooleanAndRemove(K name, boolean defaultValue) {
759 Boolean v = getBooleanAndRemove(name);
760 return v != null ? v : defaultValue;
761 }
762
763 @Override
764 public Byte getByteAndRemove(K name) {
765 V v = getAndRemove(name);
766 try {
767 return v != null ? valueConverter.convertToByte(v) : null;
768 } catch (RuntimeException ignore) {
769 return null;
770 }
771 }
772
773 @Override
774 public byte getByteAndRemove(K name, byte defaultValue) {
775 Byte v = getByteAndRemove(name);
776 return v != null ? v : defaultValue;
777 }
778
779 @Override
780 public Character getCharAndRemove(K name) {
781 V v = getAndRemove(name);
782 try {
783 return v != null ? valueConverter.convertToChar(v) : null;
784 } catch (RuntimeException ignore) {
785 return null;
786 }
787 }
788
789 @Override
790 public char getCharAndRemove(K name, char defaultValue) {
791 Character v = getCharAndRemove(name);
792 return v != null ? v : defaultValue;
793 }
794
795 @Override
796 public Short getShortAndRemove(K name) {
797 V v = getAndRemove(name);
798 try {
799 return v != null ? valueConverter.convertToShort(v) : null;
800 } catch (RuntimeException ignore) {
801 return null;
802 }
803 }
804
805 @Override
806 public short getShortAndRemove(K name, short defaultValue) {
807 Short v = getShortAndRemove(name);
808 return v != null ? v : defaultValue;
809 }
810
811 @Override
812 public Integer getIntAndRemove(K name) {
813 V v = getAndRemove(name);
814 try {
815 return v != null ? valueConverter.convertToInt(v) : null;
816 } catch (RuntimeException ignore) {
817 return null;
818 }
819 }
820
821 @Override
822 public int getIntAndRemove(K name, int defaultValue) {
823 Integer v = getIntAndRemove(name);
824 return v != null ? v : defaultValue;
825 }
826
827 @Override
828 public Long getLongAndRemove(K name) {
829 V v = getAndRemove(name);
830 try {
831 return v != null ? valueConverter.convertToLong(v) : null;
832 } catch (RuntimeException ignore) {
833 return null;
834 }
835 }
836
837 @Override
838 public long getLongAndRemove(K name, long defaultValue) {
839 Long v = getLongAndRemove(name);
840 return v != null ? v : defaultValue;
841 }
842
843 @Override
844 public Float getFloatAndRemove(K name) {
845 V v = getAndRemove(name);
846 try {
847 return v != null ? valueConverter.convertToFloat(v) : null;
848 } catch (RuntimeException ignore) {
849 return null;
850 }
851 }
852
853 @Override
854 public float getFloatAndRemove(K name, float defaultValue) {
855 Float v = getFloatAndRemove(name);
856 return v != null ? v : defaultValue;
857 }
858
859 @Override
860 public Double getDoubleAndRemove(K name) {
861 V v = getAndRemove(name);
862 try {
863 return v != null ? valueConverter.convertToDouble(v) : null;
864 } catch (RuntimeException ignore) {
865 return null;
866 }
867 }
868
869 @Override
870 public double getDoubleAndRemove(K name, double defaultValue) {
871 Double v = getDoubleAndRemove(name);
872 return v != null ? v : defaultValue;
873 }
874
875 @Override
876 public Long getTimeMillisAndRemove(K name) {
877 V v = getAndRemove(name);
878 try {
879 return v != null ? valueConverter.convertToTimeMillis(v) : null;
880 } catch (RuntimeException ignore) {
881 return null;
882 }
883 }
884
885 @Override
886 public long getTimeMillisAndRemove(K name, long defaultValue) {
887 Long v = getTimeMillisAndRemove(name);
888 return v != null ? v : defaultValue;
889 }
890
891 @SuppressWarnings("unchecked")
892 @Override
893 public boolean equals(Object o) {
894 if (!(o instanceof Headers)) {
895 return false;
896 }
897
898 return equals((Headers<K, V, ?>) o, JAVA_HASHER);
899 }
900
901 @SuppressWarnings("unchecked")
902 @Override
903 public int hashCode() {
904 return hashCode(JAVA_HASHER);
905 }
906
907
908
909
910
911
912
913
914 public final boolean equals(Headers<K, V, ?> h2, HashingStrategy<V> valueHashingStrategy) {
915 if (h2.size() != size()) {
916 return false;
917 }
918
919 if (this == h2) {
920 return true;
921 }
922
923 for (K name : names()) {
924 List<V> otherValues = h2.getAll(name);
925 List<V> values = getAll(name);
926 if (otherValues.size() != values.size()) {
927 return false;
928 }
929 for (int i = 0; i < otherValues.size(); i++) {
930 if (!valueHashingStrategy.equals(otherValues.get(i), values.get(i))) {
931 return false;
932 }
933 }
934 }
935 return true;
936 }
937
938
939
940
941
942
943 public final int hashCode(HashingStrategy<V> valueHashingStrategy) {
944 int result = HASH_CODE_SEED;
945 for (K name : names()) {
946 result = 31 * result + hashingStrategy.hashCode(name);
947 List<V> values = getAll(name);
948 for (int i = 0; i < values.size(); ++i) {
949 result = 31 * result + valueHashingStrategy.hashCode(values.get(i));
950 }
951 }
952 return result;
953 }
954
955 @Override
956 public String toString() {
957 return HeadersUtils.toString(getClass(), iterator(), size());
958 }
959
960 protected HeaderEntry<K, V> newHeaderEntry(int h, K name, V value, HeaderEntry<K, V> next) {
961 return new HeaderEntry<>(h, name, value, next, head);
962 }
963
964 protected ValueConverter<V> valueConverter() {
965 return valueConverter;
966 }
967
968 private int index(int hash) {
969 return hash & hashMask;
970 }
971
972 private void add0(int h, int i, K name, V value) {
973
974 entries[i] = newHeaderEntry(h, name, value, entries[i]);
975 ++size;
976 }
977
978
979
980
981 private V remove0(int h, int i, K name) {
982 HeaderEntry<K, V> e = entries[i];
983 if (e == null) {
984 return null;
985 }
986
987 V value = null;
988 HeaderEntry<K, V> next = e.next;
989 while (next != null) {
990 if (next.hash == h && hashingStrategy.equals(name, next.key)) {
991 value = next.value;
992 e.next = next.next;
993 next.remove();
994 --size;
995 } else {
996 e = next;
997 }
998
999 next = e.next;
1000 }
1001
1002 e = entries[i];
1003 if (e.hash == h && hashingStrategy.equals(name, e.key)) {
1004 if (value == null) {
1005 value = e.value;
1006 }
1007 entries[i] = e.next;
1008 e.remove();
1009 --size;
1010 }
1011
1012 return value;
1013 }
1014
1015 HeaderEntry<K, V> remove0(HeaderEntry<K, V> entry, HeaderEntry<K, V> previous) {
1016 int i = index(entry.hash);
1017 HeaderEntry<K, V> firstEntry = entries[i];
1018 if (firstEntry == entry) {
1019 entries[i] = entry.next;
1020 previous = entries[i];
1021 } else if (previous == null) {
1022
1023 previous = firstEntry;
1024 HeaderEntry<K, V> next = firstEntry.next;
1025 while (next != null && next != entry) {
1026 previous = next;
1027 next = next.next;
1028 }
1029 assert next != null: "Entry not found in its hash bucket: " + entry;
1030 previous.next = entry.next;
1031 } else {
1032 previous.next = entry.next;
1033 }
1034 entry.remove();
1035 --size;
1036 return previous;
1037 }
1038
1039 @SuppressWarnings("unchecked")
1040 private T thisT() {
1041 return (T) this;
1042 }
1043
1044
1045
1046
1047 public DefaultHeaders<K, V, T> copy() {
1048 DefaultHeaders<K, V, T> copy = new DefaultHeaders<>(
1049 hashingStrategy, valueConverter, nameValidator, entries.length);
1050 copy.addImpl(this);
1051 return copy;
1052 }
1053
1054 private final class HeaderIterator implements Iterator<Map.Entry<K, V>> {
1055 private HeaderEntry<K, V> current = head;
1056
1057 @Override
1058 public boolean hasNext() {
1059 return current.after != head;
1060 }
1061
1062 @Override
1063 public Entry<K, V> next() {
1064 current = current.after;
1065
1066 if (current == head) {
1067 throw new NoSuchElementException();
1068 }
1069
1070 return current;
1071 }
1072
1073 @Override
1074 public void remove() {
1075 throw new UnsupportedOperationException("read only");
1076 }
1077 }
1078
1079 private final class ValueIterator implements Iterator<V> {
1080 private final K name;
1081 private final int hash;
1082 private HeaderEntry<K, V> removalPrevious;
1083 private HeaderEntry<K, V> previous;
1084 private HeaderEntry<K, V> next;
1085
1086 ValueIterator(K name) {
1087 this.name = requireNonNull(name, "name");
1088 hash = hashingStrategy.hashCode(name);
1089 calculateNext(entries[index(hash)]);
1090 }
1091
1092 @Override
1093 public boolean hasNext() {
1094 return next != null;
1095 }
1096
1097 @Override
1098 public V next() {
1099 if (!hasNext()) {
1100 throw new NoSuchElementException();
1101 }
1102 if (previous != null) {
1103 removalPrevious = previous;
1104 }
1105 previous = next;
1106 calculateNext(next.next);
1107 return previous.value;
1108 }
1109
1110 @Override
1111 public void remove() {
1112 if (previous == null) {
1113 throw new IllegalStateException();
1114 }
1115 removalPrevious = remove0(previous, removalPrevious);
1116 previous = null;
1117 }
1118
1119 private void calculateNext(HeaderEntry<K, V> entry) {
1120 while (entry != null) {
1121 if (entry.hash == hash && hashingStrategy.equals(name, entry.key)) {
1122 next = entry;
1123 return;
1124 }
1125 entry = entry.next;
1126 }
1127 next = null;
1128 }
1129 }
1130
1131 protected static class HeaderEntry<K, V> implements Map.Entry<K, V> {
1132 protected final int hash;
1133 protected final K key;
1134 protected V value;
1135
1136
1137
1138 protected HeaderEntry<K, V> next;
1139
1140
1141
1142 protected HeaderEntry<K, V> before, after;
1143
1144 protected HeaderEntry(int hash, K key) {
1145 this.hash = hash;
1146 this.key = key;
1147 }
1148
1149 HeaderEntry(int hash, K key, V value, HeaderEntry<K, V> next, HeaderEntry<K, V> head) {
1150 this.hash = hash;
1151 this.key = key;
1152 this.value = value;
1153 this.next = next;
1154
1155 after = head;
1156 before = head.before;
1157 pointNeighborsToThis();
1158 }
1159
1160 HeaderEntry() {
1161 hash = -1;
1162 key = null;
1163 before = after = this;
1164 }
1165
1166 protected final void pointNeighborsToThis() {
1167 before.after = this;
1168 after.before = this;
1169 }
1170
1171 public final HeaderEntry<K, V> before() {
1172 return before;
1173 }
1174
1175 public final HeaderEntry<K, V> after() {
1176 return after;
1177 }
1178
1179 protected void remove() {
1180 before.after = after;
1181 after.before = before;
1182 }
1183
1184 @Override
1185 public final K getKey() {
1186 return key;
1187 }
1188
1189 @Override
1190 public final V getValue() {
1191 return value;
1192 }
1193
1194 @Override
1195 public final V setValue(V value) {
1196 requireNonNull(value, "value");
1197 V oldValue = this.value;
1198 this.value = value;
1199 return oldValue;
1200 }
1201
1202 @Override
1203 public final String toString() {
1204 return key.toString() + '=' + value.toString();
1205 }
1206
1207 @Override
1208 public boolean equals(Object o) {
1209 if (!(o instanceof Map.Entry)) {
1210 return false;
1211 }
1212 Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
1213 return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1214 (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1215 }
1216
1217 @Override
1218 public int hashCode() {
1219 return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
1220 }
1221 }
1222 }