lib/jetty/org/eclipse/jetty/util/ArrayTernaryTrie.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.nio.ByteBuffer;
  22 import java.util.Arrays;
  23 import java.util.HashSet;
  24 import java.util.Set;
  25
  26
  27 /* ------------------------------------------------------------ */
  28 /**
  29  * <p>A Ternary Trie String lookup data structure.</p>
  30  * This Trie is of a fixed size and cannot grow (which can be a good thing with regards to DOS when used as a cache).
  31  * <p>
  32  * The Trie is stored in 3 arrays:<dl>
  33  * <dt>char[] _tree</dt><dd>This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension
  34  * is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a
  35  * ternary trie of key strings.</dd>
  36  * <dt>String[] _key<dt><dd>An array of key values where each element matches a row in the _tree array. A non zero key element
  37  * indicates that the _tree row is a complete key rather than an intermediate character of a longer key.</dd>
  38  * <dt>V[] _value</dt><dd>An array of values corresponding to the _key array</dd>
  39  * </dl>
  40  * </p>
  41  * <p>The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed,
  42  * then the _key array is looked up to see if this is a complete match.  If a match is found then the _value array is looked up
  43  * to return the matching value.
  44  * </p>
  45  * <p>
  46  * This Trie may be instantiated either as case sensitive or insensitive.
  47  * </p>
  48  * <p>This Trie is not Threadsafe and contains no mutual exclusion
  49  * or deliberate memory barriers.  It is intended for an ArrayTrie to be
  50  * built by a single thread and then used concurrently by multiple threads
  51  * and not mutated during that access.  If concurrent mutations of the
  52  * Trie is required external locks need to be applied.
  53  * </p>
  54  *
  55  * @param <V>
  56  */
  57 public class ArrayTernaryTrie<V> extends AbstractTrie<V>
  58 {
  59     private static int LO=1;
  60     private static int EQ=2;
  61     private static int HI=3;
  62
  63     /**
  64      * The Size of a Trie row is the char, and the low, equal and high
  65      * child pointers
  66      */
  67     private static final int ROW_SIZE = 4;
  68
  69     /**
  70      * The Trie rows in a single array which allows a lookup of row,character
  71      * to the next row in the Trie.  This is actually a 2 dimensional
  72      * array that has been flattened to achieve locality of reference.
  73      */
  74     private final char[] _tree;
  75
  76     /**
  77      * The key (if any) for a Trie row.
  78      * A row may be a leaf, a node or both in the Trie tree.
  79      */
  80     private final String[] _key;
  81
  82     /**
  83      * The value (if any) for a Trie row.
  84      * A row may be a leaf, a node or both in the Trie tree.
  85      */
  86     private final V[] _value;
  87
  88     /**
  89      * The number of rows allocated
  90      */
  91     private char _rows;
  92
  93     /* ------------------------------------------------------------ */
  94     /** Create a case insensitive Trie of default capacity.
  95      */
  96     public ArrayTernaryTrie()
  97     {
  98         this(128);
  99     }
 100
 101     /* ------------------------------------------------------------ */
 102     /** Create a Trie of default capacity
 103      * @param insensitive true if the Trie is insensitive to the case of the key.
 104      */
 105     public ArrayTernaryTrie(boolean insensitive)
 106     {
 107         this(insensitive,128);
 108     }
 109
 110     /* ------------------------------------------------------------ */
 111     /** Create a case insensitive Trie
 112      * @param capacity  The capacity of the Trie, which is in the worst case
 113      * is the total number of characters of all keys stored in the Trie.
 114      * The capacity needed is dependent of the shared prefixes of the keys.
 115      * For example, a capacity of 6 nodes is required to store keys "foo"
 116      * and "bar", but a capacity of only 4 is required to
 117      * store "bar" and "bat".
 118      */
 119     public ArrayTernaryTrie(int capacity)
 120     {
 121         this(true,capacity);
 122     }
 123
 124     /* ------------------------------------------------------------ */
 125     /** Create a Trie
 126      * @param insensitive true if the Trie is insensitive to the case of the key.
 127      * @param capacity The capacity of the Trie, which is in the worst case
 128      * is the total number of characters of all keys stored in the Trie.
 129      * The capacity needed is dependent of the shared prefixes of the keys.
 130      * For example, a capacity of 6 nodes is required to store keys "foo"
 131      * and "bar", but a capacity of only 4 is required to
 132      * store "bar" and "bat".
 133      */
 134     public ArrayTernaryTrie(boolean insensitive, int capacity)
 135     {
 136         super(insensitive);
 137         _value=(V[])new Object[capacity];
 138         _tree=new char[capacity*ROW_SIZE];
 139         _key=new String[capacity];
 140     }
 141
 142     /* ------------------------------------------------------------ */
 143     /** Copy Trie and change capacity by a factor
 144      * @param trie
 145      * @param factor
 146      */
 147     public ArrayTernaryTrie(ArrayTernaryTrie<V> trie, double factor)
 148     {
 149         super(trie.isCaseInsensitive());
 150         int capacity=(int)(trie._value.length*factor);
 151         _rows=trie._rows;
 152         _value=Arrays.copyOf(trie._value, capacity);
 153         _tree=Arrays.copyOf(trie._tree, capacity*ROW_SIZE);
 154         _key=Arrays.copyOf(trie._key, capacity);
 155     }
 156
 157     /* ------------------------------------------------------------ */
 158     @Override
 159     public boolean put(String s, V v)
 160     {
 161         int t=0;
 162         int limit = s.length();
 163         int last=0;
 164         for(int k=0; k < limit; k++)
 165         {
 166             char c=s.charAt(k);
 167             if(isCaseInsensitive() && c<128)
 168                 c=StringUtil.lowercases[c];
 169
 170             while (true)
 171             {
 172                 int row=ROW_SIZE*t;
 173
 174                 // Do we need to create the new row?
 175                 if (t==_rows)
 176                 {
 177                     _rows++;
 178                     if (_rows>=_key.length)
 179                     {
 180                         _rows--;
 181                         return false;
 182                     }
 183                     _tree[row]=c;
 184                 }
 185
 186                 char n=_tree[row];
 187                 int diff=n-c;
 188                 if (diff==0)
 189                     t=_tree[last=(row+EQ)];
 190                 else if (diff<0)
 191                     t=_tree[last=(row+LO)];
 192                 else
 193                     t=_tree[last=(row+HI)];
 194
 195                 // do we need a new row?
 196                 if (t==0)
 197                 {
 198                     t=_rows;
 199                     _tree[last]=(char)t;
 200                 }
 201
 202                 if (diff==0)
 203                     break;
 204             }
 205         }
 206
 207         // Do we need to create the new row?
 208         if (t==_rows)
 209         {
 210             _rows++;
 211             if (_rows>=_key.length)
 212             {
 213                 _rows--;
 214                 return false;
 215             }
 216         }
 217
 218         // Put the key and value
 219         _key[t]=v==null?null:s;
 220         _value[t] = v;
 221
 222         return true;
 223     }
 224
 225
 226     /* ------------------------------------------------------------ */
 227     @Override
 228     public V get(String s,int offset, int len)
 229     {
 230         int t = 0;
 231         for(int i=0; i < len;)
 232         {
 233             char c=s.charAt(offset+i++);
 234             if(isCaseInsensitive() && c<128)
 235                 c=StringUtil.lowercases[c];
 236
 237             while (true)
 238             {
 239                 int row = ROW_SIZE*t;
 240                 char n=_tree[row];
 241                 int diff=n-c;
 242
 243                 if (diff==0)
 244                 {
 245                     t=_tree[row+EQ];
 246                     if (t==0)
 247                         return null;
 248                     break;
 249                 }
 250
 251                 t=_tree[row+hilo(diff)];
 252                 if (t==0)
 253                     return null;
 254             }
 255         }
 256
 257         return _value[t];
 258     }
 259
 260
 261     @Override
 262     public V get(ByteBuffer b, int offset, int len)
 263     {
 264         int t = 0;
 265         offset+=b.position();
 266
 267         for(int i=0; i < len;)
 268         {
 269             byte c=(byte)(b.get(offset+i++)&0x7f);
 270             if(isCaseInsensitive())
 271                 c=(byte)StringUtil.lowercases[c];
 272
 273             while (true)
 274             {
 275                 int row = ROW_SIZE*t;
 276                 char n=_tree[row];
 277                 int diff=n-c;
 278
 279                 if (diff==0)
 280                 {
 281                     t=_tree[row+EQ];
 282                     if (t==0)
 283                         return null;
 284                     break;
 285                 }
 286
 287                 t=_tree[row+hilo(diff)];
 288                 if (t==0)
 289                     return null;
 290             }
 291         }
 292
 293         return (V)_value[t];
 294     }
 295
 296     /* ------------------------------------------------------------ */
 297     @Override
 298     public V getBest(String s)
 299     {
 300         return getBest(0,s,0,s.length());
 301     }
 302
 303     /* ------------------------------------------------------------ */
 304     @Override
 305     public V getBest(String s, int offset, int length)
 306     {
 307         return getBest(0,s,offset,length);
 308     }
 309
 310     /* ------------------------------------------------------------ */
 311     private V getBest(int t,String s,int offset,int len)
 312     {
 313         int node=t;
 314         loop: for(int i=0; i<len; i++)
 315         {
 316             char c=s.charAt(offset+i);
 317             if(isCaseInsensitive() && c<128)
 318                 c=StringUtil.lowercases[c];
 319
 320             while (true)
 321             {
 322                 int row = ROW_SIZE*t;
 323                 char n=_tree[row];
 324                 int diff=n-c;
 325
 326                 if (diff==0)
 327                 {
 328                     t=_tree[row+EQ];
 329                     if (t==0)
 330                         break loop;
 331
 332                     // if this node is a match, recurse to remember
 333                     if (_key[t]!=null)
 334                     {
 335                         node=t;
 336                         V best=getBest(t,s,offset+i+1,len-i-1);
 337                         if (best!=null)
 338                             return best;
 339                     }
 340                     break;
 341                 }
 342
 343                 t=_tree[row+hilo(diff)];
 344                 if (t==0)
 345                     break loop;
 346             }
 347         }
 348         return (V)_value[node];
 349     }
 350
 351
 352     /* ------------------------------------------------------------ */
 353     @Override
 354     public V getBest(ByteBuffer b, int offset, int len)
 355     {
 356         if (b.hasArray())
 357             return getBest(0,b.array(),b.arrayOffset()+b.position()+offset,len);
 358         return getBest(0,b,offset,len);
 359     }
 360
 361     /* ------------------------------------------------------------ */
 362     private V getBest(int t,byte[] b, int offset, int len)
 363     {
 364         int node=t;
 365         loop: for(int i=0; i<len; i++)
 366         {
 367             byte c=(byte)(b[offset+i]&0x7f);
 368             if(isCaseInsensitive())
 369                 c=(byte)StringUtil.lowercases[c];
 370
 371             while (true)
 372             {
 373                 int row = ROW_SIZE*t;
 374                 char n=_tree[row];
 375                 int diff=n-c;
 376
 377                 if (diff==0)
 378                 {
 379                     t=_tree[row+EQ];
 380                     if (t==0)
 381                         break loop;
 382
 383                     // if this node is a match, recurse to remember
 384                     if (_key[t]!=null)
 385                     {
 386                         node=t;
 387                         V best=getBest(t,b,offset+i+1,len-i-1);
 388                         if (best!=null)
 389                             return best;
 390                     }
 391                     break;
 392                 }
 393
 394                 t=_tree[row+hilo(diff)];
 395                 if (t==0)
 396                     break loop;
 397             }
 398         }
 399         return (V)_value[node];
 400     }
 401
 402     /* ------------------------------------------------------------ */
 403     private V getBest(int t,ByteBuffer b, int offset, int len)
 404     {
 405         int node=t;
 406         int o= offset+b.position();
 407
 408         loop: for(int i=0; i<len; i++)
 409         {
 410             byte c=(byte)(b.get(o+i)&0x7f);
 411             if(isCaseInsensitive())
 412                 c=(byte)StringUtil.lowercases[c];
 413
 414             while (true)
 415             {
 416                 int row = ROW_SIZE*t;
 417                 char n=_tree[row];
 418                 int diff=n-c;
 419
 420                 if (diff==0)
 421                 {
 422                     t=_tree[row+EQ];
 423                     if (t==0)
 424                         break loop;
 425
 426                     // if this node is a match, recurse to remember
 427                     if (_key[t]!=null)
 428                     {
 429                         node=t;
 430                         V best=getBest(t,b,offset+i+1,len-i-1);
 431                         if (best!=null)
 432                             return best;
 433                     }
 434                     break;
 435                 }
 436
 437                 t=_tree[row+hilo(diff)];
 438                 if (t==0)
 439                     break loop;
 440             }
 441         }
 442         return (V)_value[node];
 443     }
 444
 445     @Override
 446     public String toString()
 447     {
 448         StringBuilder buf = new StringBuilder();
 449         for (int r=0;r<=_rows;r++)
 450         {
 451             if (_key[r]!=null && _value[r]!=null)
 452             {
 453                 buf.append(',');
 454                 buf.append(_key[r]);
 455                 buf.append('=');
 456                 buf.append(_value[r].toString());
 457             }
 458         }
 459         if (buf.length()==0)
 460             return "{}";
 461
 462         buf.setCharAt(0,'{');
 463         buf.append('}');
 464         return buf.toString();
 465     }
 466
 467
 468
 469     @Override
 470     public Set<String> keySet()
 471     {
 472         Set<String> keys = new HashSet<>();
 473
 474         for (int r=0;r<=_rows;r++)
 475         {
 476             if (_key[r]!=null && _value[r]!=null)
 477                 keys.add(_key[r]);
 478         }
 479         return keys;
 480     }
 481
 482     @Override
 483     public boolean isFull()
 484     {
 485         return _rows+1==_key.length;
 486     }
 487
 488     public static int hilo(int diff)
 489     {
 490         // branchless equivalent to return ((diff<0)?LO:HI);
 491         // return 3+2*((diff&Integer.MIN_VALUE)>>Integer.SIZE-1);
 492         return 1+(diff|Integer.MAX_VALUE)/(Integer.MAX_VALUE/2);
 493     }
 494
 495     public void dump()
 496     {
 497         for (int r=0;r<_rows;r++)
 498         {
 499             char c=_tree[r*ROW_SIZE+0];
 500             System.err.printf("%4d [%s,%d,%d,%d] '%s':%s%n",
 501                 r,
 502                 (c<' '||c>127)?(""+(int)c):"'"+c+"'",
 503                 (int)_tree[r*ROW_SIZE+LO],
 504                 (int)_tree[r*ROW_SIZE+EQ],
 505                 (int)_tree[r*ROW_SIZE+HI],
 506                 _key[r],
 507                 _value[r]);
 508         }
 509
 510     }
 511 }