2 // ========================================================================
3 // Copyright (c) 1995-2014 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 /* ------------------------------------------------------------ */
27 /** A Trie String lookup data structure using a fixed size array.
28 * <p>This implementation is always case insensitive and is optimal for
29 * a small number of fixed strings with few special characters.
33 public class ArrayTrie<V> extends AbstractTrie<V>
36 * The Size of a Trie row is how many characters can be looked
37 * up directly without going to a big index. This is set at
38 * 32 to cover case insensitive alphabet and a few other common
41 private static final int ROW_SIZE = 32;
44 * The index lookup table, this maps a character as a byte
45 * (ISO-8859-1 or UTF8) to an index within a Trie row
47 private static final int[] __lookup =
48 { // 0 1 2 3 4 5 6 7 8 9 A B C D E F
49 /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
50 /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 30,
51 /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, -1, -1,
52 /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
53 /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
54 /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
55 /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
56 /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
60 * The Trie rows in a single array which allows a lookup of row,character
61 * to the next row in the Trie. This is actually a 2 dimensional
62 * array that has been flattened to achieve locality of reference.
63 * The first ROW_SIZE entries are for row 0, then next ROW_SIZE
64 * entries are for row 1 etc. So in general instead of using
65 * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up
66 * the next row for a given character.
68 * The array is of characters rather than integers to save space.
70 private final char[] _rowIndex;
73 * The key (if any) for a Trie row.
74 * A row may be a leaf, a node or both in the Trie tree.
76 private final String[] _key;
79 * The value (if any) for a Trie row.
80 * A row may be a leaf, a node or both in the Trie tree.
82 private final Object[] _value;
85 * A big index for each row.
86 * If a character outside of the lookup map is needed,
87 * then a big index will be created for the row, with
88 * 256 entries, one for each possible byte.
90 private char[][] _bigIndex;
93 * The number of rows allocated
102 public ArrayTrie(int capacityInNodes)
105 _value=new Object[capacityInNodes];
106 _rowIndex=new char[capacityInNodes*32];
107 _key=new String[capacityInNodes];
111 /* ------------------------------------------------------------ */
113 public boolean put(String s, V v)
117 int limit = s.length();
118 for(k=0; k < limit; k++)
122 int index=__lookup[c&0x7f];
125 int idx=t*ROW_SIZE+index;
129 if (++_rows>=_value.length)
131 t=_rowIndex[idx]=_rows;
135 throw new IllegalArgumentException("non ascii character");
139 _bigIndex=new char[_value.length][];
140 if (t>=_bigIndex.length)
142 char[] big=_bigIndex[t];
144 big=_bigIndex[t]=new char[128];
148 if (_rows==_value.length)
154 _key[t]=v==null?null:s;
160 /* ------------------------------------------------------------ */
162 public V get(String s, int offset, int len)
165 for(int i=0; i < len; i++)
167 char c=s.charAt(offset+i);
168 int index=__lookup[c&0x7f];
171 int idx=t*ROW_SIZE+index;
178 char[] big = _bigIndex==null?null:_bigIndex[t];
189 /* ------------------------------------------------------------ */
191 public V get(ByteBuffer b,int offset,int len)
194 for(int i=0; i < len; i++)
196 byte c=b.get(offset+i);
197 int index=__lookup[c&0x7f];
200 int idx=t*ROW_SIZE+index;
207 char[] big = _bigIndex==null?null:_bigIndex[t];
218 /* ------------------------------------------------------------ */
220 public V getBest(byte[] b,int offset,int len)
222 return getBest(0,b,offset,len);
225 /* ------------------------------------------------------------ */
227 public V getBest(ByteBuffer b,int offset,int len)
230 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
231 return getBest(0,b,offset,len);
234 /* ------------------------------------------------------------ */
236 public V getBest(String s, int offset, int len)
238 return getBest(0,s,offset,len);
241 /* ------------------------------------------------------------ */
242 private V getBest(int t, String s, int offset, int len)
245 for(int i=0; i < len; i++)
247 char c=s.charAt(pos++);
248 int index=__lookup[c&0x7f];
251 int idx=t*ROW_SIZE+index;
252 int nt=_rowIndex[idx];
259 char[] big = _bigIndex==null?null:_bigIndex[t];
268 // Is the next Trie is a match
271 // Recurse so we can remember this possibility
272 V best=getBest(t,s,offset+i+1,len-i-1);
281 /* ------------------------------------------------------------ */
282 private V getBest(int t,byte[] b,int offset,int len)
284 for(int i=0; i < len; i++)
287 int index=__lookup[c&0x7f];
290 int idx=t*ROW_SIZE+index;
291 int nt=_rowIndex[idx];
298 char[] big = _bigIndex==null?null:_bigIndex[t];
307 // Is the next Trie is a match
310 // Recurse so we can remember this possibility
311 V best=getBest(t,b,offset+i+1,len-i-1);
320 private V getBest(int t,ByteBuffer b,int offset,int len)
322 int pos=b.position()+offset;
323 for(int i=0; i < len; i++)
326 int index=__lookup[c&0x7f];
329 int idx=t*ROW_SIZE+index;
330 int nt=_rowIndex[idx];
337 char[] big = _bigIndex==null?null:_bigIndex[t];
346 // Is the next Trie is a match
349 // Recurse so we can remember this possibility
350 V best=getBest(t,b,offset+i+1,len-i-1);
363 public String toString()
365 StringBuilder buf = new StringBuilder();
371 buf.setCharAt(0,'{');
373 return buf.toString();
377 private <V> void toString(Appendable out, int t)
386 out.append(_value[t].toString());
388 catch (IOException e)
390 throw new RuntimeException(e);
394 for(int i=0; i < ROW_SIZE; i++)
396 int idx=t*ROW_SIZE+i;
397 if (_rowIndex[idx] != 0)
398 toString(out,_rowIndex[idx]);
401 char[] big = _bigIndex==null?null:_bigIndex[t];
412 public Set<String> keySet()
414 Set<String> keys = new HashSet<>();
419 private void keySet(Set<String> set, int t)
421 if (t<_value.length&&_value[t]!=null)
424 for(int i=0; i < ROW_SIZE; i++)
426 int idx=t*ROW_SIZE+i;
427 if (idx<_rowIndex.length && _rowIndex[idx] != 0)
428 keySet(set,_rowIndex[idx]);
431 char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
441 public boolean isFull()
443 return _rows+1==_key.length;