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.nio.ByteBuffer;
22 import java.util.Arrays;
23 import java.util.HashSet;
27 /* ------------------------------------------------------------ */
28 /** A Ternary Trie String lookup data structure.
29 * 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).
31 * The Trie is stored in 3 arrays:<dl>
32 * <dt>char[] _tree</dt><dd>This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension
33 * is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a
34 * ternary trie of key strings.</dd>
35 * <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
36 * indicates that the _tree row is a complete key rather than an intermediate character of a longer key.</dd>
37 * <dt>V[] _value</dt><dd>An array of values corresponding to the _key array</dd>
39 * <p>The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed,
40 * 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
41 * to return the matching value.
45 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
47 private static int LO=1;
48 private static int EQ=2;
49 private static int HI=3;
52 * The Size of a Trie row is the char, and the low, equal and high
55 private static final int ROW_SIZE = 4;
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.
62 private final char[] _tree;
65 * The key (if any) for a Trie row.
66 * A row may be a leaf, a node or both in the Trie tree.
68 private final String[] _key;
71 * The value (if any) for a Trie row.
72 * A row may be a leaf, a node or both in the Trie tree.
74 private final Object[] _value;
77 * The number of rows allocated
81 public ArrayTernaryTrie()
86 public ArrayTernaryTrie(boolean insensitive)
88 this(insensitive,128);
91 public ArrayTernaryTrie(int capacityInNodes)
93 this(true,capacityInNodes);
96 public ArrayTernaryTrie(boolean insensitive, int capacityInNodes)
99 _value=new Object[capacityInNodes];
100 _tree=new char[capacityInNodes*ROW_SIZE];
101 _key=new String[capacityInNodes];
104 /* ------------------------------------------------------------ */
105 /** Copy Trie and change capacity by a factor
109 public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
111 super(trie.isCaseInsensitive());
112 int capacity=(int)(trie._value.length*factor);
114 _value=Arrays.copyOf(trie._value, capacity);
115 _tree=Arrays.copyOf(trie._tree, capacity*ROW_SIZE);
116 _key=Arrays.copyOf(trie._key, capacity);
119 /* ------------------------------------------------------------ */
121 public boolean put(String s, V v)
124 int limit = s.length();
126 for(int k=0; k < limit; k++)
129 if(isCaseInsensitive() && c<128)
130 c=StringUtil.lowercases[c];
136 // Do we need to create the new row?
140 if (_rows>=_key.length)
151 t=_tree[last=(row+EQ)];
153 t=_tree[last=(row+LO)];
155 t=_tree[last=(row+HI)];
157 // do we need a new row?
169 // Do we need to create the new row?
173 if (_rows>=_key.length)
180 // Put the key and value
181 _key[t]=v==null?null:s;
188 /* ------------------------------------------------------------ */
190 public V get(String s,int offset, int len)
193 for(int i=0; i < len;)
195 char c=s.charAt(offset+i++);
196 if(isCaseInsensitive() && c<128)
197 c=StringUtil.lowercases[c];
201 int row = ROW_SIZE*t;
213 t=_tree[row+hilo(diff)];
224 public V get(ByteBuffer b, int offset, int len)
227 offset+=b.position();
229 for(int i=0; i < len;)
231 byte c=(byte)(b.get(offset+i++)&0x7f);
232 if(isCaseInsensitive())
233 c=(byte)StringUtil.lowercases[c];
237 int row = ROW_SIZE*t;
249 t=_tree[row+hilo(diff)];
258 /* ------------------------------------------------------------ */
260 public V getBest(String s)
262 return getBest(0,s,0,s.length());
265 /* ------------------------------------------------------------ */
267 public V getBest(String s, int offset, int length)
269 return getBest(0,s,offset,length);
272 /* ------------------------------------------------------------ */
273 private V getBest(int t,String s,int offset,int len)
276 loop: for(int i=0; i<len; i++)
278 char c=s.charAt(offset+i);
279 if(isCaseInsensitive() && c<128)
280 c=StringUtil.lowercases[c];
284 int row = ROW_SIZE*t;
294 // if this node is a match, recurse to remember
298 V best=getBest(t,s,offset+i+1,len-i-1);
305 t=_tree[row+hilo(diff)];
310 return (V)_value[node];
314 /* ------------------------------------------------------------ */
316 public V getBest(ByteBuffer b, int offset, int len)
319 return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
320 return getBest(0,b,offset,len);
323 /* ------------------------------------------------------------ */
324 private V getBest(int t,byte[] b, int offset, int len)
327 loop: for(int i=0; i<len; i++)
329 byte c=(byte)(b[offset+i]&0x7f);
330 if(isCaseInsensitive())
331 c=(byte)StringUtil.lowercases[c];
335 int row = ROW_SIZE*t;
345 // if this node is a match, recurse to remember
349 V best=getBest(t,b,offset+i+1,len-i-1);
356 t=_tree[row+hilo(diff)];
361 return (V)_value[node];
364 /* ------------------------------------------------------------ */
365 private V getBest(int t,ByteBuffer b, int offset, int len)
368 int o= offset+b.position();
370 loop: for(int i=0; i<len; i++)
372 byte c=(byte)(b.get(o+i)&0x7f);
373 if(isCaseInsensitive())
374 c=(byte)StringUtil.lowercases[c];
378 int row = ROW_SIZE*t;
388 // if this node is a match, recurse to remember
392 V best=getBest(t,b,offset+i+1,len-i-1);
399 t=_tree[row+hilo(diff)];
404 return (V)_value[node];
408 public String toString()
410 StringBuilder buf = new StringBuilder();
411 for (int r=0;r<=_rows;r++)
413 if (_key[r]!=null && _value[r]!=null)
418 buf.append(_value[r].toString());
424 buf.setCharAt(0,'{');
426 return buf.toString();
432 public Set<String> keySet()
434 Set<String> keys = new HashSet<>();
436 for (int r=0;r<=_rows;r++)
438 if (_key[r]!=null && _value[r]!=null)
445 public boolean isFull()
447 return _rows+1==_key.length;
450 public static int hilo(int diff)
452 // branchless equivalent to return ((diff<0)?LO:HI);
453 // return 3+2*((diff&Integer.MIN_VALUE)>>Integer.SIZE-1);
454 return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
459 for (int r=0;r<_rows;r++)
461 char c=_tree[r*ROW_SIZE+0];
462 System.err.printf("%4d [%s,%d,%d,%d] '%s':%s%n",
464 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
465 (int)_tree[r*ROW_SIZE+LO],
466 (int)_tree[r*ROW_SIZE+EQ],
467 (int)_tree[r*ROW_SIZE+HI],