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 }