View Javadoc
1   /*
2    * Copyright 2015 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  
17  /*
18   * Copyright 2014 Twitter, Inc.
19   *
20   * Licensed under the Apache License, Version 2.0 (the "License");
21   * you may not use this file except in compliance with the License.
22   * You may obtain a copy of the License at
23   *
24   *     https://www.apache.org/licenses/LICENSE-2.0
25   *
26   * Unless required by applicable law or agreed to in writing, software
27   * distributed under the License is distributed on an "AS IS" BASIS,
28   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29   * See the License for the specific language governing permissions and
30   * limitations under the License.
31   */
32  package io.netty.handler.codec.http2;
33  
34  import static io.netty.handler.codec.http2.Http2CodecUtil.MAX_HEADER_TABLE_SIZE;
35  import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_HEADER_TABLE_SIZE;
36  
37  final class HpackDynamicTable {
38  
39      // a circular queue of header fields
40      HpackHeaderField[] hpackHeaderFields;
41      int head;
42      int tail;
43      private long size;
44      private long capacity = -1; // ensure setCapacity creates the array
45  
46      /**
47       * Creates a new dynamic table with the specified initial capacity.
48       */
49      HpackDynamicTable(long initialCapacity) {
50          setCapacity(initialCapacity);
51      }
52  
53      /**
54       * Return the number of header fields in the dynamic table.
55       */
56      public int length() {
57          int length;
58          if (head < tail) {
59              length = hpackHeaderFields.length - tail + head;
60          } else {
61              length = head - tail;
62          }
63          return length;
64      }
65  
66      /**
67       * Return the current size of the dynamic table. This is the sum of the size of the entries.
68       */
69      public long size() {
70          return size;
71      }
72  
73      /**
74       * Return the maximum allowable size of the dynamic table.
75       */
76      public long capacity() {
77          return capacity;
78      }
79  
80      /**
81       * Return the header field at the given index. The first and newest entry is always at index 1,
82       * and the oldest entry is at the index length().
83       */
84      public HpackHeaderField getEntry(int index) {
85          if (index <= 0 || index > length()) {
86              throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + length());
87          }
88          int i = head - index;
89          if (i < 0) {
90              return hpackHeaderFields[i + hpackHeaderFields.length];
91          } else {
92              return hpackHeaderFields[i];
93          }
94      }
95  
96      /**
97       * Add the header field to the dynamic table. Entries are evicted from the dynamic table until
98       * the size of the table and the new header field is less than or equal to the table's capacity.
99       * If the size of the new entry is larger than the table's capacity, the dynamic table will be
100      * cleared.
101      */
102     public void add(HpackHeaderField header) {
103         int headerSize = header.size();
104         if (headerSize > capacity) {
105             clear();
106             return;
107         }
108         while (capacity - size < headerSize) {
109             remove();
110         }
111         hpackHeaderFields[head++] = header;
112         size += headerSize;
113         if (head == hpackHeaderFields.length) {
114             head = 0;
115         }
116     }
117 
118     /**
119      * Remove and return the oldest header field from the dynamic table.
120      */
121     public HpackHeaderField remove() {
122         HpackHeaderField removed = hpackHeaderFields[tail];
123         if (removed == null) {
124             return null;
125         }
126         size -= removed.size();
127         hpackHeaderFields[tail++] = null;
128         if (tail == hpackHeaderFields.length) {
129             tail = 0;
130         }
131         return removed;
132     }
133 
134     /**
135      * Remove all entries from the dynamic table.
136      */
137     public void clear() {
138         while (tail != head) {
139             hpackHeaderFields[tail++] = null;
140             if (tail == hpackHeaderFields.length) {
141                 tail = 0;
142             }
143         }
144         head = 0;
145         tail = 0;
146         size = 0;
147     }
148 
149     /**
150      * Set the maximum size of the dynamic table. Entries are evicted from the dynamic table until
151      * the size of the table is less than or equal to the maximum size.
152      */
153     public void setCapacity(long capacity) {
154         if (capacity < MIN_HEADER_TABLE_SIZE || capacity > MAX_HEADER_TABLE_SIZE) {
155             throw new IllegalArgumentException("capacity is invalid: " + capacity);
156         }
157         // initially capacity will be -1 so init won't return here
158         if (this.capacity == capacity) {
159             return;
160         }
161         this.capacity = capacity;
162 
163         if (capacity == 0) {
164             clear();
165         } else {
166             // initially size will be 0 so remove won't be called
167             while (size > capacity) {
168                 remove();
169             }
170         }
171 
172         int maxEntries = (int) (capacity / HpackHeaderField.HEADER_ENTRY_OVERHEAD);
173         if (capacity % HpackHeaderField.HEADER_ENTRY_OVERHEAD != 0) {
174             maxEntries++;
175         }
176 
177         // check if capacity change requires us to reallocate the array
178         if (hpackHeaderFields != null && hpackHeaderFields.length == maxEntries) {
179             return;
180         }
181 
182         HpackHeaderField[] tmp = new HpackHeaderField[maxEntries];
183 
184         // initially length will be 0 so there will be no copy
185         int len = length();
186         if (hpackHeaderFields != null) {
187             int cursor = tail;
188             for (int i = 0; i < len; i++) {
189                 HpackHeaderField entry = hpackHeaderFields[cursor++];
190                 tmp[i] = entry;
191                 if (cursor == hpackHeaderFields.length) {
192                     cursor = 0;
193                 }
194             }
195         }
196 
197         tail = 0;
198         head = tail + len;
199         hpackHeaderFields = tmp;
200     }
201 }