View Javadoc

1   /*
2    * Copyright 2013 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    *   http://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  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          // Update the hash table.
100         HeaderEntry e = entries[i];
101         HeaderEntry newEntry;
102         entries[i] = newEntry = new HeaderEntry(h, name, value);
103         newEntry.next = e;
104 
105         // Update the linked list.
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 }