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.io.IOException;
22 import java.nio.ByteBuffer;
23 import java.nio.charset.StandardCharsets;
24 import java.util.ArrayList;
25 import java.util.HashSet;
26 import java.util.List;
29 /* ------------------------------------------------------------ */
30 /** A Trie String lookup data structure using a tree
31 * <p>This implementation is always case insensitive and is optimal for
32 * a variable number of fixed strings with few special characters.
34 * <p>This Trie is stored in a Tree and is unlimited in capacity</p>
36 * <p>This Trie is not Threadsafe and contains no mutual exclusion
37 * or deliberate memory barriers. It is intended for an ArrayTrie to be
38 * built by a single thread and then used concurrently by multiple threads
39 * and not mutated during that access. If concurrent mutations of the
40 * Trie is required external locks need to be applied.
45 public class TreeTrie<V> extends AbstractTrie<V>
47 private static final int[] __lookup =
48 { // 0 1 2 3 4 5 6 7 8 9 A B C D E F
49 /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
50 /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
51 /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1,
52 /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
53 /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
54 /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
55 /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
56 /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
58 private static final int INDEX = 32;
59 private final TreeTrie<V>[] _nextIndex;
60 private final List<TreeTrie<V>> _nextOther=new ArrayList<>();
61 private final char _c;
68 _nextIndex = new TreeTrie[INDEX];
72 private TreeTrie(char c)
75 _nextIndex = new TreeTrie[INDEX];
80 public boolean put(String s, V v)
83 int limit = s.length();
84 for(int k=0; k < limit; k++)
88 int index=c>=0&&c<0x7f?__lookup[c]:-1;
91 if (t._nextIndex[index] == null)
92 t._nextIndex[index] = new TreeTrie<V>(c);
93 t = t._nextIndex[index];
98 for (int i=t._nextOther.size();i-->0;)
100 n=t._nextOther.get(i);
107 n=new TreeTrie<V>(c);
113 t._key=v==null?null:s;
119 public V get(String s,int offset, int len)
121 TreeTrie<V> t = this;
122 for(int i=0; i < len; i++)
124 char c=s.charAt(offset+i);
125 int index=c>=0&&c<0x7f?__lookup[c]:-1;
128 if (t._nextIndex[index] == null)
130 t = t._nextIndex[index];
135 for (int j=t._nextOther.size();j-->0;)
137 n=t._nextOther.get(j);
151 public V get(ByteBuffer b,int offset,int len)
153 TreeTrie<V> t = this;
154 for(int i=0; i < len; i++)
156 byte c=b.get(offset+i);
157 int index=c>=0&&c<0x7f?__lookup[c]:-1;
160 if (t._nextIndex[index] == null)
162 t = t._nextIndex[index];
167 for (int j=t._nextOther.size();j-->0;)
169 n=t._nextOther.get(j);
183 public V getBest(byte[] b,int offset,int len)
185 TreeTrie<V> t = this;
186 for(int i=0; i < len; i++)
189 int index=c>=0&&c<0x7f?__lookup[c]:-1;
192 if (t._nextIndex[index] == null)
194 t = t._nextIndex[index];
199 for (int j=t._nextOther.size();j-->0;)
201 n=t._nextOther.get(j);
211 // Is the next Trie is a match
214 // Recurse so we can remember this possibility
215 V best=t.getBest(b,offset+i+1,len-i-1);
225 public V getBest(String s, int offset, int len)
228 byte[] b=s.substring(offset,offset+len).getBytes(StandardCharsets.ISO_8859_1);
229 return getBest(b,0,b.length);
233 public V getBest(ByteBuffer b,int offset,int len)
236 return getBest(b.array(),b.arrayOffset()+b.position()+offset,len);
237 return getBestByteBuffer(b,offset,len);
240 private V getBestByteBuffer(ByteBuffer b,int offset,int len)
242 TreeTrie<V> t = this;
243 int pos=b.position()+offset;
244 for(int i=0; i < len; i++)
247 int index=c>=0&&c<0x7f?__lookup[c]:-1;
250 if (t._nextIndex[index] == null)
252 t = t._nextIndex[index];
257 for (int j=t._nextOther.size();j-->0;)
259 n=t._nextOther.get(j);
269 // Is the next Trie is a match
272 // Recurse so we can remember this possibility
273 V best=t.getBest(b,offset+i+1,len-i-1);
284 public String toString()
286 StringBuilder buf = new StringBuilder();
292 buf.setCharAt(0,'{');
294 return buf.toString();
297 private static <V> void toString(Appendable out, TreeTrie<V> t)
308 out.append(t._value.toString());
310 catch (IOException e)
312 throw new RuntimeException(e);
316 for(int i=0; i < INDEX; i++)
318 if (t._nextIndex[i] != null)
319 toString(out,t._nextIndex[i]);
321 for (int i=t._nextOther.size();i-->0;)
322 toString(out,t._nextOther.get(i));
327 public Set<String> keySet()
329 Set<String> keys = new HashSet<>();
334 private static <V> void keySet(Set<String> set, TreeTrie<V> t)
341 for(int i=0; i < INDEX; i++)
343 if (t._nextIndex[i] != null)
344 keySet(set,t._nextIndex[i]);
346 for (int i=t._nextOther.size();i-->0;)
347 keySet(set,t._nextOther.get(i));
352 public boolean isFull()