2 // ========================================================================
3 // Copyright (c) 1995-2016 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.
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
19 package org.eclipse.jetty.util;
21 import java.io.IOException;
22 import java.nio.ByteBuffer;
23 import java.util.HashSet;
26 /* ------------------------------------------------------------ */
28 * <p>A Trie String lookup data structure using a fixed size array.</p>
29 * <p>This implementation is always case insensitive and is optimal for
30 * a small number of fixed strings with few special characters. The
31 * Trie is stored in an array of lookup tables, each indexed by the
32 * next character of the key. Frequently used characters are directly
33 * indexed in each lookup table, whilst infrequently used characters
34 * must use a big character table.
36 * <p>This Trie is very space efficient if the key characters are
37 * from ' ', '+', '-', ':', ';', '.', 'A' to 'Z' or 'a' to 'z'.
38 * Other ISO-8859-1 characters can be used by the key, but less space
41 * <p>This Trie is not Threadsafe and contains no mutual exclusion
42 * or deliberate memory barriers. It is intended for an ArrayTrie to be
43 * built by a single thread and then used concurrently by multiple threads
44 * and not mutated during that access. If concurrent mutations of the
45 * Trie is required external locks need to be applied.
49 public class ArrayTrie<V> extends AbstractTrie<V>
52 * The Size of a Trie row is how many characters can be looked
53 * up directly without going to a big index. This is set at
54 * 32 to cover case insensitive alphabet and a few other common
57 private static final int ROW_SIZE = 32;
60 * The index lookup table, this maps a character as a byte
61 * (ISO-8859-1 or UTF8) to an index within a Trie row
63 private static final int[] __lookup =
64 { // 0 1 2 3 4 5 6 7 8 9 A B C D E F
65 /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
66 /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
67 /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1,
68 /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
69 /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
70 /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
71 /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
72 /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
76 * The Trie rows in a single array which allows a lookup of row,character
77 * to the next row in the Trie. This is actually a 2 dimensional
78 * array that has been flattened to achieve locality of reference.
79 * The first ROW_SIZE entries are for row 0, then next ROW_SIZE
80 * entries are for row 1 etc. So in general instead of using
81 * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up
82 * the next row for a given character.
84 * The array is of characters rather than integers to save space.
86 private final char[] _rowIndex;
89 * The key (if any) for a Trie row.
90 * A row may be a leaf, a node or both in the Trie tree.
92 private final String[] _key;
95 * The value (if any) for a Trie row.
96 * A row may be a leaf, a node or both in the Trie tree.
98 private final V[] _value;
101 * A big index for each row.
102 * If a character outside of the lookup map is needed,
103 * then a big index will be created for the row, with
104 * 256 entries, one for each possible byte.
106 private char[][] _bigIndex;
109 * The number of rows allocated
118 /* ------------------------------------------------------------ */
120 * @param capacity The capacity of the trie, which at the worst case
121 * is the total number of characters of all keys stored in the Trie.
122 * The capacity needed is dependent of the shared prefixes of the keys.
123 * For example, a capacity of 6 nodes is required to store keys "foo"
124 * and "bar", but a capacity of only 4 is required to
125 * store "bar" and "bat".
127 @SuppressWarnings("unchecked")
128 public ArrayTrie(int capacity)
131 _value=(V[])new Object[capacity];
132 _rowIndex=new char[capacity*32];
133 _key=new String[capacity];
137 /* ------------------------------------------------------------ */
139 public boolean put(String s, V v)
143 int limit = s.length();
144 for(k=0; k < limit; k++)
148 int index=__lookup[c&0x7f];
151 int idx=t*ROW_SIZE+index;
155 if (++_rows>=_value.length)
157 t=_rowIndex[idx]=_rows;
161 throw new IllegalArgumentException("non ascii character");
165 _bigIndex=new char[_value.length][];
166 if (t>=_bigIndex.length)
168 char[] big=_bigIndex[t];
170 big=_bigIndex[t]=new char[128];
174 if (_rows==_value.length)
183 _rows=(char)_key.length;
187 _key[t]=v==null?null:s;
192 /* ------------------------------------------------------------ */
194 public V get(String s, int offset, int len)
197 for(int i=0; i < len; i++)
199 char c=s.charAt(offset+i);
200 int index=__lookup[c&0x7f];
203 int idx=t*ROW_SIZE+index;
210 char[] big = _bigIndex==null?null:_bigIndex[t];
221 /* ------------------------------------------------------------ */
223 public V get(ByteBuffer b,int offset,int len)
226 for(int i=0; i < len; i++)
228 byte c=b.get(offset+i);
229 int index=__lookup[c&0x7f];
232 int idx=t*ROW_SIZE+index;
239 char[] big = _bigIndex==null?null:_bigIndex[t];
250 /* ------------------------------------------------------------ */
252 public V getBest(byte[] b,int offset,int len)
254 return getBest(0,b,offset,len);
257 /* ------------------------------------------------------------ */
259 public V getBest(ByteBuffer b,int offset,int len)
262 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
263 return getBest(0,b,offset,len);
266 /* ------------------------------------------------------------ */
268 public V getBest(String s, int offset, int len)
270 return getBest(0,s,offset,len);
273 /* ------------------------------------------------------------ */
274 private V getBest(int t, String s, int offset, int len)
277 for(int i=0; i < len; i++)
279 char c=s.charAt(pos++);
280 int index=__lookup[c&0x7f];
283 int idx=t*ROW_SIZE+index;
284 int nt=_rowIndex[idx];
291 char[] big = _bigIndex==null?null:_bigIndex[t];
300 // Is the next Trie is a match
303 // Recurse so we can remember this possibility
304 V best=getBest(t,s,offset+i+1,len-i-1);
313 /* ------------------------------------------------------------ */
314 private V getBest(int t,byte[] b,int offset,int len)
316 for(int i=0; i < len; i++)
319 int index=__lookup[c&0x7f];
322 int idx=t*ROW_SIZE+index;
323 int nt=_rowIndex[idx];
330 char[] big = _bigIndex==null?null:_bigIndex[t];
339 // Is the next Trie is a match
342 // Recurse so we can remember this possibility
343 V best=getBest(t,b,offset+i+1,len-i-1);
352 private V getBest(int t,ByteBuffer b,int offset,int len)
354 int pos=b.position()+offset;
355 for(int i=0; i < len; i++)
358 int index=__lookup[c&0x7f];
361 int idx=t*ROW_SIZE+index;
362 int nt=_rowIndex[idx];
369 char[] big = _bigIndex==null?null:_bigIndex[t];
378 // Is the next Trie is a match
381 // Recurse so we can remember this possibility
382 V best=getBest(t,b,offset+i+1,len-i-1);
395 public String toString()
397 StringBuilder buf = new StringBuilder();
403 buf.setCharAt(0,'{');
405 return buf.toString();
409 private void toString(Appendable out, int t)
418 out.append(_value[t].toString());
420 catch (IOException e)
422 throw new RuntimeException(e);
426 for(int i=0; i < ROW_SIZE; i++)
428 int idx=t*ROW_SIZE+i;
429 if (_rowIndex[idx] != 0)
430 toString(out,_rowIndex[idx]);
433 char[] big = _bigIndex==null?null:_bigIndex[t];
444 public Set<String> keySet()
446 Set<String> keys = new HashSet<>();
451 private void keySet(Set<String> set, int t)
453 if (t<_value.length&&_value[t]!=null)
456 for(int i=0; i < ROW_SIZE; i++)
458 int idx=t*ROW_SIZE+i;
459 if (idx<_rowIndex.length && _rowIndex[idx] != 0)
460 keySet(set,_rowIndex[idx]);
463 char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
473 public boolean isFull()
475 return _rows+1>=_key.length;