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