View Javadoc

1   // ========================================================================
2   // Copyright (c) 2004-2009 Mort Bay Consulting Pty. Ltd.
3   // ------------------------------------------------------------------------
4   // All rights reserved. This program and the accompanying materials
5   // are made available under the terms of the Eclipse Public License v1.0
6   // and Apache License v2.0 which accompanies this distribution.
7   // The Eclipse Public License is available at 
8   // http://www.eclipse.org/legal/epl-v10.html
9   // The Apache License v2.0 is available at
10  // http://www.opensource.org/licenses/apache2.0.php
11  // You may elect to redistribute this code under either of these licenses. 
12  // ========================================================================
13  
14  package org.eclipse.jetty.util;
15  
16  import java.io.Externalizable;
17  import java.util.AbstractMap;
18  import java.util.Collections;
19  import java.util.HashMap;
20  import java.util.HashSet;
21  import java.util.Map;
22  import java.util.Set;
23  
24  /* ------------------------------------------------------------ */
25  /** Map implementation Optimized for Strings keys..
26   * This String Map has been optimized for mapping small sets of
27   * Strings where the most frequently accessed Strings have been put to
28   * the map first.
29   *
30   * It also has the benefit that it can look up entries by substring or
31   * sections of char and byte arrays.  This can prevent many String
32   * objects from being created just to look up in the map.
33   *
34   * This map is NOT synchronized.
35   *
36   * 
37   */
38  public class StringMap extends AbstractMap implements Externalizable
39  {
40      public static final boolean CASE_INSENSTIVE=true;
41      protected static final int __HASH_WIDTH=17;
42      
43      /* ------------------------------------------------------------ */
44      protected int _width=__HASH_WIDTH;
45      protected Node _root=new Node();
46      protected boolean _ignoreCase=false;
47      protected NullEntry _nullEntry=null;
48      protected Object _nullValue=null;
49      protected HashSet _entrySet=new HashSet(3);
50      protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
51      
52      /* ------------------------------------------------------------ */
53      /** Constructor. 
54       */
55      public StringMap()
56      {}
57      
58      /* ------------------------------------------------------------ */
59      /** Constructor. 
60       * @param ignoreCase 
61       */
62      public StringMap(boolean ignoreCase)
63      {
64          this();
65          _ignoreCase=ignoreCase;
66      }
67      
68      /* ------------------------------------------------------------ */
69      /** Constructor. 
70       * @param ignoreCase 
71       * @param width Width of hash tables, larger values are faster but
72       * use more memory.
73       */
74      public StringMap(boolean ignoreCase,int width)
75      {
76          this();
77          _ignoreCase=ignoreCase;
78          _width=width;
79      }
80      
81      /* ------------------------------------------------------------ */
82      /** Set the ignoreCase attribute.
83       * @param ic If true, the map is case insensitive for keys.
84       */
85      public void setIgnoreCase(boolean ic)
86      {
87          if (_root._children!=null)
88              throw new IllegalStateException("Must be set before first put");
89          _ignoreCase=ic;
90      }
91  
92      /* ------------------------------------------------------------ */
93      public boolean isIgnoreCase()
94      {
95          return _ignoreCase;
96      }
97  
98      /* ------------------------------------------------------------ */
99      /** Set the hash width.
100      * @param width Width of hash tables, larger values are faster but
101      * use more memory.
102      */
103     public void setWidth(int width)
104     {
105         _width=width;
106     }
107 
108     /* ------------------------------------------------------------ */
109     public int getWidth()
110     {
111         return _width;
112     }
113     
114     /* ------------------------------------------------------------ */
115     @Override
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     @Override
236     public Object get(Object key)
237     {
238         if (key==null)
239             return _nullValue;
240         if (key instanceof String)
241             return get((String)key);
242         return get(key.toString());
243     }
244     
245     /* ------------------------------------------------------------ */
246     public Object get(String key)
247     {
248         if (key==null)
249             return _nullValue;
250         
251         Map.Entry entry = getEntry(key,0,key.length());
252         if (entry==null)
253             return null;
254         return entry.getValue();
255     }
256     
257     /* ------------------------------------------------------------ */
258     /** Get a map entry by substring key.
259      * @param key String containing the key
260      * @param offset Offset of the key within the String.
261      * @param length The length of the key 
262      * @return The Map.Entry for the key or null if the key is not in
263      * the map.
264      */
265     public Map.Entry getEntry(String key,int offset, int length)
266     {
267         if (key==null)
268             return _nullEntry;
269         
270         Node node = _root;
271         int ni=-1;
272 
273         // look for best match
274     charLoop:
275         for (int i=0;i<length;i++)
276         {
277             char c=key.charAt(offset+i);
278 
279             // Advance node
280             if (ni==-1)
281             {
282                 ni=0;
283                 node=(node._children==null)?null:node._children[c%_width];
284             }
285             
286             // Look through the node chain
287             while (node!=null) 
288             {
289                 // If it is a matching node, goto next char
290                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
291                 {
292                     ni++;
293                     if (ni==node._char.length)
294                         ni=-1;
295                     continue charLoop;
296                 }
297 
298                 // No char match, so if mid node then no match at all.
299                 if (ni>0) return null;
300 
301                 // try next in chain
302                 node=node._next;                
303             }
304             return null;
305         }
306         
307         if (ni>0) return null;
308         if (node!=null && node._key==null)
309             return null;
310         return node;
311     }
312     
313     /* ------------------------------------------------------------ */
314     /** Get a map entry by char array key.
315      * @param key char array containing the key
316      * @param offset Offset of the key within the array.
317      * @param length The length of the key 
318      * @return The Map.Entry for the key or null if the key is not in
319      * the map.
320      */
321     public Map.Entry getEntry(char[] key,int offset, int length)
322     {
323         if (key==null)
324             return _nullEntry;
325         
326         Node node = _root;
327         int ni=-1;
328 
329         // look for best match
330     charLoop:
331         for (int i=0;i<length;i++)
332         {
333             char c=key[offset+i];
334 
335             // Advance node
336             if (ni==-1)
337             {
338                 ni=0;
339                 node=(node._children==null)?null:node._children[c%_width];
340             }
341             
342             // While we have a node to try
343             while (node!=null) 
344             {
345                 // If it is a matching node, goto next char
346                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
347                 {
348                     ni++;
349                     if (ni==node._char.length)
350                         ni=-1;
351                     continue charLoop;
352                 }
353 
354                 // No char match, so if mid node then no match at all.
355                 if (ni>0) return null;
356 
357                 // try next in chain
358                 node=node._next;                
359             }
360             return null;
361         }
362         
363         if (ni>0) return null;
364         if (node!=null && node._key==null)
365             return null;
366         return node;
367     }
368 
369     /* ------------------------------------------------------------ */
370     /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
371      * A simple 8859-1 byte to char mapping is assumed.
372      * @param key char array containing the key
373      * @param offset Offset of the key within the array.
374      * @param maxLength The length of the key 
375      * @return The Map.Entry for the key or null if the key is not in
376      * the map.
377      */
378     public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
379     {
380         if (key==null)
381             return _nullEntry;
382         
383         Node node = _root;
384         int ni=-1;
385 
386         // look for best match
387     charLoop:
388         for (int i=0;i<maxLength;i++)
389         {
390             char c=(char)key[offset+i];
391 
392             // Advance node
393             if (ni==-1)
394             {
395                 ni=0;
396                 
397                 Node child = (node._children==null)?null:node._children[c%_width];
398                 
399                 if (child==null && i>0)
400                     return node; // This is the best match
401                 node=child;           
402             }
403             
404             // While we have a node to try
405             while (node!=null) 
406             {
407                 // If it is a matching node, goto next char
408                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
409                 {
410                     ni++;
411                     if (ni==node._char.length)
412                         ni=-1;
413                     continue charLoop;
414                 }
415 
416                 // No char match, so if mid node then no match at all.
417                 if (ni>0) return null;
418 
419                 // try next in chain
420                 node=node._next;                
421             }
422             return null;
423         }
424         
425         if (ni>0) return null;
426         if (node!=null && node._key==null)
427             return null;
428         return node;
429     }
430     
431     
432     /* ------------------------------------------------------------ */
433     @Override
434     public Object remove(Object key)
435     {
436         if (key==null)
437             return remove(null);
438         return remove(key.toString());
439     }
440     
441     /* ------------------------------------------------------------ */
442     public Object remove(String key)
443     {
444         if (key==null)
445         {
446             Object oldValue=_nullValue;
447             if (_nullEntry!=null)
448             {
449                 _entrySet.remove(_nullEntry);   
450                 _nullEntry=null;
451                 _nullValue=null;
452             }
453             return oldValue;
454         }
455         
456         Node node = _root;
457         int ni=-1;
458 
459         // look for best match
460     charLoop:
461         for (int i=0;i<key.length();i++)
462         {
463             char c=key.charAt(i);
464 
465             // Advance node
466             if (ni==-1)
467             {
468                 ni=0;
469                 node=(node._children==null)?null:node._children[c%_width];
470             }
471             
472             // While we have a node to try
473             while (node!=null) 
474             {
475                 // If it is a matching node, goto next char
476                 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
477                 {
478                     ni++;
479                     if (ni==node._char.length)
480                         ni=-1;
481                     continue charLoop;
482                 }
483 
484                 // No char match, so if mid node then no match at all.
485                 if (ni>0) return null;
486 
487                 // try next in chain
488                 node=node._next;         
489             }
490             return null;
491         }
492 
493         if (ni>0) return null;
494         if (node!=null && node._key==null)
495             return null;
496         
497         Object old = node._value;
498         _entrySet.remove(node);
499         node._value=null;
500         node._key=null;
501         
502         return old; 
503     }
504 
505     /* ------------------------------------------------------------ */
506     @Override
507     public Set entrySet()
508     {
509         return _umEntrySet;
510     }
511     
512     /* ------------------------------------------------------------ */
513     @Override
514     public int size()
515     {
516         return _entrySet.size();
517     }
518 
519     /* ------------------------------------------------------------ */
520     @Override
521     public boolean isEmpty()
522     {
523         return _entrySet.isEmpty();
524     }
525 
526     /* ------------------------------------------------------------ */
527     @Override
528     public boolean containsKey(Object key)
529     {
530         if (key==null)
531             return _nullEntry!=null;
532         return
533             getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
534     }
535     
536     /* ------------------------------------------------------------ */
537     @Override
538     public void clear()
539     {
540         _root=new Node();
541         _nullEntry=null;
542         _nullValue=null;
543         _entrySet.clear();
544     }
545 
546     
547     /* ------------------------------------------------------------ */
548     /* ------------------------------------------------------------ */
549     /* ------------------------------------------------------------ */
550     private static class Node implements Map.Entry
551     {
552         char[] _char;
553         char[] _ochar;
554         Node _next;
555         Node[] _children;
556         String _key;
557         Object _value;
558         
559         Node(){}
560         
561         Node(boolean ignoreCase,String s, int offset)
562         {
563             int l=s.length()-offset;
564             _char=new char[l];
565             _ochar=new char[l];
566             for (int i=0;i<l;i++)
567             {
568                 char c=s.charAt(offset+i);
569                 _char[i]=c;
570                 if (ignoreCase)
571                 {
572                     char o=c;
573                     if (Character.isUpperCase(c))
574                         o=Character.toLowerCase(c);
575                     else if (Character.isLowerCase(c))
576                         o=Character.toUpperCase(c);
577                     _ochar[i]=o;
578                 }
579             }
580         }
581 
582         Node split(StringMap map,int offset)
583         {
584             Node split = new Node();
585             int sl=_char.length-offset;
586             
587             char[] tmp=this._char;
588             this._char=new char[offset];
589             split._char = new char[sl];
590             System.arraycopy(tmp,0,this._char,0,offset);
591             System.arraycopy(tmp,offset,split._char,0,sl);
592 
593             if (this._ochar!=null)
594             {
595                 tmp=this._ochar;
596                 this._ochar=new char[offset];
597                 split._ochar = new char[sl];
598                 System.arraycopy(tmp,0,this._ochar,0,offset);
599                 System.arraycopy(tmp,offset,split._ochar,0,sl);
600             }
601             
602             split._key=this._key;
603             split._value=this._value;
604             this._key=null;
605             this._value=null;
606             if (map._entrySet.remove(this))
607                 map._entrySet.add(split);
608 
609             split._children=this._children;            
610             this._children=new Node[map._width];
611             this._children[split._char[0]%map._width]=split;
612             if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
613                 this._children[split._ochar[0]%map._width]=split;
614 
615             return split;
616         }
617         
618         public Object getKey(){return _key;}
619         public Object getValue(){return _value;}
620         public Object setValue(Object o){Object old=_value;_value=o;return old;}
621         @Override
622         public String toString()
623         {
624             StringBuilder buf=new StringBuilder();
625             toString(buf);
626             return buf.toString();
627         }
628 
629         private void toString(StringBuilder buf)
630         {
631             buf.append("{[");
632             if (_char==null)
633                 buf.append('-');
634             else
635                 for (int i=0;i<_char.length;i++)
636                     buf.append(_char[i]);
637             buf.append(':');
638             buf.append(_key);
639             buf.append('=');
640             buf.append(_value);
641             buf.append(']');
642             if (_children!=null)
643             {
644                 for (int i=0;i<_children.length;i++)
645                 {
646                     buf.append('|');
647                     if (_children[i]!=null)
648                         _children[i].toString(buf);
649                     else
650                         buf.append("-");
651                 }
652             }
653             buf.append('}');
654             if (_next!=null)
655             {
656                 buf.append(",\n");
657                 _next.toString(buf);
658             }
659         }
660     }
661 
662     /* ------------------------------------------------------------ */
663     /* ------------------------------------------------------------ */
664     private class NullEntry implements Map.Entry
665     {
666         public Object getKey(){return null;}
667         public Object getValue(){return _nullValue;}
668         public Object setValue(Object o)
669             {Object old=_nullValue;_nullValue=o;return old;}
670         @Override
671         public String toString(){return "[:null="+_nullValue+"]";}
672     }
673 
674     /* ------------------------------------------------------------ */
675     public void writeExternal(java.io.ObjectOutput out)
676         throws java.io.IOException
677     {
678         HashMap map = new HashMap(this);
679         out.writeBoolean(_ignoreCase);
680         out.writeObject(map);
681     }
682     
683     /* ------------------------------------------------------------ */
684     public void readExternal(java.io.ObjectInput in)
685         throws java.io.IOException, ClassNotFoundException
686     {
687         boolean ic=in.readBoolean();
688         HashMap map = (HashMap)in.readObject();
689         setIgnoreCase(ic);
690         this.putAll(map);
691     }
692 }