src/java/org/eclipse/jetty/util/StringMap.java

//
//  ========================================================================
//  Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd.
//  ------------------------------------------------------------------------
//  All rights reserved. This program and the accompanying materials
//  are made available under the terms of the Eclipse Public License v1.0
//  and Apache License v2.0 which accompanies this distribution.
//
//      The Eclipse Public License is available at
//      http://www.eclipse.org/legal/epl-v10.html
//
//      The Apache License v2.0 is available at
//      http://www.opensource.org/licenses/apache2.0.php
//
//  You may elect to redistribute this code under either of these licenses.
//  ========================================================================
//

package org.eclipse.jetty.util;

import java.io.Externalizable;
import java.util.AbstractMap;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/* ------------------------------------------------------------ */
/** Map implementation Optimized for Strings keys..
 * This String Map has been optimized for mapping small sets of
 * Strings where the most frequently accessed Strings have been put to
 * the map first.
 *
 * It also has the benefit that it can look up entries by substring or
 * sections of char and byte arrays.  This can prevent many String
 * objects from being created just to look up in the map.
 *
 * This map is NOT synchronized.
 */
public class StringMap extends AbstractMap implements Externalizable
{
    public static final boolean CASE_INSENSTIVE=true;
    protected static final int __HASH_WIDTH=17;
    
