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