View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5    * "License"); you may not use this file except in compliance with the License. You may obtain a
6    * copy of the License at:
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software distributed under the License
11   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12   * or implied. See the License for the specific language governing permissions and limitations under
13   * the License.
14   */
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  /**
37   * Default implementation of {@link Headers};
38   *
39   * @param <K> the type of the header name.
40   * @param <V> the type of the header value.
41   * @param <T> the type to use for return values when the intention is to return {@code this} object.
42   */
43  public class DefaultHeaders<K, V, T extends Headers<K, V, T>> implements Headers<K, V, T> {
44      /**
45       * Constant used to seed the hash code generation. Could be anything but this was borrowed from murmur3.
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           * Verify that {@code name} is valid.
61           * @param name The name to validate.
62           * @throws RuntimeException if {@code name} is not valid.
63           */
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      /**
96       * Create a new instance.
97       * @param nameHashingStrategy Used to hash and equality compare names.
98       * @param valueConverter Used to convert values to/from native types.
99       * @param nameValidator Used to validate name elements.
100      * @param arraySizeHint A hint as to how large the hash data structure should be.
101      * The next positive power of two will be used. An upper bound may be enforced.
102      */
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         // Enforce a bound of [2, 128] because hashMask is a byte. The max possible value of hashMask is one less
110         // than the length of this array, and we want the mask to be > 0.
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         // loop until the first header was found
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     /**
178      * Equivalent to {@link #getAll(Object)} but no intermediate list is generated.
179      * @param name the name of the header to retrieve
180      * @return an {@link Iterator} of header values corresponding to {@code name}.
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(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                 // Fastest copy
409                 while (e != defaultHeaders.head) {
410                     add0(e.hash, index(e.hash), e.key, e.value);
411                     e = e.after;
412                 }
413             } else {
414                 // Fast copy
415                 while (e != defaultHeaders.head) {
416                     add(e.key, e.value);
417                     e = e.after;
418                 }
419             }
420         } else {
421             // Slow copy
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     /**
908      * Test this object for equality against {@code h2}.
909      * @param h2 The object to check equality for.
910      * @param valueHashingStrategy Defines how values will be compared for equality.
911      * @return {@code true} if this object equals {@code h2} given {@code valueHashingStrategy}.
912      * {@code false} otherwise.
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      * Generate a hash code for this object given a {@link HashingStrategy} to generate hash codes for
940      * individual values.
941      * @param valueHashingStrategy Defines how values will be hashed.
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<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         // Update the hash table.
974         entries[i] = newHeaderEntry(h, name, value, entries[i]);
975         ++size;
976     }
977 
978     /**
979      * @return the first value inserted whose hash code equals {@code h} and whose name is equal to {@code name}.
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     @SuppressWarnings("unchecked")
1016     private T thisT() {
1017         return (T) this;
1018     }
1019 
1020     /**
1021      * Returns a deep copy of this instance.
1022      */
1023     public DefaultHeaders<K, V, T> copy() {
1024         DefaultHeaders<K, V, T> copy = new DefaultHeaders<K, V, T>(
1025                 hashingStrategy, valueConverter, nameValidator, entries.length);
1026         copy.addImpl(this);
1027         return copy;
1028     }
1029 
1030     private final class HeaderIterator implements Iterator<Map.Entry<K, V>> {
1031         private HeaderEntry<K, V> current = head;
1032 
1033         @Override
1034         public boolean hasNext() {
1035             return current.after != head;
1036         }
1037 
1038         @Override
1039         public Entry<K, V> next() {
1040             current = current.after;
1041 
1042             if (current == head) {
1043                 throw new NoSuchElementException();
1044             }
1045 
1046             return current;
1047         }
1048 
1049         @Override
1050         public void remove() {
1051             throw new UnsupportedOperationException("read only");
1052         }
1053     }
1054 
1055     private final class ValueIterator implements Iterator<V> {
1056         private final K name;
1057         private final int hash;
1058         private HeaderEntry<K, V> next;
1059 
1060         ValueIterator(K name) {
1061             this.name = checkNotNull(name, "name");
1062             hash = hashingStrategy.hashCode(name);
1063             calculateNext(entries[index(hash)]);
1064         }
1065 
1066         @Override
1067         public boolean hasNext() {
1068             return next != null;
1069         }
1070 
1071         @Override
1072         public V next() {
1073             if (!hasNext()) {
1074                 throw new NoSuchElementException();
1075             }
1076             HeaderEntry<K, V> current = next;
1077             calculateNext(next.next);
1078             return current.value;
1079         }
1080 
1081         @Override
1082         public void remove() {
1083             throw new UnsupportedOperationException("read only");
1084         }
1085 
1086         private void calculateNext(HeaderEntry<K, V> entry) {
1087             while (entry != null) {
1088                 if (entry.hash == hash && hashingStrategy.equals(name, entry.key)) {
1089                     next = entry;
1090                     return;
1091                 }
1092                 entry = entry.next;
1093             }
1094             next = null;
1095         }
1096     }
1097 
1098     protected static class HeaderEntry<K, V> implements Map.Entry<K, V> {
1099         protected final int hash;
1100         protected final K key;
1101         protected V value;
1102         /**
1103          * In bucket linked list
1104          */
1105         protected HeaderEntry<K, V> next;
1106         /**
1107          * Overall insertion order linked list
1108          */
1109         protected HeaderEntry<K, V> before, after;
1110 
1111         protected HeaderEntry(int hash, K key) {
1112             this.hash = hash;
1113             this.key = key;
1114         }
1115 
1116         HeaderEntry(int hash, K key, V value, HeaderEntry<K, V> next, HeaderEntry<K, V> head) {
1117             this.hash = hash;
1118             this.key = key;
1119             this.value = value;
1120             this.next = next;
1121 
1122             after = head;
1123             before = head.before;
1124             pointNeighborsToThis();
1125         }
1126 
1127         HeaderEntry() {
1128             hash = -1;
1129             key = null;
1130             before = after = this;
1131         }
1132 
1133         protected final void pointNeighborsToThis() {
1134             before.after = this;
1135             after.before = this;
1136         }
1137 
1138         public final HeaderEntry<K, V> before() {
1139             return before;
1140         }
1141 
1142         public final HeaderEntry<K, V> after() {
1143             return after;
1144         }
1145 
1146         protected void remove() {
1147             before.after = after;
1148             after.before = before;
1149         }
1150 
1151         @Override
1152         public final K getKey() {
1153             return key;
1154         }
1155 
1156         @Override
1157         public final V getValue() {
1158             return value;
1159         }
1160 
1161         @Override
1162         public final V setValue(V value) {
1163             checkNotNull(value, "value");
1164             V oldValue = this.value;
1165             this.value = value;
1166             return oldValue;
1167         }
1168 
1169         @Override
1170         public final String toString() {
1171             return key.toString() + '=' + value.toString();
1172         }
1173 
1174         @Override
1175         public boolean equals(Object o) {
1176             if (!(o instanceof Map.Entry)) {
1177                 return false;
1178             }
1179             Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
1180             return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey()))  &&
1181                    (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1182         }
1183 
1184         @Override
1185         public int hashCode() {
1186             return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
1187         }
1188     }
1189 }