1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
58 {
59 private static int LO=1;
60 private static int EQ=2;
61 private static int HI=3;
62
63
64
65
66
67 private static final int ROW_SIZE = 4;
68
69
70
71
72
73
74 private final char[] _tree;
75
76
77
78
79
80 private final String[] _key;
81
82
83
84
85
86 private final V[] _value;
87
88
89
90
91 private char _rows;
92
93
94
95
96 public ArrayTernaryTrie()
97 {
98 this(128);
99 }
100
101
102
103
104
105 public ArrayTernaryTrie(boolean insensitive)
106 {
107 this(insensitive,128);
108 }
109
110
111
112
113
114
115
116
117
118
119 public ArrayTernaryTrie(int capacity)
120 {
121 this(true,capacity);
122 }
123
124
125
126
127
128
129
130
131
132
133
134 public ArrayTernaryTrie(boolean insensitive, int capacity)
135 {
136 super(insensitive);
137 _value=(V[])new Object[capacity];
138 _tree=new char[capacity*ROW_SIZE];
139 _key=new String[capacity];
140 }
141
142
143
144
145
146
147 public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
148 {
149 super(trie.isCaseInsensitive());
150 int capacity=(int)(trie._value.length*factor);
151 _rows=trie._rows;
152 _value=Arrays.copyOf(trie._value, capacity);
153 _tree=Arrays.copyOf(trie._tree, capacity*ROW_SIZE);
154 _key=Arrays.copyOf(trie._key, capacity);
155 }
156
157
158 @Override
159 public boolean put(String s, V v)
160 {
161 int t=0;
162 int limit = s.length();
163 int last=0;
164 for(int k=0; k < limit; k++)
165 {
166 char c=s.charAt(k);
167 if(isCaseInsensitive() && c<128)
168 c=StringUtil.lowercases[c];
169
170 while (true)
171 {
172 int row=ROW_SIZE*t;
173
174
175 if (t==_rows)
176 {
177 _rows++;
178 if (_rows>=_key.length)
179 {
180 _rows--;
181 return false;
182 }
183 _tree[row]=c;
184 }
185
186 char n=_tree[row];
187 int diff=n-c;
188 if (diff==0)
189 t=_tree[last=(row+EQ)];
190 else if (diff<0)
191 t=_tree[last=(row+LO)];
192 else
193 t=_tree[last=(row+HI)];
194
195
196 if (t==0)
197 {
198 t=_rows;
199 _tree[last]=(char)t;
200 }
201
202 if (diff==0)
203 break;
204 }
205 }
206
207
208 if (t==_rows)
209 {
210 _rows++;
211 if (_rows>=_key.length)
212 {
213 _rows--;
214 return false;
215 }
216 }
217
218
219 _key[t]=v==null?null:s;
220 _value[t] = v;
221
222 return true;
223 }
224
225
226
227 @Override
228 public V get(String s,int offset, int len)
229 {
230 int t = 0;
231 for(int i=0; i < len;)
232 {
233 char c=s.charAt(offset+i++);
234 if(isCaseInsensitive() && c<128)
235 c=StringUtil.lowercases[c];
236
237 while (true)
238 {
239 int row = ROW_SIZE*t;
240 char n=_tree[row];
241 int diff=n-c;
242
243 if (diff==0)
244 {
245 t=_tree[row+EQ];
246 if (t==0)
247 return null;
248 break;
249 }
250
251 t=_tree[row+hilo(diff)];
252 if (t==0)
253 return null;
254 }
255 }
256
257 return _value[t];
258 }
259
260
261 @Override
262 public V get(ByteBuffer b, int offset, int len)
263 {
264 int t = 0;
265 offset+=b.position();
266
267 for(int i=0; i < len;)
268 {
269 byte c=(byte)(b.get(offset+i++)&0x7f);
270 if(isCaseInsensitive())
271 c=(byte)StringUtil.lowercases[c];
272
273 while (true)
274 {
275 int row = ROW_SIZE*t;
276 char n=_tree[row];
277 int diff=n-c;
278
279 if (diff==0)
280 {
281 t=_tree[row+EQ];
282 if (t==0)
283 return null;
284 break;
285 }
286
287 t=_tree[row+hilo(diff)];
288 if (t==0)
289 return null;
290 }
291 }
292
293 return (V)_value[t];
294 }
295
296
297 @Override
298 public V getBest(String s)
299 {
300 return getBest(0,s,0,s.length());
301 }
302
303
304 @Override
305 public V getBest(String s, int offset, int length)
306 {
307 return getBest(0,s,offset,length);
308 }
309
310
311 private V getBest(int t,String s,int offset,int len)
312 {
313 int node=t;
314 loop: for(int i=0; i<len; i++)
315 {
316 char c=s.charAt(offset+i);
317 if(isCaseInsensitive() && c<128)
318 c=StringUtil.lowercases[c];
319
320 while (true)
321 {
322 int row = ROW_SIZE*t;
323 char n=_tree[row];
324 int diff=n-c;
325
326 if (diff==0)
327 {
328 t=_tree[row+EQ];
329 if (t==0)
330 break loop;
331
332
333 if (_key[t]!=null)
334 {
335 node=t;
336 V best=getBest(t,s,offset+i+1,len-i-1);
337 if (best!=null)
338 return best;
339 }
340 break;
341 }
342
343 t=_tree[row+hilo(diff)];
344 if (t==0)
345 break loop;
346 }
347 }
348 return (V)_value[node];
349 }
350
351
352
353 @Override
354 public V getBest(ByteBuffer b, int offset, int len)
355 {
356 if (b.hasArray())
357 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
358 return getBest(0,b,offset,len);
359 }
360
361
362 private V getBest(int t,byte[] b, int offset, int len)
363 {
364 int node=t;
365 loop: for(int i=0; i<len; i++)
366 {
367 byte c=(byte)(b[offset+i]&0x7f);
368 if(isCaseInsensitive())
369 c=(byte)StringUtil.lowercases[c];
370
371 while (true)
372 {
373 int row = ROW_SIZE*t;
374 char n=_tree[row];
375 int diff=n-c;
376
377 if (diff==0)
378 {
379 t=_tree[row+EQ];
380 if (t==0)
381 break loop;
382
383
384 if (_key[t]!=null)
385 {
386 node=t;
387 V best=getBest(t,b,offset+i+1,len-i-1);
388 if (best!=null)
389 return best;
390 }
391 break;
392 }
393
394 t=_tree[row+hilo(diff)];
395 if (t==0)
396 break loop;
397 }
398 }
399 return (V)_value[node];
400 }
401
402
403 private V getBest(int t,ByteBuffer b, int offset, int len)
404 {
405 int node=t;
406 int o= offset+b.position();
407
408 loop: for(int i=0; i<len; i++)
409 {
410 byte c=(byte)(b.get(o+i)&0x7f);
411 if(isCaseInsensitive())
412 c=(byte)StringUtil.lowercases[c];
413
414 while (true)
415 {
416 int row = ROW_SIZE*t;
417 char n=_tree[row];
418 int diff=n-c;
419
420 if (diff==0)
421 {
422 t=_tree[row+EQ];
423 if (t==0)
424 break loop;
425
426
427 if (_key[t]!=null)
428 {
429 node=t;
430 V best=getBest(t,b,offset+i+1,len-i-1);
431 if (best!=null)
432 return best;
433 }
434 break;
435 }
436
437 t=_tree[row+hilo(diff)];
438 if (t==0)
439 break loop;
440 }
441 }
442 return (V)_value[node];
443 }
444
445 @Override
446 public String toString()
447 {
448 StringBuilder buf = new StringBuilder();
449 for (int r=0;r<=_rows;r++)
450 {
451 if (_key[r]!=null && _value[r]!=null)
452 {
453 buf.append(',');
454 buf.append(_key[r]);
455 buf.append('=');
456 buf.append(_value[r].toString());
457 }
458 }
459 if (buf.length()==0)
460 return "{}";
461
462 buf.setCharAt(0,'{');
463 buf.append('}');
464 return buf.toString();
465 }
466
467
468
469 @Override
470 public Set<String> keySet()
471 {
472 Set<String> keys = new HashSet<>();
473
474 for (int r=0;r<=_rows;r++)
475 {
476 if (_key[r]!=null && _value[r]!=null)
477 keys.add(_key[r]);
478 }
479 return keys;
480 }
481
482 @Override
483 public boolean isFull()
484 {
485 return _rows+1==_key.length;
486 }
487
488 public static int hilo(int diff)
489 {
490
491
492 return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
493 }
494
495 public void dump()
496 {
497 for (int r=0;r<_rows;r++)
498 {
499 char c=_tree[r*ROW_SIZE+0];
500 System.err.printf("%4d [%s,%d,%d,%d] '%s':%s%n",
501 r,
502 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
503 (int)_tree[r*ROW_SIZE+LO],
504 (int)_tree[r*ROW_SIZE+EQ],
505 (int)_tree[r*ROW_SIZE+HI],
506 _key[r],
507 _value[r]);
508 }
509
510 }
511 }