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