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.nio.ByteBuffer;
22 import java.util.HashSet;
23 import java.util.Set;
24
25
26 /* ------------------------------------------------------------ */
27 /** A Ternary Trie String lookup data structure.
28 * 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).
29 * @param <V>
30 */
31 public class ArrayTernaryTrie<V> implements Trie<V>
32 {
33 private static int LO=1;
34 private static int EQ=2;
35 private static int HI=3;
36
37 /**
38 * The Size of a Trie row is the char, and the low, equal and high
39 * child pointers
40 */
41 private static final int ROW_SIZE = 4;
42
43 /**
44 * The Trie rows in a single array which allows a lookup of row,character
45 * to the next row in the Trie. This is actually a 2 dimensional
46 * array that has been flattened to achieve locality of reference.
47 */
48 private final char[] _tree;
49
50 /**
51 * The key (if any) for a Trie row.
52 * A row may be a leaf, a node or both in the Trie tree.
53 */
54 private final String[] _key;
55
56 /**
57 * The value (if any) for a Trie row.
58 * A row may be a leaf, a node or both in the Trie tree.
59 */
60 private final Object[] _value;
61
62
63 /**
64 * The number of rows allocated
65 */
66 private char _rows;
67
68 public ArrayTernaryTrie()
69 {
70 this(128);
71 }
72
73 public ArrayTernaryTrie(int capacityInNodes)
74 {
75 _value=new Object[capacityInNodes];
76 _tree=new char[capacityInNodes*ROW_SIZE];
77 _key=new String[capacityInNodes];
78 }
79
80
81 /* ------------------------------------------------------------ */
82 @Override
83 public boolean put(String s, V v)
84 {
85 int last=EQ;
86 int t=_tree[last];
87 int k;
88 int limit = s.length();
89 int node=0;
90 for(k=0; k < limit; k++)
91 {
92 char c=s.charAt(k);
93 if (c<128)
94 c=StringUtil.lowercases[c&0x7f];
95
96 while (true)
97 {
98 if (t==0)
99 {
100 node=t=++_rows;
101 if (_rows>=_key.length)
102 {
103 _rows--;
104 return false;
105 }
106 int row=ROW_SIZE*t;
107 _tree[row]=c;
108 _tree[last]=(char)t;
109 last=row+EQ;
110 t=0;
111 break;
112 }
113
114 int row=ROW_SIZE*t;
115 char n=_tree[row];
116 int diff=n-c;
117 if (diff==0)
118 {
119 node=t;
120 t=_tree[last=(row+EQ)];
121 break;
122 }
123 if (diff<0)
124 t=_tree[last=(row+LO)];
125 else
126 t=_tree[last=(row+HI)];
127 }
128 }
129 _key[node]=v==null?null:s;
130 _value[node] = v;
131
132 return true;
133 }
134
135
136 /* ------------------------------------------------------------ */
137 @Override
138 public boolean put(V v)
139 {
140 return put(v.toString(),v);
141 }
142
143 /* ------------------------------------------------------------ */
144 @Override
145 public V remove(String s)
146 {
147 V o=get(s);
148 put(s,null);
149 return o;
150 }
151
152 /* ------------------------------------------------------------ */
153 @Override
154 public V get(String s)
155 {
156 int t = _tree[EQ];
157 int len = s.length();
158 int node=0;
159 for(int i=0; t!=0 && i < len ; i++)
160 {
161 char c=StringUtil.lowercases[s.charAt(i)&0x7f];
162 while (t!=0)
163 {
164 int row = ROW_SIZE*t;
165 char n=_tree[row];
166 int diff=n-c;
167
168 if (diff==0)
169 {
170 node=t;
171 t=_tree[row+EQ];
172 break;
173 }
174
175 if (diff<0)
176 t=_tree[row+LO];
177 else
178 t=_tree[row+HI];
179 }
180 }
181
182 return (V)_value[node];
183 }
184
185 /* ------------------------------------------------------------ */
186 @Override
187 public V get(ByteBuffer b,int offset,int len)
188 {
189 int t = _tree[EQ];
190 int node=0;
191 for(int i=0; t!=0 && i<len; i++)
192 {
193 char c=StringUtil.lowercases[b.get(offset+i)&0x7f];
194
195 while (t!=0)
196 {
197 int row = ROW_SIZE*t;
198 char n=_tree[row];
199 int diff=n-c;
200
201 if (diff==0)
202 {
203 node=t;
204 t=_tree[row+EQ];
205 break;
206 }
207
208 if (diff<0)
209 t=_tree[row+LO];
210 else
211 t=_tree[row+HI];
212 }
213 }
214
215 return (V)_value[node];
216 }
217
218 /* ------------------------------------------------------------ */
219 @Override
220 public V getBest(byte[] b,int offset,int len)
221 {
222 return getBest(_tree[EQ],b,offset,len);
223 }
224
225 /* ------------------------------------------------------------ */
226 @Override
227 public V getBest(ByteBuffer b,int offset,int len)
228 {
229 if (b.hasArray())
230 return getBest(_tree[EQ],b.array(),b.arrayOffset()+b.position()+offset,len);
231 return getBest(_tree[EQ],b,offset,len);
232 }
233
234 private V getBest(int t,byte[] b,int offset,int len)
235 {
236 int node=0;
237 for(int i=0; t!=0 && i<len; i++)
238 {
239 char c=StringUtil.lowercases[b[offset+i]&0x7f];
240
241 while (t!=0)
242 {
243 int row = ROW_SIZE*t;
244 char n=_tree[row];
245 int diff=n-c;
246
247 if (diff==0)
248 {
249 node=t;
250 t=_tree[row+EQ];
251
252 // if this node is a match, recurse to remember
253 if (_key[node]!=null)
254 {
255 V best=getBest(t,b,offset+i+1,len-i-1);
256 if (best!=null)
257 return best;
258 return (V)_value[node];
259 }
260
261 break;
262 }
263
264 if (diff<0)
265 t=_tree[row+LO];
266 else
267 t=_tree[row+HI];
268 }
269 }
270 return null;
271 }
272
273 private V getBest(int t,ByteBuffer b,int offset,int len)
274 {
275 int pos=b.position()+offset;
276 int node=0;
277 for(int i=0; t!=0 && i<len; i++)
278 {
279 char c=StringUtil.lowercases[b.get(pos++)&0x7f];
280
281 while (t!=0)
282 {
283 int row = ROW_SIZE*t;
284 char n=_tree[row];
285 int diff=n-c;
286
287 if (diff==0)
288 {
289 node=t;
290 t=_tree[row+EQ];
291
292 // if this node is a match, recurse to remember
293 if (_key[node]!=null)
294 {
295 V best=getBest(t,b,offset+i+1,len-i-1);
296 if (best!=null)
297 return best;
298 return (V)_value[node];
299 }
300
301 break;
302 }
303
304 if (diff<0)
305 t=_tree[row+LO];
306 else
307 t=_tree[row+HI];
308 }
309 }
310 return null;
311 }
312
313
314
315
316 @Override
317 public String toString()
318 {
319 StringBuilder buf = new StringBuilder();
320 for (int r=1;r<=_rows;r++)
321 {
322 if (_key[r]!=null && _value[r]!=null)
323 {
324 buf.append(',');
325 buf.append(_key[r]);
326 buf.append('=');
327 buf.append(_value[r].toString());
328 }
329 }
330 if (buf.length()==0)
331 return "{}";
332
333 buf.setCharAt(0,'{');
334 buf.append('}');
335 return buf.toString();
336 }
337
338
339
340 @Override
341 public Set<String> keySet()
342 {
343 Set<String> keys = new HashSet<>();
344
345 for (int r=1;r<=_rows;r++)
346 {
347 if (_key[r]!=null && _value[r]!=null)
348 keys.add(_key[r]);
349 }
350 return keys;
351 }
352
353 @Override
354 public boolean isFull()
355 {
356 return _rows+1==_key.length;
357 }
358 }