maybe the files will attach as text files...
----- Original Message -----
From: "Stephen Colebourne" <[EMAIL PROTECTED]>
To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]>
Sent: Sunday, March 09, 2003 12:12 AM
Subject: Re: [collections] Faster than HashMap?
> Trying to attach the files again...
>
> ----- Original Message -----
> From: "Juozas Baliuka" <[EMAIL PROTECTED]>
> To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]>
> Sent: Saturday, March 08, 2003 7:09 PM
> Subject: Re: [collections] Faster than HashMap?
>
>
> >
> > No file is attached.
> > It will be faster on "small" maps, but method code size is limited,
65535
> > bytes or something like this and it needs some workaround.
> >
> > ----- Original Message -----
> > From: "Stephen Colebourne" <[EMAIL PROTECTED]>
> > To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]>
> > Sent: Saturday, March 08, 2003 7:43 PM
> > Subject: [collections] Faster than HashMap?
> >
> >
> > > I'd had an idea for a way to create a map thats faster to read than a
> > > HashMap...
> > >
> > > The idea was to bytecode generate the mapping from the hashcode to the
> > > index:
> > > public int lookupIndex(Object key) {
> > > switch (key.hashCode()) {
> > > case -1682: // hashcode
> > > return 2; // index of Map.Entry
> > > case 86929 // hashcode
> > > return 0; // index of Map.Entry
> > > case 1596969: // hashcode
> > > return 1; // index of Map.Entry
> > > }
> > > return -1;
> > > }
> > >
> > > Simple? No hashcode collisions. Should go faster....
> > >
> > > Attached are the java files. My initial testing was with a size 3 map,
> and
> > > that goes about 40% faster. Unfortunately, the bytecode map's
> performance
> > > degenerates with size. Depending on exact data size 50 entries or more
> may
> > > be slower, gradually getting slower.
> > >
> > > Of course now I realise that the switch statement in bytecode isn't
> > magical
> > > and is just doing a binary search, so was always going to suffer this
> > > problem. What an idiot I am.
> > >
> > > If anyone else wants to take a look and see if I've missed something,
or
> > has
> > > another bright idea triggered by this then feel free to take a look at
> the
> > > code. Otherwise, its not worth adding to [collections]. :-((((
> > >
> > > Stephen
> > >
> > >
> >
> >
>
> --------------------------------------------------------------------------
> --
> > ----
> >
> >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: [EMAIL PROTECTED]
> > > For additional commands, e-mail: [EMAIL PROTECTED]
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [EMAIL PROTECTED]
> > For additional commands, e-mail: [EMAIL PROTECTED]
> >
>
>
----------------------------------------------------------------------------
----
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
/*
* $Header:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/iterators/ResetableIterator.java,v
1.1 2003/01/15 21:49:59 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
*/
package org.apache.commons.collections;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import org.apache.bcel.Constants;
import org.apache.bcel.generic.BIPUSH;
import org.apache.bcel.generic.ClassGen;
import org.apache.bcel.generic.ConstantPoolGen;
import org.apache.bcel.generic.InstructionConstants;
import org.apache.bcel.generic.InstructionFactory;
import org.apache.bcel.generic.InstructionHandle;
import org.apache.bcel.generic.InstructionList;
import org.apache.bcel.generic.LOOKUPSWITCH;
import org.apache.bcel.generic.MethodGen;
import org.apache.bcel.generic.SIPUSH;
import org.apache.bcel.generic.Type;
/**
* <code>CodeGenMapGenerator</code> code generates the class for the map.
*
* @since Commons Collections 2.2
* @version $Revision: 1.1 $ $Date: 2003/01/15 21:49:59 $
*
* @author Stephen Colebourne
*/
public class CodeGenMapGenerator extends ClassLoader {
private static final Type[] NO_ARGS = new Type[0];
private static final Type[] ARG_TYPES = new Type[] {Type.OBJECT};
private static final String[] ARG_NAMES = new String[] {"key"};
/** Counter used to distinguish separate instances of the lookup */
private static long counter = 0;
/** Table of loaded classes (thread-safe) */
private Map classes = Collections.synchronizedMap(new HashMap());
/**
* Constructor.
* @param parent the parent class loader
*/
CodeGenMapGenerator(ClassLoader parent) {
super(parent);
}
// protected synchronized Class loadClass(String name, boolean resolve) throws
ClassNotFoundException {
// return super.loadClass(name, resolve);
// }
public static void main(String[] args) {
Map map = new CodeGenMap(null, true);
map.put("one", "onevalue");
map.put("day", "dayvalue");
map.put("this", "thisvalue");
map.put("will", "willvalue");
map.put("work", "workvalue");
map.put("well", null);
}
/**
* Create the lookup object.
*/
CodeGenMap.IndexLookup createLookup(CodeGenMap map) {
// long currentCounter = 0;
// synchronized (CodeGenHashMapGenerator.class) {
// currentCounter = counter++;
// }
String className = "org.apache.commons.collections.CodeGenMap$Lookup";// +
Long.toString(currentCounter);
ClassGen cg = new ClassGen(
className,
"org.apache.commons.collections.CodeGenMap$IndexLookup", // superclass
"<generated>", // filename
Constants.ACC_SUPER | Constants.ACC_PUBLIC | Constants.ACC_FINAL,
null
);
ConstantPoolGen cp = cg.getConstantPool();
InstructionList il = new InstructionList();
// constructor
cg.addEmptyConstructor(Constants.ACC_PUBLIC);
// lookupIndex()
MethodGen mg = new MethodGen(
Constants.ACC_PUBLIC | Constants.ACC_FINAL,
Type.INT, ARG_TYPES, ARG_NAMES,
"lookupIndex", className, il, cp
);
InstructionFactory factory = new InstructionFactory(cg);
// call key.hashCode()
il.append(InstructionConstants.ALOAD_1);
il.append(factory.createInvoke("java.lang.Object", "hashCode", Type.INT,
NO_ARGS, Constants.INVOKEVIRTUAL));
InstructionHandle switchPos = il.getEnd();
// sort entries by hashcode
int size = size = map.size();
int[] hashCodes = new int[size];
int[] indices = new int[size];
hashCodes[0] = map.mappings[0].getKey().hashCode();
indices[0] = 0;
for (int i = 1; i < size; i++) {
int loopHashCode = map.mappings[i].getKey().hashCode();
int insert = search(hashCodes, i, loopHashCode);
if (insert < (size - 1) && loopHashCode == hashCodes[insert]) {
throw new IllegalArgumentException("Duplicate hashCode");
}
if (insert < i) {
System.arraycopy(hashCodes, insert, hashCodes, insert + 1, i - insert);
System.arraycopy(indices, insert, indices, insert + 1, i - insert);
}
hashCodes[insert] = loopHashCode;
indices[insert] = i;
}
// build up bytecode
InstructionHandle[] targets = new InstructionHandle[size];
for (int i = 0; i < size; i++) {
int index = indices[i];
if (index == 0) {
targets[i] = il.append(InstructionConstants.ICONST_0);
} else if (index == 1) {
targets[i] = il.append(InstructionConstants.ICONST_1);
} else if (index == 2) {
targets[i] = il.append(InstructionConstants.ICONST_2);
} else if (index == 3) {
targets[i] = il.append(InstructionConstants.ICONST_3);
} else if (index == 4) {
targets[i] = il.append(InstructionConstants.ICONST_4);
} else if (index == 5) {
targets[i] = il.append(InstructionConstants.ICONST_5);
} else if (index < 128) {
targets[i] = il.append(new BIPUSH((byte) index));
} else if (index < 32768) {
targets[i] = il.append(new SIPUSH((short) index));
} else {
throw new IllegalArgumentException("CodeGenMap max size exceeded");
}
il.append(InstructionConstants.IRETURN);
}
InstructionHandle defaultTarget = il.append(InstructionConstants.ICONST_M1);
il.append(InstructionConstants.IRETURN);
il.append(switchPos, new LOOKUPSWITCH(hashCodes, targets, defaultTarget));
mg.setMaxStack();
cg.addMethod(mg.getMethod());
il.dispose();
// try {
// ByteArrayOutputStream out = new ByteArrayOutputStream();
// cg.getJavaClass().dump(out);
// byte[] bytes = out.toByteArray();
// for (int i = 0; i < bytes.length; i++) {
// System.out.println(Integer.toHexString(bytes[i]) + " " + bytes[i] +
" " + ((char) bytes[i]));
// }
// cg.getJavaClass().dump("D:/dev/AA.class");
// } catch (IOException ex) {
// }
Class cl = null;
try {
byte[] bytes = cg.getJavaClass().getBytes();
cl = defineClass(className, bytes, 0, bytes.length);
return (CodeGenMap.IndexLookup) cl.newInstance();
} catch (InstantiationException ex) {
throw new IllegalStateException("Instantiation error during code
generation - " + ex.getMessage());
} catch (IllegalAccessException ex) {
throw new IllegalStateException("Illegal access error during code
generation - " + ex.getMessage());
}
}
/**
* Binary search of an array with specified bounds.
* <p>
* The array must be presorted.
*
* @param array the array
* @param size the size to limit by
* @param search the search value
* @return index of the search or insertion point
*/
private int search(int[] array, int size, int search) {
int start = 0;
int end = size - 1;
while (start <= end) {
int midIndex = (start + end) >> 1;
int midVal = array[midIndex];
if (midVal < search) {
start = midIndex + 1;
} else if (midVal > search) {
end = midIndex - 1;
} else {
// exact match found
return midIndex;
}
}
// no exact match found
return start;
}
}
/*
* $Header:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/iterators/ResetableIterator.java,v
1.1 2003/01/15 21:49:59 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
*/
package org.apache.commons.collections;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Map.Entry;
import org.apache.commons.collections.iterators.ResetableIterator;
/**
* <code>CodeGenMap</code> is a Map implementation that uses bytecode generation
* at runtime to optimise the hashcode lookup.
* <p>
* It is most efficient to use another map type (such as a HashMap) to initially
* setup the map. Those values can then be copied into the CodeGenMap in one go,
* requiring only one bytecode generation.
* <p>
* The map can be made unmodifiable directly, using one of the constructors. This
* will be more efficient than using <code>Collections.unmodifiableMap()</code>.
*
* @since Commons Collections 2.2
* @version $Revision: 1.1 $ $Date: 2003/01/15 21:49:59 $
*
* @author Stephen Colebourne
*/
public class CodeGenMap implements Map, Cloneable {
/** Singleton instance of the empty lookup */
protected static final IndexLookup EMPTY_LOOKUP = new EmptyIndexLookup();
/** Serial version id */
private static final long serialVersionUID = 96239629072091L;
/** Maximum size of map is bytecode limited (a short divided by two) */
private static final int MAX_SIZE = 32768;
/**
* The array of key-values.
*/
protected MapEntryImpl[] mappings = new MapEntryImpl[8];
/**
* The size of the mappings.
*/
protected int size = 0;
/**
* Whether the map is modifiable.
*/
protected boolean modifiable = true;
/**
* The lookup hash to value object.
*/
protected transient IndexLookup lookup = EMPTY_LOOKUP;
/**
* The modifiaction counter used to implement the fail-fast behaviour.
*/
protected transient volatile int modCount;
/**
* The lazily created entry set.
*/
protected transient Set entrySet;
/**
* The lazily created key set.
*/
protected transient Set keySet;
/**
* The lazily created values collection.
*/
protected transient Collection valuesCollection;
// Constructors
// ----------------------------------------------------------------------
/**
* Constructs a new empty modifiable CodeGenMap instance.
*/
public CodeGenMap() {
this(null, true);
}
/**
* Constructs a new modifiable CodeGenMap instance, copying an existing map.
*
* @param map the map to copy, may be null (empty map created)
*/
public CodeGenMap(Map map) {
this(map, true);
}
/**
* Constructs a new CodeGenMap instance, copying an existing map.
* <p>
* The map may optionally be set to be unmodifiable.
*
* @param map the map to copy, may be null (empty map created)
* @param modifiable the modifiability of the map
*/
public CodeGenMap(Map map, boolean modifiable) {
super();
if (map != null) {
if (map.containsKey(null)) {
throw new NullPointerException("Map must not contain a null Key");
}
putAll(map);
}
this.modifiable = modifiable;
}
// Map access
// ----------------------------------------------------------------------
/**
* Gets the value to which the specified key is mapped.
* <p>
* Returns <code>null</code> if the map contains no mapping for this key,
* or if there is a mapping with a value of <code>null</code>. Use the
* <code>containsKey()</code> method to separate these cases.
*
* @param key the key whose value is to be returned
* @return the value mapped to that key, or null
*/
public Object get(Object key) {
// if (key != null) {
// MapIterator it = mapIterator();
// while (it.hasNext()) {
// Object loopKey = (Object) it.next();
// if (key == loopKey || key.equals(loopKey)) {
// return it.getValue();
// }
// }
// }
// return null;
try {
if (key != null) {
MapEntryImpl e = mappings[lookup.lookupIndex(key)];
if (key == e.key || key.equals(e.key)) {
return e.value;
}
}
return null;
} catch (ArrayIndexOutOfBoundsException ex) {
// from key not found
return null;
}
}
/**
* Gets the number of key-value mappings in this map.
*
* @return the current size of the map
*/
public int size() {
return size;
}
/**
* Returns <code>true</code> if this map contains no mappings.
*
* @return is the map currently empty
*/
public boolean isEmpty() {
return (size == 0);
}
/**
* Returns <code>true</code> if this map contains a mapping for the
* specified key. <code>null</code> may be passed into this method
* and will always return false.
*
* @param key the key to be searched for
* @return true if the map contains the key
*/
public boolean containsKey(Object key) {
if (key != null) {
return (lookupEntry(key) != null);
}
return false;
}
/**
* Returns <code>true</code> if this map contains one or more keys
* mapping to the specified value.
*
* @param value the value to be searched for
* @return true if the map contains the value
*/
public boolean containsValue(Object value) {
if (value == null) {
for (int i = 0; i < size; i++) {
if (mappings[i].value == null) {
return true;
}
}
} else {
for (int i = 0; i < size; i++) {
if (value.equals(mappings[i].value)) {
return true;
}
}
}
return false;
}
// Map modification
// ----------------------------------------------------------------------
/**
* Associates the specified value with the specified key in this map.
* <p>
* If the map previously contained a mapping for this key, the old
* value is replaced <i>in position</i> and returned. In all other cases,
* the new key and value are appended to the <i>end</i> of the map.
*
* @param key the key with which the value is to be associated
* @param value the value to be associated with this key
* @return the value previously mapped to the key, or null
* @throws NullPointerException if the key is <code>null</code>
* @throws UnsupportedOperationException if the map is not modifiable
*/
public Object put(Object key, Object value) {
if (modifiable == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
if (key == null) {
throw new NullPointerException("Key must not be null");
}
// do the put
Object previous = null;
MapEntryImpl entry = lookupEntry(key);
if (entry == null) {
// key not previously there, so append
ensureCapacity(size + 1);
mappings[size++] = new MapEntryImpl(this, key, value);
modCount++;
rehash();
} else {
// overwrite previous value
previous = entry.value;
entry.key = key;
entry.value = value;
}
return previous;
}
/**
* Copies all of the mappings from the specified map to this one.
* <p>
* If the map previously contained a mapping for a key, the old
* value is replaced <i>in position</i>. In all other cases, the
* new key and value are appended to the <i>end</i> of the map.
*
* @param in the map whose mappings are to be copied
* @throws NullPointerException if the map is <code>null</code>
* @throws NullPointerException if the map contains a <code>null</code> key
* @throws UnsupportedOperationException if the map is not modifiable
*/
public void putAll(Map map) {
if (modifiable == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
if (map == null) {
throw new NullPointerException("Map must not be null");
}
if (map.size() == 0) {
return;
}
if (map.containsKey(null)) {
throw new NullPointerException("Map must not contain a null Key");
}
ensureCapacity(size + map.size());
// loop to copy data
int index = 0;
for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry) it.next();
MapEntryImpl ourEntry = lookupEntry(entry.getKey());
if (ourEntry == null) {
// key not previously there, so append
mappings[size++] = new MapEntryImpl(this, entry.getKey(),
entry.getValue());
modCount++;
} else {
// overwrite previous value
ourEntry.key = entry.getKey();
ourEntry.value = entry.getValue();
}
}
rehash();
}
/**
* Removes any mapping for this key, and return any previously mapped value.
* An attempt to remove a <code>null</code> key will have no effect.
*
* @param key the key whose mapping is to be removed
* @return the value removed, or null
* @throws UnsupportedOperationException if the map is not modifiable
*/
public Object remove(Object key) {
if (modifiable == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
if (key == null) {
return null;
}
Object previous = null;
MapEntryImpl entry = lookupEntry(key);
if (entry == null) {
return null; // nothing to remove
}
previous = entry.value;
int index = lookup.lookupIndex(key);
if (index < (size - 1)) {
System.arraycopy(mappings, index + 1, mappings, index, size - index - 1);
}
size--;
modCount++;
mappings[size] = null;
rehash();
return previous;
}
/**
* Removes all mappings from this map.
*
* @throws UnsupportedOperationException if the map is not modifiable
*/
public void clear() {
if (modifiable == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
modCount++;
mappings = new MapEntryImpl[0];
size = 0;
rehash();
}
/**
* Is this map modifiable?
*
* @return true if modifiable
*/
public boolean isModifiable() {
return modifiable;
}
// // Map iterator view
// // ----------------------------------------------------------------------
// /**
// * Gets a MapIterator used for fast access to the keys and values
// * in a Map.
// * <p>
// * This iterator will be more efficient than using
// * <code>entrySet().iterator()</code>.
// *
// * @return a MapIterator instance
// */
// public MapIterator mapIterator() {
// return new MapIteratorImpl(this);
// }
//
// /**
// * Map iterator implementation.
// */
// protected static class MapIteratorImpl extends IteratorImpl implements
MapIterator {
// /**
// * Constructor
// */
// protected MapIteratorImpl(CodeGenMap map) {
// super(map);
// }
// /**
// * Gets the next entry
// */
// protected Object nextEntry() {
// return map.lookupEntry(index).getKey();
// }
// /**
// * @see org.apache.commons.collections.MapIterator#getKey()
// */
// public Object getKey() {
// if (index == -1) {
// throw new IllegalStateException("next() must be called before
getKey()");
// }
// return map.lookupEntry(index).getKey();
// }
// /**
// * @see org.apache.commons.collections.MapIterator#getValue()
// */
// public Object getValue() {
// if (index == -1) {
// throw new IllegalStateException("next() must be called before
getValue()");
// }
// return map.lookupEntry(index).getValue();
// }
// /**
// * @see org.apache.commons.collections.MapIterator#setValue()
// */
// public void setValue(Object value) {
// if (map.isModifiable() == false) {
// throw new UnsupportedOperationException("The map cannot be
modified");
// }
// if (index == -1) {
// throw new IllegalStateException("next() must be called before
setValue()");
// }
// map.lookupEntry(index).setValue(value);
// }
// /**
// * @see org.apache.commons.collections.MapIterator#getMapEntry()
// */
// public Entry getMapEntry() {
// if (index == -1) {
// throw new IllegalStateException("next() must be called before
getMapEntry()");
// }
// return map.lookupEntry(index);
// }
// }
// Entry set view
// ----------------------------------------------------------------------
/**
* Gets a set of the entries in the Map. Each element in the returned
* collection is a <code>Map.Entry</code>.
* <p>
* Where possible use [EMAIL PROTECTED] #mapIterator()} as this is
* more efficient than using <code>entrySet().iterator()</code>.
* <p>
* The iterator does not support <code>add</code> or <code>addAll</code>.
*
* @return Set of the map keys
*/
public Set entrySet() {
if (entrySet == null) {
entrySet = new EntrySetImpl(this);
}
return entrySet;
}
/**
* Entry set implementation.
*/
protected static class EntrySetImpl extends AbstractSet {
protected final CodeGenMap map;
/**
* Constructor.
* @param map the owning map
*/
protected EntrySetImpl(CodeGenMap map) {
super();
this.map = map;
}
/**
* @see java.util.Collection#size()
*/
public int size() {
return map.size();
}
/**
* @see java.util.Collection#iterator()
*/
public Iterator iterator() {
return new EntrySetIteratorImpl(map);
}
/**
* @see java.util.Collection#remove(java.lang.Object)
*/
public boolean remove(Object entry) {
if (entry instanceof Map.Entry == false) {
return false;
}
Object key = ((Map.Entry) entry).getKey();
if (map.containsKey(key) == false) {
return false;
}
map.remove(key);
return true;
}
/**
* @see java.util.Collection#clear()
*/
public void clear() {
map.clear();
}
/**
* @see java.lang.Object#toString()
*/
public String toString() {
return "EntrySetImpl[size=" + size() + "]";
}
}
/**
* EntrySet iterator implementation.
*/
protected static class EntrySetIteratorImpl extends IteratorImpl {
/**
* Constructor.
*/
protected EntrySetIteratorImpl(CodeGenMap map) {
super(map);
}
/**
* Gets the next entry
*/
protected Object nextEntry() {
return map.lookupEntry(index);
}
}
// Key set view
// ----------------------------------------------------------------------
/**
* Gets a set of the keys in the Map.
* <p>
* Where possible use [EMAIL PROTECTED] #mapIterator()} as this is
* more efficient than using a key set.
* <p>
* The iterator does not support <code>add</code> or <code>addAll</code>.
*
* @return Set of the map keys
*/
public Set keySet() {
if (keySet == null) {
keySet = new KeySetImpl(this);
}
return keySet;
}
/**
* Key set implementation.
*/
protected static class KeySetImpl extends AbstractSet {
protected final CodeGenMap map;
/**
* Constructor.
* @param map the owning map
*/
protected KeySetImpl(CodeGenMap map) {
super();
this.map = map;
}
/**
* @see java.util.Collection#size()
*/
public int size() {
return map.size();
}
/**
* @see java.util.Collection#iterator()
*/
public Iterator iterator() {
return new KeySetIteratorImpl(map);
}
/**
* @see java.util.Collection#remove(java.lang.Object)
*/
public boolean remove(Object key) {
if (map.containsKey(key) == false) {
return false;
}
map.remove(key);
return true;
}
/**
* @see java.util.Collection#clear()
*/
public void clear() {
map.clear();
}
/**
* @see java.lang.Object#toString()
*/
public String toString() {
return "KeySetImpl[size=" + size() + "]";
}
}
/**
* KeySet iterator implementation.
*/
protected static class KeySetIteratorImpl extends IteratorImpl {
/**
* Constructor.
*/
protected KeySetIteratorImpl(CodeGenMap map) {
super(map);
}
/**
* Gets the next entry
*/
protected Object nextEntry() {
return map.lookupEntry(index).getKey();
}
}
// Value collection view
// ----------------------------------------------------------------------
/**
* Gets a collection of the values in the Map.
* <p>
* The iterator does not support <code>add</code> or <code>addAll</code>.
*
* @return Collection of the map values
*/
public Collection values() {
if (valuesCollection == null) {
valuesCollection = new ValuesImpl(this);
}
return valuesCollection;
}
/**
* Values collection implementation.
*/
protected static class ValuesImpl extends AbstractCollection {
protected final CodeGenMap map;
/**
* Constructor.
* @param map the owning map
*/
protected ValuesImpl(CodeGenMap map) {
super();
this.map = map;
}
/**
* @see java.util.Collection#size()
*/
public int size() {
return map.size();
}
/**
* @see java.util.Collection#iterator()
*/
public Iterator iterator() {
return new ValuesIteratorImpl(map);
}
// delegate remove to AbstractCollection, which will iterate correctly
/**
* @see java.util.Collection#clear()
*/
public void clear() {
map.clear();
}
/**
* @see java.lang.Object#toString()
*/
public String toString() {
return "ValuesImpl[size=" + size() + "]";
}
}
/**
* Values iterator implementation.
*/
protected static class ValuesIteratorImpl extends IteratorImpl {
/**
* Constructor.
*/
protected ValuesIteratorImpl(CodeGenMap map) {
super(map);
}
/**
* Gets the next entry
*/
protected Object nextEntry() {
return map.lookupEntry(index).getValue();
}
}
// Implementation
// ----------------------------------------------------------------------
/**
* Lookup a key to an entry.
*
* @param key the key of the object to lookup
* @return the entry
*/
protected MapEntryImpl lookupEntry(Object key) {
// if (key != null) {
// MapIterator it = mapIterator();
// while (it.hasNext()) {
// Object loopKey = (Object) it.next();
// if (key == loopKey || key.equals(loopKey)) {
// return (MapEntryImpl) it.getMapEntry();
// }
// }
// }
// return null;
if (key != null) {
int index = lookup.lookupIndex(key);
if (index != -1) {
MapEntryImpl e = mappings[index];
if (key == e.key || key.equals(e.key)) {
return e;
}
}
}
return null;
}
/**
* Gets the entry for a specified index.
*
* @param index the index
* @return the entry
*/
protected MapEntryImpl lookupEntry(int index) {
return mappings[index];
}
/**
* Create the code generated hash object.
*/
protected void rehash() {
if (size == 0) {
lookup = EMPTY_LOOKUP;
} else if (size == 1) {
lookup = new SingletonIndexLookup(mappings[0].key);
} else {
lookup = new
CodeGenMapGenerator(getClass().getClassLoader()).createLookup(this);
}
}
/**
* Increase the size of the backing storage array as required.
*
* @param requiredSize the required size to increase to
*/
protected void ensureCapacity(int requiredSize) {
if (mappings == null) {
mappings = new MapEntryImpl[requiredSize];
} else {
if (requiredSize < 0) {
throw new IllegalStateException("Unable to increase capacity to
required size");
}
if (requiredSize >= MAX_SIZE) {
throw new IllegalStateException("Unable to increase capacity to
required size");
}
if (mappings.length < requiredSize) {
Object[] oldMappings = mappings;
int newMappingsSize = ((mappings.length * 3) / 2) + 1;
if (newMappingsSize >= MAX_SIZE) {
newMappingsSize = MAX_SIZE;
} else if (newMappingsSize < 8) {
newMappingsSize = 8;
}
if (newMappingsSize < requiredSize) {
newMappingsSize = requiredSize;
}
mappings = new MapEntryImpl[newMappingsSize];
System.arraycopy(oldMappings, 0, mappings, 0, size);
}
}
}
// Basic object methods
// ----------------------------------------------------------------------
/**
* Compare the specified object with this list for equality. This
* implementation uses exactly the code that is used to define the
* map equals function in the documentation for the
* <code>Map.equals</code> method.
* <p>
* Note in particular that the order of the entries is unimportant
* for this comparison.
*
* @param other the object to be compared to this map
* @return true if the two maps are equal
*/
public boolean equals(Object other) {
if (other == this) {
return true;
}
if (other instanceof Map == false) {
return false;
}
Map otherMap = (Map) other;
if (otherMap.size() != size()) {
return false;
}
// check keys and values
for (int i = 0; i < size; i++) {
MapEntryImpl entry = (MapEntryImpl) mappings[i];
if (entry.value == null) {
if ((otherMap.get(entry.key) == null &&
otherMap.containsKey(entry.key)) == false) {
return false;
}
} else {
if (entry.value.equals(otherMap.get(entry.key)) == false) {
return false;
}
}
}
return true;
}
/**
* Return the hash code value for this map. This implementation uses
* exactly the code that is used to define the list hash function in the
* documentation for the <code>Map.hashCode</code> method.
*
* @return suitable integer hashcode
*/
public int hashCode() {
int total = 0;
for (int i = 0; i < size; i++) {
MapEntryImpl entry = (MapEntryImpl) mappings[i];
total += ((entry.key == null ? 0 : entry.key.hashCode()) ^
(entry.value == null ? 0 : entry.value.hashCode()));
}
return total;
}
/**
* Return a shallow copy of this map.
* The keys and values themselves are not copied.
*
* @return a clone of this map
*/
public Object clone() {
try {
CodeGenMap cloned = (CodeGenMap) super.clone();
cloned.modCount = 0;
cloned.mappings = new MapEntryImpl[size];
for (int i = 0; i < size; i++) {
cloned.mappings[i] = new MapEntryImpl(cloned, mappings[i].key,
mappings[i].value);
}
cloned.rehash();
return cloned;
} catch (CloneNotSupportedException ex) {
throw new InternalError();
}
}
/**
* Gets a String version of the map, using the same format as
* [EMAIL PROTECTED] java.util.AbstractMap#toString()}.
*
* @return string version of the map
*/
public String toString() {
if (size == 0) {
return "{}";
}
StringBuffer buf = new StringBuffer(32 * size);
buf.append('{');
for (int i = 0; i < size; i++) {
buf.append(mappings[i].key == this ? "(this Map)" : mappings[i].key);
buf.append('=');
buf.append(mappings[i].value == this ? "(this Map)" : mappings[i].value);
buf.append(", ");
}
buf.setLength(buf.length() - 2);
buf.append('}');
return buf.toString();
}
/**
* Writes this object during serialization.
*
* @serialData the modifiable flag, the map size, the map data as an Object array
*/
protected void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeBoolean(modifiable);
out.writeInt(size);
for (int i = 0, isize = size; i < isize; i++) {
out.writeObject(mappings[i].key);
out.writeObject(mappings[i].value);
}
}
/**
* Reads the object from a stream during deserialization.
*/
protected void readObject(ObjectInputStream in) throws IOException,
ClassNotFoundException {
in.defaultReadObject();
modifiable = in.readBoolean();
size = in.readInt();
mappings = new MapEntryImpl[size];
for (int i = 0, isize = size; i < isize; i++) {
mappings[i] = new MapEntryImpl(this, in.readObject(), in.readObject());
}
rehash();
}
// Map entry
//-----------------------------------------------------------------------
/**
* Map entry implementation.
*/
protected static class MapEntryImpl implements Map.Entry {
private final CodeGenMap map;
Object key;
Object value;
/**
* Constructor.
* @param map the owning map
* @param key the key
* @param value the value
*/
protected MapEntryImpl(CodeGenMap map, Object key, Object value) {
super();
this.map = map;
this.key = key;
this.value = value;
}
/**
* Gets the key part of the map entry.
* @return the key
*/
public Object getKey() {
return key;
}
/**
* Gets the value part of the map entry.
* @return the value
*/
public Object getValue() {
return value;
}
/**
* Sets the value of the map entry
* @param value the value to set the entry to
* @return the old value of the map entry
* @throws UnsupportedOperationException if the map is unmodifiable
*/
public Object setValue(Object value) {
if (map.isModifiable() == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
Object previous = value;
this.value = value;
return previous;
}
/**
* Compares this map entry to another.
* @param other the other object
* @return true if the entries are equal (key and value)
*/
public boolean equals(Object other) {
if(other == this) {
return true;
}
if (other instanceof Map.Entry == false) {
return false;
}
Map.Entry otherEntry = (Map.Entry) other;
return (
(getKey() == null ? otherEntry.getKey() == null :
getKey().equals(otherEntry.getKey())) &&
(getValue() == null ? otherEntry.getValue() == null :
getValue().equals(otherEntry.getValue()))
);
}
/**
* Returns a suitable hash code.
* @return a hash code
*/
public int hashCode() {
return ((getKey() == null ? 0 : getKey().hashCode()) ^
(getValue() == null ? 0 : getValue().hashCode())
);
}
/**
* Returns a debugging string.
* @return debugging string
*/
public String toString() {
return "MapEntryImpl[key=" + key + ",value=" + value + "]";
}
}
// Superclass for iterators
//-----------------------------------------------------------------------
/**
* Iterator implementation.
*/
protected static abstract class IteratorImpl implements ResetableIterator {
protected final CodeGenMap map;
protected int endIndex;
protected int index;
protected boolean removeAllowed = false;
protected int expectedModCount;
/**
* Constructor.
* @param map the owning map
*/
protected IteratorImpl(CodeGenMap map) {
super();
this.map = map;
this.endIndex = map.size() - 1;
this.index = -1;
this.expectedModCount = map.modCount;
}
/**
* Does the iterator have another entry.
* @return true if there is another entry
*/
public boolean hasNext() {
return (index < endIndex);
}
/**
* @see java.util.Iterator#next()
*/
public final Object next() {
if (hasNext() == false) {
throw new NoSuchElementException("No more elements in iteration");
}
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException("A change has been made to
the map during iteration");
}
index++;
removeAllowed = true;
return nextEntry();
}
/**
* Gets the next entry.
*
* @return the next iterator entry
*/
protected abstract Object nextEntry();
/**
* Removes the last returned entry.
* @throws UnsupportedOperationException if the map is unmodifiable
*/
public void remove() {
if (map.isModifiable() == false) {
throw new UnsupportedOperationException("The map cannot be modified");
}
if (removeAllowed == false) {
throw new IllegalStateException("next() must be called before each
call to remove()");
}
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException("A change has been made to
the map during iteration");
}
map.remove(map.lookupEntry(index).key);
removeAllowed = false;
index--;
endIndex--;
expectedModCount = map.modCount;
}
/**
* Reset the iterator back to the start.
*/
public void reset() {
index = -1;
}
/**
* Returns a debugging string.
* @return debugging string
*/
public String toString() {
return "IteratorImpl[index=" + index + "]";
}
}
// Abstract class defining the lookup
//-----------------------------------------------------------------------
/**
* The lookup abstract class.
* <p>
* An abstract class is used as a virtual method call is faster than an
* interface method call at the bytecode level.
*/
public static abstract class IndexLookup {
/**
* Lookup a hashCode to an index.
*
* @param key the key of the object to lookup
* @return the index into the mappings array for the <b>value</b>
*/
public abstract int lookupIndex(Object key);
}
/**
* Index lookup used when the map is empty.
*/
static final class EmptyIndexLookup extends IndexLookup {
public final int lookupIndex(Object key) {
return -1;
}
}
/**
* Index lookup used when the map is size one.
*/
static final class SingletonIndexLookup extends IndexLookup {
private final Object key;
private final int keyHashCode;
SingletonIndexLookup(Object singletonKey) {
super();
key = singletonKey;
keyHashCode = key.hashCode();
}
public final int lookupIndex(Object key) {
if (key.hashCode() == keyHashCode) {
return 0;
}
return -1;
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
