View Javadoc

    1   // ========================================================================
    2   // Copyright 2004-2005 Mort Bay Consulting Pty. Ltd.
    3   // ------------------------------------------------------------------------
    4   // Licensed under the Apache License, Version 2.0 (the "License");
    5   // you may not use this file except in compliance with the License.
    6   // You may obtain a copy of the License at
    7   // http://www.apache.org/licenses/LICENSE-2.0
    8   // Unless required by applicable law or agreed to in writing, software
    9   // distributed under the License is distributed on an "AS IS" BASIS,
    10  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    11  // See the License for the specific language governing permissions and
    12  // limitations under the License.
    13  // ========================================================================
    14
    15  package org.mortbay.util;
    16
    17  import java.io.Externalizable;
    18  import java.util.AbstractMap;
    19  import java.util.Collections;
    20  import java.util.HashMap;
    21  import java.util.HashSet;
    22  import java.util.Map;
    23  import java.util.Set;
    24
    25  /* ------------------------------------------------------------ */
    26  /** Map implementation Optimized for Strings keys..
    27   * This String Map has been optimized for mapping small sets of
    28   * Strings where the most frequently accessed Strings have been put to
    29   * the map first.
    30   *
    31   * It also has the benefit that it can look up entries by substring or
    32   * sections of char and byte arrays.  This can prevent many String
    33   * objects from being created just to look up in the map.
    34   *
    35   * This map is NOT synchronized.
    36   *
    37   * @author Greg Wilkins (gregw)
    38   */
    39  public class StringMap extends AbstractMap implements Externalizable
    40  {
    41      public static final boolean CASE_INSENSTIVE=true;
    42      protected static final int __HASH_WIDTH=17;
    43
    44      /* ------------------------------------------------------------ */
    45      protected int _width=__HASH_WIDTH;
    46      protected Node _root=new Node();
    47      protected boolean _ignoreCase=false;
    48      protected NullEntry _nullEntry=null;
    49      protected Object _nullValue=null;
    50  	protected HashSet _entrySet=new HashSet(3);
    51  	protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
    52
    53      /* ------------------------------------------------------------ */
    54      /** Constructor.
    55       */
    56      public StringMap()
    57      {}
    58
    59      /* ------------------------------------------------------------ */
    60      /** Constructor.
    61       * @param ignoreCase
    62       */
    63      public StringMap(boolean ignoreCase)
    64      {
    65          this();
    66          _ignoreCase=ignoreCase;
    67      }
    68
    69      /* ------------------------------------------------------------ */
    70      /** Constructor.
    71       * @param ignoreCase
    72       * @param width Width of hash tables, larger values are faster but
    73       * use more memory.
    74       */
    75      public StringMap(boolean ignoreCase,int width)
    76      {
    77          this();
    78          _ignoreCase=ignoreCase;
    79          _width=width;
    80      }
    81
    82      /* ------------------------------------------------------------ */
    83      /** Set the ignoreCase attribute.
    84       * @param ic If true, the map is case insensitive for keys.
    85       */
    86      public void setIgnoreCase(boolean ic)
    87      {
    88          if (_root._children!=null)
    89              throw new IllegalStateException("Must be set before first put");
    90          _ignoreCase=ic;
    91      }
    92
    93      /* ------------------------------------------------------------ */
    94      public boolean isIgnoreCase()
    95      {
    96          return _ignoreCase;
    97      }
    98
    99      /* ------------------------------------------------------------ */
    100     /** Set the hash width.
    101      * @param width Width of hash tables, larger values are faster but
    102      * use more memory.
    103      */
    104     public void setWidth(int width)
    105     {
    106         _width=width;
    107     }
    108
    109     /* ------------------------------------------------------------ */
    110     public int getWidth()
    111     {
    112         return _width;
    113     }
    114
    115     /* ------------------------------------------------------------ */
    116     public Object put(Object key, Object value)
    117     {
    118         if (key==null)
    119             return put(null,value);
    120         return put(key.toString(),value);
    121     }
    122
    123     /* ------------------------------------------------------------ */
    124     public Object put(String key, Object value)
    125     {
    126         if (key==null)
    127         {
    128             Object oldValue=_nullValue;
    129             _nullValue=value;
    130             if (_nullEntry==null)
    131             {
    132                 _nullEntry=new NullEntry();
    133                 _entrySet.add(_nullEntry);
    134             }
    135             return oldValue;
    136         }
    137
    138         Node node = _root;
    139         int ni=-1;
    140         Node prev = null;
    141         Node parent = null;
    142
    143         // look for best match
    144     charLoop:
    145         for (int i=0;i<key.length();i++)
    146         {
    147             char c=key.charAt(i);
    148
    149             // Advance node
    150             if (ni==-1)
    151             {
    152                 parent=node;
    153                 prev=null;
    154                 ni=0;
    155                 node=(node._children==null)?null:node._children[c%_width];
    156             }
    157
    158             // Loop through a node chain at the same level
    159             while (node!=null)
    160             {
    161                 // If it is a matching node, goto next char
    162                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
    163                 {
    164                     prev=null;
    165                     ni++;
    166                     if (ni==node._char.length)
    167                         ni=-1;
    168                     continue charLoop;
    169                 }
    170
    171                 // no char match
    172                 // if the first char,
    173                 if (ni==0)
    174                 {
    175                     // look along the chain for a char match
    176                     prev=node;
    177                     node=node._next;
    178                 }
    179                 else
    180                 {
    181                     // Split the current node!
    182                     node.split(this,ni);
    183                     i--;
    184                     ni=-1;
    185                     continue charLoop;
    186                 }
    187             }
    188
    189             // We have run out of nodes, so as this is a put, make one
    190             node = new Node(_ignoreCase,key,i);
    191
    192             if (prev!=null) // add to end of chain
    193                 prev._next=node;
    194             else if (parent!=null) // add new child
    195             {
    196                 if (parent._children==null)
    197                     parent._children=new Node[_width];
    198                 parent._children[c%_width]=node;
    199                 int oi=node._ochar[0]%_width;
    200                 if (node._ochar!=null && node._char[0]%_width!=oi)
    201                 {
    202                     if (parent._children[oi]==null)
    203                         parent._children[oi]=node;
    204                     else
    205                     {
    206                         Node n=parent._children[oi];
    207                         while(n._next!=null)
    208                             n=n._next;
    209                         n._next=node;
    210                     }
    211                 }
    212             }
    213             else // this is the root.
    214                 _root=node;
    215             break;
    216         }
    217
    218         // Do we have a node
    219         if (node!=null)
    220         {
    221             // Split it if we are in the middle
    222             if(ni>0)
    223                 node.split(this,ni);
    224
    225             Object old = node._value;
    226             node._key=key;
    227             node._value=value;
    228             _entrySet.add(node);
    229             return old;
    230         }
    231         return null;
    232     }
    233
    234     /* ------------------------------------------------------------ */
    235     public Object get(Object key)
    236     {
    237         if (key==null)
    238             return _nullValue;
    239         if (key instanceof String)
    240             return get((String)key);
    241         return get(key.toString());
    242     }
    243
    244     /* ------------------------------------------------------------ */
    245     public Object get(String key)
    246     {
    247         if (key==null)
    248             return _nullValue;
    249
    250         Map.Entry entry = getEntry(key,0,key.length());
    251         if (entry==null)
    252             return null;
    253         return entry.getValue();
    254     }
    255
    256     /* ------------------------------------------------------------ */
    257     /** Get a map entry by substring key.
    258      * @param key String containing the key
    259      * @param offset Offset of the key within the String.
    260      * @param length The length of the key
    261      * @return The Map.Entry for the key or null if the key is not in
    262      * the map.
    263      */
    264     public Map.Entry getEntry(String key,int offset, int length)
    265     {
    266         if (key==null)
    267             return _nullEntry;
    268
    269         Node node = _root;
    270         int ni=-1;
    271
    272         // look for best match
    273     charLoop:
    274         for (int i=0;i<length;i++)
    275         {
    276             char c=key.charAt(offset+i);
    277
    278             // Advance node
    279             if (ni==-1)
    280             {
    281                 ni=0;
    282                 node=(node._children==null)?null:node._children[c%_width];
    283             }
    284
    285             // Look through the node chain
    286             while (node!=null)
    287             {
    288                 // If it is a matching node, goto next char
    289                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
    290                 {
    291                     ni++;
    292                     if (ni==node._char.length)
    293                         ni=-1;
    294                     continue charLoop;
    295                 }
    296
    297                 // No char match, so if mid node then no match at all.
    298                 if (ni>0) return null;
    299
    300                 // try next in chain
    301                 node=node._next;
    302             }
    303             return null;
    304         }
    305
    306         if (ni>0) return null;
    307         if (node!=null && node._key==null)
    308             return null;
    309         return node;
    310     }
    311
    312     /* ------------------------------------------------------------ */
    313     /** Get a map entry by char array key.
    314      * @param key char array containing the key
    315      * @param offset Offset of the key within the array.
    316      * @param length The length of the key
    317      * @return The Map.Entry for the key or null if the key is not in
    318      * the map.
    319      */
    320     public Map.Entry getEntry(char[] key,int offset, int length)
    321     {
    322         if (key==null)
    323             return _nullEntry;
    324
    325         Node node = _root;
    326         int ni=-1;
    327
    328         // look for best match
    329     charLoop:
    330         for (int i=0;i<length;i++)
    331         {
    332             char c=key[offset+i];
    333
    334             // Advance node
    335             if (ni==-1)
    336             {
    337                 ni=0;
    338                 node=(node._children==null)?null:node._children[c%_width];
    339             }
    340
    341             // While we have a node to try
    342             while (node!=null)
    343             {
    344                 // If it is a matching node, goto next char
    345                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
    346                 {
    347                     ni++;
    348                     if (ni==node._char.length)
    349                         ni=-1;
    350                     continue charLoop;
    351                 }
    352
    353                 // No char match, so if mid node then no match at all.
    354                 if (ni>0) return null;
    355
    356                 // try next in chain
    357                 node=node._next;
    358             }
    359             return null;
    360         }
    361
    362         if (ni>0) return null;
    363         if (node!=null && node._key==null)
    364             return null;
    365         return node;
    366     }
    367
    368     /* ------------------------------------------------------------ */
    369     /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
    370      * A simple 8859-1 byte to char mapping is assumed.
    371      * @param key char array containing the key
    372      * @param offset Offset of the key within the array.
    373      * @param maxLength The length of the key
    374      * @return The Map.Entry for the key or null if the key is not in
    375      * the map.
    376      */
    377     public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
    378     {
    379         if (key==null)
    380             return _nullEntry;
    381
    382         Node node = _root;
    383         int ni=-1;
    384
    385         // look for best match
    386     charLoop:
    387         for (int i=0;i<maxLength;i++)
    388         {
    389             char c=(char)key[offset+i];
    390
    391             // Advance node
    392             if (ni==-1)
    393             {
    394                 ni=0;
    395
    396                 Node child = (node._children==null)?null:node._children[c%_width];
    397
    398                 if (child==null && i>0)
    399                     return node; // This is the best match
    400                 node=child;
    401             }
    402
    403             // While we have a node to try
    404             while (node!=null)
    405             {
    406                 // If it is a matching node, goto next char
    407                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
    408                 {
    409                     ni++;
    410                     if (ni==node._char.length)
    411                         ni=-1;
    412                     continue charLoop;
    413                 }
    414
    415                 // No char match, so if mid node then no match at all.
    416                 if (ni>0) return null;
    417
    418                 // try next in chain
    419                 node=node._next;
    420             }
    421             return null;
    422         }
    423
    424         if (ni>0) return null;
    425         if (node!=null && node._key==null)
    426             return null;
    427         return node;
    428     }
    429
    430
    431     /* ------------------------------------------------------------ */
    432     public Object remove(Object key)
    433     {
    434         if (key==null)
    435             return remove(null);
    436         return remove(key.toString());
    437     }
    438
    439     /* ------------------------------------------------------------ */
    440     public Object remove(String key)
    441     {
    442         if (key==null)
    443         {
    444             Object oldValue=_nullValue;
    445             if (_nullEntry!=null)
    446             {
    447                 _entrySet.remove(_nullEntry);
    448                 _nullEntry=null;
    449                 _nullValue=null;
    450             }
    451             return oldValue;
    452         }
    453
    454         Node node = _root;
    455         int ni=-1;
    456
    457         // look for best match
    458     charLoop:
    459         for (int i=0;i<key.length();i++)
    460         {
    461             char c=key.charAt(i);
    462
    463             // Advance node
    464             if (ni==-1)
    465             {
    466                 ni=0;
    467                 node=(node._children==null)?null:node._children[c%_width];
    468             }
    469
    470             // While we have a node to try
    471             while (node!=null)
    472             {
    473                 // If it is a matching node, goto next char
    474                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
    475                 {
    476                     ni++;
    477                     if (ni==node._char.length)
    478                         ni=-1;
    479                     continue charLoop;
    480                 }
    481
    482                 // No char match, so if mid node then no match at all.
    483                 if (ni>0) return null;
    484
    485                 // try next in chain
    486                 node=node._next;
    487             }
    488             return null;
    489         }
    490
    491         if (ni>0) return null;
    492         if (node!=null && node._key==null)
    493             return null;
    494
    495         Object old = node._value;
    496         _entrySet.remove(node);
    497         node._value=null;
    498         node._key=null;
    499
    500         return old;
    501     }
    502
    503     /* ------------------------------------------------------------ */
    504     public Set entrySet()
    505     {
    506         return _umEntrySet;
    507     }
    508
    509     /* ------------------------------------------------------------ */
    510     public int size()
    511     {
    512         return _entrySet.size();
    513     }
    514
    515     /* ------------------------------------------------------------ */
    516     public boolean isEmpty()
    517     {
    518         return _entrySet.isEmpty();
    519     }
    520
    521     /* ------------------------------------------------------------ */
    522     public boolean containsKey(Object key)
    523     {
    524         if (key==null)
    525             return _nullEntry!=null;
    526         return
    527             getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
    528     }
    529
    530     /* ------------------------------------------------------------ */
    531     public void clear()
    532     {
    533         _root=new Node();
    534         _nullEntry=null;
    535         _nullValue=null;
    536         _entrySet.clear();
    537     }
    538
    539
    540     /* ------------------------------------------------------------ */
    541     /* ------------------------------------------------------------ */
    542     /* ------------------------------------------------------------ */
    543     private static class Node implements Map.Entry
    544     {
    545         char[] _char;
    546         char[] _ochar;
    547         Node _next;
    548         Node[] _children;
    549         String _key;
    550         Object _value;
    551
    552         Node(){}
    553
    554         Node(boolean ignoreCase,String s, int offset)
    555         {
    556             int l=s.length()-offset;
    557             _char=new char[l];
    558             _ochar=new char[l];
    559             for (int i=0;i<l;i++)
    560             {
    561                 char c=s.charAt(offset+i);
    562                 _char[i]=c;
    563                 if (ignoreCase)
    564                 {
    565                     char o=c;
    566                     if (Character.isUpperCase(c))
    567                         o=Character.toLowerCase(c);
    568                     else if (Character.isLowerCase(c))
    569                         o=Character.toUpperCase(c);
    570                     _ochar[i]=o;
    571                 }
    572             }
    573         }
    574
    575         Node split(StringMap map,int offset)
    576         {
    577             Node split = new Node();
    578             int sl=_char.length-offset;
    579
    580             char[] tmp=this._char;
    581             this._char=new char[offset];
    582             split._char = new char[sl];
    583             System.arraycopy(tmp,0,this._char,0,offset);
    584             System.arraycopy(tmp,offset,split._char,0,sl);
    585
    586             if (this._ochar!=null)
    587             {
    588                 tmp=this._ochar;
    589                 this._ochar=new char[offset];
    590                 split._ochar = new char[sl];
    591                 System.arraycopy(tmp,0,this._ochar,0,offset);
    592                 System.arraycopy(tmp,offset,split._ochar,0,sl);
    593             }
    594
    595             split._key=this._key;
    596             split._value=this._value;
    597             this._key=null;
    598             this._value=null;
    599             if (map._entrySet.remove(this))
    600                 map._entrySet.add(split);
    601
    602             split._children=this._children;
    603             this._children=new Node[map._width];
    604             this._children[split._char[0]%map._width]=split;
    605             if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
    606                 this._children[split._ochar[0]%map._width]=split;
    607
    608             return split;
    609         }
    610
    611         public Object getKey(){return _key;}
    612         public Object getValue(){return _value;}
    613         public Object setValue(Object o){Object old=_value;_value=o;return old;}
    614         public String toString()
    615         {
    616             StringBuffer buf=new StringBuffer();
    617             synchronized(buf)
    618             {
    619                 toString(buf);
    620             }
    621             return buf.toString();
    622         }
    623
    624         private void toString(StringBuffer buf)
    625         {
    626             buf.append("{[");
    627             if (_char==null)
    628                 buf.append('-');
    629             else
    630                 for (int i=0;i<_char.length;i++)
    631                     buf.append(_char[i]);
    632             buf.append(':');
    633             buf.append(_key);
    634             buf.append('=');
    635             buf.append(_value);
    636             buf.append(']');
    637             if (_children!=null)
    638             {
    639                 for (int i=0;i<_children.length;i++)
    640                 {
    641                     buf.append('|');
    642                     if (_children[i]!=null)
    643                         _children[i].toString(buf);
    644                     else
    645                         buf.append("-");
    646                 }
    647             }
    648             buf.append('}');
    649             if (_next!=null)
    650             {
    651                 buf.append(",\n");
    652                 _next.toString(buf);
    653             }
    654         }
    655     }
    656
    657     /* ------------------------------------------------------------ */
    658     /* ------------------------------------------------------------ */
    659     private class NullEntry implements Map.Entry
    660     {
    661         public Object getKey(){return null;}
    662         public Object getValue(){return _nullValue;}
    663         public Object setValue(Object o)
    664             {Object old=_nullValue;_nullValue=o;return old;}
    665         public String toString(){return "[:null="+_nullValue+"]";}
    666     }
    667
    668     /* ------------------------------------------------------------ */
    669     public void writeExternal(java.io.ObjectOutput out)
    670         throws java.io.IOException
    671     {
    672         HashMap map = new HashMap(this);
    673         out.writeBoolean(_ignoreCase);
    674         out.writeObject(map);
    675     }
    676
    677     /* ------------------------------------------------------------ */
    678     public void readExternal(java.io.ObjectInput in)
    679         throws java.io.IOException, ClassNotFoundException
    680     {
    681         boolean ic=in.readBoolean();
    682         HashMap map = (HashMap)in.readObject();
    683         setIgnoreCase(ic);
    684         this.putAll(map);
    685     }
    686 }