View Javadoc

1   //
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.
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.io.IOException;
22  import java.nio.ByteBuffer;
23  import java.util.ArrayList;
24  import java.util.Arrays;
25  import java.util.HashSet;
26  import java.util.List;
27  import java.util.Set;
28  
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.
33   * </p>
34   * <p>This Trie is stored in a Tree and is unlimited in capacity</p>
35   * 
36   * <p>This Trie is not Threadsafe and contains no mutual exclusion 
37   * or deliberate memory barriers.  It is intended for an TreeTrie 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.
41   * </p>
42   * 
43   * @param <V> the entry type
44   */
45  public class TreeTrie<V> extends AbstractTrie<V>
46  {
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,
57      };
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;
62      private String _key;
63      private V _value;
64  
65      public TreeTrie()
66      {
67          super(true);
68          _nextIndex = new TreeTrie[INDEX];
69          _c=0;
70      }
71      
72      private TreeTrie(char c)
73      {
74          super(true);
75          _nextIndex = new TreeTrie[INDEX];
76          this._c=c;
77      }
78      
79      @Override
80      public void clear()
81      {
82          Arrays.fill(_nextIndex,null);
83          _nextOther.clear();
84          _key=null;
85          _value=null;
86      }
87  
88      @Override
89      public boolean put(String s, V v)
90      {
91          TreeTrie<V> t = this;
92          int limit = s.length();
93          for(int k=0; k < limit; k++)
94          {
95              char c=s.charAt(k);
96              
97              int index=c>=0&&c<0x7f?__lookup[c]:-1;
98              if (index>=0)
99              {
100                 if (t._nextIndex[index] == null)
101                     t._nextIndex[index] = new TreeTrie<V>(c);
102                 t = t._nextIndex[index];
103             }
104             else
105             {
106                 TreeTrie<V> n=null;
107                 for (int i=t._nextOther.size();i-->0;)
108                 {
109                     n=t._nextOther.get(i);
110                     if (n._c==c)
111                         break;
112                     n=null;
113                 }
114                 if (n==null)
115                 {
116                     n=new TreeTrie<V>(c);
117                     t._nextOther.add(n);
118                 }
119                 t=n;
120             }
121         }
122         t._key=v==null?null:s;
123         t._value = v;
124         return true;
125     }
126 
127     @Override
128     public V get(String s,int offset, int len)
129     {
130         TreeTrie<V> t = this;
131         for(int i=0; i < len; i++)
132         {
133             char c=s.charAt(offset+i);
134             int index=c>=0&&c<0x7f?__lookup[c]:-1;
135             if (index>=0)
136             {
137                 if (t._nextIndex[index] == null) 
138                     return null;
139                 t = t._nextIndex[index];
140             }
141             else
142             {
143                 TreeTrie<V> n=null;
144                 for (int j=t._nextOther.size();j-->0;)
145                 {
146                     n=t._nextOther.get(j);
147                     if (n._c==c)
148                         break;
149                     n=null;
150                 }
151                 if (n==null)
152                     return null;
153                 t=n;
154             }
155         }
156         return t._value;
157     }
158 
159     @Override
160     public V get(ByteBuffer b,int offset,int len)
161     {
162         TreeTrie<V> t = this;
163         for(int i=0; i < len; i++)
164         {
165             byte c=b.get(offset+i);
166             int index=c>=0&&c<0x7f?__lookup[c]:-1;
167             if (index>=0)
168             {
169                 if (t._nextIndex[index] == null) 
170                     return null;
171                 t = t._nextIndex[index];
172             }
173             else
174             {
175                 TreeTrie<V> n=null;
176                 for (int j=t._nextOther.size();j-->0;)
177                 {
178                     n=t._nextOther.get(j);
179                     if (n._c==c)
180                         break;
181                     n=null;
182                 }
183                 if (n==null)
184                     return null;
185                 t=n;
186             }
187         }
188         return t._value;
189     }
190 
191     @Override
192     public V getBest(byte[] b,int offset,int len)
193     {
194         TreeTrie<V> t = this;
195         for(int i=0; i < len; i++)
196         {
197             byte c=b[offset+i];
198             int index=c>=0&&c<0x7f?__lookup[c]:-1;
199             if (index>=0)
200             {
201                 if (t._nextIndex[index] == null) 
202                     break;
203                 t = t._nextIndex[index];
204             }
205             else
206             {
207                 TreeTrie<V> n=null;
208                 for (int j=t._nextOther.size();j-->0;)
209                 {
210                     n=t._nextOther.get(j);
211                     if (n._c==c)
212                         break;
213                     n=null;
214                 }
215                 if (n==null)
216                     break;
217                 t=n;
218             }
219             
220             // Is the next Trie is a match
221             if (t._key!=null)
222             {
223                 // Recurse so we can remember this possibility
224                 V best=t.getBest(b,offset+i+1,len-i-1);
225                 if (best!=null)
226                     return best;
227                 break;
228             }
229         }
230         return t._value;
231     }
232 
233     @Override
234     public V getBest(String s, int offset, int len)
235     {
236         TreeTrie<V> t = this;
237         for(int i=0; i < len; i++)
238         {
239             byte c=(byte)(0xff&s.charAt(offset+i));
240             int index=c>=0&&c<0x7f?__lookup[c]:-1;
241             if (index>=0)
242             {
243                 if (t._nextIndex[index] == null) 
244                     break;
245                 t = t._nextIndex[index];
246             }
247             else
248             {
249                 TreeTrie<V> n=null;
250                 for (int j=t._nextOther.size();j-->0;)
251                 {
252                     n=t._nextOther.get(j);
253                     if (n._c==c)
254                         break;
255                     n=null;
256                 }
257                 if (n==null)
258                     break;
259                 t=n;
260             }
261             
262             // Is the next Trie is a match
263             if (t._key!=null)
264             {
265                 // Recurse so we can remember this possibility
266                 V best=t.getBest(s,offset+i+1,len-i-1);
267                 if (best!=null)
268                     return best;
269                 break;
270             }
271         }
272         return t._value;
273     }
274     
275     @Override
276     public V getBest(ByteBuffer b,int offset,int len)
277     {
278         if (b.hasArray())
279             return getBest(b.array(),b.arrayOffset()+b.position()+offset,len);
280         return getBestByteBuffer(b,offset,len);
281     }
282     
283     private V getBestByteBuffer(ByteBuffer b,int offset,int len)
284     {
285         TreeTrie<V> t = this;
286         int pos=b.position()+offset;
287         for(int i=0; i < len; i++)
288         {
289             byte c=b.get(pos++);
290             int index=c>=0&&c<0x7f?__lookup[c]:-1;
291             if (index>=0)
292             {
293                 if (t._nextIndex[index] == null) 
294                     break;
295                 t = t._nextIndex[index];
296             }
297             else
298             {
299                 TreeTrie<V> n=null;
300                 for (int j=t._nextOther.size();j-->0;)
301                 {
302                     n=t._nextOther.get(j);
303                     if (n._c==c)
304                         break;
305                     n=null;
306                 }
307                 if (n==null)
308                     break;
309                 t=n;
310             }
311             
312             // Is the next Trie is a match
313             if (t._key!=null)
314             {
315                 // Recurse so we can remember this possibility
316                 V best=t.getBest(b,offset+i+1,len-i-1);
317                 if (best!=null)
318                     return best;
319                 break;
320             }
321         }
322         return t._value;
323     }
324     
325 
326     @Override
327     public String toString()
328     {
329         StringBuilder buf = new StringBuilder();
330         toString(buf,this);
331         
332         if (buf.length()==0)
333             return "{}";
334         
335         buf.setCharAt(0,'{');
336         buf.append('}');
337         return buf.toString();
338     }
339 
340     private static <V> void toString(Appendable out, TreeTrie<V> t)
341     {
342         if (t != null)
343         {
344             if (t._value!=null)
345             {
346                 try
347                 {
348                     out.append(',');
349                     out.append(t._key);
350                     out.append('=');
351                     out.append(t._value.toString());
352                 }
353                 catch (IOException e)
354                 {
355                     throw new RuntimeException(e);
356                 }
357             }
358            
359             for(int i=0; i < INDEX; i++)
360             {
361                 if (t._nextIndex[i] != null)
362                     toString(out,t._nextIndex[i]);
363             }
364             for (int i=t._nextOther.size();i-->0;)
365                 toString(out,t._nextOther.get(i));
366         }           
367     }
368 
369     @Override
370     public Set<String> keySet()
371     {
372         Set<String> keys = new HashSet<>();
373         keySet(keys,this);
374         return keys;
375     }
376     
377     private static <V> void keySet(Set<String> set, TreeTrie<V> t)
378     {
379         if (t != null)
380         {
381             if (t._key!=null)
382                 set.add(t._key);
383            
384             for(int i=0; i < INDEX; i++)
385             {
386                 if (t._nextIndex[i] != null)
387                     keySet(set,t._nextIndex[i]);
388             }
389             for (int i=t._nextOther.size();i-->0;)
390                 keySet(set,t._nextOther.get(i));
391         }           
392     }
393     
394     @Override
395     public boolean isFull()
396     {
397         return false;
398     }
399 
400 
401 }