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