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 public class TreeTrie<V> implements Trie<V>
29 {
30 private static final int[] __lookup =
31 {
32
33
34
35
36
37
38
39
40 };
41 private static final int INDEX = 32;
42 private final TreeTrie<V>[] _nextIndex;
43 private final List<TreeTrie<V>> _nextOther=new ArrayList<>();
44 private final char _c;
45 private String _key;
46 private V _value;
47
48 public TreeTrie()
49 {
50 _nextIndex = new TreeTrie[INDEX];
51 _c=0;
52 }
53
54 private TreeTrie(char c)
55 {
56 _nextIndex = new TreeTrie[INDEX];
57 this._c=c;
58 }
59
60 @Override
61 public boolean put(V v)
62 {
63 return put(v.toString(),v);
64 }
65
66 @Override
67 public boolean put(String s, V v)
68 {
69 TreeTrie<V> t = this;
70 int k;
71 int limit = s.length();
72 for(k=0; k < limit; k++)
73 {
74 char c=s.charAt(k);
75
76 int index=c>=0&&c<0x7f?__lookup[c]:-1;
77 if (index>=0)
78 {
79 if (t._nextIndex[index] == null)
80 t._nextIndex[index] = new TreeTrie<V>(c);
81 t = t._nextIndex[index];
82 }
83 else
84 {
85 TreeTrie<V> n=null;
86 for (int i=t._nextOther.size();i-->0;)
87 {
88 n=t._nextOther.get(i);
89 if (n._c==c)
90 break;
91 n=null;
92 }
93 if (n==null)
94 {
95 n=new TreeTrie<V>(c);
96 t._nextOther.add(n);
97 }
98 t=n;
99 }
100 }
101 t._key=v==null?null:s;
102 V old=t._value;
103 t._value = v;
104 return true;
105 }
106
107 @Override
108 public V remove(String s)
109 {
110 V o=get(s);
111 put(s,null);
112 return o;
113 }
114
115 @Override
116 public V get(String s)
117 {
118 TreeTrie<V> t = this;
119 int len = s.length();
120 for(int i=0; i < len; i++)
121 {
122 char c=s.charAt(i);
123 int index=c>=0&&c<0x7f?__lookup[c]:-1;
124 if (index>=0)
125 {
126 if (t._nextIndex[index] == null)
127 return null;
128 t = t._nextIndex[index];
129 }
130 else
131 {
132 TreeTrie<V> n=null;
133 for (int j=t._nextOther.size();j-->0;)
134 {
135 n=t._nextOther.get(j);
136 if (n._c==c)
137 break;
138 n=null;
139 }
140 if (n==null)
141 return null;
142 t=n;
143 }
144 }
145 return t._value;
146 }
147
148 @Override
149 public V get(ByteBuffer b,int offset,int len)
150 {
151 TreeTrie<V> t = this;
152 for(int i=0; i < len; i++)
153 {
154 byte c=b.get(offset+i);
155 int index=c>=0&&c<0x7f?__lookup[c]:-1;
156 if (index>=0)
157 {
158 if (t._nextIndex[index] == null)
159 return null;
160 t = t._nextIndex[index];
161 }
162 else
163 {
164 TreeTrie<V> n=null;
165 for (int j=t._nextOther.size();j-->0;)
166 {
167 n=t._nextOther.get(j);
168 if (n._c==c)
169 break;
170 n=null;
171 }
172 if (n==null)
173 return null;
174 t=n;
175 }
176 }
177 return t._value;
178 }
179
180 @Override
181 public V getBest(byte[] b,int offset,int len)
182 {
183 TreeTrie<V> t = this;
184 for(int i=0; i < len; i++)
185 {
186 byte c=b[offset+i];
187 int index=c>=0&&c<0x7f?__lookup[c]:-1;
188 if (index>=0)
189 {
190 if (t._nextIndex[index] == null)
191 return null;
192 t = t._nextIndex[index];
193 }
194 else
195 {
196 TreeTrie<V> n=null;
197 for (int j=t._nextOther.size();j-->0;)
198 {
199 n=t._nextOther.get(j);
200 if (n._c==c)
201 break;
202 n=null;
203 }
204 if (n==null)
205 return null;
206 t=n;
207 }
208
209
210 if (t._key!=null)
211 {
212
213 V best=t.getBest(b,offset+i+1,len-i-1);
214 if (best!=null)
215 return best;
216 return t._value;
217 }
218 }
219 return t._value;
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 return null;
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 return null;
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 return t._value;
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 }