1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package io.netty.handler.codec.spdy;
17
18 import java.util.Iterator;
19 import java.util.LinkedList;
20 import java.util.List;
21 import java.util.Map;
22 import java.util.Map.Entry;
23 import java.util.NoSuchElementException;
24 import java.util.Set;
25 import java.util.TreeSet;
26
27
28 public class DefaultSpdyHeaders extends SpdyHeaders {
29
30 private static final int BUCKET_SIZE = 17;
31
32 private static int hash(String name) {
33 int h = 0;
34 for (int i = name.length() - 1; i >= 0; i --) {
35 char c = name.charAt(i);
36 if (c >= 'A' && c <= 'Z') {
37 c += 32;
38 }
39 h = 31 * h + c;
40 }
41
42 if (h > 0) {
43 return h;
44 } else if (h == Integer.MIN_VALUE) {
45 return Integer.MAX_VALUE;
46 } else {
47 return -h;
48 }
49 }
50
51 private static boolean eq(String name1, String name2) {
52 int nameLen = name1.length();
53 if (nameLen != name2.length()) {
54 return false;
55 }
56
57 for (int i = nameLen - 1; i >= 0; i --) {
58 char c1 = name1.charAt(i);
59 char c2 = name2.charAt(i);
60 if (c1 != c2) {
61 if (c1 >= 'A' && c1 <= 'Z') {
62 c1 += 32;
63 }
64 if (c2 >= 'A' && c2 <= 'Z') {
65 c2 += 32;
66 }
67 if (c1 != c2) {
68 return false;
69 }
70 }
71 }
72 return true;
73 }
74
75 private static int index(int hash) {
76 return hash % BUCKET_SIZE;
77 }
78
79 private final HeaderEntry[] entries = new HeaderEntry[BUCKET_SIZE];
80 private final HeaderEntry head = new HeaderEntry(-1, null, null);
81
82 DefaultSpdyHeaders() {
83 head.before = head.after = head;
84 }
85
86 @Override
87 public SpdyHeaders add(final String name, final Object value) {
88 String lowerCaseName = name.toLowerCase();
89 SpdyCodecUtil.validateHeaderName(lowerCaseName);
90 String strVal = toString(value);
91 SpdyCodecUtil.validateHeaderValue(strVal);
92 int h = hash(lowerCaseName);
93 int i = index(h);
94 add0(h, i, lowerCaseName, strVal);
95 return this;
96 }
97
98 private void add0(int h, int i, final String name, final String value) {
99
100 HeaderEntry e = entries[i];
101 HeaderEntry newEntry;
102 entries[i] = newEntry = new HeaderEntry(h, name, value);
103 newEntry.next = e;
104
105
106 newEntry.addBefore(head);
107 }
108
109 @Override
110 public SpdyHeaders remove(final String name) {
111 if (name == null) {
112 throw new NullPointerException("name");
113 }
114 String lowerCaseName = name.toLowerCase();
115 int h = hash(lowerCaseName);
116 int i = index(h);
117 remove0(h, i, lowerCaseName);
118 return this;
119 }
120
121 private void remove0(int h, int i, String name) {
122 HeaderEntry e = entries[i];
123 if (e == null) {
124 return;
125 }
126
127 for (;;) {
128 if (e.hash == h && eq(name, e.key)) {
129 e.remove();
130 HeaderEntry next = e.next;
131 if (next != null) {
132 entries[i] = next;
133 e = next;
134 } else {
135 entries[i] = null;
136 return;
137 }
138 } else {
139 break;
140 }
141 }
142
143 for (;;) {
144 HeaderEntry next = e.next;
145 if (next == null) {
146 break;
147 }
148 if (next.hash == h && eq(name, next.key)) {
149 e.next = next.next;
150 next.remove();
151 } else {
152 e = next;
153 }
154 }
155 }
156
157 @Override
158 public SpdyHeaders set(final String name, final Object value) {
159 String lowerCaseName = name.toLowerCase();
160 SpdyCodecUtil.validateHeaderName(lowerCaseName);
161 String strVal = toString(value);
162 SpdyCodecUtil.validateHeaderValue(strVal);
163 int h = hash(lowerCaseName);
164 int i = index(h);
165 remove0(h, i, lowerCaseName);
166 add0(h, i, lowerCaseName, strVal);
167 return this;
168 }
169
170 @Override
171 public SpdyHeaders set(final String name, final Iterable<?> values) {
172 if (values == null) {
173 throw new NullPointerException("values");
174 }
175
176 String lowerCaseName = name.toLowerCase();
177 SpdyCodecUtil.validateHeaderName(lowerCaseName);
178
179 int h = hash(lowerCaseName);
180 int i = index(h);
181
182 remove0(h, i, lowerCaseName);
183 for (Object v: values) {
184 if (v == null) {
185 break;
186 }
187 String strVal = toString(v);
188 SpdyCodecUtil.validateHeaderValue(strVal);
189 add0(h, i, lowerCaseName, strVal);
190 }
191 return this;
192 }
193
194 @Override
195 public SpdyHeaders clear() {
196 for (int i = 0; i < entries.length; i ++) {
197 entries[i] = null;
198 }
199 head.before = head.after = head;
200 return this;
201 }
202
203 @Override
204 public String get(final String name) {
205 if (name == null) {
206 throw new NullPointerException("name");
207 }
208
209 int h = hash(name);
210 int i = index(h);
211 HeaderEntry e = entries[i];
212 while (e != null) {
213 if (e.hash == h && eq(name, e.key)) {
214 return e.value;
215 }
216
217 e = e.next;
218 }
219 return null;
220 }
221
222 @Override
223 public List<String> getAll(final String name) {
224 if (name == null) {
225 throw new NullPointerException("name");
226 }
227
228 LinkedList<String> values = new LinkedList<String>();
229
230 int h = hash(name);
231 int i = index(h);
232 HeaderEntry e = entries[i];
233 while (e != null) {
234 if (e.hash == h && eq(name, e.key)) {
235 values.addFirst(e.value);
236 }
237 e = e.next;
238 }
239 return values;
240 }
241
242 @Override
243 public List<Map.Entry<String, String>> entries() {
244 List<Map.Entry<String, String>> all =
245 new LinkedList<Map.Entry<String, String>>();
246
247 HeaderEntry e = head.after;
248 while (e != head) {
249 all.add(e);
250 e = e.after;
251 }
252 return all;
253 }
254
255 @Override
256 public Iterator<Map.Entry<String, String>> iterator() {
257 return new HeaderIterator();
258 }
259
260 @Override
261 public boolean contains(String name) {
262 return get(name) != null;
263 }
264
265 @Override
266 public Set<String> names() {
267 Set<String> names = new TreeSet<String>();
268
269 HeaderEntry e = head.after;
270 while (e != head) {
271 names.add(e.key);
272 e = e.after;
273 }
274 return names;
275 }
276
277 @Override
278 public SpdyHeaders add(String name, Iterable<?> values) {
279 SpdyCodecUtil.validateHeaderValue(name);
280 int h = hash(name);
281 int i = index(h);
282 for (Object v: values) {
283 String vstr = toString(v);
284 SpdyCodecUtil.validateHeaderValue(vstr);
285 add0(h, i, name, vstr);
286 }
287 return this;
288 }
289
290 @Override
291 public boolean isEmpty() {
292 return head == head.after;
293 }
294
295 private static String toString(Object value) {
296 if (value == null) {
297 return null;
298 }
299 return value.toString();
300 }
301
302 private final class HeaderIterator implements Iterator<Map.Entry<String, String>> {
303
304 private HeaderEntry current = head;
305
306 @Override
307 public boolean hasNext() {
308 return current.after != head;
309 }
310
311 @Override
312 public Entry<String, String> next() {
313 current = current.after;
314
315 if (current == head) {
316 throw new NoSuchElementException();
317 }
318
319 return current;
320 }
321
322 @Override
323 public void remove() {
324 throw new UnsupportedOperationException();
325 }
326 }
327
328 private static final class HeaderEntry implements Map.Entry<String, String> {
329 final int hash;
330 final String key;
331 String value;
332 HeaderEntry next;
333 HeaderEntry before, after;
334
335 HeaderEntry(int hash, String key, String value) {
336 this.hash = hash;
337 this.key = key;
338 this.value = value;
339 }
340
341 void remove() {
342 before.after = after;
343 after.before = before;
344 }
345
346 void addBefore(HeaderEntry e) {
347 after = e;
348 before = e.before;
349 before.after = this;
350 after.before = this;
351 }
352
353 @Override
354 public String getKey() {
355 return key;
356 }
357
358 @Override
359 public String getValue() {
360 return value;
361 }
362
363 @Override
364 public String setValue(String value) {
365 if (value == null) {
366 throw new NullPointerException("value");
367 }
368 SpdyCodecUtil.validateHeaderValue(value);
369 String oldValue = this.value;
370 this.value = value;
371 return oldValue;
372 }
373
374 @Override
375 public String toString() {
376 return key + '=' + value;
377 }
378 }
379 }