1 //
2 // ========================================================================
3 // Copyright (c) 1995-2013 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.
8 //
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
11 //
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
14 //
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
17 //
18
19 package org.eclipse.jetty.util;
20
21 import java.util.HashSet;
22 import java.util.Set;
23
24
25 /* ------------------------------------------------------------ */
26 /** A Ternary Trie String lookup data structure.
27 * 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).
28 * @param <V>
29 */
30 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
31 {
32 private static int LO=1;
33 private static int EQ=2;
34 private static int HI=3;
35
36 /**
37 * The Size of a Trie row is the char, and the low, equal and high
38 * child pointers
39 */
40 private static final int ROW_SIZE = 4;
41
42 /**
43 * The Trie rows in a single array which allows a lookup of row,character
44 * to the next row in the Trie. This is actually a 2 dimensional
45 * array that has been flattened to achieve locality of reference.
46 */
47 private final char[] _tree;
48
49 /**
50 * The key (if any) for a Trie row.
51 * A row may be a leaf, a node or both in the Trie tree.
52 */
53 private final String[] _key;
54
55 /**
56 * The value (if any) for a Trie row.
57 * A row may be a leaf, a node or both in the Trie tree.
58 */
59 private final Object[] _value;
60
61
62 /**
63 * The number of rows allocated
64 */
65 private char _rows;
66
67 public ArrayTernaryTrie()
68 {
69 this(128);
70 }
71
72 public ArrayTernaryTrie(boolean insensitive)
73 {
74 this(insensitive,128);
75 }
76
77 public ArrayTernaryTrie(int capacityInNodes)
78 {
79 this(true,capacityInNodes);
80 }
81
82 public ArrayTernaryTrie(boolean insensitive, int capacityInNodes)
83 {
84 super(insensitive);
85 _value=new Object[capacityInNodes];
86 _tree=new char[capacityInNodes*ROW_SIZE];
87 _key=new String[capacityInNodes];
88 }
89
90 /* ------------------------------------------------------------ */
91 /** Copy Trie and change capacity by a factor
92 * @param trie
93 * @param factor
94 */
95 public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
96 {
97 this(trie.isCaseInsensitive(),(int)(trie._value.length*factor));
98 _rows=trie._rows;
99 System.arraycopy(trie._value,0,_value,0,trie._value.length);
100 System.arraycopy(trie._tree,0,_tree,0,trie._tree.length);
101 System.arraycopy(trie._key,0,_key,0,trie._key.length);
102 }
103
104 /* ------------------------------------------------------------ */
105 @Override
106 public boolean put(String s, V v)
107 {
108 int last=EQ;
109 int t=_tree[last];
110 int k;
111 int limit = s.length();
112 int node=0;
113 for(k=0; k < limit; k++)
114 {
115 char c=s.charAt(k);
116 if(isCaseInsensitive() && c<128)
117 c=StringUtil.lowercases[c];
118
119 while (true)
120 {
121 if (t==0)
122 {
123 node=t=++_rows;
124 if (_rows>=_key.length)
125 {
126 _rows--;
127 return false;
128 }
129 int row=ROW_SIZE*t;
130 _tree[row]=c;
131 _tree[last]=(char)t;
132 last=row+EQ;
133 t=0;
134 break;
135 }
136
137 int row=ROW_SIZE*t;
138 char n=_tree[row];
139 int diff=n-c;
140 if (diff==0)
141 {
142 node=t;
143 t=_tree[last=(row+EQ)];
144 break;
145 }
146 if (diff<0)
147 t=_tree[last=(row+LO)];
148 else
149 t=_tree[last=(row+HI)];
150 }
151 }
152 _key[node]=v==null?null:s;
153 _value[node] = v;
154
155 return true;
156 }
157
158 /* ------------------------------------------------------------ */
159 @Override
160 public V get(String s,int offset, int length)
161 {
162 int t = _tree[EQ];
163 int len = length;
164 int i=0;
165 while(i<len)
166 {
167 char c=s.charAt(offset+i++);
168 if(isCaseInsensitive() && c<128)
169 c=StringUtil.lowercases[c];
170
171 while (true)
172 {
173 int row = ROW_SIZE*t;
174 char n=_tree[row];
175 int diff=n-c;
176
177 if (diff==0)
178 {
179 if (i==len)
180 return (V)_value[t];
181 t=_tree[row+EQ];
182 if (t==0)
183 return null;
184 break;
185 }
186
187 t=_tree[row+((diff<0)?LO:HI)];
188 if (t==0)
189 return null;
190 }
191 }
192
193 return null;
194 }
195
196
197 /* ------------------------------------------------------------ */
198 @Override
199 public V getBest(String s)
200 {
201 return getBest(_tree[EQ],s,0,s.length());
202 }
203
204 /* ------------------------------------------------------------ */
205 @Override
206 public V getBest(String s, int offset, int length)
207 {
208 return getBest(_tree[EQ],s,offset,length);
209 }
210
211 /* ------------------------------------------------------------ */
212 private V getBest(int t,String s,int offset,int len)
213 {
214 int node=0;
215 for(int i=0; t!=0 && i<len; i++)
216 {
217 char c=s.charAt(offset+i);
218 if(isCaseInsensitive() && c<128)
219 c=StringUtil.lowercases[c];
220
221 while (t!=0)
222 {
223 int row = ROW_SIZE*t;
224 char n=_tree[row];
225 int diff=n-c;
226
227 if (diff==0)
228 {
229 node=t;
230 t=_tree[row+EQ];
231
232 // if this node is a match, recurse to remember
233 if (_key[node]!=null)
234 {
235 V best=getBest(t,s,offset+i+1,len-i-1);
236 if (best!=null)
237 return best;
238 return (V)_value[node];
239 }
240
241 break;
242 }
243
244 t=_tree[row+((diff<0)?LO:HI)];
245 }
246 }
247 return null;
248 }
249
250
251 @Override
252 public String toString()
253 {
254 StringBuilder buf = new StringBuilder();
255 for (int r=1;r<=_rows;r++)
256 {
257 if (_key[r]!=null && _value[r]!=null)
258 {
259 buf.append(',');
260 buf.append(_key[r]);
261 buf.append('=');
262 buf.append(_value[r].toString());
263 }
264 }
265 if (buf.length()==0)
266 return "{}";
267
268 buf.setCharAt(0,'{');
269 buf.append('}');
270 return buf.toString();
271 }
272
273
274
275 @Override
276 public Set<String> keySet()
277 {
278 Set<String> keys = new HashSet<>();
279
280 for (int r=1;r<=_rows;r++)
281 {
282 if (_key[r]!=null && _value[r]!=null)
283 keys.add(_key[r]);
284 }
285 return keys;
286 }
287
288 @Override
289 public boolean isFull()
290 {
291 return _rows+1==_key.length;
292 }
293 }