changeset 836:e161dca40760

remove StringMap
author Franklin Schmidt <fschmidt@gmail.com>
date Fri, 16 Sep 2016 12:35:17 -0600
parents 88b70b8dab9c
children 3ff59e08a1b7
files src/org/eclipse/jetty/io/BufferCache.java src/org/eclipse/jetty/util/StringMap.java
diffstat 2 files changed, 151 insertions(+), 820 deletions(-) [+]
line wrap: on
line diff
diff -r 88b70b8dab9c -r e161dca40760 src/org/eclipse/jetty/io/BufferCache.java
--- a/src/org/eclipse/jetty/io/BufferCache.java	Fri Sep 16 00:54:15 2016 -0600
+++ b/src/org/eclipse/jetty/io/BufferCache.java	Fri Sep 16 12:35:17 2016 -0600
@@ -20,9 +20,9 @@
 
 import java.util.ArrayList;
 import java.util.HashMap;
-import java.util.Map.Entry;
+import java.util.Map;
+import java.util.TreeMap;
 
-import org.eclipse.jetty.util.StringMap;
 
 /* ------------------------------------------------------------------------------- */
 /** 
@@ -32,138 +32,164 @@
  */
 public class BufferCache
 {
-    private final HashMap _bufferMap=new HashMap();
-    private final StringMap _stringMap=new StringMap(StringMap.CASE_INSENSTIVE);
-    private final ArrayList _index= new ArrayList();
+	private final HashMap _bufferMap=new HashMap();
+	private final TreeMap _stringMap = new TreeMap();
+	private final ArrayList _index= new ArrayList();
 
-    /* ------------------------------------------------------------------------------- */
-    /** Add a buffer to the cache at the specified index.
-     * @param value The content of the buffer.
-     */
-    public CachedBuffer add(String value, int ordinal)
-    {
-        CachedBuffer buffer= new CachedBuffer(value, ordinal);
-        _bufferMap.put(buffer, buffer);
-        _stringMap.put(value, buffer);
-        while ((ordinal - _index.size()) >= 0)
-            _index.add(null);
-        if (_index.get(ordinal)==null)
-            _index.add(ordinal, buffer);
-        return buffer;
-    }
-
-    public CachedBuffer get(int ordinal)
-    {
-        if (ordinal < 0 || ordinal >= _index.size())
-            return null;
-        return (CachedBuffer)_index.get(ordinal);
-    }
+	/* ------------------------------------------------------------------------------- */
+	/** Add a buffer to the cache at the specified index.
+	 * @param value The content of the buffer.
+	 */
+	public CachedBuffer add(String value, int ordinal)
+	{
+		CachedBuffer buffer= new CachedBuffer(value, ordinal);
+		_bufferMap.put(buffer, buffer);
+		_stringMap.put(value.toLowerCase(), buffer);
+		while ((ordinal - _index.size()) >= 0)
+			_index.add(null);
+		if (_index.get(ordinal)==null)
+			_index.add(ordinal, buffer);
+		return buffer;
+	}
 
-    public CachedBuffer get(Buffer buffer)
-    {
-        return (CachedBuffer)_bufferMap.get(buffer);
-    }
+	public CachedBuffer get(int ordinal)
+	{
+		if (ordinal < 0 || ordinal >= _index.size())
+			return null;
+		return (CachedBuffer)_index.get(ordinal);
+	}
 
-    public CachedBuffer get(String value)
-    {
-        return (CachedBuffer)_stringMap.get(value);
-    }
+	public CachedBuffer get(Buffer buffer)
+	{
+		return (CachedBuffer)_bufferMap.get(buffer);
+	}
 
-    public Buffer lookup(Buffer buffer)
-    {
-        if (buffer instanceof CachedBuffer)
-            return buffer;
-        
-        Buffer b= get(buffer);
-        if (b == null)
-        {
-            if (buffer instanceof Buffer.CaseInsensitve)
-                return buffer;
-            return new ByteArrayBuffer.CaseInsensitive(buffer.asArray(),0,buffer.length(),Buffer.IMMUTABLE);
-        }
+	public CachedBuffer get(String value)
+	{
+		return (CachedBuffer)_stringMap.get(value.toLowerCase());
+	}
 
-        return b;
-    }
-    
-    public CachedBuffer getBest(byte[] value, int offset, int maxLength)
-    {
-        Entry entry = _stringMap.getBestEntry(value, offset, maxLength);
-        if (entry!=null)
-            return (CachedBuffer)entry.getValue();
-        return null;
-    }
+	public Buffer lookup(Buffer buffer)
+	{
+		if (buffer instanceof CachedBuffer)
+			return buffer;
+		
+		Buffer b= get(buffer);
+		if (b == null)
+		{
+			if (buffer instanceof Buffer.CaseInsensitve)
+				return buffer;
+			return new ByteArrayBuffer.CaseInsensitive(buffer.asArray(),0,buffer.length(),Buffer.IMMUTABLE);
+		}
 
-    public Buffer lookup(String value)
-    {
-        Buffer b= get(value);
-        if (b == null)
-        {
-            return new CachedBuffer(value,-1);
-        }
-        return b;
-    }
+		return b;
+	}
+	
+	public CachedBuffer getBest(byte[] value, int offset, int maxLength)
+	{
+		String key = new String(value,offset,maxLength).toLowerCase();
+		CachedBuffer buffer = (CachedBuffer)_stringMap.get(key);
+		if( buffer != null )
+			return buffer;
+		Map.Entry floor = _stringMap.floorEntry(key);
+		Map.Entry ceiling = _stringMap.ceilingEntry(key);
+		if( floor==null ) {
+			if( ceiling==null )
+				return null;
+			String ceilingKey = (String)ceiling.getKey();
+			return key.charAt(0) == ceilingKey.charAt(0) ? (CachedBuffer)ceiling.getValue() : null;
+		} else {
+			String floorKey = (String)floor.getKey();
+			if( ceiling==null )
+				return key.charAt(0) == floorKey.charAt(0) ? (CachedBuffer)floor.getValue() : null;
+			String ceilingKey = (String)ceiling.getKey();
+			int n = Math.min( key.length(), Math.min( floorKey.length(), ceilingKey.length() ) );
+			int i = 0;
+			while( ++i <= n && key.regionMatches(0,floorKey,0,i) && key.regionMatches(0,ceilingKey,0,i) );
+			i--;
+			if( i==0 )
+				return null;
+			return i==0 ? null : key.regionMatches(0,floorKey,0,i) ? (CachedBuffer)floor.getValue() : (CachedBuffer)ceiling.getValue();
+		}
+/*
+		Entry entry = _stringMap.getBestEntry(value, offset, maxLength);
+		if (entry!=null)
+			return (CachedBuffer)entry.getValue();
+		return null;
+*/
+	}
 
-    public String toString(Buffer buffer)
-    {
-        return lookup(buffer).toString();
-    }
+	public Buffer lookup(String value)
+	{
+		Buffer b= get(value);
+		if (b == null)
+		{
+			return new CachedBuffer(value,-1);
+		}
+		return b;
+	}
+
+	public String toString(Buffer buffer)
+	{
+		return lookup(buffer).toString();
+	}
 
-    public int getOrdinal(String value)
-    {
-        CachedBuffer buffer = (CachedBuffer)_stringMap.get(value);
-        return buffer==null?-1:buffer.getOrdinal();
-    }
-    
-    public int getOrdinal(Buffer buffer)
-    {
-        if (buffer instanceof CachedBuffer)
-            return ((CachedBuffer)buffer).getOrdinal();
-        buffer=lookup(buffer);
-        if (buffer!=null && buffer instanceof CachedBuffer)
-            return ((CachedBuffer)buffer).getOrdinal();
-        return -1;
-    }
-    
-    public static class CachedBuffer extends ByteArrayBuffer.CaseInsensitive
-    {
-        private final int _ordinal;
-        private HashMap _associateMap=null;
-        
-        public CachedBuffer(String value, int ordinal)
-        {
-            super(value);
-            _ordinal= ordinal;
-        }
+	public int getOrdinal(String value)
+	{
+		CachedBuffer buffer = (CachedBuffer)_stringMap.get(value.toLowerCase());
+		return buffer==null?-1:buffer.getOrdinal();
+	}
+	
+	public int getOrdinal(Buffer buffer)
+	{
+		if (buffer instanceof CachedBuffer)
+			return ((CachedBuffer)buffer).getOrdinal();
+		buffer=lookup(buffer);
+		if (buffer!=null && buffer instanceof CachedBuffer)
+			return ((CachedBuffer)buffer).getOrdinal();
+		return -1;
+	}
+	
+	public static class CachedBuffer extends ByteArrayBuffer.CaseInsensitive
+	{
+		private final int _ordinal;
+		private HashMap _associateMap=null;
+		
+		public CachedBuffer(String value, int ordinal)
+		{
+			super(value);
+			_ordinal= ordinal;
+		}
 
-        public int getOrdinal()
-        {
-            return _ordinal;
-        }
+		public int getOrdinal()
+		{
+			return _ordinal;
+		}
 
-        public CachedBuffer getAssociate(Object key)
-        {
-            if (_associateMap==null)
-                return null;
-            return (CachedBuffer)_associateMap.get(key);
-        }
+		public CachedBuffer getAssociate(Object key)
+		{
+			if (_associateMap==null)
+				return null;
+			return (CachedBuffer)_associateMap.get(key);
+		}
 
-        // TODO Replace Associate with a mime encoding specific solution
-        public void setAssociate(Object key, CachedBuffer associate)
-        {
-            if (_associateMap==null)
-                _associateMap=new HashMap();
-            _associateMap.put(key,associate);
-        }
-    }
-    
-    
-    @Override
-    public String toString()
-    {
-        return "CACHE["+
-        	"bufferMap="+_bufferMap+
-        	",stringMap="+_stringMap+
-        	",index="+_index+
-        	"]";
-    }
+		// TODO Replace Associate with a mime encoding specific solution
+		public void setAssociate(Object key, CachedBuffer associate)
+		{
+			if (_associateMap==null)
+				_associateMap=new HashMap();
+			_associateMap.put(key,associate);
+		}
+	}
+	
+	
+	@Override
+	public String toString()
+	{
+		return "CACHE["+
+			"bufferMap="+_bufferMap+
+			",stringMap="+_stringMap+
+			",index="+_index+
+			"]";
+	}
 }
diff -r 88b70b8dab9c -r e161dca40760 src/org/eclipse/jetty/util/StringMap.java
--- a/src/org/eclipse/jetty/util/StringMap.java	Fri Sep 16 00:54:15 2016 -0600
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,695 +0,0 @@
-//
-//  ========================================================================
-//  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);
-    }
-}