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