jdk/src/jdk.incubator.httpclient/share/classes/jdk/incubator/http/internal/hpack/HeaderTable.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package jdk.incubator.http.internal.hpack;

 import jdk.internal.vm.annotation.Stable;

 import java.util.HashMap;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.NoSuchElementException;

 import static java.lang.String.format;

 //
 // Header Table combined from two tables: static and dynamic.
 //
 // There is a single address space for index values. Index-aware methods
 // correspond to the table as a whole. Size-aware methods only to the dynamic
 // part of it.
 //
 final class HeaderTable {

     @Stable
     private static final HeaderField[] staticTable = {
             null, // To make index 1-based, instead of 0-based
             new HeaderField(":authority"),
             new HeaderField(":method", "GET"),
             new HeaderField(":method", "POST"),
             new HeaderField(":path", "/"),
             new HeaderField(":path", "/index.html"),
             new HeaderField(":scheme", "http"),
             new HeaderField(":scheme", "https"),
             new HeaderField(":status", "200"),
             new HeaderField(":status", "204"),
             new HeaderField(":status", "206"),
             new HeaderField(":status", "304"),
             new HeaderField(":status", "400"),
             new HeaderField(":status", "404"),
             new HeaderField(":status", "500"),
             new HeaderField("accept-charset"),
             new HeaderField("accept-encoding", "gzip, deflate"),
             new HeaderField("accept-language"),
             new HeaderField("accept-ranges"),
             new HeaderField("accept"),
             new HeaderField("access-control-allow-origin"),
             new HeaderField("age"),
             new HeaderField("allow"),
             new HeaderField("authorization"),
             new HeaderField("cache-control"),
             new HeaderField("content-disposition"),
             new HeaderField("content-encoding"),
             new HeaderField("content-language"),
             new HeaderField("content-length"),
             new HeaderField("content-location"),
             new HeaderField("content-range"),
             new HeaderField("content-type"),
             new HeaderField("cookie"),
             new HeaderField("date"),
             new HeaderField("etag"),
             new HeaderField("expect"),
             new HeaderField("expires"),
             new HeaderField("from"),
             new HeaderField("host"),
             new HeaderField("if-match"),
             new HeaderField("if-modified-since"),
             new HeaderField("if-none-match"),
             new HeaderField("if-range"),
             new HeaderField("if-unmodified-since"),
             new HeaderField("last-modified"),
             new HeaderField("link"),
             new HeaderField("location"),
             new HeaderField("max-forwards"),
             new HeaderField("proxy-authenticate"),
             new HeaderField("proxy-authorization"),
             new HeaderField("range"),
             new HeaderField("referer"),
             new HeaderField("refresh"),
             new HeaderField("retry-after"),
             new HeaderField("server"),
             new HeaderField("set-cookie"),
             new HeaderField("strict-transport-security"),
             new HeaderField("transfer-encoding"),
             new HeaderField("user-agent"),
             new HeaderField("vary"),
             new HeaderField("via"),
             new HeaderField("www-authenticate")
     };

     private static final int STATIC_TABLE_LENGTH = staticTable.length - 1;
     private static final int ENTRY_SIZE = 32;
     private static final Map<String, LinkedHashMap<String, Integer>> staticIndexes;

     static {
         staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of
         for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) {
             HeaderField f = staticTable[i];
             Map<String, Integer> values = staticIndexes
                     .computeIfAbsent(f.name, k -> new LinkedHashMap<>());
             values.put(f.value, i);
         }
     }

     private final Table dynamicTable = new Table(0);
     private int maxSize;
     private int size;

     public HeaderTable(int maxSize) {
         setMaxSize(maxSize);
     }

     //
     // The method returns:
     //
     // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an
     // index of an entry with a header (n, v), where n.equals(name) &&
     // v.equals(value)
     //
     // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an
     // index of an entry with a header (n, v), where n.equals(name)
     //
     // * 0 if there's no entry e such that e.getName().equals(name)
     //
     // The rationale behind this design is to allow to pack more useful data
     // into a single invocation, facilitating a single pass where possible
     // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)).
     //
     public int indexOf(CharSequence name, CharSequence value) {
         // Invoking toString() will possibly allocate Strings for the sake of
         // the search, which doesn't feel right.
         String n = name.toString();
         String v = value.toString();

         // 1. Try exact match in the static region
         Map<String, Integer> values = staticIndexes.get(n);
         if (values != null) {
             Integer idx = values.get(v);
             if (idx != null) {
                 return idx;
             }
         }
         // 2. Try exact match in the dynamic region
         int didx = dynamicTable.indexOf(n, v);
         if (didx > 0) {
             return STATIC_TABLE_LENGTH + didx;
         } else if (didx < 0) {
             if (values != null) {
                 // 3. Return name match from the static region
                 return -values.values().iterator().next(); // Iterator allocation
             } else {
                 // 4. Return name match from the dynamic region
                 return -STATIC_TABLE_LENGTH + didx;
             }
         } else {
             if (values != null) {
                 // 3. Return name match from the static region
                 return -values.values().iterator().next(); // Iterator allocation
             } else {
                 return 0;
             }
         }
     }

     public int size() {
         return size;
     }

     public int maxSize() {
         return maxSize;
     }

     public int length() {
         return STATIC_TABLE_LENGTH + dynamicTable.size();
     }

     HeaderField get(int index) {
         checkIndex(index);
         if (index <= STATIC_TABLE_LENGTH) {
             return staticTable[index];
         } else {
             return dynamicTable.get(index - STATIC_TABLE_LENGTH);
         }
     }

     void put(CharSequence name, CharSequence value) {
         // Invoking toString() will possibly allocate Strings. But that's
         // unavoidable at this stage. If a CharSequence is going to be stored in
         // the table, it must not be mutable (e.g. for the sake of hashing).
         put(new HeaderField(name.toString(), value.toString()));
     }

     private void put(HeaderField h) {
         int entrySize = sizeOf(h);
         while (entrySize > maxSize - size && size != 0) {
             evictEntry();
         }
         if (entrySize > maxSize - size) {
             return;
         }
         size += entrySize;
         dynamicTable.add(h);
     }

     void setMaxSize(int maxSize) {
         if (maxSize < 0) {
             throw new IllegalArgumentException
                     ("maxSize >= 0: maxSize=" + maxSize);
         }
         while (maxSize < size && size != 0) {
             evictEntry();
         }
         this.maxSize = maxSize;
         int upperBound = (maxSize / ENTRY_SIZE) + 1;
         this.dynamicTable.setCapacity(upperBound);
     }

     HeaderField evictEntry() {
         HeaderField f = dynamicTable.remove();
         size -= sizeOf(f);
         return f;
     }

     @Override
     public String toString() {
         double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize);
         return format("entries: %d; used %s/%s (%.1f%%)", dynamicTable.size(),
                 size, maxSize, used);
     }

     int checkIndex(int index) {
         if (index < 1 || index > STATIC_TABLE_LENGTH + dynamicTable.size()) {
             throw new IllegalArgumentException(
                     format("1 <= index <= length(): index=%s, length()=%s",
                             index, length()));
         }
         return index;
     }

     int sizeOf(HeaderField f) {
         return f.name.length() + f.value.length() + ENTRY_SIZE;
     }

     //
     // Diagnostic information in the form used in the RFC 7541
     //
     String getStateString() {
         if (size == 0) {
             return "empty.";
         }

         StringBuilder b = new StringBuilder();
         for (int i = 1, size = dynamicTable.size(); i <= size; i++) {
             HeaderField e = dynamicTable.get(i);
             b.append(format("[%3d] (s = %3d) %s: %s\n", i,
                     sizeOf(e), e.name, e.value));
         }
         b.append(format("      Table size:%4s", this.size));
         return b.toString();
     }

     // Convert to a Value Object (JDK-8046159)?
     static final class HeaderField {

         final String name;
         final String value;

         public HeaderField(String name) {
             this(name, "");
         }

         public HeaderField(String name, String value) {
             this.name = name;
             this.value = value;
         }

         @Override
         public String toString() {
             return value.isEmpty() ? name : name + ": " + value;
         }

         @Override
         public boolean equals(Object o) {
             if (this == o) {
                 return true;
             }
             if (o == null || getClass() != o.getClass()) {
                 return false;
             }
             HeaderField that = (HeaderField) o;
             return name.equals(that.name) && value.equals(that.value);
         }

         @Override
         public int hashCode() {
             return 31 * name.hashCode() + value.hashCode();
         }
     }

     //
     // To quickly find an index of an entry in the dynamic table with the given
     // contents an effective inverse mapping is needed. Here's a simple idea
     // behind such a mapping.
     //
     // # The problem:
     //
     // We have a queue with an O(1) lookup by index:
     //
     //     get: index -> x
     //
     // What we want is an O(1) reverse lookup:
     //
     //     indexOf: x -> index
     //
     // # Solution:
     //
     // Let's store an inverse mapping in a Map<x, Integer>. This have a problem
     // that when a new element is added to the queue, all indexes in the map
     // become invalid. Namely, the new element is assigned with an index of 1,
     // and each index i, i > 1 becomes shifted by 1 to the left:
     //
     //     1, 1, 2, 3, ... , n-1, n
     //
     // Re-establishing the invariant would seem to require a pass through the
     // map incrementing all indexes (map values) by 1, which is O(n).
     //
     // The good news is we can do much better then this!
     //
     // Let's create a single field of type long, called 'counter'. Then each
     // time a new element 'x' is added to the queue, a value of this field gets
     // incremented. Then the resulting value of the 'counter_x' is then put as a
     // value under key 'x' to the map:
     //
     //    map.put(x, counter_x)
     //
     // It gives us a map that maps an element to a value the counter had at the
     // time the element had been added.
     //
     // In order to retrieve an index of any element 'x' in the queue (at any
     // given time) we simply need to subtract the value (the snapshot of the
     // counter at the time when the 'x' was added) from the current value of the
     // counter. This operation basically answers the question:
     //
     //     How many elements ago 'x' was the tail of the queue?
     //
     // Which is the same as its index in the queue now. Given, of course, it's
     // still in the queue.
     //
     // I'm pretty sure in a real life long overflow will never happen, so it's
     // not too practical to add recalibrating code, but a pedantic person might
     // want to do so:
     //
     //     if (counter == Long.MAX_VALUE) {
     //         recalibrate();
     //     }
     //
     // Where 'recalibrate()' goes through the table doing this:
     //
     //     value -= counter
     //
     // That's given, of course, the size of the table itself is less than
     // Long.MAX_VALUE :-)
     //
     private static final class Table {

         private final Map<String, Map<String, Long>> map;
         private final CircularBuffer<HeaderField> buffer;
         private long counter = 1;

         Table(int capacity) {
             buffer = new CircularBuffer<>(capacity);
             map = new HashMap<>(capacity);
         }

         void add(HeaderField f) {
             buffer.add(f);
             Map<String, Long> values = map.computeIfAbsent(f.name, k -> new HashMap<>());
             values.put(f.value, counter++);
         }

         HeaderField get(int index) {
             return buffer.get(index - 1);
         }

         int indexOf(String name, String value) {
             Map<String, Long> values = map.get(name);
             if (values == null) {
                 return 0;
             }
             Long index = values.get(value);
             if (index != null) {
                 return (int) (counter - index);
             } else {
                 assert !values.isEmpty();
                 Long any = values.values().iterator().next(); // Iterator allocation
                 return -(int) (counter - any);
             }
         }

         HeaderField remove() {
             HeaderField f = buffer.remove();
             Map<String, Long> values = map.get(f.name);
             Long index = values.remove(f.value);
             assert index != null;
             if (values.isEmpty()) {
                 map.remove(f.name);
             }
             return f;
         }

         int size() {
             return buffer.size;
         }

         public void setCapacity(int capacity) {
             buffer.resize(capacity);
         }
     }

     //                    head
     //                    v
     // [ ][ ][A][B][C][D][ ][ ][ ]
     //        ^
     //        tail
     //
     //       |<- size ->| (4)
     // |<------ capacity ------->| (9)
     //
     static final class CircularBuffer<E> {

         int tail, head, size, capacity;
         Object[] elements;

         CircularBuffer(int capacity) {
             this.capacity = capacity;
             elements = new Object[capacity];
         }

         void add(E elem) {
             if (size == capacity) {
                 throw new IllegalStateException(
                         format("No room for '%s': capacity=%s", elem, capacity));
             }
             elements[head] = elem;
             head = (head + 1) % capacity;
             size++;
         }

         @SuppressWarnings("unchecked")
         E remove() {
             if (size == 0) {
                 throw new NoSuchElementException("Empty");
             }
             E elem = (E) elements[tail];
             elements[tail] = null;
             tail = (tail + 1) % capacity;
             size--;
             return elem;
         }

         @SuppressWarnings("unchecked")
         E get(int index) {
             if (index < 0 || index >= size) {
                 throw new IndexOutOfBoundsException(
                         format("0 <= index <= capacity: index=%s, capacity=%s",
                                 index, capacity));
             }
             int idx = (tail + (size - index - 1)) % capacity;
             return (E) elements[idx];
         }

         public void resize(int newCapacity) {
             if (newCapacity < size) {
                 throw new IllegalStateException(
                         format("newCapacity >= size: newCapacity=%s, size=%s",
                                 newCapacity, size));
             }

             Object[] newElements = new Object[newCapacity];

             if (tail < head || size == 0) {
                 System.arraycopy(elements, tail, newElements, 0, size);
             } else {
                 System.arraycopy(elements, tail, newElements, 0, elements.length - tail);
                 System.arraycopy(elements, 0, newElements, elements.length - tail, head);
             }

             elements = newElements;
             tail = 0;
             head = size;
             this.capacity = newCapacity;
         }
     }
 }
	/*
	* Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package jdk.incubator.http.internal.hpack;

	import jdk.internal.vm.annotation.Stable;

	import java.util.HashMap;
	import java.util.LinkedHashMap;
	import java.util.Map;
	import java.util.NoSuchElementException;

	import static java.lang.String.format;

	//
	// Header Table combined from two tables: static and dynamic.
	//
	// There is a single address space for index values. Index-aware methods
	// correspond to the table as a whole. Size-aware methods only to the dynamic
	// part of it.
	//
	final class HeaderTable {

	@Stable
	private static final HeaderField[] staticTable = {
	null, // To make index 1-based, instead of 0-based
	new HeaderField(":authority"),
	new HeaderField(":method", "GET"),
	new HeaderField(":method", "POST"),
	new HeaderField(":path", "/"),
	new HeaderField(":path", "/index.html"),
	new HeaderField(":scheme", "http"),
	new HeaderField(":scheme", "https"),
	new HeaderField(":status", "200"),
	new HeaderField(":status", "204"),
	new HeaderField(":status", "206"),
	new HeaderField(":status", "304"),
	new HeaderField(":status", "400"),
	new HeaderField(":status", "404"),
	new HeaderField(":status", "500"),
	new HeaderField("accept-charset"),
	new HeaderField("accept-encoding", "gzip, deflate"),
	new HeaderField("accept-language"),
	new HeaderField("accept-ranges"),
	new HeaderField("accept"),
	new HeaderField("access-control-allow-origin"),
	new HeaderField("age"),
	new HeaderField("allow"),
	new HeaderField("authorization"),
	new HeaderField("cache-control"),
	new HeaderField("content-disposition"),
	new HeaderField("content-encoding"),
	new HeaderField("content-language"),
	new HeaderField("content-length"),
	new HeaderField("content-location"),
	new HeaderField("content-range"),
	new HeaderField("content-type"),
	new HeaderField("cookie"),
	new HeaderField("date"),
	new HeaderField("etag"),
	new HeaderField("expect"),
	new HeaderField("expires"),
	new HeaderField("from"),
	new HeaderField("host"),
	new HeaderField("if-match"),
	new HeaderField("if-modified-since"),
	new HeaderField("if-none-match"),
	new HeaderField("if-range"),
	new HeaderField("if-unmodified-since"),
	new HeaderField("last-modified"),
	new HeaderField("link"),
	new HeaderField("location"),
	new HeaderField("max-forwards"),
	new HeaderField("proxy-authenticate"),
	new HeaderField("proxy-authorization"),
	new HeaderField("range"),
	new HeaderField("referer"),
	new HeaderField("refresh"),
	new HeaderField("retry-after"),
	new HeaderField("server"),
	new HeaderField("set-cookie"),
	new HeaderField("strict-transport-security"),
	new HeaderField("transfer-encoding"),
	new HeaderField("user-agent"),
	new HeaderField("vary"),
	new HeaderField("via"),
	new HeaderField("www-authenticate")
	};

	private static final int STATIC_TABLE_LENGTH = staticTable.length - 1;
	private static final int ENTRY_SIZE = 32;
	private static final Map<String, LinkedHashMap<String, Integer>> staticIndexes;

	static {
	staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of
	for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) {
	HeaderField f = staticTable[i];
	Map<String, Integer> values = staticIndexes
	.computeIfAbsent(f.name, k -> new LinkedHashMap<>());
	values.put(f.value, i);
	}
	}

	private final Table dynamicTable = new Table(0);
	private int maxSize;
	private int size;

	public HeaderTable(int maxSize) {
	setMaxSize(maxSize);
	}

	//
	// The method returns:
	//
	// * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an
	// index of an entry with a header (n, v), where n.equals(name) &&
	// v.equals(value)
	//
	// * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an
	// index of an entry with a header (n, v), where n.equals(name)
	//
	// * 0 if there's no entry e such that e.getName().equals(name)
	//
	// The rationale behind this design is to allow to pack more useful data
	// into a single invocation, facilitating a single pass where possible
	// (the idea is the same as in java.util.Arrays.binarySearch(int[], int)).
	//
	public int indexOf(CharSequence name, CharSequence value) {
	// Invoking toString() will possibly allocate Strings for the sake of
	// the search, which doesn't feel right.
	String n = name.toString();
	String v = value.toString();

	// 1. Try exact match in the static region
	Map<String, Integer> values = staticIndexes.get(n);
	if (values != null) {
	Integer idx = values.get(v);
	if (idx != null) {
	return idx;
	}
	}
	// 2. Try exact match in the dynamic region
	int didx = dynamicTable.indexOf(n, v);
	if (didx > 0) {
	return STATIC_TABLE_LENGTH + didx;
	} else if (didx < 0) {
	if (values != null) {
	// 3. Return name match from the static region
	return -values.values().iterator().next(); // Iterator allocation
	} else {
	// 4. Return name match from the dynamic region
	return -STATIC_TABLE_LENGTH + didx;
	}
	} else {
	if (values != null) {
	// 3. Return name match from the static region
	return -values.values().iterator().next(); // Iterator allocation
	} else {
	return 0;
	}
	}
	}

	public int size() {
	return size;
	}

	public int maxSize() {
	return maxSize;
	}

	public int length() {
	return STATIC_TABLE_LENGTH + dynamicTable.size();
	}

	HeaderField get(int index) {
	checkIndex(index);
	if (index <= STATIC_TABLE_LENGTH) {
	return staticTable[index];
	} else {
	return dynamicTable.get(index - STATIC_TABLE_LENGTH);
	}
	}

	void put(CharSequence name, CharSequence value) {
	// Invoking toString() will possibly allocate Strings. But that's
	// unavoidable at this stage. If a CharSequence is going to be stored in
	// the table, it must not be mutable (e.g. for the sake of hashing).
	put(new HeaderField(name.toString(), value.toString()));
	}

	private void put(HeaderField h) {
	int entrySize = sizeOf(h);
	while (entrySize > maxSize - size && size != 0) {
	evictEntry();
	}
	if (entrySize > maxSize - size) {
	return;
	}
	size += entrySize;
	dynamicTable.add(h);
	}

	void setMaxSize(int maxSize) {
	if (maxSize < 0) {
	throw new IllegalArgumentException
	("maxSize >= 0: maxSize=" + maxSize);
	}
	while (maxSize < size && size != 0) {
	evictEntry();
	}
	this.maxSize = maxSize;
	int upperBound = (maxSize / ENTRY_SIZE) + 1;
	this.dynamicTable.setCapacity(upperBound);
	}

	HeaderField evictEntry() {
	HeaderField f = dynamicTable.remove();
	size -= sizeOf(f);
	return f;
	}

	@Override
	public String toString() {
	double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize);
	return format("entries: %d; used %s/%s (%.1f%%)", dynamicTable.size(),
	size, maxSize, used);
	}

	int checkIndex(int index) {
	if (index < 1 \|\| index > STATIC_TABLE_LENGTH + dynamicTable.size()) {
	throw new IllegalArgumentException(
	format("1 <= index <= length(): index=%s, length()=%s",
	index, length()));
	}
	return index;
	}

	int sizeOf(HeaderField f) {
	return f.name.length() + f.value.length() + ENTRY_SIZE;
	}

	//
	// Diagnostic information in the form used in the RFC 7541
	//
	String getStateString() {
	if (size == 0) {
	return "empty.";
	}

	StringBuilder b = new StringBuilder();
	for (int i = 1, size = dynamicTable.size(); i <= size; i++) {
	HeaderField e = dynamicTable.get(i);
	b.append(format("[%3d] (s = %3d) %s: %s\n", i,
	sizeOf(e), e.name, e.value));
	}
	b.append(format(" Table size:%4s", this.size));
	return b.toString();
	}

	// Convert to a Value Object (JDK-8046159)?
	static final class HeaderField {

	final String name;
	final String value;

	public HeaderField(String name) {
	this(name, "");
	}

	public HeaderField(String name, String value) {
	this.name = name;
	this.value = value;
	}

	@Override
	public String toString() {
	return value.isEmpty() ? name : name + ": " + value;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) {
	return true;
	}
	if (o == null \|\| getClass() != o.getClass()) {
	return false;
	}
	HeaderField that = (HeaderField) o;
	return name.equals(that.name) && value.equals(that.value);
	}

	@Override
	public int hashCode() {
	return 31 * name.hashCode() + value.hashCode();
	}
	}

	//
	// To quickly find an index of an entry in the dynamic table with the given
	// contents an effective inverse mapping is needed. Here's a simple idea
	// behind such a mapping.
	//
	// # The problem:
	//
	// We have a queue with an O(1) lookup by index:
	//
	// get: index -> x
	//
	// What we want is an O(1) reverse lookup:
	//
	// indexOf: x -> index
	//
	// # Solution:
	//
	// Let's store an inverse mapping in a Map<x, Integer>. This have a problem
	// that when a new element is added to the queue, all indexes in the map
	// become invalid. Namely, the new element is assigned with an index of 1,
	// and each index i, i > 1 becomes shifted by 1 to the left:
	//
	// 1, 1, 2, 3, ... , n-1, n
	//
	// Re-establishing the invariant would seem to require a pass through the
	// map incrementing all indexes (map values) by 1, which is O(n).
	//
	// The good news is we can do much better then this!
	//
	// Let's create a single field of type long, called 'counter'. Then each
	// time a new element 'x' is added to the queue, a value of this field gets
	// incremented. Then the resulting value of the 'counter_x' is then put as a
	// value under key 'x' to the map:
	//
	// map.put(x, counter_x)
	//
	// It gives us a map that maps an element to a value the counter had at the
	// time the element had been added.
	//
	// In order to retrieve an index of any element 'x' in the queue (at any
	// given time) we simply need to subtract the value (the snapshot of the
	// counter at the time when the 'x' was added) from the current value of the
	// counter. This operation basically answers the question:
	//
	// How many elements ago 'x' was the tail of the queue?
	//
	// Which is the same as its index in the queue now. Given, of course, it's
	// still in the queue.
	//
	// I'm pretty sure in a real life long overflow will never happen, so it's
	// not too practical to add recalibrating code, but a pedantic person might
	// want to do so:
	//
	// if (counter == Long.MAX_VALUE) {
	// recalibrate();
	// }
	//
	// Where 'recalibrate()' goes through the table doing this:
	//
	// value -= counter
	//
	// That's given, of course, the size of the table itself is less than
	// Long.MAX_VALUE :-)
	//
	private static final class Table {

	private final Map<String, Map<String, Long>> map;
	private final CircularBuffer<HeaderField> buffer;
	private long counter = 1;

	Table(int capacity) {
	buffer = new CircularBuffer<>(capacity);
	map = new HashMap<>(capacity);
	}

	void add(HeaderField f) {
	buffer.add(f);
	Map<String, Long> values = map.computeIfAbsent(f.name, k -> new HashMap<>());
	values.put(f.value, counter++);
	}

	HeaderField get(int index) {
	return buffer.get(index - 1);
	}

	int indexOf(String name, String value) {
	Map<String, Long> values = map.get(name);
	if (values == null) {
	return 0;
	}
	Long index = values.get(value);
	if (index != null) {
	return (int) (counter - index);
	} else {
	assert !values.isEmpty();
	Long any = values.values().iterator().next(); // Iterator allocation
	return -(int) (counter - any);
	}
	}

	HeaderField remove() {
	HeaderField f = buffer.remove();
	Map<String, Long> values = map.get(f.name);
	Long index = values.remove(f.value);
	assert index != null;
	if (values.isEmpty()) {
	map.remove(f.name);
	}
	return f;
	}

	int size() {
	return buffer.size;
	}

	public void setCapacity(int capacity) {
	buffer.resize(capacity);
	}
	}

	// head
	// v
	// [ ][ ][A][B][C][D][ ][ ][ ]
	// ^
	// tail
	//
	// \|<- size ->\| (4)
	// \|<------ capacity ------->\| (9)
	//
	static final class CircularBuffer<E> {

	int tail, head, size, capacity;
	Object[] elements;

	CircularBuffer(int capacity) {
	this.capacity = capacity;
	elements = new Object[capacity];
	}

	void add(E elem) {
	if (size == capacity) {
	throw new IllegalStateException(
	format("No room for '%s': capacity=%s", elem, capacity));
	}
	elements[head] = elem;
	head = (head + 1) % capacity;
	size++;
	}

	@SuppressWarnings("unchecked")
	E remove() {
	if (size == 0) {
	throw new NoSuchElementException("Empty");
	}
	E elem = (E) elements[tail];
	elements[tail] = null;
	tail = (tail + 1) % capacity;
	size--;
	return elem;
	}

	@SuppressWarnings("unchecked")
	E get(int index) {
	if (index < 0 \|\| index >= size) {
	throw new IndexOutOfBoundsException(
	format("0 <= index <= capacity: index=%s, capacity=%s",
	index, capacity));
	}
	int idx = (tail + (size - index - 1)) % capacity;
	return (E) elements[idx];
	}

	public void resize(int newCapacity) {
	if (newCapacity < size) {
	throw new IllegalStateException(
	format("newCapacity >= size: newCapacity=%s, size=%s",
	newCapacity, size));
	}

	Object[] newElements = new Object[newCapacity];

	if (tail < head \|\| size == 0) {
	System.arraycopy(elements, tail, newElements, 0, size);
	} else {
	System.arraycopy(elements, tail, newElements, 0, elements.length - tail);
	System.arraycopy(elements, 0, newElements, elements.length - tail, head);
	}

	elements = newElements;
	tail = 0;
	head = size;
	this.capacity = newCapacity;
	}
	}
	}