1
15 package io.netty.handler.codec;
16
17 import io.netty.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.netty.util.HashingStrategy.JAVA_HASHER;
31 import static io.netty.util.internal.MathUtil.findNextPositivePowerOfTwo;
32 import static io.netty.util.internal.ObjectUtil.checkNotNull;
33 import static java.lang.Math.max;
34 import static java.lang.Math.min;
35
36
43 public class DefaultHeaders<K, V, T extends Headers<K, V, T>> implements Headers<K, V, T> {
44
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
64 void validateName(K name);
65
66 @SuppressWarnings("rawtypes")
67 NameValidator NOT_NULL = new NameValidator() {
68 @Override
69 public void validateName(Object name) {
70 checkNotNull(name, "name");
71 }
72 };
73 }
74
75 @SuppressWarnings("unchecked")
76 public DefaultHeaders(ValueConverter<V> valueConverter) {
77 this(JAVA_HASHER, valueConverter);
78 }
79
80 @SuppressWarnings("unchecked")
81 public DefaultHeaders(ValueConverter<V> valueConverter, NameValidator<K> nameValidator) {
82 this(JAVA_HASHER, valueConverter, nameValidator);
83 }
84
85 @SuppressWarnings("unchecked")
86 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy, ValueConverter<V> valueConverter) {
87 this(nameHashingStrategy, valueConverter, NameValidator.NOT_NULL);
88 }
89
90 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy,
91 ValueConverter<V> valueConverter, NameValidator<K> nameValidator) {
92 this(nameHashingStrategy, valueConverter, nameValidator, 16);
93 }
94
95
103 @SuppressWarnings("unchecked")
104 public DefaultHeaders(HashingStrategy<K> nameHashingStrategy,
105 ValueConverter<V> valueConverter, NameValidator<K> nameValidator, int arraySizeHint) {
106 this.valueConverter = checkNotNull(valueConverter, "valueConverter");
107 this.nameValidator = checkNotNull(nameValidator, "nameValidator");
108 this.hashingStrategy = checkNotNull(nameHashingStrategy, "nameHashingStrategy");
109
110
111 entries = new DefaultHeaders.HeaderEntry[findNextPositivePowerOfTwo(max(2, min(arraySizeHint, 128)))];
112 hashMask = (byte) (entries.length - 1);
113 head = new HeaderEntry<K, V>();
114 }
115
116 @Override
117 public V get(K name) {
118 checkNotNull(name, "name");
119
120 int h = hashingStrategy.hashCode(name);
121 int i = index(h);
122 HeaderEntry<K, V> e = entries[i];
123 V value = null;
124
125 while (e != null) {
126 if (e.hash == h && hashingStrategy.equals(name, e.key)) {
127 value = e.value;
128 }
129
130 e = e.next;
131 }
132 return value;
133 }
134
135 @Override
136 public V get(K name, V defaultValue) {
137 V value = get(name);
138 if (value == null) {
139 return defaultValue;
140 }
141 return value;
142 }
143
144 @Override
145 public V getAndRemove(K name) {
146 int h = hashingStrategy.hashCode(name);
147 return remove0(h, index(h), checkNotNull(name, "name"));
148 }
149
150 @Override
151 public V getAndRemove(K name, V defaultValue) {
152 V value = getAndRemove(name);
153 if (value == null) {
154 return defaultValue;
155 }
156 return value;
157 }
158
159 @Override
160 public List<V> getAll(K name) {
161 checkNotNull(name, "name");
162
163 LinkedList<V> values = new LinkedList<V>();
164
165 int h = hashingStrategy.hashCode(name);
166 int i = index(h);
167 HeaderEntry<K, V> e = entries[i];
168 while (e != null) {
169 if (e.hash == h && hashingStrategy.equals(name, e.key)) {
170 values.addFirst(e.getValue());
171 }
172 e = e.next;
173 }
174 return values;
175 }
176
177
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(checkNotNull(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 checkNotNull(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<K>(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 checkNotNull(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(checkNotNull(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 checkNotNull(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 checkNotNull(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 checkNotNull(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 checkNotNull(value, "value");
480 V convertedValue = checkNotNull(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
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
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<K, V>(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
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 private HeaderEntry<K, V> remove0(HeaderEntry<K, V> entry, HeaderEntry<K, V> previous) {
1016 int i = index(entry.hash);
1017 HeaderEntry<K, V> e = entries[i];
1018 if (e == entry) {
1019 entries[i] = entry.next;
1020 previous = entries[i];
1021 } else {
1022 previous.next = entry.next;
1023 }
1024 entry.remove();
1025 --size;
1026 return previous;
1027 }
1028
1029 @SuppressWarnings("unchecked")
1030 private T thisT() {
1031 return (T) this;
1032 }
1033
1034
1037 public DefaultHeaders<K, V, T> copy() {
1038 DefaultHeaders<K, V, T> copy = new DefaultHeaders<K, V, T>(
1039 hashingStrategy, valueConverter, nameValidator, entries.length);
1040 copy.addImpl(this);
1041 return copy;
1042 }
1043
1044 private final class HeaderIterator implements Iterator<Map.Entry<K, V>> {
1045 private HeaderEntry<K, V> current = head;
1046
1047 @Override
1048 public boolean hasNext() {
1049 return current.after != head;
1050 }
1051
1052 @Override
1053 public Entry<K, V> next() {
1054 current = current.after;
1055
1056 if (current == head) {
1057 throw new NoSuchElementException();
1058 }
1059
1060 return current;
1061 }
1062
1063 @Override
1064 public void remove() {
1065 throw new UnsupportedOperationException("read only");
1066 }
1067 }
1068
1069 private final class ValueIterator implements Iterator<V> {
1070 private final K name;
1071 private final int hash;
1072 private HeaderEntry<K, V> removalPrevious;
1073 private HeaderEntry<K, V> previous;
1074 private HeaderEntry<K, V> next;
1075
1076 ValueIterator(K name) {
1077 this.name = checkNotNull(name, "name");
1078 hash = hashingStrategy.hashCode(name);
1079 calculateNext(entries[index(hash)]);
1080 }
1081
1082 @Override
1083 public boolean hasNext() {
1084 return next != null;
1085 }
1086
1087 @Override
1088 public V next() {
1089 if (!hasNext()) {
1090 throw new NoSuchElementException();
1091 }
1092 if (previous != null) {
1093 removalPrevious = previous;
1094 }
1095 previous = next;
1096 calculateNext(next.next);
1097 return previous.value;
1098 }
1099
1100 @Override
1101 public void remove() {
1102 if (previous == null) {
1103 throw new IllegalStateException();
1104 }
1105 removalPrevious = remove0(previous, removalPrevious);
1106 previous = null;
1107 }
1108
1109 private void calculateNext(HeaderEntry<K, V> entry) {
1110 while (entry != null) {
1111 if (entry.hash == hash && hashingStrategy.equals(name, entry.key)) {
1112 next = entry;
1113 return;
1114 }
1115 entry = entry.next;
1116 }
1117 next = null;
1118 }
1119 }
1120
1121 protected static class HeaderEntry<K, V> implements Map.Entry<K, V> {
1122 protected final int hash;
1123 protected final K key;
1124 protected V value;
1125
1128 protected HeaderEntry<K, V> next;
1129
1132 protected HeaderEntry<K, V> before, after;
1133
1134 protected HeaderEntry(int hash, K key) {
1135 this.hash = hash;
1136 this.key = key;
1137 }
1138
1139 HeaderEntry(int hash, K key, V value, HeaderEntry<K, V> next, HeaderEntry<K, V> head) {
1140 this.hash = hash;
1141 this.key = key;
1142 this.value = value;
1143 this.next = next;
1144
1145 after = head;
1146 before = head.before;
1147 pointNeighborsToThis();
1148 }
1149
1150 HeaderEntry() {
1151 hash = -1;
1152 key = null;
1153 before = after = this;
1154 }
1155
1156 protected final void pointNeighborsToThis() {
1157 before.after = this;
1158 after.before = this;
1159 }
1160
1161 public final HeaderEntry<K, V> before() {
1162 return before;
1163 }
1164
1165 public final HeaderEntry<K, V> after() {
1166 return after;
1167 }
1168
1169 protected void remove() {
1170 before.after = after;
1171 after.before = before;
1172 }
1173
1174 @Override
1175 public final K getKey() {
1176 return key;
1177 }
1178
1179 @Override
1180 public final V getValue() {
1181 return value;
1182 }
1183
1184 @Override
1185 public final V setValue(V value) {
1186 checkNotNull(value, "value");
1187 V oldValue = this.value;
1188 this.value = value;
1189 return oldValue;
1190 }
1191
1192 @Override
1193 public final String toString() {
1194 return key.toString() + '=' + value.toString();
1195 }
1196
1197 @Override
1198 public boolean equals(Object o) {
1199 if (!(o instanceof Map.Entry)) {
1200 return false;
1201 }
1202 Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
1203 return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1204 (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1205 }
1206
1207 @Override
1208 public int hashCode() {
1209 return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
1210 }
1211 }
1212 }
1213