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.nio.ByteBuffer;
22 import java.util.Arrays;
23 import java.util.HashSet;
27 /* ------------------------------------------------------------ */
29 * <p>A Ternary Trie String lookup data structure.</p>
30 * This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache).
32 * The Trie is stored in 3 arrays:<dl>
33 * <dt>char[] _tree</dt><dd>This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension
34 * is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a
35 * ternary trie of key strings.</dd>
36 * <dt>String[] _key<dt><dd>An array of key values where each element matches a row in the _tree array. A non zero key element
37 * indicates that the _tree row is a complete key rather than an intermediate character of a longer key.</dd>
38 * <dt>V[] _value</dt><dd>An array of values corresponding to the _key array</dd>
41 * <p>The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed,
42 * then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up
43 * to return the matching value.
46 * This Trie may be instantiated either as case sensitive or insensitive.
48 * <p>This Trie is not Threadsafe and contains no mutual exclusion
49 * or deliberate memory barriers. It is intended for an ArrayTrie to be
50 * built by a single thread and then used concurrently by multiple threads
51 * and not mutated during that access. If concurrent mutations of the
52 * Trie is required external locks need to be applied.
57 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
59 private static int LO=1;
60 private static int EQ=2;
61 private static int HI=3;
64 * The Size of a Trie row is the char, and the low, equal and high
67 private static final int ROW_SIZE = 4;
70 * The Trie rows in a single array which allows a lookup of row,character
71 * to the next row in the Trie. This is actually a 2 dimensional
72 * array that has been flattened to achieve locality of reference.
74 private final char[] _tree;
77 * The key (if any) for a Trie row.
78 * A row may be a leaf, a node or both in the Trie tree.
80 private final String[] _key;
83 * The value (if any) for a Trie row.
84 * A row may be a leaf, a node or both in the Trie tree.
86 private final V[] _value;
89 * The number of rows allocated
93 /* ------------------------------------------------------------ */
94 /** Create a case insensitive Trie of default capacity.
96 public ArrayTernaryTrie()
101 /* ------------------------------------------------------------ */
102 /** Create a Trie of default capacity
103 * @param insensitive true if the Trie is insensitive to the case of the key.
105 public ArrayTernaryTrie(boolean insensitive)
107 this(insensitive,128);
110 /* ------------------------------------------------------------ */
111 /** Create a case insensitive Trie
112 * @param capacity The capacity of the Trie, which is in the worst case
113 * is the total number of characters of all keys stored in the Trie.
114 * The capacity needed is dependent of the shared prefixes of the keys.
115 * For example, a capacity of 6 nodes is required to store keys "foo"
116 * and "bar", but a capacity of only 4 is required to
117 * store "bar" and "bat".
119 public ArrayTernaryTrie(int capacity)
124 /* ------------------------------------------------------------ */
126 * @param insensitive true if the Trie is insensitive to the case of the key.
127 * @param capacity The capacity of the Trie, which is in the worst case
128 * is the total number of characters of all keys stored in the Trie.
129 * The capacity needed is dependent of the shared prefixes of the keys.
130 * For example, a capacity of 6 nodes is required to store keys "foo"
131 * and "bar", but a capacity of only 4 is required to
132 * store "bar" and "bat".
134 public ArrayTernaryTrie(boolean insensitive, int capacity)
137 _value=(V[])new Object[capacity];
138 _tree=new char[capacity*ROW_SIZE];
139 _key=new String[capacity];
142 /* ------------------------------------------------------------ */
143 /** Copy Trie and change capacity by a factor
147 public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
149 super(trie.isCaseInsensitive());
150 int capacity=(int)(trie._value.length*factor);
152 _value=Arrays.copyOf(trie._value, capacity);
153 _tree=Arrays.copyOf(trie._tree, capacity*ROW_SIZE);
154 _key=Arrays.copyOf(trie._key, capacity);
157 /* ------------------------------------------------------------ */
159 public boolean put(String s, V v)
162 int limit = s.length();
164 for(int k=0; k < limit; k++)
167 if(isCaseInsensitive() && c<128)
168 c=StringUtil.lowercases[c];
174 // Do we need to create the new row?
178 if (_rows>=_key.length)
189 t=_tree[last=(row+EQ)];
191 t=_tree[last=(row+LO)];
193 t=_tree[last=(row+HI)];
195 // do we need a new row?
207 // Do we need to create the new row?
211 if (_rows>=_key.length)
218 // Put the key and value
219 _key[t]=v==null?null:s;
226 /* ------------------------------------------------------------ */
228 public V get(String s,int offset, int len)
231 for(int i=0; i < len;)
233 char c=s.charAt(offset+i++);
234 if(isCaseInsensitive() && c<128)
235 c=StringUtil.lowercases[c];
239 int row = ROW_SIZE*t;
251 t=_tree[row+hilo(diff)];
262 public V get(ByteBuffer b, int offset, int len)
265 offset+=b.position();
267 for(int i=0; i < len;)
269 byte c=(byte)(b.get(offset+i++)&0x7f);
270 if(isCaseInsensitive())
271 c=(byte)StringUtil.lowercases[c];
275 int row = ROW_SIZE*t;
287 t=_tree[row+hilo(diff)];
296 /* ------------------------------------------------------------ */
298 public V getBest(String s)
300 return getBest(0,s,0,s.length());
303 /* ------------------------------------------------------------ */
305 public V getBest(String s, int offset, int length)
307 return getBest(0,s,offset,length);
310 /* ------------------------------------------------------------ */
311 private V getBest(int t,String s,int offset,int len)
314 loop: for(int i=0; i<len; i++)
316 char c=s.charAt(offset+i);
317 if(isCaseInsensitive() && c<128)
318 c=StringUtil.lowercases[c];
322 int row = ROW_SIZE*t;
332 // if this node is a match, recurse to remember
336 V best=getBest(t,s,offset+i+1,len-i-1);
343 t=_tree[row+hilo(diff)];
348 return (V)_value[node];
352 /* ------------------------------------------------------------ */
354 public V getBest(ByteBuffer b, int offset, int len)
357 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
358 return getBest(0,b,offset,len);
361 /* ------------------------------------------------------------ */
362 private V getBest(int t,byte[] b, int offset, int len)
365 loop: for(int i=0; i<len; i++)
367 byte c=(byte)(b[offset+i]&0x7f);
368 if(isCaseInsensitive())
369 c=(byte)StringUtil.lowercases[c];
373 int row = ROW_SIZE*t;
383 // if this node is a match, recurse to remember
387 V best=getBest(t,b,offset+i+1,len-i-1);
394 t=_tree[row+hilo(diff)];
399 return (V)_value[node];
402 /* ------------------------------------------------------------ */
403 private V getBest(int t,ByteBuffer b, int offset, int len)
406 int o= offset+b.position();
408 loop: for(int i=0; i<len; i++)
410 byte c=(byte)(b.get(o+i)&0x7f);
411 if(isCaseInsensitive())
412 c=(byte)StringUtil.lowercases[c];
416 int row = ROW_SIZE*t;
426 // if this node is a match, recurse to remember
430 V best=getBest(t,b,offset+i+1,len-i-1);
437 t=_tree[row+hilo(diff)];
442 return (V)_value[node];
446 public String toString()
448 StringBuilder buf = new StringBuilder();
449 for (int r=0;r<=_rows;r++)
451 if (_key[r]!=null && _value[r]!=null)
456 buf.append(_value[r].toString());
462 buf.setCharAt(0,'{');
464 return buf.toString();
470 public Set<String> keySet()
472 Set<String> keys = new HashSet<>();
474 for (int r=0;r<=_rows;r++)
476 if (_key[r]!=null && _value[r]!=null)
483 public boolean isFull()
485 return _rows+1==_key.length;
488 public static int hilo(int diff)
490 // branchless equivalent to return ((diff<0)?LO:HI);
491 // return 3+2*((diff&Integer.MIN_VALUE)>>Integer.SIZE-1);
492 return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
497 for (int r=0;r<_rows;r++)
499 char c=_tree[r*ROW_SIZE+0];
500 System.err.printf("%4d [%s,%d,%d,%d] '%s':%s%n",
502 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
503 (int)_tree[r*ROW_SIZE+LO],
504 (int)_tree[r*ROW_SIZE+EQ],
505 (int)_tree[r*ROW_SIZE+HI],