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.nio.charset.StandardCharsets;
24 import java.util.ArrayList;
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 boolean put(String s, V v)
81 {
82 TreeTrie<V> t = this;
83 int limit = s.length();
84 for(int k=0; k < limit; k++)
85 {
86 char c=s.charAt(k);
87
88 int index=c>=0&&c<0x7f?__lookup[c]:-1;
89 if (index>=0)
90 {
91 if (t._nextIndex[index] == null)
92 t._nextIndex[index] = new TreeTrie<V>(c);
93 t = t._nextIndex[index];
94 }
95 else
96 {
97 TreeTrie<V> n=null;
98 for (int i=t._nextOther.size();i-->0;)
99 {
100 n=t._nextOther.get(i);
101 if (n._c==c)
102 break;
103 n=null;
104 }
105 if (n==null)
106 {
107 n=new TreeTrie<V>(c);
108 t._nextOther.add(n);
109 }
110 t=n;
111 }
112 }
113 t._key=v==null?null:s;
114 t._value = v;
115 return true;
116 }
117
118 @Override
119 public V get(String s,int offset, int len)
120 {
121 TreeTrie<V> t = this;
122 for(int i=0; i < len; i++)
123 {
124 char c=s.charAt(offset+i);
125 int index=c>=0&&c<0x7f?__lookup[c]:-1;
126 if (index>=0)
127 {
128 if (t._nextIndex[index] == null)
129 return null;
130 t = t._nextIndex[index];
131 }
132 else
133 {
134 TreeTrie<V> n=null;
135 for (int j=t._nextOther.size();j-->0;)
136 {
137 n=t._nextOther.get(j);
138 if (n._c==c)
139 break;
140 n=null;
141 }
142 if (n==null)
143 return null;
144 t=n;
145 }
146 }
147 return t._value;
148 }
149
150 @Override
151 public V get(ByteBuffer b,int offset,int len)
152 {
153 TreeTrie<V> t = this;
154 for(int i=0; i < len; i++)
155 {
156 byte c=b.get(offset+i);
157 int index=c>=0&&c<0x7f?__lookup[c]:-1;
158 if (index>=0)
159 {
160 if (t._nextIndex[index] == null)
161 return null;
162 t = t._nextIndex[index];
163 }
164 else
165 {
166 TreeTrie<V> n=null;
167 for (int j=t._nextOther.size();j-->0;)
168 {
169 n=t._nextOther.get(j);
170 if (n._c==c)
171 break;
172 n=null;
173 }
174 if (n==null)
175 return null;
176 t=n;
177 }
178 }
179 return t._value;
180 }
181
182 @Override
183 public V getBest(byte[] b,int offset,int len)
184 {
185 TreeTrie<V> t = this;
186 for(int i=0; i < len; i++)
187 {
188 byte c=b[offset+i];
189 int index=c>=0&&c<0x7f?__lookup[c]:-1;
190 if (index>=0)
191 {
192 if (t._nextIndex[index] == null)
193 break;
194 t = t._nextIndex[index];
195 }
196 else
197 {
198 TreeTrie<V> n=null;
199 for (int j=t._nextOther.size();j-->0;)
200 {
201 n=t._nextOther.get(j);
202 if (n._c==c)
203 break;
204 n=null;
205 }
206 if (n==null)
207 break;
208 t=n;
209 }
210
211
212 if (t._key!=null)
213 {
214
215 V best=t.getBest(b,offset+i+1,len-i-1);
216 if (best!=null)
217 return best;
218 break;
219 }
220 }
221 return t._value;
222 }
223
224 @Override
225 public V getBest(String s, int offset, int len)
226 {
227
228 byte[] b=s.substring(offset,offset+len).getBytes(StandardCharsets.ISO_8859_1);
229 return getBest(b,0,b.length);
230 }
231
232 @Override
233 public V getBest(ByteBuffer b,int offset,int len)
234 {
235 if (b.hasArray())
236 return getBest(b.array(),b.arrayOffset()+b.position()+offset,len);
237 return getBestByteBuffer(b,offset,len);
238 }
239
240 private V getBestByteBuffer(ByteBuffer b,int offset,int len)
241 {
242 TreeTrie<V> t = this;
243 int pos=b.position()+offset;
244 for(int i=0; i < len; i++)
245 {
246 byte c=b.get(pos++);
247 int index=c>=0&&c<0x7f?__lookup[c]:-1;
248 if (index>=0)
249 {
250 if (t._nextIndex[index] == null)
251 break;
252 t = t._nextIndex[index];
253 }
254 else
255 {
256 TreeTrie<V> n=null;
257 for (int j=t._nextOther.size();j-->0;)
258 {
259 n=t._nextOther.get(j);
260 if (n._c==c)
261 break;
262 n=null;
263 }
264 if (n==null)
265 break;
266 t=n;
267 }
268
269
270 if (t._key!=null)
271 {
272
273 V best=t.getBest(b,offset+i+1,len-i-1);
274 if (best!=null)
275 return best;
276 break;
277 }
278 }
279 return t._value;
280 }
281
282
283 @Override
284 public String toString()
285 {
286 StringBuilder buf = new StringBuilder();
287 toString(buf,this);
288
289 if (buf.length()==0)
290 return "{}";
291
292 buf.setCharAt(0,'{');
293 buf.append('}');
294 return buf.toString();
295 }
296
297 private static <V> void toString(Appendable out, TreeTrie<V> t)
298 {
299 if (t != null)
300 {
301 if (t._value!=null)
302 {
303 try
304 {
305 out.append(',');
306 out.append(t._key);
307 out.append('=');
308 out.append(t._value.toString());
309 }
310 catch (IOException e)
311 {
312 throw new RuntimeException(e);
313 }
314 }
315
316 for(int i=0; i < INDEX; i++)
317 {
318 if (t._nextIndex[i] != null)
319 toString(out,t._nextIndex[i]);
320 }
321 for (int i=t._nextOther.size();i-->0;)
322 toString(out,t._nextOther.get(i));
323 }
324 }
325
326 @Override
327 public Set<String> keySet()
328 {
329 Set<String> keys = new HashSet<>();
330 keySet(keys,this);
331 return keys;
332 }
333
334 private static <V> void keySet(Set<String> set, TreeTrie<V> t)
335 {
336 if (t != null)
337 {
338 if (t._key!=null)
339 set.add(t._key);
340
341 for(int i=0; i < INDEX; i++)
342 {
343 if (t._nextIndex[i] != null)
344 keySet(set,t._nextIndex[i]);
345 }
346 for (int i=t._nextOther.size();i-->0;)
347 keySet(set,t._nextOther.get(i));
348 }
349 }
350
351 @Override
352 public boolean isFull()
353 {
354 return false;
355 }
356
357
358 }