    /* ------------------------------------------------------------ */
    protected int _width=__HASH_WIDTH;
    protected Node _root=new Node();
    protected boolean _ignoreCase=false;
    protected NullEntry _nullEntry=null;
    protected Object _nullValue=null;
    protected HashSet _entrySet=new HashSet(3);
    protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet);
    
    /* ------------------------------------------------------------ */
    /** Constructor. 
     */
    public StringMap()
    {}
    
    /* ------------------------------------------------------------ */
    /** Constructor. 
     * @param ignoreCase 
     */
    public StringMap(boolean ignoreCase)
    {
        this();
        _ignoreCase=ignoreCase;
    }
    
    /* ------------------------------------------------------------ */
    /** Constructor. 
     * @param ignoreCase 
     * @param width Width of hash tables, larger values are faster but
     * use more memory.
     */
    public StringMap(boolean ignoreCase,int width)
    {
        this();
        _ignoreCase=ignoreCase;
        _width=width;
    }
    
    /* ------------------------------------------------------------ */
    /** Set the ignoreCase attribute.
     * @param ic If true, the map is case insensitive for keys.
     */
    public void setIgnoreCase(boolean ic)
    {
        if (_root._children!=null)
            throw new IllegalStateException("Must be set before first put");
        _ignoreCase=ic;
    }

    /* ------------------------------------------------------------ */
    public boolean isIgnoreCase()
    {
        return _ignoreCase;
    }

    /* ------------------------------------------------------------ */
    /** Set the hash width.
     * @param width Width of hash tables, larger values are faster but
     * use more memory.
     */
    public void setWidth(int width)
    {
        _width=width;
    }

    /* ------------------------------------------------------------ */
    public int getWidth()
    {
        return _width;
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public Object put(Object key, Object value)
    {
        if (key==null)
            return put(null,value);
        return put(key.toString(),value);
    }
        
    /* ------------------------------------------------------------ */
    public Object put(String key, Object value)
    {
        if (key==null)
        {
            Object oldValue=_nullValue;
            _nullValue=value;
            if (_nullEntry==null)
            {   
                _nullEntry=new NullEntry();
                _entrySet.add(_nullEntry);
            }
            return oldValue;
        }
        
        Node node = _root;
        int ni=-1;
        Node prev = null;
        Node parent = null;

        // look for best match
    charLoop:
        for (int i=0;i<key.length();i++)
        {
            char c=key.charAt(i);
            
            // Advance node
            if (ni==-1)
            {
                parent=node;
                prev=null;
                ni=0;
                node=(node._children==null)?null:node._children[c%_width];
            }
            
            // Loop through a node chain at the same level
            while (node!=null) 
            {
                // If it is a matching node, goto next char
                if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
                {
                    prev=null;
                    ni++;
                    if (ni==node._char.length)
                        ni=-1;
                    continue charLoop;
                }

                // no char match
                // if the first char,
                if (ni==0)
                {
                    // look along the chain for a char match
                    prev=node;
                    node=node._next;
                }
                else
                {
                    // Split the current node!
                    node.split(this,ni);
                    i--;
                    ni=-1;
                    continue charLoop;
                }
            }

            // We have run out of nodes, so as this is a put, make one
            node = new Node(_ignoreCase,key,i);

            if (prev!=null) // add to end of chain
                prev._next=node;
            else if (parent!=null) // add new child
            {
                if (parent._children==null)
                    parent._children=new Node[_width];
                parent._children[c%_width]=node;
                int oi=node._ochar[0]%_width;
                if (node._ochar!=null && node._char[0]%_width!=oi)
                {
                    if (parent._children[oi]==null)
                        parent._children[oi]=node;
                    else
                    {
                        Node n=parent._children[oi];
                        while(n._next!=null)
                            n=n._next;
                        n._next=node;
                    }
                }
            }
            else // this is the root.
                _root=node;
            break;
        }
        
        // Do we have a node
        if (node!=null)
        {
            // Split it if we are in the middle
            if(ni>0)
                node.split(this,ni);
        
            Object old = node._value;
            node._key=key;
            node._value=value;
            _entrySet.add(node);
            return old;
        }
        return null;
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public Object get(Object key)
    {
        if (key==null)
            return _nullValue;
        if (key instanceof String)
            return get((String)key);
        return get(key.toString());
    }
    
    /* ------------------------------------------------------------ */
    public Object get(String key)
    {
        if (key==null)
            return _nullValue;
        
        Map.Entry entry = getEntry(key,0,key.length());
        if (entry==null)
            return null;
        return entry.getValue();
    }
    
    /* ------------------------------------------------------------ */
    /** Get a map entry by substring key.
     * @param key String containing the key
     * @param offset Offset of the key within the String.
     * @param length The length of the key 
     * @return The Map.Entry for the key or null if the key is not in
     * the map.
     */
    public Map.Entry getEntry(String key,int offset, int length)
    {
        if (key==null)
            return _nullEntry;
        
        Node node = _root;
        int ni=-1;

        // look for best match
    charLoop:
        for (int i=0;i<length;i++)
        {
            char c=key.charAt(offset+i);

            // Advance node
            if (ni==-1)
            {
                ni=0;
                node=(node._children==null)?null:node._children[c%_width];
            }
            
            // Look through the node chain
            while (node!=null) 
            {
                // If it is a matching node, goto next char
                if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
                {
                    ni++;
                    if (ni==node._char.length)
                        ni=-1;
                    continue charLoop;
                }

                // No char match, so if mid node then no match at all.
                if (ni>0) return null;

                // try next in chain
                node=node._next;                
            }
            return null;
        }
        
        if (ni>0) return null;
        if (node!=null && node._key==null)
            return null;
        return node;
    }
    
    /* ------------------------------------------------------------ */
    /** Get a map entry by char array key.
     * @param key char array containing the key
     * @param offset Offset of the key within the array.
     * @param length The length of the key 
     * @return The Map.Entry for the key or null if the key is not in
     * the map.
     */
    public Map.Entry getEntry(char[] key,int offset, int length)
    {
        if (key==null)
            return _nullEntry;
        
        Node node = _root;
        int ni=-1;

        // look for best match
    charLoop:
        for (int i=0;i<length;i++)
        {
            char c=key[offset+i];

            // Advance node
            if (ni==-1)
            {
                ni=0;
                node=(node._children==null)?null:node._children[c%_width];
            }
            
            // While we have a node to try
            while (node!=null) 
            {
                // If it is a matching node, goto next char
                if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
                {
                    ni++;
                    if (ni==node._char.length)
                        ni=-1;
                    continue charLoop;
                }

                // No char match, so if mid node then no match at all.
                if (ni>0) return null;

                // try next in chain
                node=node._next;                
            }
            return null;
        }
        
        if (ni>0) return null;
        if (node!=null && node._key==null)
            return null;
        return node;
    }

    /* ------------------------------------------------------------ */
    /** Get a map entry by byte array key, using as much of the passed key as needed for a match.
     * A simple 8859-1 byte to char mapping is assumed.
     * @param key char array containing the key
     * @param offset Offset of the key within the array.
     * @param maxLength The length of the key 
     * @return The Map.Entry for the key or null if the key is not in
     * the map.
     */
    public Map.Entry getBestEntry(byte[] key,int offset, int maxLength)
    {
        if (key==null)
            return _nullEntry;
        
        Node node = _root;
        int ni=-1;

        // look for best match
    charLoop:
        for (int i=0;i<maxLength;i++)
        {
            char c=(char)key[offset+i];

            // Advance node
            if (ni==-1)
            {
                ni=0;
                
                Node child = (node._children==null)?null:node._children[c%_width];
                
                if (child==null && i>0)
                    return node; // This is the best match
                node=child;           
            }
            
            // While we have a node to try
            while (node!=null) 
            {
                // If it is a matching node, goto next char
                if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
                {
                    ni++;
                    if (ni==node._char.length)
                        ni=-1;
                    continue charLoop;
                }

                // No char match, so if mid node then no match at all.
                if (ni>0) return null;

                // try next in chain
                node=node._next;                
            }
            return null;
        }
        
        if (ni>0) return null;
        if (node!=null && node._key==null)
            return null;
        return node;
    }
    
    
    /* ------------------------------------------------------------ */
    @Override
    public Object remove(Object key)
    {
        if (key==null)
            return remove(null);
        return remove(key.toString());
    }
    
    /* ------------------------------------------------------------ */
    public Object remove(String key)
    {
        if (key==null)
        {
            Object oldValue=_nullValue;
            if (_nullEntry!=null)
            {
                _entrySet.remove(_nullEntry);   
                _nullEntry=null;
                _nullValue=null;
            }
            return oldValue;
        }
        
        Node node = _root;
        int ni=-1;

        // look for best match
    charLoop:
        for (int i=0;i<key.length();i++)
        {
            char c=key.charAt(i);

            // Advance node
            if (ni==-1)
            {
                ni=0;
                node=(node._children==null)?null:node._children[c%_width];
            }
            
            // While we have a node to try
            while (node!=null) 
            {
                // If it is a matching node, goto next char
                if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
                {
                    ni++;
                    if (ni==node._char.length)
                        ni=-1;
                    continue charLoop;
                }

                // No char match, so if mid node then no match at all.
                if (ni>0) return null;

                // try next in chain
                node=node._next;         
            }
            return null;
        }

        if (ni>0) return null;
        if (node!=null && node._key==null)
            return null;
        
        Object old = node._value;
        _entrySet.remove(node);
        node._value=null;
        node._key=null;
        
        return old; 
    }

    /* ------------------------------------------------------------ */
    @Override
    public Set entrySet()
    {
        return _umEntrySet;
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public int size()
    {
        return _entrySet.size();
    }

    /* ------------------------------------------------------------ */
    @Override
    public boolean isEmpty()
    {
        return _entrySet.isEmpty();
    }

    /* ------------------------------------------------------------ */
    @Override
    public boolean containsKey(Object key)
    {
        if (key==null)
            return _nullEntry!=null;
        return
            getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public void clear()
    {
        _root=new Node();
        _nullEntry=null;
        _nullValue=null;
        _entrySet.clear();
    }

    
    /* ------------------------------------------------------------ */
    /* ------------------------------------------------------------ */
    /* ------------------------------------------------------------ */
    private static class Node implements Map.Entry
    {
        char[] _char;
        char[] _ochar;
        Node _next;
        Node[] _children;
        String _key;
        Object _value;
        
        Node(){}
        
        Node(boolean ignoreCase,String s, int offset)
        {
            int l=s.length()-offset;
            _char=new char[l];
            _ochar=new char[l];
            for (int i=0;i<l;i++)
            {
                char c=s.charAt(offset+i);
                _char[i]=c;
                if (ignoreCase)
                {
                    char o=c;
                    if (Character.isUpperCase(c))
                        o=Character.toLowerCase(c);
                    else if (Character.isLowerCase(c))
                        o=Character.toUpperCase(c);
                    _ochar[i]=o;
                }
            }
        }

        Node split(StringMap map,int offset)
        {
            Node split = new Node();
            int sl=_char.length-offset;
            
            char[] tmp=this._char;
            this._char=new char[offset];
            split._char = new char[sl];
            System.arraycopy(tmp,0,this._char,0,offset);
            System.arraycopy(tmp,offset,split._char,0,sl);

            if (this._ochar!=null)
            {
                tmp=this._ochar;
                this._ochar=new char[offset];
                split._ochar = new char[sl];
                System.arraycopy(tmp,0,this._ochar,0,offset);
                System.arraycopy(tmp,offset,split._ochar,0,sl);
            }
            
            split._key=this._key;
            split._value=this._value;
            this._key=null;
            this._value=null;
            if (map._entrySet.remove(this))
                map._entrySet.add(split);

            split._children=this._children;            
            this._children=new Node[map._width];
            this._children[split._char[0]%map._width]=split;
            if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
                this._children[split._ochar[0]%map._width]=split;

            return split;
        }
        
        public Object getKey(){return _key;}
        public Object getValue(){return _value;}
        public Object setValue(Object o){Object old=_value;_value=o;return old;}
        @Override
        public String toString()
        {
            StringBuilder buf=new StringBuilder();
            toString(buf);
            return buf.toString();
        }

        private void toString(StringBuilder buf)
        {
            buf.append("{[");
            if (_char==null)
                buf.append('-');
            else
                for (int i=0;i<_char.length;i++)
                    buf.append(_char[i]);
            buf.append(':');
            buf.append(_key);
            buf.append('=');
            buf.append(_value);
            buf.append(']');
            if (_children!=null)
            {
                for (int i=0;i<_children.length;i++)
                {
                    buf.append('|');
                    if (_children[i]!=null)
                        _children[i].toString(buf);
                    else
                        buf.append("-");
                }
            }
            buf.append('}');
            if (_next!=null)
            {
                buf.append(",\n");
                _next.toString(buf);
            }
        }
    }

    /* ------------------------------------------------------------ */
    /* ------------------------------------------------------------ */
    private class NullEntry implements Map.Entry
    {
        public Object getKey(){return null;}
        public Object getValue(){return _nullValue;}
        public Object setValue(Object o)
            {Object old=_nullValue;_nullValue=o;return old;}
        @Override
        public String toString(){return "[:null="+_nullValue+"]";}
    }

    /* ------------------------------------------------------------ */
    public void writeExternal(java.io.ObjectOutput out)
        throws java.io.IOException
    {
        HashMap map = new HashMap(this);
        out.writeBoolean(_ignoreCase);
        out.writeObject(map);
    }
    
    /* ------------------------------------------------------------ */
    public void readExternal(java.io.ObjectInput in)
        throws java.io.IOException, ClassNotFoundException
    {
        boolean ic=in.readBoolean();
        HashMap map = (HashMap)in.readObject();
        setIgnoreCase(ic);
        this.putAll(map);
    }
}