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 last=EQ;
122 int t=_tree[last];
123 int k;
124 int limit = s.length();
125 int node=0;
126 for(k=0; k < limit; k++)
127 {
128 char c=s.charAt(k);
129 if(isCaseInsensitive() && c<128)
130 c=StringUtil.lowercases[c];
131
132 while (true)
133 {
134 if (t==0)
135 {
136 node=t=++_rows;
137 if (_rows>=_key.length)
138 {
139 _rows--;
140 return false;
141 }
142 int row=ROW_SIZE*t;
143 _tree[row]=c;
144 _tree[last]=(char)t;
145 last=row+EQ;
146 }
147
148 int row=ROW_SIZE*t;
149 char n=_tree[row];
150 int diff=n-c;
151 if (diff==0)
152 {
153 node=t;
154 t=_tree[last=(row+EQ)];
155 break;
156 }
157 if (diff<0)
158 t=_tree[last=(row+LO)];
159 else
160 t=_tree[last=(row+HI)];
161 }
162 }
163 _key[node]=v==null?null:s;
164 _value[node] = v;
165
166 return true;
167 }
168
169 /* ------------------------------------------------------------ */
170 @Override
171 public V get(String s,int offset, int length)
172 {
173 int t = _tree[EQ];
174 int len = length;
175 int i=0;
176 while(i<len)
177 {
178 char c=s.charAt(offset+i++);
179 if(isCaseInsensitive() && c<128)
180 c=StringUtil.lowercases[c];
181
182 while (true)
183 {
184 int row = ROW_SIZE*t;
185 char n=_tree[row];
186 int diff=n-c;
187
188 if (diff==0)
189 {
190 if (i==len)
191 return (V)_value[t];
192 t=_tree[row+EQ];
193 if (t==0)
194 return null;
195 break;
196 }
197
198 t=_tree[row+hilo(diff)];
199 if (t==0)
200 return null;
201 }
202 }
203
204 return null;
205 }
206
207
208 @Override
209 public V get(ByteBuffer b, int offset, int length)
210 {
211 int t = _tree[EQ];
212 int len = length;
213 int i=0;
214 offset+=b.position();
215
216 while(i<len)
217 {
218 byte c=(byte)(b.get(offset+i++)&0x7f);
219 if(isCaseInsensitive())
220 c=(byte)StringUtil.lowercases[c];
221
222 while (true)
223 {
224 int row = ROW_SIZE*t;
225 char n=_tree[row];
226 int diff=n-c;
227
228 if (diff==0)
229 {
230 if (i==len)
231 return (V)_value[t];
232 t=_tree[row+EQ];
233 if (t==0)
234 return null;
235 break;
236 }
237
238 t=_tree[row+hilo(diff)];
239 if (t==0)
240 return null;
241 }
242 }
243
244 return null;
245 }
246
247 /* ------------------------------------------------------------ */
248 @Override
249 public V getBest(String s)
250 {
251 return getBest(_tree[EQ],s,0,s.length());
252 }
253
254 /* ------------------------------------------------------------ */
255 @Override
256 public V getBest(String s, int offset, int length)
257 {
258 return getBest(_tree[EQ],s,offset,length);
259 }
260
261 /* ------------------------------------------------------------ */
262 private V getBest(int t,String s,int offset,int len)
263 {
264 int node=0;
265 for(int i=0; t!=0 && i<len; i++)
266 {
267 char c=s.charAt(offset+i);
268 if(isCaseInsensitive() && c<128)
269 c=StringUtil.lowercases[c];
270
271 while (t!=0)
272 {
273 int row = ROW_SIZE*t;
274 char n=_tree[row];
275 int diff=n-c;
276
277 if (diff==0)
278 {
279 node=t;
280 t=_tree[row+EQ];
281
282 // if this node is a match, recurse to remember
283 if (_key[node]!=null)
284 {
285 V best=getBest(t,s,offset+i+1,len-i-1);
286 if (best!=null)
287 return best;
288 return (V)_value[node];
289 }
290
291 break;
292 }
293
294 t=_tree[row+hilo(diff)];
295 }
296 }
297 return null;
298 }
299
300
301 /* ------------------------------------------------------------ */
302 @Override
303 public V getBest(ByteBuffer b, int offset, int len)
304 {
305 if (b.hasArray())
306 return getBest(_tree[EQ],b.array(),b.arrayOffset()+b.position()+offset,len);
307 return getBest(_tree[EQ],b,offset,len);
308 }
309
310 /* ------------------------------------------------------------ */
311 private V getBest(int t,byte[] b, int offset, int len)
312 {
313 int node=0;
314 for(int i=0; t!=0 && i<len; i++)
315 {
316 byte c=(byte)(b[offset+i]&0x7f);
317 if(isCaseInsensitive())
318 c=(byte)StringUtil.lowercases[c];
319
320 while (t!=0)
321 {
322 int row = ROW_SIZE*t;
323 char n=_tree[row];
324 int diff=n-c;
325
326 if (diff==0)
327 {
328 node=t;
329 t=_tree[row+EQ];
330
331 // if this node is a match, recurse to remember
332 if (_key[node]!=null)
333 {
334 V best=getBest(t,b,offset+i+1,len-i-1);
335 if (best!=null)
336 return best;
337 return (V)_value[node];
338 }
339
340 break;
341 }
342
343 t=_tree[row+hilo(diff)];
344 }
345 }
346 return null;
347 }
348
349 /* ------------------------------------------------------------ */
350 private V getBest(int t,ByteBuffer b, int offset, int len)
351 {
352 int node=0;
353 int o= offset+b.position();
354
355 for(int i=0; t!=0 && i<len; i++)
356 {
357 byte c=(byte)(b.get(o+i)&0x7f);
358 if(isCaseInsensitive())
359 c=(byte)StringUtil.lowercases[c];
360
361 while (t!=0)
362 {
363 int row = ROW_SIZE*t;
364 char n=_tree[row];
365 int diff=n-c;
366
367 if (diff==0)
368 {
369 node=t;
370 t=_tree[row+EQ];
371
372 // if this node is a match, recurse to remember
373 if (_key[node]!=null)
374 {
375 V best=getBest(t,b,offset+i+1,len-i-1);
376 if (best!=null)
377 return best;
378 return (V)_value[node];
379 }
380
381 break;
382 }
383
384 t=_tree[row+hilo(diff)];
385 }
386 }
387 return null;
388 }
389
390 @Override
391 public String toString()
392 {
393 StringBuilder buf = new StringBuilder();
394 for (int r=1;r<=_rows;r++)
395 {
396 if (_key[r]!=null && _value[r]!=null)
397 {
398 buf.append(',');
399 buf.append(_key[r]);
400 buf.append('=');
401 buf.append(_value[r].toString());
402 }
403 }
404 if (buf.length()==0)
405 return "{}";
406
407 buf.setCharAt(0,'{');
408 buf.append('}');
409 return buf.toString();
410 }
411
412
413
414 @Override
415 public Set<String> keySet()
416 {
417 Set<String> keys = new HashSet<>();
418
419 for (int r=1;r<=_rows;r++)
420 {
421 if (_key[r]!=null && _value[r]!=null)
422 keys.add(_key[r]);
423 }
424 return keys;
425 }
426
427 @Override
428 public boolean isFull()
429 {
430 return _rows+1==_key.length;
431 }
432
433 public static int hilo(int diff)
434 {
435 // branchless equivalent to return ((diff<0)?LO:HI);
436 // return 3+2*((diff&Integer.MIN_VALUE)>>Integer.SIZE-1);
437 return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
438 }
439
440 public void dump()
441 {
442 for (int r=0;r<=_rows;r++)
443 {
444 char c=_tree[r*ROW_SIZE+0];
445 System.err.printf("%4d [%s,%d,%d,%d] %s:%s%n",
446 r,
447 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
448 (int)_tree[r*ROW_SIZE+LO],
449 (int)_tree[r*ROW_SIZE+EQ],
450 (int)_tree[r*ROW_SIZE+HI],
451 _key[r],
452 _value[r]);
453 }
454
455 }
456 }