1 //
2 // ========================================================================
3 // Copyright (c) 1995-2013 Mort Bay Consulting Pty. Ltd.
4 // ------------------------------------------------------------------------
5 // All rights reserved. This program and the accompanying materials
6 // are made available under the terms of the Eclipse Public License v1.0
7 // and Apache License v2.0 which accompanies this distribution.
8 //
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
11 //
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
14 //
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
17 //
18
19 package org.eclipse.jetty.util;
20
21 import java.io.IOException;
22 import java.nio.ByteBuffer;
23 import java.util.HashSet;
24 import java.util.Set;
25
26 /* ------------------------------------------------------------ */
27 /** A Trie String lookup data structure using a fixed size array.
28 * <p>This implementation is always case insensitive and is optimal for
29 * a small number of fixed strings with few special characters.
30 * </p>
31 * @param <V>
32 */
33 public class ArrayTrie<V> extends AbstractTrie<V>
34 {
35 /**
36 * The Size of a Trie row is how many characters can be looked
37 * up directly without going to a big index. This is set at
38 * 32 to cover case insensitive alphabet and a few other common
39 * characters.
40 */
41 private static final int ROW_SIZE = 32;
42
43 /**
44 * The index lookup table, this maps a character as a byte
45 * (ISO-8859-1 or UTF8) to an index within a Trie row
46 */
47 private static final int[] __lookup =
48 { // 0 1 2 3 4 5 6 7 8 9 A B C D E F
49 /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
50 /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 30,
51 /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, -1, -1,
52 /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
53 /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
54 /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
55 /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
56 /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
57 };
58
59 /**
60 * The Trie rows in a single array which allows a lookup of row,character
61 * to the next row in the Trie. This is actually a 2 dimensional
62 * array that has been flattened to achieve locality of reference.
63 * The first ROW_SIZE entries are for row 0, then next ROW_SIZE
64 * entries are for row 1 etc. So in general instead of using
65 * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up
66 * the next row for a given character.
67 *
68 * The array is of characters rather than integers to save space.
69 */
70 private final char[] _rowIndex;
71
72 /**
73 * The key (if any) for a Trie row.
74 * A row may be a leaf, a node or both in the Trie tree.
75 */
76 private final String[] _key;
77
78 /**
79 * The value (if any) for a Trie row.
80 * A row may be a leaf, a node or both in the Trie tree.
81 */
82 private final Object[] _value;
83
84 /**
85 * A big index for each row.
86 * If a character outside of the lookup map is needed,
87 * then a big index will be created for the row, with
88 * 256 entries, one for each possible byte.
89 */
90 private char[][] _bigIndex;
91
92 /**
93 * The number of rows allocated
94 */
95 private char _rows;
96
97 public ArrayTrie()
98 {
99 this(128);
100 }
101
102 public ArrayTrie(int capacityInNodes)
103 {
104 super(true);
105 _value=new Object[capacityInNodes];
106 _rowIndex=new char[capacityInNodes*32];
107 _key=new String[capacityInNodes];
108 }
109
110
111 /* ------------------------------------------------------------ */
112 @Override
113 public boolean put(String s, V v)
114 {
115 int t=0;
116 int k;
117 int limit = s.length();
118 for(k=0; k < limit; k++)
119 {
120 char c=s.charAt(k);
121
122 int index=__lookup[c&0x7f];
123 if (index>=0)
124 {
125 int idx=t*ROW_SIZE+index;
126 t=_rowIndex[idx];
127 if (t==0)
128 {
129 if (++_rows>=_value.length)
130 return false;
131 t=_rowIndex[idx]=_rows;
132 }
133 }
134 else if (c>127)
135 throw new IllegalArgumentException("non ascii character");
136 else
137 {
138 if (_bigIndex==null)
139 _bigIndex=new char[_value.length][];
140 if (t>=_bigIndex.length)
141 return false;
142 char[] big=_bigIndex[t];
143 if (big==null)
144 big=_bigIndex[t]=new char[128];
145 t=big[c];
146 if (t==0)
147 {
148 if (_rows==_value.length)
149 return false;
150 t=big[c]=++_rows;
151 }
152 }
153 }
154 _key[t]=v==null?null:s;
155 V old=(V)_value[t];
156 _value[t] = v;
157 return true;
158 }
159
160 /* ------------------------------------------------------------ */
161 @Override
162 public V get(String s, int offset, int len)
163 {
164 int t = 0;
165 for(int i=0; i < len; i++)
166 {
167 char c=s.charAt(offset+i);
168 int index=__lookup[c&0x7f];
169 if (index>=0)
170 {
171 int idx=t*ROW_SIZE+index;
172 t=_rowIndex[idx];
173 if (t==0)
174 return null;
175 }
176 else
177 {
178 char[] big = _bigIndex==null?null:_bigIndex[t];
179 if (big==null)
180 return null;
181 t=big[c];
182 if (t==0)
183 return null;
184 }
185 }
186 return (V)_value[t];
187 }
188
189 /* ------------------------------------------------------------ */
190 @Override
191 public V get(ByteBuffer b,int offset,int len)
192 {
193 int t = 0;
194 for(int i=0; i < len; i++)
195 {
196 byte c=b.get(offset+i);
197 int index=__lookup[c&0x7f];
198 if (index>=0)
199 {
200 int idx=t*ROW_SIZE+index;
201 t=_rowIndex[idx];
202 if (t==0)
203 return null;
204 }
205 else
206 {
207 char[] big = _bigIndex==null?null:_bigIndex[t];
208 if (big==null)
209 return null;
210 t=big[c];
211 if (t==0)
212 return null;
213 }
214 }
215 return (V)_value[t];
216 }
217
218 /* ------------------------------------------------------------ */
219 @Override
220 public V getBest(byte[] b,int offset,int len)
221 {
222 return getBest(0,b,offset,len);
223 }
224
225 /* ------------------------------------------------------------ */
226 @Override
227 public V getBest(ByteBuffer b,int offset,int len)
228 {
229 if (b.hasArray())
230 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
231 return getBest(0,b,offset,len);
232 }
233
234 /* ------------------------------------------------------------ */
235 @Override
236 public V getBest(String s, int offset, int len)
237 {
238 return getBest(0,s,offset,len);
239 }
240
241 /* ------------------------------------------------------------ */
242 private V getBest(int t, String s, int offset, int len)
243 {
244 int pos=offset;
245 for(int i=0; i < len; i++)
246 {
247 char c=s.charAt(pos++);
248 int index=__lookup[c&0x7f];
249 if (index>=0)
250 {
251 int idx=t*ROW_SIZE+index;
252 int nt=_rowIndex[idx];
253 if (nt==0)
254 break;
255 t=nt;
256 }
257 else
258 {
259 char[] big = _bigIndex==null?null:_bigIndex[t];
260 if (big==null)
261 return null;
262 int nt=big[c];
263 if (nt==0)
264 break;
265 t=nt;
266 }
267
268 // Is the next Trie is a match
269 if (_key[t]!=null)
270 {
271 // Recurse so we can remember this possibility
272 V best=getBest(t,s,offset+i+1,len-i-1);
273 if (best!=null)
274 return best;
275 return (V)_value[t];
276 }
277 }
278 return (V)_value[t];
279 }
280
281 /* ------------------------------------------------------------ */
282 private V getBest(int t,byte[] b,int offset,int len)
283 {
284 for(int i=0; i < len; i++)
285 {
286 byte c=b[offset+i];
287 int index=__lookup[c&0x7f];
288 if (index>=0)
289 {
290 int idx=t*ROW_SIZE+index;
291 int nt=_rowIndex[idx];
292 if (nt==0)
293 break;
294 t=nt;
295 }
296 else
297 {
298 char[] big = _bigIndex==null?null:_bigIndex[t];
299 if (big==null)
300 return null;
301 int nt=big[c];
302 if (nt==0)
303 break;
304 t=nt;
305 }
306
307 // Is the next Trie is a match
308 if (_key[t]!=null)
309 {
310 // Recurse so we can remember this possibility
311 V best=getBest(t,b,offset+i+1,len-i-1);
312 if (best!=null)
313 return best;
314 break;
315 }
316 }
317 return (V)_value[t];
318 }
319
320 private V getBest(int t,ByteBuffer b,int offset,int len)
321 {
322 int pos=b.position()+offset;
323 for(int i=0; i < len; i++)
324 {
325 byte c=b.get(pos++);
326 int index=__lookup[c&0x7f];
327 if (index>=0)
328 {
329 int idx=t*ROW_SIZE+index;
330 int nt=_rowIndex[idx];
331 if (nt==0)
332 break;
333 t=nt;
334 }
335 else
336 {
337 char[] big = _bigIndex==null?null:_bigIndex[t];
338 if (big==null)
339 return null;
340 int nt=big[c];
341 if (nt==0)
342 break;
343 t=nt;
344 }
345
346 // Is the next Trie is a match
347 if (_key[t]!=null)
348 {
349 // Recurse so we can remember this possibility
350 V best=getBest(t,b,offset+i+1,len-i-1);
351 if (best!=null)
352 return best;
353 break;
354 }
355 }
356 return (V)_value[t];
357 }
358
359
360
361
362 @Override
363 public String toString()
364 {
365 StringBuilder buf = new StringBuilder();
366 toString(buf,0);
367
368 if (buf.length()==0)
369 return "{}";
370
371 buf.setCharAt(0,'{');
372 buf.append('}');
373 return buf.toString();
374 }
375
376
377 private <V> void toString(Appendable out, int t)
378 {
379 if (_value[t]!=null)
380 {
381 try
382 {
383 out.append(',');
384 out.append(_key[t]);
385 out.append('=');
386 out.append(_value[t].toString());
387 }
388 catch (IOException e)
389 {
390 throw new RuntimeException(e);
391 }
392 }
393
394 for(int i=0; i < ROW_SIZE; i++)
395 {
396 int idx=t*ROW_SIZE+i;
397 if (_rowIndex[idx] != 0)
398 toString(out,_rowIndex[idx]);
399 }
400
401 char[] big = _bigIndex==null?null:_bigIndex[t];
402 if (big!=null)
403 {
404 for (int i:big)
405 if (i!=0)
406 toString(out,i);
407 }
408
409 }
410
411 @Override
412 public Set<String> keySet()
413 {
414 Set<String> keys = new HashSet<>();
415 keySet(keys,0);
416 return keys;
417 }
418
419 private void keySet(Set<String> set, int t)
420 {
421 if (t<_value.length&&_value[t]!=null)
422 set.add(_key[t]);
423
424 for(int i=0; i < ROW_SIZE; i++)
425 {
426 int idx=t*ROW_SIZE+i;
427 if (idx<_rowIndex.length && _rowIndex[idx] != 0)
428 keySet(set,_rowIndex[idx]);
429 }
430
431 char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
432 if (big!=null)
433 {
434 for (int i:big)
435 if (i!=0)
436 keySet(set,i);
437 }
438 }
439
440 @Override
441 public boolean isFull()
442 {
443 return _rows+1==_key.length;
444 }
445 }