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