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