lib/jetty/org/eclipse/jetty/util/TreeTrie.java

   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.nio.charset.StandardCharsets;
  24 import java.util.ArrayList;
  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 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.
  41  * </p>
  42  *
  43  * @param <V>
  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 boolean put(String s, V v)
  81     {
  82         TreeTrie<V> t = this;
  83         int limit = s.length();
  84         for(int k=0; k < limit; k++)
  85         {
  86             char c=s.charAt(k);
  87
  88             int index=c>=0&&c<0x7f?__lookup[c]:-1;
  89             if (index>=0)
  90             {
  91                 if (t._nextIndex[index] == null)
  92                     t._nextIndex[index] = new TreeTrie<V>(c);
  93                 t = t._nextIndex[index];
  94             }
  95             else
  96             {
  97                 TreeTrie<V> n=null;
  98                 for (int i=t._nextOther.size();i-->0;)
  99                 {
 100                     n=t._nextOther.get(i);
 101                     if (n._c==c)
 102                         break;
 103                     n=null;
 104                 }
 105                 if (n==null)
 106                 {
 107                     n=new TreeTrie<V>(c);
 108                     t._nextOther.add(n);
 109                 }
 110                 t=n;
 111             }
 112         }
 113         t._key=v==null?null:s;
 114         t._value = v;
 115         return true;
 116     }
 117
 118     @Override
 119     public V get(String s,int offset, int len)
 120     {
 121         TreeTrie<V> t = this;
 122         for(int i=0; i < len; i++)
 123         {
 124             char c=s.charAt(offset+i);
 125             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 126             if (index>=0)
 127             {
 128                 if (t._nextIndex[index] == null)
 129                     return null;
 130                 t = t._nextIndex[index];
 131             }
 132             else
 133             {
 134                 TreeTrie<V> n=null;
 135                 for (int j=t._nextOther.size();j-->0;)
 136                 {
 137                     n=t._nextOther.get(j);
 138                     if (n._c==c)
 139                         break;
 140                     n=null;
 141                 }
 142                 if (n==null)
 143                     return null;
 144                 t=n;
 145             }
 146         }
 147         return t._value;
 148     }
 149
 150     @Override
 151     public V get(ByteBuffer b,int offset,int len)
 152     {
 153         TreeTrie<V> t = this;
 154         for(int i=0; i < len; i++)
 155         {
 156             byte c=b.get(offset+i);
 157             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 158             if (index>=0)
 159             {
 160                 if (t._nextIndex[index] == null)
 161                     return null;
 162                 t = t._nextIndex[index];
 163             }
 164             else
 165             {
 166                 TreeTrie<V> n=null;
 167                 for (int j=t._nextOther.size();j-->0;)
 168                 {
 169                     n=t._nextOther.get(j);
 170                     if (n._c==c)
 171                         break;
 172                     n=null;
 173                 }
 174                 if (n==null)
 175                     return null;
 176                 t=n;
 177             }
 178         }
 179         return t._value;
 180     }
 181
 182     @Override
 183     public V getBest(byte[] b,int offset,int len)
 184     {
 185         TreeTrie<V> t = this;
 186         for(int i=0; i < len; i++)
 187         {
 188             byte c=b[offset+i];
 189             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 190             if (index>=0)
 191             {
 192                 if (t._nextIndex[index] == null)
 193                     break;
 194                 t = t._nextIndex[index];
 195             }
 196             else
 197             {
 198                 TreeTrie<V> n=null;
 199                 for (int j=t._nextOther.size();j-->0;)
 200                 {
 201                     n=t._nextOther.get(j);
 202                     if (n._c==c)
 203                         break;
 204                     n=null;
 205                 }
 206                 if (n==null)
 207                     break;
 208                 t=n;
 209             }
 210
 211             // Is the next Trie is a match
 212             if (t._key!=null)
 213             {
 214                 // Recurse so we can remember this possibility
 215                 V best=t.getBest(b,offset+i+1,len-i-1);
 216                 if (best!=null)
 217                     return best;
 218                 break;
 219             }
 220         }
 221         return t._value;
 222     }
 223
 224     @Override
 225     public V getBest(String s, int offset, int len)
 226     {
 227         // TODO inefficient
 228         byte[] b=s.substring(offset,offset+len).getBytes(StandardCharsets.ISO_8859_1);
 229         return getBest(b,0,b.length);
 230     }
 231
 232     @Override
 233     public V getBest(ByteBuffer b,int offset,int len)
 234     {
 235         if (b.hasArray())
 236             return getBest(b.array(),b.arrayOffset()+b.position()+offset,len);
 237         return getBestByteBuffer(b,offset,len);
 238     }
 239
 240     private V getBestByteBuffer(ByteBuffer b,int offset,int len)
 241     {
 242         TreeTrie<V> t = this;
 243         int pos=b.position()+offset;
 244         for(int i=0; i < len; i++)
 245         {
 246             byte c=b.get(pos++);
 247             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 248             if (index>=0)
 249             {
 250                 if (t._nextIndex[index] == null)
 251                     break;
 252                 t = t._nextIndex[index];
 253             }
 254             else
 255             {
 256                 TreeTrie<V> n=null;
 257                 for (int j=t._nextOther.size();j-->0;)
 258                 {
 259                     n=t._nextOther.get(j);
 260                     if (n._c==c)
 261                         break;
 262                     n=null;
 263                 }
 264                 if (n==null)
 265                     break;
 266                 t=n;
 267             }
 268
 269             // Is the next Trie is a match
 270             if (t._key!=null)
 271             {
 272                 // Recurse so we can remember this possibility
 273                 V best=t.getBest(b,offset+i+1,len-i-1);
 274                 if (best!=null)
 275                     return best;
 276                 break;
 277             }
 278         }
 279         return t._value;
 280     }
 281
 282
 283     @Override
 284     public String toString()
 285     {
 286         StringBuilder buf = new StringBuilder();
 287         toString(buf,this);
 288
 289         if (buf.length()==0)
 290             return "{}";
 291
 292         buf.setCharAt(0,'{');
 293         buf.append('}');
 294         return buf.toString();
 295     }
 296
 297     private static <V> void toString(Appendable out, TreeTrie<V> t)
 298     {
 299         if (t != null)
 300         {
 301             if (t._value!=null)
 302             {
 303                 try
 304                 {
 305                     out.append(',');
 306                     out.append(t._key);
 307                     out.append('=');
 308                     out.append(t._value.toString());
 309                 }
 310                 catch (IOException e)
 311                 {
 312                     throw new RuntimeException(e);
 313                 }
 314             }
 315
 316             for(int i=0; i < INDEX; i++)
 317             {
 318                 if (t._nextIndex[i] != null)
 319                     toString(out,t._nextIndex[i]);
 320             }
 321             for (int i=t._nextOther.size();i-->0;)
 322                 toString(out,t._nextOther.get(i));
 323         }
 324     }
 325
 326     @Override
 327     public Set<String> keySet()
 328     {
 329         Set<String> keys = new HashSet<>();
 330         keySet(keys,this);
 331         return keys;
 332     }
 333
 334     private static <V> void keySet(Set<String> set, TreeTrie<V> t)
 335     {
 336         if (t != null)
 337         {
 338             if (t._key!=null)
 339                 set.add(t._key);
 340
 341             for(int i=0; i < INDEX; i++)
 342             {
 343                 if (t._nextIndex[i] != null)
 344                     keySet(set,t._nextIndex[i]);
 345             }
 346             for (int i=t._nextOther.size();i-->0;)
 347                 keySet(set,t._nextOther.get(i));
 348         }
 349     }
 350
 351     @Override
 352     public boolean isFull()
 353     {
 354         return false;
 355     }
 356
 357
 358 }