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