1 //
2 // ========================================================================
3 // Copyright (c) 1995-2016 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.nio.ByteBuffer;
22 import java.util.Arrays;
23 import java.util.HashSet;
24 import java.util.Set;
25
26
27 /**
28 * <p>A Ternary Trie String lookup data structure.</p>
29 * <p>
30 * This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache).
31 * </p>
32 * <p>
33 * The Trie is stored in 3 arrays:
34 * </p>
35 * <dl>
36 * <dt>char[] _tree</dt><dd>This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension
37 * is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a
38 * ternary trie of key strings.</dd>
39 * <dt>String[] _key</dt><dd>An array of key values where each element matches a row in the _tree array. A non zero key element
40 * indicates that the _tree row is a complete key rather than an intermediate character of a longer key.</dd>
41 * <dt>V[] _value</dt><dd>An array of values corresponding to the _key array</dd>
42 * </dl>
43 * <p>The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed,
44 * then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up
45 * to return the matching value.
46 * </p>
47 * <p>
48 * This Trie may be instantiated either as case sensitive or insensitive.
49 * </p>
50 * <p>This Trie is not Threadsafe and contains no mutual exclusion
51 * or deliberate memory barriers. It is intended for an ArrayTrie to be
52 * built by a single thread and then used concurrently by multiple threads
53 * and not mutated during that access. If concurrent mutations of the
54 * Trie is required external locks need to be applied.
55 * </p>
56 *
57 * @param <V> the Entry type
58 */
59 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
60 {
61 private static int LO=1;
62 private static int EQ=2;
63 private static int HI=3;
64
65 /**
66 * The Size of a Trie row is the char, and the low, equal and high
67 * child pointers
68 */
69 private static final int ROW_SIZE = 4;
70
71 /**
72 * The Trie rows in a single array which allows a lookup of row,character
73 * to the next row in the Trie. This is actually a 2 dimensional
74 * array that has been flattened to achieve locality of reference.
75 */
76 private final char[] _tree;
77
78 /**
79 * The key (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 String[] _key;
83
84 /**
85 * The value (if any) for a Trie row.
86 * A row may be a leaf, a node or both in the Trie tree.
87 */
88 private final V[] _value;
89
90 /**
91 * The number of rows allocated
92 */
93 private char _rows;
94
95 /* ------------------------------------------------------------ */
96 /** Create a case insensitive Trie of default capacity.
97 */
98 public ArrayTernaryTrie()
99 {
100 this(128);
101 }
102
103 /* ------------------------------------------------------------ */
104 /** Create a Trie of default capacity
105 * @param insensitive true if the Trie is insensitive to the case of the key.
106 */
107 public ArrayTernaryTrie(boolean insensitive)
108 {
109 this(insensitive,128);
110 }
111
112 /* ------------------------------------------------------------ */
113 /** Create a case insensitive Trie
114 * @param capacity The capacity of the Trie, which is in the worst case
115 * is the total number of characters of all keys stored in the Trie.
116 * The capacity needed is dependent of the shared prefixes of the keys.
117 * For example, a capacity of 6 nodes is required to store keys "foo"
118 * and "bar", but a capacity of only 4 is required to
119 * store "bar" and "bat".
120 */
121 public ArrayTernaryTrie(int capacity)
122 {
123 this(true,capacity);
124 }
125
126 /* ------------------------------------------------------------ */
127 /** Create a Trie
128 * @param insensitive true if the Trie is insensitive to the case of the key.
129 * @param capacity The capacity of the Trie, which is in the worst case
130 * is the total number of characters of all keys stored in the Trie.
131 * The capacity needed is dependent of the shared prefixes of the keys.
132 * For example, a capacity of 6 nodes is required to store keys "foo"
133 * and "bar", but a capacity of only 4 is required to
134 * store "bar" and "bat".
135 */
136 public ArrayTernaryTrie(boolean insensitive, int capacity)
137 {
138 super(insensitive);
139 _value=(V[])new Object[capacity];
140 _tree=new char[capacity*ROW_SIZE];
141 _key=new String[capacity];
142 }
143
144 /* ------------------------------------------------------------ */
145 /** Copy Trie and change capacity by a factor
146 * @param trie the trie to copy from
147 * @param factor the factor to grow the capacity by
148 */
149 public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
150 {
151 super(trie.isCaseInsensitive());
152 int capacity=(int)(trie._value.length*factor);
153 _rows=trie._rows;
154 _value=Arrays.copyOf(trie._value, capacity);
155 _tree=Arrays.copyOf(trie._tree, capacity*ROW_SIZE);
156 _key=Arrays.copyOf(trie._key, capacity);
157 }
158
159 /* ------------------------------------------------------------ */
160 @Override
161 public void clear()
162 {
163 _rows=0;
164 Arrays.fill(_value,null);
165 Arrays.fill(_tree,(char)0);
166 Arrays.fill(_key,null);
167 }
168
169 /* ------------------------------------------------------------ */
170 @Override
171 public boolean put(String s, V v)
172 {
173 int t=0;
174 int limit = s.length();
175 int last=0;
176 for(int k=0; k < limit; k++)
177 {
178 char c=s.charAt(k);
179 if(isCaseInsensitive() && c<128)
180 c=StringUtil.lowercases[c];
181
182 while (true)
183 {
184 int row=ROW_SIZE*t;
185
186 // Do we need to create the new row?
187 if (t==_rows)
188 {
189 _rows++;
190 if (_rows>=_key.length)
191 {
192 _rows--;
193 return false;
194 }
195 _tree[row]=c;
196 }
197
198 char n=_tree[row];
199 int diff=n-c;
200 if (diff==0)
201 t=_tree[last=(row+EQ)];
202 else if (diff<0)
203 t=_tree[last=(row+LO)];
204 else
205 t=_tree[last=(row+HI)];
206
207 // do we need a new row?
208 if (t==0)
209 {
210 t=_rows;
211 _tree[last]=(char)t;
212 }
213
214 if (diff==0)
215 break;
216 }
217 }
218
219 // Do we need to create the new row?
220 if (t==_rows)
221 {
222 _rows++;
223 if (_rows>=_key.length)
224 {
225 _rows--;
226 return false;
227 }
228 }
229
230 // Put the key and value
231 _key[t]=v==null?null:s;
232 _value[t] = v;
233
234 return true;
235 }
236
237
238 /* ------------------------------------------------------------ */
239 @Override
240 public V get(String s,int offset, int len)
241 {
242 int t = 0;
243 for(int i=0; i < len;)
244 {
245 char c=s.charAt(offset+i++);
246 if(isCaseInsensitive() && c<128)
247 c=StringUtil.lowercases[c];
248
249 while (true)
250 {
251 int row = ROW_SIZE*t;
252 char n=_tree[row];
253 int diff=n-c;
254
255 if (diff==0)
256 {
257 t=_tree[row+EQ];
258 if (t==0)
259 return null;
260 break;
261 }
262
263 t=_tree[row+hilo(diff)];
264 if (t==0)
265 return null;
266 }
267 }
268
269 return _value[t];
270 }
271
272
273 @Override
274 public V get(ByteBuffer b, int offset, int len)
275 {
276 int t = 0;
277 offset+=b.position();
278
279 for(int i=0; i < len;)
280 {
281 byte c=(byte)(b.get(offset+i++)&0x7f);
282 if(isCaseInsensitive())
283 c=(byte)StringUtil.lowercases[c];
284
285 while (true)
286 {
287 int row = ROW_SIZE*t;
288 char n=_tree[row];
289 int diff=n-c;
290
291 if (diff==0)
292 {
293 t=_tree[row+EQ];
294 if (t==0)
295 return null;
296 break;
297 }
298
299 t=_tree[row+hilo(diff)];
300 if (t==0)
301 return null;
302 }
303 }
304
305 return (V)_value[t];
306 }
307
308 /* ------------------------------------------------------------ */
309 @Override
310 public V getBest(String s)
311 {
312 return getBest(0,s,0,s.length());
313 }
314
315 /* ------------------------------------------------------------ */
316 @Override
317 public V getBest(String s, int offset, int length)
318 {
319 return getBest(0,s,offset,length);
320 }
321
322 /* ------------------------------------------------------------ */
323 private V getBest(int t,String s,int offset,int len)
324 {
325 int node=t;
326 int end=offset+len;
327 loop: while(offset<end)
328 {
329 char c=s.charAt(offset++);
330 len--;
331 if(isCaseInsensitive() && c<128)
332 c=StringUtil.lowercases[c];
333
334 while (true)
335 {
336 int row = ROW_SIZE*t;
337 char n=_tree[row];
338 int diff=n-c;
339
340 if (diff==0)
341 {
342 t=_tree[row+EQ];
343 if (t==0)
344 break loop;
345
346 // if this node is a match, recurse to remember
347 if (_key[t]!=null)
348 {
349 node=t;
350 V better=getBest(t,s,offset,len);
351 if (better!=null)
352 return better;
353 }
354 break;
355 }
356
357 t=_tree[row+hilo(diff)];
358 if (t==0)
359 break loop;
360 }
361 }
362 return (V)_value[node];
363 }
364
365
366 /* ------------------------------------------------------------ */
367 @Override
368 public V getBest(ByteBuffer b, int offset, int len)
369 {
370 if (b.hasArray())
371 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
372 return getBest(0,b,offset,len);
373 }
374
375 /* ------------------------------------------------------------ */
376 private V getBest(int t,byte[] b, int offset, int len)
377 {
378 int node=t;
379 int end=offset+len;
380 loop: while(offset<end)
381 {
382 byte c=(byte)(b[offset++]&0x7f);
383 len--;
384 if(isCaseInsensitive())
385 c=(byte)StringUtil.lowercases[c];
386
387 while (true)
388 {
389 int row = ROW_SIZE*t;
390 char n=_tree[row];
391 int diff=n-c;
392
393 if (diff==0)
394 {
395 t=_tree[row+EQ];
396 if (t==0)
397 break loop;
398
399 // if this node is a match, recurse to remember
400 if (_key[t]!=null)
401 {
402 node=t;
403 V better=getBest(t,b,offset,len);
404 if (better!=null)
405 return better;
406 }
407 break;
408 }
409
410 t=_tree[row+hilo(diff)];
411 if (t==0)
412 break loop;
413 }
414 }
415 return (V)_value[node];
416 }
417
418 /* ------------------------------------------------------------ */
419 private V getBest(int t,ByteBuffer b, int offset, int len)
420 {
421 int node=t;
422 int o= offset+b.position();
423
424 loop: for(int i=0; i<len; i++)
425 {
426 byte c=(byte)(b.get(o+i)&0x7f);
427 if(isCaseInsensitive())
428 c=(byte)StringUtil.lowercases[c];
429
430 while (true)
431 {
432 int row = ROW_SIZE*t;
433 char n=_tree[row];
434 int diff=n-c;
435
436 if (diff==0)
437 {
438 t=_tree[row+EQ];
439 if (t==0)
440 break loop;
441
442 // if this node is a match, recurse to remember
443 if (_key[t]!=null)
444 {
445 node=t;
446 V best=getBest(t,b,offset+i+1,len-i-1);
447 if (best!=null)
448 return best;
449 }
450 break;
451 }
452
453 t=_tree[row+hilo(diff)];
454 if (t==0)
455 break loop;
456 }
457 }
458 return (V)_value[node];
459 }
460
461 @Override
462 public String toString()
463 {
464 StringBuilder buf = new StringBuilder();
465 for (int r=0;r<=_rows;r++)
466 {
467 if (_key[r]!=null && _value[r]!=null)
468 {
469 buf.append(',');
470 buf.append(_key[r]);
471 buf.append('=');
472 buf.append(_value[r].toString());
473 }
474 }
475 if (buf.length()==0)
476 return "{}";
477
478 buf.setCharAt(0,'{');
479 buf.append('}');
480 return buf.toString();
481 }
482
483
484
485 @Override
486 public Set<String> keySet()
487 {
488 Set<String> keys = new HashSet<>();
489
490 for (int r=0;r<=_rows;r++)
491 {
492 if (_key[r]!=null && _value[r]!=null)
493 keys.add(_key[r]);
494 }
495 return keys;
496 }
497
498 @Override
499 public boolean isFull()
500 {
501 return _rows+1==_key.length;
502 }
503
504 public static int hilo(int diff)
505 {
506 // branchless equivalent to return ((diff<0)?LO:HI);
507 // return 3+2*((diff&Integer.MIN_VALUE)>>Integer.SIZE-1);
508 return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
509 }
510
511 public void dump()
512 {
513 for (int r=0;r<_rows;r++)
514 {
515 char c=_tree[r*ROW_SIZE+0];
516 System.err.printf("%4d [%s,%d,%d,%d] '%s':%s%n",
517 r,
518 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
519 (int)_tree[r*ROW_SIZE+LO],
520 (int)_tree[r*ROW_SIZE+EQ],
521 (int)_tree[r*ROW_SIZE+HI],
522 _key[r],
523 _value[r]);
524 }
525
526 }
527 }