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