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         return v != null ? valueConverter.convertToBoolean(v) : null;
607     }
608 
609     @Override
610     public boolean getBoolean(K name, boolean defaultValue) {
611         Boolean v = getBoolean(name);
612         return v != null ? v : defaultValue;
613     }
614 
615     @Override
616     public Byte getByte(K name) {
617         V v = get(name);
618         return v != null ? valueConverter.convertToByte(v) : null;
619     }
620 
621     @Override
622     public byte getByte(K name, byte defaultValue) {
623         Byte v = getByte(name);
624         return v != null ? v : defaultValue;
625     }
626 
627     @Override
628     public Character getChar(K name) {
629         V v = get(name);
630         return v != null ? valueConverter.convertToChar(v) : null;
631     }
632 
633     @Override
634     public char getChar(K name, char defaultValue) {
635         Character v = getChar(name);
636         return v != null ? v : defaultValue;
637     }
638 
639     @Override
640     public Short getShort(K name) {
641         V v = get(name);
642         return v != null ? valueConverter.convertToShort(v) : null;
643     }
644 
645     @Override
646     public short getShort(K name, short defaultValue) {
647         Short v = getShort(name);
648         return v != null ? v : defaultValue;
649     }
650 
651     @Override
652     public Integer getInt(K name) {
653         V v = get(name);
654         return v != null ? valueConverter.convertToInt(v) : null;
655     }
656 
657     @Override
658     public int getInt(K name, int defaultValue) {
659         Integer v = getInt(name);
660         return v != null ? v : defaultValue;
661     }
662 
663     @Override
664     public Long getLong(K name) {
665         V v = get(name);
666         return v != null ? valueConverter.convertToLong(v) : null;
667     }
668 
669     @Override
670     public long getLong(K name, long defaultValue) {
671         Long v = getLong(name);
672         return v != null ? v : defaultValue;
673     }
674 
675     @Override
676     public Float getFloat(K name) {
677         V v = get(name);
678         return v != null ? valueConverter.convertToFloat(v) : null;
679     }
680 
681     @Override
682     public float getFloat(K name, float defaultValue) {
683         Float v = getFloat(name);
684         return v != null ? v : defaultValue;
685     }
686 
687     @Override
688     public Double getDouble(K name) {
689         V v = get(name);
690         return v != null ? valueConverter.convertToDouble(v) : null;
691     }
692 
693     @Override
694     public double getDouble(K name, double defaultValue) {
695         Double v = getDouble(name);
696         return v != null ? v : defaultValue;
697     }
698 
699     @Override
700     public Long getTimeMillis(K name) {
701         V v = get(name);
702         return v != null ? valueConverter.convertToTimeMillis(v) : null;
703     }
704 
705     @Override
706     public long getTimeMillis(K name, long defaultValue) {
707         Long v = getTimeMillis(name);
708         return v != null ? v : defaultValue;
709     }
710 
711     @Override
712     public Boolean getBooleanAndRemove(K name) {
713         V v = getAndRemove(name);
714         return v != null ? valueConverter.convertToBoolean(v) : null;
715     }
716 
717     @Override
718     public boolean getBooleanAndRemove(K name, boolean defaultValue) {
719         Boolean v = getBooleanAndRemove(name);
720         return v != null ? v : defaultValue;
721     }
722 
723     @Override
724     public Byte getByteAndRemove(K name) {
725         V v = getAndRemove(name);
726         return v != null ? valueConverter.convertToByte(v) : null;
727     }
728 
729     @Override
730     public byte getByteAndRemove(K name, byte defaultValue) {
731         Byte v = getByteAndRemove(name);
732         return v != null ? v : defaultValue;
733     }
734 
735     @Override
736     public Character getCharAndRemove(K name) {
737         V v = getAndRemove(name);
738         if (v == null) {
739             return null;
740         }
741         try {
742             return valueConverter.convertToChar(v);
743         } catch (Throwable ignored) {
744             return null;
745         }
746     }
747 
748     @Override
749     public char getCharAndRemove(K name, char defaultValue) {
750         Character v = getCharAndRemove(name);
751         return v != null ? v : defaultValue;
752     }
753 
754     @Override
755     public Short getShortAndRemove(K name) {
756         V v = getAndRemove(name);
757         return v != null ? valueConverter.convertToShort(v) : null;
758     }
759 
760     @Override
761     public short getShortAndRemove(K name, short defaultValue) {
762         Short v = getShortAndRemove(name);
763         return v != null ? v : defaultValue;
764     }
765 
766     @Override
767     public Integer getIntAndRemove(K name) {
768         V v = getAndRemove(name);
769         return v != null ? valueConverter.convertToInt(v) : null;
770     }
771 
772     @Override
773     public int getIntAndRemove(K name, int defaultValue) {
774         Integer v = getIntAndRemove(name);
775         return v != null ? v : defaultValue;
776     }
777 
778     @Override
779     public Long getLongAndRemove(K name) {
780         V v = getAndRemove(name);
781         return v != null ? valueConverter.convertToLong(v) : null;
782     }
783 
784     @Override
785     public long getLongAndRemove(K name, long defaultValue) {
786         Long v = getLongAndRemove(name);
787         return v != null ? v : defaultValue;
788     }
789 
790     @Override
791     public Float getFloatAndRemove(K name) {
792         V v = getAndRemove(name);
793         return v != null ? valueConverter.convertToFloat(v) : null;
794     }
795 
796     @Override
797     public float getFloatAndRemove(K name, float defaultValue) {
798         Float v = getFloatAndRemove(name);
799         return v != null ? v : defaultValue;
800     }
801 
802     @Override
803     public Double getDoubleAndRemove(K name) {
804         V v = getAndRemove(name);
805         return v != null ? valueConverter.convertToDouble(v) : null;
806     }
807 
808     @Override
809     public double getDoubleAndRemove(K name, double defaultValue) {
810         Double v = getDoubleAndRemove(name);
811         return v != null ? v : defaultValue;
812     }
813 
814     @Override
815     public Long getTimeMillisAndRemove(K name) {
816         V v = getAndRemove(name);
817         return v != null ? valueConverter.convertToTimeMillis(v) : null;
818     }
819 
820     @Override
821     public long getTimeMillisAndRemove(K name, long defaultValue) {
822         Long v = getTimeMillisAndRemove(name);
823         return v != null ? v : defaultValue;
824     }
825 
826     @SuppressWarnings("unchecked")
827     @Override
828     public boolean equals(Object o) {
829         if (!(o instanceof Headers)) {
830             return false;
831         }
832 
833         return equals((Headers<K, V, ?>) o, JAVA_HASHER);
834     }
835 
836     @SuppressWarnings("unchecked")
837     @Override
838     public int hashCode() {
839         return hashCode(JAVA_HASHER);
840     }
841 
842     /**
843      * Test this object for equality against {@code h2}.
844      * @param h2 The object to check equality for.
845      * @param valueHashingStrategy Defines how values will be compared for equality.
846      * @return {@code true} if this object equals {@code h2} given {@code valueHashingStrategy}.
847      * {@code false} otherwise.
848      */
849     public final boolean equals(Headers<K, V, ?> h2, HashingStrategy<V> valueHashingStrategy) {
850         if (h2.size() != size()) {
851             return false;
852         }
853 
854         if (this == h2) {
855             return true;
856         }
857 
858         for (K name : names()) {
859             List<V> otherValues = h2.getAll(name);
860             List<V> values = getAll(name);
861             if (otherValues.size() != values.size()) {
862                 return false;
863             }
864             for (int i = 0; i < otherValues.size(); i++) {
865                 if (!valueHashingStrategy.equals(otherValues.get(i), values.get(i))) {
866                     return false;
867                 }
868             }
869         }
870         return true;
871     }
872 
873     /**
874      * Generate a hash code for this object given a {@link HashingStrategy} to generate hash codes for
875      * individual values.
876      * @param valueHashingStrategy Defines how values will be hashed.
877      */
878     public final int hashCode(HashingStrategy<V> valueHashingStrategy) {
879         int result = HASH_CODE_SEED;
880         for (K name : names()) {
881             result = 31 * result + hashingStrategy.hashCode(name);
882             List<V> values = getAll(name);
883             for (int i = 0; i < values.size(); ++i) {
884                 result = 31 * result + valueHashingStrategy.hashCode(values.get(i));
885             }
886         }
887         return result;
888     }
889 
890     @Override
891     public String toString() {
892         return HeadersUtils.toString(getClass(), iterator(), size());
893     }
894 
895     protected HeaderEntry<K, V> newHeaderEntry(int h, K name, V value, HeaderEntry<K, V> next) {
896         return new HeaderEntry<K, V>(h, name, value, next, head);
897     }
898 
899     protected ValueConverter<V> valueConverter() {
900         return valueConverter;
901     }
902 
903     private int index(int hash) {
904         return hash & hashMask;
905     }
906 
907     private void add0(int h, int i, K name, V value) {
908         // Update the hash table.
909         entries[i] = newHeaderEntry(h, name, value, entries[i]);
910         ++size;
911     }
912 
913     /**
914      * @return the first value inserted whose hash code equals {@code h} and whose name is equal to {@code name}.
915      */
916     private V remove0(int h, int i, K name) {
917         HeaderEntry<K, V> e = entries[i];
918         if (e == null) {
919             return null;
920         }
921 
922         V value = null;
923         HeaderEntry<K, V> next = e.next;
924         while (next != null) {
925             if (next.hash == h && hashingStrategy.equals(name, next.key)) {
926                 value = next.value;
927                 e.next = next.next;
928                 next.remove();
929                 --size;
930             } else {
931                 e = next;
932             }
933 
934             next = e.next;
935         }
936 
937         e = entries[i];
938         if (e.hash == h && hashingStrategy.equals(name, e.key)) {
939             if (value == null) {
940                 value = e.value;
941             }
942             entries[i] = e.next;
943             e.remove();
944             --size;
945         }
946 
947         return value;
948     }
949 
950     @SuppressWarnings("unchecked")
951     private T thisT() {
952         return (T) this;
953     }
954 
955     private final class HeaderIterator implements Iterator<Map.Entry<K, V>> {
956         private HeaderEntry<K, V> current = head;
957 
958         @Override
959         public boolean hasNext() {
960             return current.after != head;
961         }
962 
963         @Override
964         public Entry<K, V> next() {
965             current = current.after;
966 
967             if (current == head) {
968                 throw new NoSuchElementException();
969             }
970 
971             return current;
972         }
973 
974         @Override
975         public void remove() {
976             throw new UnsupportedOperationException("read only");
977         }
978     }
979 
980     private final class ValueIterator implements Iterator<V> {
981         private final K name;
982         private final int hash;
983         private HeaderEntry<K, V> next;
984 
985         ValueIterator(K name) {
986             this.name = checkNotNull(name, "name");
987             hash = hashingStrategy.hashCode(name);
988             calculateNext(entries[index(hash)]);
989         }
990 
991         @Override
992         public boolean hasNext() {
993             return next != null;
994         }
995 
996         @Override
997         public V next() {
998             if (!hasNext()) {
999                 throw new NoSuchElementException();
1000             }
1001             HeaderEntry<K, V> current = next;
1002             calculateNext(next.next);
1003             return current.value;
1004         }
1005 
1006         @Override
1007         public void remove() {
1008             throw new UnsupportedOperationException("read only");
1009         }
1010 
1011         private void calculateNext(HeaderEntry<K, V> entry) {
1012             while (entry != null) {
1013                 if (entry.hash == hash && hashingStrategy.equals(name, entry.key)) {
1014                     next = entry;
1015                     return;
1016                 }
1017                 entry = entry.next;
1018             }
1019             next = null;
1020         }
1021     }
1022 
1023     protected static class HeaderEntry<K, V> implements Map.Entry<K, V> {
1024         protected final int hash;
1025         protected final K key;
1026         protected V value;
1027         /**
1028          * In bucket linked list
1029          */
1030         protected HeaderEntry<K, V> next;
1031         /**
1032          * Overall insertion order linked list
1033          */
1034         protected HeaderEntry<K, V> before, after;
1035 
1036         protected HeaderEntry(int hash, K key) {
1037             this.hash = hash;
1038             this.key = key;
1039         }
1040 
1041         HeaderEntry(int hash, K key, V value, HeaderEntry<K, V> next, HeaderEntry<K, V> head) {
1042             this.hash = hash;
1043             this.key = key;
1044             this.value = value;
1045             this.next = next;
1046 
1047             after = head;
1048             before = head.before;
1049             pointNeighborsToThis();
1050         }
1051 
1052         HeaderEntry() {
1053             hash = -1;
1054             key = null;
1055             before = after = this;
1056         }
1057 
1058         protected final void pointNeighborsToThis() {
1059             before.after = this;
1060             after.before = this;
1061         }
1062 
1063         public final HeaderEntry<K, V> before() {
1064             return before;
1065         }
1066 
1067         public final HeaderEntry<K, V> after() {
1068             return after;
1069         }
1070 
1071         protected void remove() {
1072             before.after = after;
1073             after.before = before;
1074         }
1075 
1076         @Override
1077         public final K getKey() {
1078             return key;
1079         }
1080 
1081         @Override
1082         public final V getValue() {
1083             return value;
1084         }
1085 
1086         @Override
1087         public final V setValue(V value) {
1088             checkNotNull(value, "value");
1089             V oldValue = this.value;
1090             this.value = value;
1091             return oldValue;
1092         }
1093 
1094         @Override
1095         public final String toString() {
1096             return key.toString() + '=' + value.toString();
1097         }
1098     }
1099 }