lib/jetty/org/eclipse/jetty/util/ArrayTrie.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.util.HashSet;
  24 import java.util.Set;
  25
  26 /* ------------------------------------------------------------ */
  27 /**
  28  * <p>A Trie String lookup data structure using a fixed size array.</p>
  29  * <p>This implementation is always case insensitive and is optimal for
  30  * a small number of fixed strings with few special characters.  The
  31  * Trie is stored in an array of lookup tables, each indexed by the
  32  * next character of the key.   Frequently used characters are directly
  33  * indexed in each lookup table, whilst infrequently used characters
  34  * must use a big character table.
  35  * </p>
  36  * <p>This Trie is very space efficient if the key characters are
  37  * from ' ', '+', '-', ':', ';', '.', 'A' to 'Z' or 'a' to 'z'.
  38  * Other ISO-8859-1 characters can be used by the key, but less space
  39  * efficiently.
  40  * </p>
  41  * <p>This Trie is not Threadsafe and contains no mutual exclusion
  42  * or deliberate memory barriers.  It is intended for an ArrayTrie to be
  43  * built by a single thread and then used concurrently by multiple threads
  44  * and not mutated during that access.  If concurrent mutations of the
  45  * Trie is required external locks need to be applied.
  46  * </p>
  47  * @param <V>
  48  */
  49 public class ArrayTrie<V> extends AbstractTrie<V>
  50 {
  51     /**
  52      * The Size of a Trie row is how many characters can be looked
  53      * up directly without going to a big index.  This is set at
  54      * 32 to cover case insensitive alphabet and a few other common
  55      * characters.
  56      */
  57     private static final int ROW_SIZE = 32;
  58
  59     /**
  60      * The index lookup table, this maps a character as a byte
  61      * (ISO-8859-1 or UTF8) to an index within a Trie row
  62      */
  63     private static final int[] __lookup =
  64     { // 0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
  65    /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  66    /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  67    /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1,
  68    /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
  69    /*4*/-1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  70    /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  71    /*6*/-1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  72    /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  73     };
  74
  75     /**
  76      * The Trie rows in a single array which allows a lookup of row,character
  77      * to the next row in the Trie.  This is actually a 2 dimensional
  78      * array that has been flattened to achieve locality of reference.
  79      * The first ROW_SIZE entries are for row 0, then next ROW_SIZE
  80      * entries are for row 1 etc.   So in general instead of using
  81      * _rows[row][index], we use _rows[row*ROW_SIZE+index] to look up
  82      * the next row for a given character.
  83      *
  84      * The array is of characters rather than integers to save space.
  85      */
  86     private final char[] _rowIndex;
  87
  88     /**
  89      * The key (if any) for a Trie row.
  90      * A row may be a leaf, a node or both in the Trie tree.
  91      */
  92     private final String[] _key;
  93
  94     /**
  95      * The value (if any) for a Trie row.
  96      * A row may be a leaf, a node or both in the Trie tree.
  97      */
  98     private final V[] _value;
  99
 100     /**
 101      * A big index for each row.
 102      * If a character outside of the lookup map is needed,
 103      * then a big index will be created for the row, with
 104      * 256 entries, one for each possible byte.
 105      */
 106     private char[][] _bigIndex;
 107
 108     /**
 109      * The number of rows allocated
 110      */
 111     private char _rows;
 112
 113     public ArrayTrie()
 114     {
 115         this(128);
 116     }
 117
 118     /* ------------------------------------------------------------ */
 119     /**
 120      * @param capacity  The capacity of the trie, which at the worst case
 121      * is the total number of characters of all keys stored in the Trie.
 122      * The capacity needed is dependent of the shared prefixes of the keys.
 123      * For example, a capacity of 6 nodes is required to store keys "foo"
 124      * and "bar", but a capacity of only 4 is required to
 125      * store "bar" and "bat".
 126      */
 127     @SuppressWarnings("unchecked")
 128     public ArrayTrie(int capacity)
 129     {
 130         super(true);
 131         _value=(V[])new Object[capacity];
 132         _rowIndex=new char[capacity*32];
 133         _key=new String[capacity];
 134     }
 135
 136
 137     /* ------------------------------------------------------------ */
 138     @Override
 139     public boolean put(String s, V v)
 140     {
 141         int t=0;
 142         int k;
 143         int limit = s.length();
 144         for(k=0; k < limit; k++)
 145         {
 146             char c=s.charAt(k);
 147
 148             int index=__lookup[c&0x7f];
 149             if (index>=0)
 150             {
 151                 int idx=t*ROW_SIZE+index;
 152                 t=_rowIndex[idx];
 153                 if (t==0)
 154                 {
 155                     if (++_rows>=_value.length)
 156                         return false;
 157                     t=_rowIndex[idx]=_rows;
 158                 }
 159             }
 160             else if (c>127)
 161                 throw new IllegalArgumentException("non ascii character");
 162             else
 163             {
 164                 if (_bigIndex==null)
 165                     _bigIndex=new char[_value.length][];
 166                 if (t>=_bigIndex.length)
 167                     return false;
 168                 char[] big=_bigIndex[t];
 169                 if (big==null)
 170                     big=_bigIndex[t]=new char[128];
 171                 t=big[c];
 172                 if (t==0)
 173                 {
 174                     if (_rows==_value.length)
 175                         return false;
 176                     t=big[c]=++_rows;
 177                 }
 178             }
 179         }
 180
 181         if (t>=_key.length)
 182         {
 183             _rows=(char)_key.length;
 184             return false;
 185         }
 186
 187         _key[t]=v==null?null:s;
 188         _value[t] = v;
 189         return true;
 190     }
 191
 192     /* ------------------------------------------------------------ */
 193     @Override
 194     public V get(String s, int offset, int len)
 195     {
 196         int t = 0;
 197         for(int i=0; i < len; i++)
 198         {
 199             char c=s.charAt(offset+i);
 200             int index=__lookup[c&0x7f];
 201             if (index>=0)
 202             {
 203                 int idx=t*ROW_SIZE+index;
 204                 t=_rowIndex[idx];
 205                 if (t==0)
 206                     return null;
 207             }
 208             else
 209             {
 210                 char[] big = _bigIndex==null?null:_bigIndex[t];
 211                 if (big==null)
 212                     return null;
 213                 t=big[c];
 214                 if (t==0)
 215                     return null;
 216             }
 217         }
 218         return _value[t];
 219     }
 220
 221     /* ------------------------------------------------------------ */
 222     @Override
 223     public V get(ByteBuffer b,int offset,int len)
 224     {
 225         int t = 0;
 226         for(int i=0; i < len; i++)
 227         {
 228             byte c=b.get(offset+i);
 229             int index=__lookup[c&0x7f];
 230             if (index>=0)
 231             {
 232                 int idx=t*ROW_SIZE+index;
 233                 t=_rowIndex[idx];
 234                 if (t==0)
 235                     return null;
 236             }
 237             else
 238             {
 239                 char[] big = _bigIndex==null?null:_bigIndex[t];
 240                 if (big==null)
 241                     return null;
 242                 t=big[c];
 243                 if (t==0)
 244                     return null;
 245             }
 246         }
 247         return (V)_value[t];
 248     }
 249
 250     /* ------------------------------------------------------------ */
 251     @Override
 252     public V getBest(byte[] b,int offset,int len)
 253     {
 254         return getBest(0,b,offset,len);
 255     }
 256
 257     /* ------------------------------------------------------------ */
 258     @Override
 259     public V getBest(ByteBuffer b,int offset,int len)
 260     {
 261         if (b.hasArray())
 262             return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
 263         return getBest(0,b,offset,len);
 264     }
 265
 266     /* ------------------------------------------------------------ */
 267     @Override
 268     public V getBest(String s, int offset, int len)
 269     {
 270         return getBest(0,s,offset,len);
 271     }
 272
 273     /* ------------------------------------------------------------ */
 274     private V getBest(int t, String s, int offset, int len)
 275     {
 276         int pos=offset;
 277         for(int i=0; i < len; i++)
 278         {
 279             char c=s.charAt(pos++);
 280             int index=__lookup[c&0x7f];
 281             if (index>=0)
 282             {
 283                 int idx=t*ROW_SIZE+index;
 284                 int nt=_rowIndex[idx];
 285                 if (nt==0)
 286                     break;
 287                 t=nt;
 288             }
 289             else
 290             {
 291                 char[] big = _bigIndex==null?null:_bigIndex[t];
 292                 if (big==null)
 293                     return null;
 294                 int nt=big[c];
 295                 if (nt==0)
 296                     break;
 297                 t=nt;
 298             }
 299
 300             // Is the next Trie is a match
 301             if (_key[t]!=null)
 302             {
 303                 // Recurse so we can remember this possibility
 304                 V best=getBest(t,s,offset+i+1,len-i-1);
 305                 if (best!=null)
 306                     return best;
 307                 return (V)_value[t];
 308             }
 309         }
 310         return (V)_value[t];
 311     }
 312
 313     /* ------------------------------------------------------------ */
 314     private V getBest(int t,byte[] b,int offset,int len)
 315     {
 316         for(int i=0; i < len; i++)
 317         {
 318             byte c=b[offset+i];
 319             int index=__lookup[c&0x7f];
 320             if (index>=0)
 321             {
 322                 int idx=t*ROW_SIZE+index;
 323                 int nt=_rowIndex[idx];
 324                 if (nt==0)
 325                     break;
 326                 t=nt;
 327             }
 328             else
 329             {
 330                 char[] big = _bigIndex==null?null:_bigIndex[t];
 331                 if (big==null)
 332                     return null;
 333                 int nt=big[c];
 334                 if (nt==0)
 335                     break;
 336                 t=nt;
 337             }
 338
 339             // Is the next Trie is a match
 340             if (_key[t]!=null)
 341             {
 342                 // Recurse so we can remember this possibility
 343                 V best=getBest(t,b,offset+i+1,len-i-1);
 344                 if (best!=null)
 345                     return best;
 346                 break;
 347             }
 348         }
 349         return (V)_value[t];
 350     }
 351
 352     private V getBest(int t,ByteBuffer b,int offset,int len)
 353     {
 354         int pos=b.position()+offset;
 355         for(int i=0; i < len; i++)
 356         {
 357             byte c=b.get(pos++);
 358             int index=__lookup[c&0x7f];
 359             if (index>=0)
 360             {
 361                 int idx=t*ROW_SIZE+index;
 362                 int nt=_rowIndex[idx];
 363                 if (nt==0)
 364                     break;
 365                 t=nt;
 366             }
 367             else
 368             {
 369                 char[] big = _bigIndex==null?null:_bigIndex[t];
 370                 if (big==null)
 371                     return null;
 372                 int nt=big[c];
 373                 if (nt==0)
 374                     break;
 375                 t=nt;
 376             }
 377
 378             // Is the next Trie is a match
 379             if (_key[t]!=null)
 380             {
 381                 // Recurse so we can remember this possibility
 382                 V best=getBest(t,b,offset+i+1,len-i-1);
 383                 if (best!=null)
 384                     return best;
 385                 break;
 386             }
 387         }
 388         return (V)_value[t];
 389     }
 390
 391
 392
 393
 394     @Override
 395     public String toString()
 396     {
 397         StringBuilder buf = new StringBuilder();
 398         toString(buf,0);
 399
 400         if (buf.length()==0)
 401             return "{}";
 402
 403         buf.setCharAt(0,'{');
 404         buf.append('}');
 405         return buf.toString();
 406     }
 407
 408
 409     private void toString(Appendable out, int t)
 410     {
 411         if (_value[t]!=null)
 412         {
 413             try
 414             {
 415                 out.append(',');
 416                 out.append(_key[t]);
 417                 out.append('=');
 418                 out.append(_value[t].toString());
 419             }
 420             catch (IOException e)
 421             {
 422                 throw new RuntimeException(e);
 423             }
 424         }
 425
 426         for(int i=0; i < ROW_SIZE; i++)
 427         {
 428             int idx=t*ROW_SIZE+i;
 429             if (_rowIndex[idx] != 0)
 430                 toString(out,_rowIndex[idx]);
 431         }
 432
 433         char[] big = _bigIndex==null?null:_bigIndex[t];
 434         if (big!=null)
 435         {
 436             for (int i:big)
 437                 if (i!=0)
 438                     toString(out,i);
 439         }
 440
 441     }
 442
 443     @Override
 444     public Set<String> keySet()
 445     {
 446         Set<String> keys = new HashSet<>();
 447         keySet(keys,0);
 448         return keys;
 449     }
 450
 451     private void keySet(Set<String> set, int t)
 452     {
 453         if (t<_value.length&&_value[t]!=null)
 454             set.add(_key[t]);
 455
 456         for(int i=0; i < ROW_SIZE; i++)
 457         {
 458             int idx=t*ROW_SIZE+i;
 459             if (idx<_rowIndex.length && _rowIndex[idx] != 0)
 460                 keySet(set,_rowIndex[idx]);
 461         }
 462
 463         char[] big = _bigIndex==null||t>=_bigIndex.length?null:_bigIndex[t];
 464         if (big!=null)
 465         {
 466             for (int i:big)
 467                 if (i!=0)
 468                     keySet(set,i);
 469         }
 470     }
 471
 472     @Override
 473     public boolean isFull()
 474     {
 475         return _rows+1>=_key.length;
 476     }
 477 }