| // |
| // ======================================================================== |
| // 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); |
| } |
| } |