| // |
| // ======================================================================== |
| // Copyright (c) 1995-2017 Mort Bay Consulting Pty. Ltd. |
| // ------------------------------------------------------------------------ |
| // All rights reserved. This program and the accompanying materials |
| // are made available under the terms of the Eclipse Public License v1.0 |
| // and Apache License v2.0 which accompanies this distribution. |
| // |
| // The Eclipse Public License is available at |
| // http://www.eclipse.org/legal/epl-v10.html |
| // |
| // The Apache License v2.0 is available at |
| // http://www.opensource.org/licenses/apache2.0.php |
| // |
| // You may elect to redistribute this code under either of these licenses. |
| // ======================================================================== |
| // |
| |
| package org.eclipse.jetty.util; |
| |
| import java.io.IOException; |
| import java.nio.ByteBuffer; |
| import java.util.Arrays; |
| import java.util.HashSet; |
| import java.util.Set; |
| |
| /* ------------------------------------------------------------ */ |
| /** |
| * <p>A Trie String lookup data structure using a fixed size array.</p> |
| * <p>This implementation is always case insensitive and is optimal for |
| * a small number of fixed strings with few special characters. The |
| * Trie is stored in an array of lookup tables, each indexed by the |
| * next character of the key. Frequently used characters are directly |
| * indexed in each lookup table, whilst infrequently used characters |
| * must use a big character table. |
| * </p> |
| * <p>This Trie is very space efficient if the key characters are |
| * from ' ', '+', '-', ':', ';', '.', 'A' to 'Z' or 'a' to 'z'. |
| * Other ISO-8859-1 characters can be used by the key, but less space |
| * efficiently. |
| * </p> |
| * <p>This Trie is not Threadsafe and contains no mutual exclusion |
| * or deliberate memory barriers. It is intended for an ArrayTrie to be |
| * built by a single thread and then used concurrently by multiple threads |
| * and not mutated during that access. If concurrent mutations of the |
| * Trie is required external locks need to be applied. |
| * </p> |
| * @param <V> the entry type |
| */ |
| public class ArrayTrie<V> extends AbstractTrie<V> |
| { |
| /** |
| * The Size of a Trie row is how many characters can be looked |
| * up directly without going to a big index. This is set at |
| * 32 to cover case insensitive alphabet and a few other common |
| * characters. |
| */ |
| private static final int ROW_SIZE = 32; |
| |
| /** |
| * The index lookup table, this maps a character as a byte |
| * (ISO-8859-1 or UTF8) to an index within a Trie row |
| */ |
| private static final int[] __lookup = |
| { // 0 1 2 3 4 5 6 7 8 9 A B C D E F |
| /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, |
| /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, |
| /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1, |
| /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1, |
| /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, |
| /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1, |
| /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, |
| /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1, |
| }; |
| |
| /** |
| * The Trie rows in a single array which allows a lookup of row,character |
| * to the next row in the Trie. This is actually a 2 dimensional |
| * array that has been flattened to achieve locality of reference. |
| * The first ROW_SIZE entries are for row 0, then next ROW_SIZE |
| * entries are for row 1 etc. So in general instead of using |
| * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up |
| * the next row for a given character. |
| * |
| * The array is of characters rather than integers to save space. |
| */ |
| private final char[] _rowIndex; |
| |
| /** |
| * The key (if any) for a Trie row. |
| * A row may be a leaf, a node or both in the Trie tree. |
| */ |
| private final String[] _key; |
| |
| /** |
| * The value (if any) for a Trie row. |
| * A row may be a leaf, a node or both in the Trie tree. |
| */ |
| private final V[] _value; |
| |
| /** |
| * A big index for each row. |
| * If a character outside of the lookup map is needed, |
| * then a big index will be created for the row, with |
| * 256 entries, one for each possible byte. |
| */ |
| private char[][] _bigIndex; |
| |
| /** |
| * The number of rows allocated |
| */ |
| private char _rows; |
| |
| public ArrayTrie() |
| { |
| this(128); |
| } |
| |
| /* ------------------------------------------------------------ */ |
| /** |
| * @param capacity The capacity of the trie, which at the worst case |
| * is the total number of characters of all keys stored in the Trie. |
| * The capacity needed is dependent of the shared prefixes of the keys. |
| * For example, a capacity of 6 nodes is required to store keys "foo" |
| * and "bar", but a capacity of only 4 is required to |
| * store "bar" and "bat". |
| */ |
| @SuppressWarnings("unchecked") |
| public ArrayTrie(int capacity) |
| { |
| super(true); |
| _value=(V[])new Object[capacity]; |
| _rowIndex=new char[capacity*32]; |
| _key=new String[capacity]; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public void clear() |
| { |
| _rows=0; |
| Arrays.fill(_value,null); |
| Arrays.fill(_rowIndex,(char)0); |
| Arrays.fill(_key,null); |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public boolean put(String s, V v) |
| { |
| int t=0; |
| int k; |
| int limit = s.length(); |
| for(k=0; k < limit; k++) |
| { |
| char c=s.charAt(k); |
| |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| t=_rowIndex[idx]; |
| if (t==0) |
| { |
| if (++_rows>=_value.length) |
| return false; |
| t=_rowIndex[idx]=_rows; |
| } |
| } |
| else if (c>127) |
| throw new IllegalArgumentException("non ascii character"); |
| else |
| { |
| if (_bigIndex==null) |
| _bigIndex=new char[_value.length][]; |
| if (t>=_bigIndex.length) |
| return false; |
| char[] big=_bigIndex[t]; |
| if (big==null) |
| big=_bigIndex[t]=new char[128]; |
| t=big[c]; |
| if (t==0) |
| { |
| if (_rows==_value.length) |
| return false; |
| t=big[c]=++_rows; |
| } |
| } |
| } |
| |
| if (t>=_key.length) |
| { |
| _rows=(char)_key.length; |
| return false; |
| } |
| |
| _key[t]=v==null?null:s; |
| _value[t] = v; |
| return true; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public V get(String s, int offset, int len) |
| { |
| int t = 0; |
| for(int i=0; i < len; i++) |
| { |
| char c=s.charAt(offset+i); |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| t=_rowIndex[idx]; |
| if (t==0) |
| return null; |
| } |
| else |
| { |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big==null) |
| return null; |
| t=big[c]; |
| if (t==0) |
| return null; |
| } |
| } |
| return _value[t]; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public V get(ByteBuffer b,int offset,int len) |
| { |
| int t = 0; |
| for(int i=0; i < len; i++) |
| { |
| byte c=b.get(offset+i); |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| t=_rowIndex[idx]; |
| if (t==0) |
| return null; |
| } |
| else |
| { |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big==null) |
| return null; |
| t=big[c]; |
| if (t==0) |
| return null; |
| } |
| } |
| return (V)_value[t]; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public V getBest(byte[] b,int offset,int len) |
| { |
| return getBest(0,b,offset,len); |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public V getBest(ByteBuffer b,int offset,int len) |
| { |
| if (b.hasArray()) |
| return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len); |
| return getBest(0,b,offset,len); |
| } |
| |
| /* ------------------------------------------------------------ */ |
| @Override |
| public V getBest(String s, int offset, int len) |
| { |
| return getBest(0,s,offset,len); |
| } |
| |
| /* ------------------------------------------------------------ */ |
| private V getBest(int t, String s, int offset, int len) |
| { |
| int pos=offset; |
| for(int i=0; i < len; i++) |
| { |
| char c=s.charAt(pos++); |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| int nt=_rowIndex[idx]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| else |
| { |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big==null) |
| return null; |
| int nt=big[c]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| |
| // Is the next Trie is a match |
| if (_key[t]!=null) |
| { |
| // Recurse so we can remember this possibility |
| V best=getBest(t,s,offset+i+1,len-i-1); |
| if (best!=null) |
| return best; |
| return (V)_value[t]; |
| } |
| } |
| return (V)_value[t]; |
| } |
| |
| /* ------------------------------------------------------------ */ |
| private V getBest(int t,byte[] b,int offset,int len) |
| { |
| for(int i=0; i < len; i++) |
| { |
| byte c=b[offset+i]; |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| int nt=_rowIndex[idx]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| else |
| { |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big==null) |
| return null; |
| int nt=big[c]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| |
| // Is the next Trie is a match |
| if (_key[t]!=null) |
| { |
| // Recurse so we can remember this possibility |
| V best=getBest(t,b,offset+i+1,len-i-1); |
| if (best!=null) |
| return best; |
| break; |
| } |
| } |
| return (V)_value[t]; |
| } |
| |
| private V getBest(int t,ByteBuffer b,int offset,int len) |
| { |
| int pos=b.position()+offset; |
| for(int i=0; i < len; i++) |
| { |
| byte c=b.get(pos++); |
| int index=__lookup[c&0x7f]; |
| if (index>=0) |
| { |
| int idx=t*ROW_SIZE+index; |
| int nt=_rowIndex[idx]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| else |
| { |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big==null) |
| return null; |
| int nt=big[c]; |
| if (nt==0) |
| break; |
| t=nt; |
| } |
| |
| // Is the next Trie is a match |
| if (_key[t]!=null) |
| { |
| // Recurse so we can remember this possibility |
| V best=getBest(t,b,offset+i+1,len-i-1); |
| if (best!=null) |
| return best; |
| break; |
| } |
| } |
| return (V)_value[t]; |
| } |
| |
| |
| |
| |
| @Override |
| public String toString() |
| { |
| StringBuilder buf = new StringBuilder(); |
| toString(buf,0); |
| |
| if (buf.length()==0) |
| return "{}"; |
| |
| buf.setCharAt(0,'{'); |
| buf.append('}'); |
| return buf.toString(); |
| } |
| |
| |
| private void toString(Appendable out, int t) |
| { |
| if (_value[t]!=null) |
| { |
| try |
| { |
| out.append(','); |
| out.append(_key[t]); |
| out.append('='); |
| out.append(_value[t].toString()); |
| } |
| catch (IOException e) |
| { |
| throw new RuntimeException(e); |
| } |
| } |
| |
| for(int i=0; i < ROW_SIZE; i++) |
| { |
| int idx=t*ROW_SIZE+i; |
| if (_rowIndex[idx] != 0) |
| toString(out,_rowIndex[idx]); |
| } |
| |
| char[] big = _bigIndex==null?null:_bigIndex[t]; |
| if (big!=null) |
| { |
| for (int i:big) |
| if (i!=0) |
| toString(out,i); |
| } |
| |
| } |
| |
| @Override |
| public Set<String> keySet() |
| { |
| Set<String> keys = new HashSet<>(); |
| keySet(keys,0); |
| return keys; |
| } |
| |
| private void keySet(Set<String> set, int t) |
| { |
| if (t<_value.length&&_value[t]!=null) |
| set.add(_key[t]); |
| |
| for(int i=0; i < ROW_SIZE; i++) |
| { |
| int idx=t*ROW_SIZE+i; |
| if (idx<_rowIndex.length && _rowIndex[idx] != 0) |
| keySet(set,_rowIndex[idx]); |
| } |
| |
| char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t]; |
| if (big!=null) |
| { |
| for (int i:big) |
| if (i!=0) |
| keySet(set,i); |
| } |
| } |
| |
| @Override |
| public boolean isFull() |
| { |
| return _rows+1>=_key.length; |
| } |
| } |
