1 //
2 // ========================================================================
3 // Copyright (c) 1995-2013 Mort Bay Consulting Pty. Ltd.
4 // ------------------------------------------------------------------------
5 // All rights reserved. This program and the accompanying materials
6 // are made available under the terms of the Eclipse Public License v1.0
7 // and Apache License v2.0 which accompanies this distribution.
8 //
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
11 //
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
14 //
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
17 //
18
19 package org.eclipse.jetty.util;
20
21 import java.io.IOException;
22 import java.nio.ByteBuffer;
23 import java.util.HashSet;
24 import java.util.Set;
25
26
27 /* ------------------------------------------------------------ */
28 /** A Trie String lookup data structure.
29 * @param <V>
30 */
31 public class ArrayTrie<V> implements Trie<V>
32 {
33 /**
34 * The Size of a Trie row is how many characters can be looked
35 * up directly without going to a big index. This is set at
36 * 32 to cover case insensitive alphabet and a few other common
37 * characters.
38 */
39 private static final int ROW_SIZE = 32;
40
41 /**
42 * The index lookup table, this maps a character as a byte
43 * (ISO-8859-1 or UTF8) to an index within a Trie row
44 */
45 private static final int[] __lookup =
46 { // 0 1 2 3 4 5 6 7 8 9 A B C D E F
47 /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
48 /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 30,
49 /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, -1, -1,
50 /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
51 /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
52 /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
53 /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
54 /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
55 };
56
57 /**
58 * The Trie rows in a single array which allows a lookup of row,character
59 * to the next row in the Trie. This is actually a 2 dimensional
60 * array that has been flattened to achieve locality of reference.
61 * The first ROW_SIZE entries are for row 0, then next ROW_SIZE
62 * entries are for row 1 etc. So in general instead of using
63 * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up
64 * the next row for a given character.
65 *
66 * The array is of characters rather than integers to save space.
67 */
68 private final char[] _rowIndex;
69
70 /**
71 * The key (if any) for a Trie row.
72 * A row may be a leaf, a node or both in the Trie tree.
73 */
74 private final String[] _key;
75
76 /**
77 * The value (if any) for a Trie row.
78 * A row may be a leaf, a node or both in the Trie tree.
79 */
80 private final Object[] _value;
81
82 /**
83 * A big index for each row.
84 * If a character outside of the lookup map is needed,
85 * then a big index will be created for the row, with
86 * 256 entries, one for each possible byte.
87 */
88 private char[][] _bigIndex;
89
90 /**
91 * The number of rows allocated
92 */
93 private char _rows;
94
95 public ArrayTrie()
96 {
97 this(128);
98 }
99
100 public ArrayTrie(int capacityInNodes)
101 {
102 _value=new Object[capacityInNodes];
103 _rowIndex=new char[capacityInNodes*32];
104 _key=new String[capacityInNodes];
105 }
106
107
108 /* ------------------------------------------------------------ */
109 @Override
110 public boolean put(String s, V v)
111 {
112 int t=0;
113 int k;
114 int limit = s.length();
115 for(k=0; k < limit; k++)
116 {
117 char c=s.charAt(k);
118
119 int index=__lookup[c&0x7f];
120 if (index>=0)
121 {
122 int idx=t*ROW_SIZE+index;
123 t=_rowIndex[idx];
124 if (t==0)
125 {
126 if (++_rows>=_value.length)
127 return false;
128 t=_rowIndex[idx]=_rows;
129 }
130 }
131 else if (c>127)
132 throw new IllegalArgumentException("non ascii character");
133 else
134 {
135 if (_bigIndex==null)
136 _bigIndex=new char[_value.length][];
137 if (t>=_bigIndex.length)
138 return false;
139 char[] big=_bigIndex[t];
140 if (big==null)
141 big=_bigIndex[t]=new char[128];
142 t=big[c];
143 if (t==0)
144 {
145 if (_rows==_value.length)
146 return false;
147 t=big[c]=++_rows;
148 }
149 }
150 }
151 _key[t]=v==null?null:s;
152 V old=(V)_value[t];
153 _value[t] = v;
154 return true;
155 }
156
157
158 /* ------------------------------------------------------------ */
159 @Override
160 public boolean put(V v)
161 {
162 return put(v.toString(),v);
163 }
164
165 /* ------------------------------------------------------------ */
166 @Override
167 public V remove(String s)
168 {
169 V o=get(s);
170 put(s,null);
171 return o;
172 }
173
174 /* ------------------------------------------------------------ */
175 @Override
176 public V get(String s)
177 {
178 int t = 0;
179 int len = s.length();
180 for(int i=0; i < len; i++)
181 {
182 char c=s.charAt(i);
183 int index=__lookup[c&0x7f];
184 if (index>=0)
185 {
186 int idx=t*ROW_SIZE+index;
187 t=_rowIndex[idx];
188 if (t==0)
189 return null;
190 }
191 else
192 {
193 char[] big = _bigIndex==null?null:_bigIndex[t];
194 if (big==null)
195 return null;
196 t=big[c];
197 if (t==0)
198 return null;
199 }
200 }
201 return (V)_value[t];
202 }
203
204 /* ------------------------------------------------------------ */
205 @Override
206 public V get(ByteBuffer b,int offset,int len)
207 {
208 int t = 0;
209 for(int i=0; i < len; i++)
210 {
211 byte c=b.get(offset+i);
212 int index=__lookup[c&0x7f];
213 if (index>=0)
214 {
215 int idx=t*ROW_SIZE+index;
216 t=_rowIndex[idx];
217 if (t==0)
218 return null;
219 }
220 else
221 {
222 char[] big = _bigIndex==null?null:_bigIndex[t];
223 if (big==null)
224 return null;
225 t=big[c];
226 if (t==0)
227 return null;
228 }
229 }
230 return (V)_value[t];
231 }
232
233 /* ------------------------------------------------------------ */
234 @Override
235 public V getBest(byte[] b,int offset,int len)
236 {
237 return getBest(0,b,offset,len);
238 }
239
240 /* ------------------------------------------------------------ */
241 @Override
242 public V getBest(ByteBuffer b,int offset,int len)
243 {
244 if (b.hasArray())
245 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
246 return getBest(0,b,offset,len);
247 }
248
249 private V getBest(int t,byte[] b,int offset,int len)
250 {
251 for(int i=0; i < len; i++)
252 {
253 byte c=b[offset+i];
254 int index=__lookup[c&0x7f];
255 if (index>=0)
256 {
257 int idx=t*ROW_SIZE+index;
258 t=_rowIndex[idx];
259 if (t==0)
260 return null;
261 }
262 else
263 {
264 char[] big = _bigIndex==null?null:_bigIndex[t];
265 if (big==null)
266 return null;
267 t=big[c];
268 if (t==0)
269 return null;
270 }
271
272 // Is the next Trie is a match
273 if (_key[t]!=null)
274 {
275 // Recurse so we can remember this possibility
276 V best=getBest(t,b,offset+i+1,len-i-1);
277 if (best!=null)
278 return best;
279 return (V)_value[t];
280 }
281 }
282 return (V)_value[t];
283 }
284
285 private V getBest(int t,ByteBuffer b,int offset,int len)
286 {
287 int pos=b.position()+offset;
288 for(int i=0; i < len; i++)
289 {
290 byte c=b.get(pos++);
291 int index=__lookup[c&0x7f];
292 if (index>=0)
293 {
294 int idx=t*ROW_SIZE+index;
295 t=_rowIndex[idx];
296 if (t==0)
297 return null;
298 }
299 else
300 {
301 char[] big = _bigIndex==null?null:_bigIndex[t];
302 if (big==null)
303 return null;
304 t=big[c];
305 if (t==0)
306 return null;
307 }
308
309 // Is the next Trie is a match
310 if (_key[t]!=null)
311 {
312 // Recurse so we can remember this possibility
313 V best=getBest(t,b,offset+i+1,len-i-1);
314 if (best!=null)
315 return best;
316 return (V)_value[t];
317 }
318 }
319 return (V)_value[t];
320 }
321
322
323
324
325 @Override
326 public String toString()
327 {
328 StringBuilder buf = new StringBuilder();
329 toString(buf,0);
330
331 if (buf.length()==0)
332 return "{}";
333
334 buf.setCharAt(0,'{');
335 buf.append('}');
336 return buf.toString();
337 }
338
339
340 private <V> void toString(Appendable out, int t)
341 {
342 if (_value[t]!=null)
343 {
344 try
345 {
346 out.append(',');
347 out.append(_key[t]);
348 out.append('=');
349 out.append(_value[t].toString());
350 }
351 catch (IOException e)
352 {
353 throw new RuntimeException(e);
354 }
355 }
356
357 for(int i=0; i < ROW_SIZE; i++)
358 {
359 int idx=t*ROW_SIZE+i;
360 if (_rowIndex[idx] != 0)
361 toString(out,_rowIndex[idx]);
362 }
363
364 char[] big = _bigIndex==null?null:_bigIndex[t];
365 if (big!=null)
366 {
367 for (int i:big)
368 if (i!=0)
369 toString(out,i);
370 }
371
372 }
373
374 @Override
375 public Set<String> keySet()
376 {
377 Set<String> keys = new HashSet<>();
378 keySet(keys,0);
379 return keys;
380 }
381
382 private void keySet(Set<String> set, int t)
383 {
384 if (t<_value.length&&_value[t]!=null)
385 set.add(_key[t]);
386
387 for(int i=0; i < ROW_SIZE; i++)
388 {
389 int idx=t*ROW_SIZE+i;
390 if (idx<_rowIndex.length && _rowIndex[idx] != 0)
391 keySet(set,_rowIndex[idx]);
392 }
393
394 char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
395 if (big!=null)
396 {
397 for (int i:big)
398 if (i!=0)
399 keySet(set,i);
400 }
401 }
402
403 @Override
404 public boolean isFull()
405 {
406 return _rows+1==_key.length;
407 }
408 }