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

   1 //
   2 //  ========================================================================
   3 //  Copyright (c) 1995-2014 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  * @param <V>
  35  */
  36 public class TreeTrie<V> extends AbstractTrie<V>
  37 {
  38     private static final int[] __lookup =
  39     { // 0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
  40    /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  41    /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 30,
  42    /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, -1, -1,
  43    /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
  44    /*4*/-1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  45    /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  46    /*6*/-1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  47    /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  48     };
  49     private static final int INDEX = 32;
  50     private final TreeTrie<V>[]  _nextIndex;
  51     private final List<TreeTrie<V>> _nextOther=new ArrayList<>();
  52     private final char _c;
  53     private String _key;
  54     private V _value;
  55
  56     public TreeTrie()
  57     {
  58         super(true);
  59         _nextIndex = new TreeTrie[INDEX];
  60         _c=0;
  61     }
  62
  63     private TreeTrie(char c)
  64     {
  65         super(true);
  66         _nextIndex = new TreeTrie[INDEX];
  67         this._c=c;
  68     }
  69
  70     @Override
  71     public boolean put(String s, V v)
  72     {
  73         TreeTrie<V> t = this;
  74         int limit = s.length();
  75         for(int k=0; k < limit; k++)
  76         {
  77             char c=s.charAt(k);
  78
  79             int index=c>=0&&c<0x7f?__lookup[c]:-1;
  80             if (index>=0)
  81             {
  82                 if (t._nextIndex[index] == null)
  83                     t._nextIndex[index] = new TreeTrie<V>(c);
  84                 t = t._nextIndex[index];
  85             }
  86             else
  87             {
  88                 TreeTrie<V> n=null;
  89                 for (int i=t._nextOther.size();i-->0;)
  90                 {
  91                     n=t._nextOther.get(i);
  92                     if (n._c==c)
  93                         break;
  94                     n=null;
  95                 }
  96                 if (n==null)
  97                 {
  98                     n=new TreeTrie<V>(c);
  99                     t._nextOther.add(n);
 100                 }
 101                 t=n;
 102             }
 103         }
 104         t._key=v==null?null:s;
 105         t._value = v;
 106         return true;
 107     }
 108
 109     @Override
 110     public V get(String s,int offset, int len)
 111     {
 112         TreeTrie<V> t = this;
 113         for(int i=0; i < len; i++)
 114         {
 115             char c=s.charAt(offset+i);
 116             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 117             if (index>=0)
 118             {
 119                 if (t._nextIndex[index] == null)
 120                     return null;
 121                 t = t._nextIndex[index];
 122             }
 123             else
 124             {
 125                 TreeTrie<V> n=null;
 126                 for (int j=t._nextOther.size();j-->0;)
 127                 {
 128                     n=t._nextOther.get(j);
 129                     if (n._c==c)
 130                         break;
 131                     n=null;
 132                 }
 133                 if (n==null)
 134                     return null;
 135                 t=n;
 136             }
 137         }
 138         return t._value;
 139     }
 140
 141     @Override
 142     public V get(ByteBuffer b,int offset,int len)
 143     {
 144         TreeTrie<V> t = this;
 145         for(int i=0; i < len; i++)
 146         {
 147             byte c=b.get(offset+i);
 148             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 149             if (index>=0)
 150             {
 151                 if (t._nextIndex[index] == null)
 152                     return null;
 153                 t = t._nextIndex[index];
 154             }
 155             else
 156             {
 157                 TreeTrie<V> n=null;
 158                 for (int j=t._nextOther.size();j-->0;)
 159                 {
 160                     n=t._nextOther.get(j);
 161                     if (n._c==c)
 162                         break;
 163                     n=null;
 164                 }
 165                 if (n==null)
 166                     return null;
 167                 t=n;
 168             }
 169         }
 170         return t._value;
 171     }
 172
 173     @Override
 174     public V getBest(byte[] b,int offset,int len)
 175     {
 176         TreeTrie<V> t = this;
 177         for(int i=0; i < len; i++)
 178         {
 179             byte c=b[offset+i];
 180             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 181             if (index>=0)
 182             {
 183                 if (t._nextIndex[index] == null)
 184                     break;
 185                 t = t._nextIndex[index];
 186             }
 187             else
 188             {
 189                 TreeTrie<V> n=null;
 190                 for (int j=t._nextOther.size();j-->0;)
 191                 {
 192                     n=t._nextOther.get(j);
 193                     if (n._c==c)
 194                         break;
 195                     n=null;
 196                 }
 197                 if (n==null)
 198                     break;
 199                 t=n;
 200             }
 201
 202             // Is the next Trie is a match
 203             if (t._key!=null)
 204             {
 205                 // Recurse so we can remember this possibility
 206                 V best=t.getBest(b,offset+i+1,len-i-1);
 207                 if (best!=null)
 208                     return best;
 209                 break;
 210             }
 211         }
 212         return t._value;
 213     }
 214
 215     @Override
 216     public V getBest(String s, int offset, int len)
 217     {
 218         // TODO inefficient
 219         byte[] b=s.substring(offset,offset+len).getBytes(StandardCharsets.ISO_8859_1);
 220         return getBest(b,0,b.length);
 221     }
 222
 223     @Override
 224     public V getBest(ByteBuffer b,int offset,int len)
 225     {
 226         if (b.hasArray())
 227             return getBest(b.array(),b.arrayOffset()+b.position()+offset,len);
 228         return getBestByteBuffer(b,offset,len);
 229     }
 230
 231     private V getBestByteBuffer(ByteBuffer b,int offset,int len)
 232     {
 233         TreeTrie<V> t = this;
 234         int pos=b.position()+offset;
 235         for(int i=0; i < len; i++)
 236         {
 237             byte c=b.get(pos++);
 238             int index=c>=0&&c<0x7f?__lookup[c]:-1;
 239             if (index>=0)
 240             {
 241                 if (t._nextIndex[index] == null)
 242                     break;
 243                 t = t._nextIndex[index];
 244             }
 245             else
 246             {
 247                 TreeTrie<V> n=null;
 248                 for (int j=t._nextOther.size();j-->0;)
 249                 {
 250                     n=t._nextOther.get(j);
 251                     if (n._c==c)
 252                         break;
 253                     n=null;
 254                 }
 255                 if (n==null)
 256                     break;
 257                 t=n;
 258             }
 259
 260             // Is the next Trie is a match
 261             if (t._key!=null)
 262             {
 263                 // Recurse so we can remember this possibility
 264                 V best=t.getBest(b,offset+i+1,len-i-1);
 265                 if (best!=null)
 266                     return best;
 267                 break;
 268             }
 269         }
 270         return t._value;
 271     }
 272
 273
 274     @Override
 275     public String toString()
 276     {
 277         StringBuilder buf = new StringBuilder();
 278         toString(buf,this);
 279
 280         if (buf.length()==0)
 281             return "{}";
 282
 283         buf.setCharAt(0,'{');
 284         buf.append('}');
 285         return buf.toString();
 286     }
 287
 288     private static <V> void toString(Appendable out, TreeTrie<V> t)
 289     {
 290         if (t != null)
 291         {
 292             if (t._value!=null)
 293             {
 294                 try
 295                 {
 296                     out.append(',');
 297                     out.append(t._key);
 298                     out.append('=');
 299                     out.append(t._value.toString());
 300                 }
 301                 catch (IOException e)
 302                 {
 303                     throw new RuntimeException(e);
 304                 }
 305             }
 306
 307             for(int i=0; i < INDEX; i++)
 308             {
 309                 if (t._nextIndex[i] != null)
 310                     toString(out,t._nextIndex[i]);
 311             }
 312             for (int i=t._nextOther.size();i-->0;)
 313                 toString(out,t._nextOther.get(i));
 314         }
 315     }
 316
 317     @Override
 318     public Set<String> keySet()
 319     {
 320         Set<String> keys = new HashSet<>();
 321         keySet(keys,this);
 322         return keys;
 323     }
 324
 325     private static <V> void keySet(Set<String> set, TreeTrie<V> t)
 326     {
 327         if (t != null)
 328         {
 329             if (t._key!=null)
 330                 set.add(t._key);
 331
 332             for(int i=0; i < INDEX; i++)
 333             {
 334                 if (t._nextIndex[i] != null)
 335                     keySet(set,t._nextIndex[i]);
 336             }
 337             for (int i=t._nextOther.size();i-->0;)
 338                 keySet(set,t._nextOther.get(i));
 339         }
 340     }
 341
 342     @Override
 343     public boolean isFull()
 344     {
 345         return false;
 346     }
 347
 348
 349 }