You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2003/12/07 02:23:54 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/map TestLRUMap.java TestAll.java
scolebourne 2003/12/06 17:23:54
Modified: collections/data/test
IdentityMap.fullCollection.version3.obj
HashedMap.emptyCollection.version3.obj
HashedMap.fullCollection.version3.obj
LinkedMap.fullCollection.version3.obj
IdentityMap.emptyCollection.version3.obj
LinkedMap.emptyCollection.version3.obj
collections/src/java/org/apache/commons/collections/map
HashedMap.java LinkedMap.java
collections/src/test/org/apache/commons/collections/map
TestAll.java
Added: collections/data/test LRUMap.fullCollection.version3.obj
LRUMap.emptyCollection.version3.obj
collections/src/java/org/apache/commons/collections/map
LRUMap.java
collections/src/test/org/apache/commons/collections/map
TestLRUMap.java
Log:
Add LRUMap implementation
Refactor serialization behaviour in HashedMap hierarchy
Revision Changes Path
1.2 +1 -2 jakarta-commons/collections/data/test/IdentityMap.fullCollection.version3.obj
<<Binary file>>
1.2 +1 -2 jakarta-commons/collections/data/test/HashedMap.emptyCollection.version3.obj
<<Binary file>>
1.2 +1 -2 jakarta-commons/collections/data/test/HashedMap.fullCollection.version3.obj
<<Binary file>>
1.2 +1 -2 jakarta-commons/collections/data/test/LinkedMap.fullCollection.version3.obj
<<Binary file>>
1.2 +1 -2 jakarta-commons/collections/data/test/IdentityMap.emptyCollection.version3.obj
<<Binary file>>
1.2 +1 -2 jakarta-commons/collections/data/test/LinkedMap.emptyCollection.version3.obj
<<Binary file>>
1.1 jakarta-commons/collections/data/test/LRUMap.fullCollection.version3.obj
<<Binary file>>
1.1 jakarta-commons/collections/data/test/LRUMap.emptyCollection.version3.obj
<<Binary file>>
1.8 +206 -51 jakarta-commons/collections/src/java/org/apache/commons/collections/map/HashedMap.java
Index: HashedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/HashedMap.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- HashedMap.java 6 Dec 2003 14:02:11 -0000 1.7
+++ HashedMap.java 7 Dec 2003 01:23:54 -0000 1.8
@@ -113,7 +113,7 @@
protected static final Object NULL = new Object();
/** Load factor, normally 0.75 */
- protected final float loadFactor;
+ protected transient float loadFactor;
/** The size of the map */
protected transient int size;
/** Map entries */
@@ -157,14 +157,14 @@
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is less than one
- * @throws IllegalArgumentException if the load factor is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
*/
public HashedMap(int initialCapacity, float loadFactor) {
super();
if (initialCapacity < 1) {
throw new IllegalArgumentException("Initial capacity must be greater than 0");
}
- if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
+ if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor must be greater than 0");
}
this.loadFactor = loadFactor;
@@ -296,14 +296,13 @@
while (entry != null) {
if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
Object oldValue = entry.getValue();
- entry.setValue(value);
+ updateEntry(entry, value);
return oldValue;
}
entry = entry.next;
}
- modCount++;
- add(hashCode, index, key, value);
+ addMapping(index, hashCode, key, value);
return null;
}
@@ -335,18 +334,13 @@
key = convertKey(key);
int hashCode = hash(key);
int index = hashIndex(hashCode, data.length);
- HashEntry entry = data[index];
+ HashEntry entry = data[index];
HashEntry previous = null;
while (entry != null) {
if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
- modCount++;
- if (previous == null) {
- data[index] = entry.next;
- } else {
- previous.next = entry.next;
- }
- size--;
- return destroyEntry(entry);
+ Object oldValue = entry.getValue();
+ removeMapping(entry, index, previous);
+ return oldValue;
}
previous = entry;
entry = entry.next;
@@ -369,25 +363,6 @@
//-----------------------------------------------------------------------
/**
- * Gets the entry mapped to the key specified.
- *
- * @param key the key
- * @return the entry, null if no match
- */
- protected HashEntry getEntry(Object key) {
- key = convertKey(key);
- int hashCode = hash(key);
- HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
- while (entry != null) {
- if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
- return entry;
- }
- entry = entry.next;
- }
- return null;
- }
-
- /**
* Converts input keys to another object for storage in the map.
* This implementation masks nulls.
* Subclasses can override this to perform alternate key conversions.
@@ -459,9 +434,91 @@
return hashCode & (dataSize - 1);
}
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the entry mapped to the key specified.
+ * <p>
+ * This method exists for subclasses that may need to perform a multi-step
+ * process accessing the entry. The public methods in this class don't use this
+ * method to gain a small performance boost.
+ *
+ * @param key the key
+ * @return the entry, null if no match
+ */
+ protected HashEntry getEntry(Object key) {
+ key = convertKey(key);
+ int hashCode = hash(key);
+ HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
+ while (entry != null) {
+ if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
+ return entry;
+ }
+ entry = entry.next;
+ }
+ return null;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Updates an existing key-value mapping to change the value.
+ * <p>
+ * This implementation calls <code>setValue()</code> on the entry.
+ * Subclasses could override to handle changes to the map.
+ *
+ * @param entry the entry to update
+ * @param newValue the new value to store
+ * @return value the previous value
+ */
+ protected void updateEntry(HashEntry entry, Object newValue) {
+ entry.setValue(newValue);
+ }
+
+ /**
+ * Reuses an existing key-value mapping, storing completely new data.
+ * <p>
+ * This implementation sets all the data fields on the entry.
+ * Subclasses could populate additional entry fields.
+ *
+ * @param entry the entry to update, not null
+ * @param hashIndex the index in the data array
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ */
+ protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) {
+ entry.next = data[hashIndex];
+ entry.hashCode = hashCode;
+ entry.key = key;
+ entry.value = value;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Adds a new key-value mapping into this map.
+ * <p>
+ * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
+ * and <code>checkCapacity</code>.
+ * It also handles changes to <code>modCount</code> and <code>size</code>.
+ * Subclasses could override to fully control adds to the map.
+ *
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ * @return the value previously mapped to this key, null if none
+ */
+ protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
+ modCount++;
+ HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
+ addEntry(entry, hashIndex);
+ size++;
+ checkCapacity();
+ }
+
/**
- * Creates an entry to store the data.
- * This implementation creates a HashEntry instance.
+ * Creates an entry to store the key-value data.
+ * <p>
+ * This implementation creates a new HashEntry instance.
* Subclasses can override this to return a different storage class,
* or implement caching.
*
@@ -476,29 +533,81 @@
}
/**
+ * Adds an entry into this map.
+ * <p>
+ * This implementation adds the entry to the data storage table.
+ * Subclasses could override to handle changes to the map.
+ *
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ * @return the value previously mapped to this key, null if none
+ */
+ protected void addEntry(HashEntry entry, int hashIndex) {
+ data[hashIndex] = entry;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Removes a mapping from the map.
+ * <p>
+ * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
+ * It also handles changes to <code>modCount</code> and <code>size</code>.
+ * Subclasses could override to fully control removals from the map.
+ *
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
+ */
+ protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
+ modCount++;
+ removeEntry(entry, hashIndex, previous);
+ size--;
+ destroyEntry(entry);
+ }
+
+ /**
+ * Removes an entry from the chain stored in a particular index.
+ * <p>
+ * This implementation removes the entry from the data storage table.
+ * The size is not updated.
+ * Subclasses could override to handle changes to the map.
+ *
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
+ */
+ protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
+ if (previous == null) {
+ data[hashIndex] = entry.next;
+ } else {
+ previous.next = entry.next;
+ }
+ }
+
+ /**
* Kills an entry ready for the garbage collector.
+ * <p>
* This implementation prepares the HashEntry for garbage collection.
* Subclasses can override this to implement caching (override clear as well).
*
* @param entry the entry to destroy
- * @return the value from the entry
*/
- protected Object destroyEntry(HashEntry entry) {
+ protected void destroyEntry(HashEntry entry) {
entry.next = null;
- return entry.value;
+ entry.key = null;
+ entry.value = null;
}
+ //-----------------------------------------------------------------------
/**
- * Adds a new key-value mapping into this map.
- * Subclasses could override to fix the size of the map.
- *
- * @param key the key to add
- * @param value the value to add
- * @return the value previously mapped to this key, null if none
+ * Checks the capacity of the map and enlarges it if necessary.
+ * <p>
+ * This implementation uses the threshold to check if the map needs enlarging
*/
- protected void add(int hashCode, int hashIndex, Object key, Object value) {
- data[hashIndex] = createEntry(data[hashIndex], hashCode, key, value);
- if (size++ >= threshold) {
+ protected void checkCapacity() {
+ if (size >= threshold) {
ensureCapacity(data.length * 2);
}
}
@@ -874,17 +983,21 @@
this.key = key;
this.value = value;
}
+
public Object getKey() {
return (key == NULL ? null : key);
}
+
public Object getValue() {
return value;
}
+
public Object setValue(Object value) {
Object old = this.value;
this.value = value;
return old;
}
+
public boolean equals(Object obj) {
if (obj == this) {
return true;
@@ -897,10 +1010,12 @@
(getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
(getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
}
+
public int hashCode() {
return (getKey() == null ? 0 : getKey().hashCode()) ^
(getValue() == null ? 0 : getValue().hashCode());
}
+
public String toString() {
return new StringBuffer().append(getKey()).append('=').append(getValue()).toString();
}
@@ -981,12 +1096,48 @@
//-----------------------------------------------------------------------
/**
+ * Write the data of subclasses.
+ * <p>
+ * Serialization is not one of the JDK's nicest topics. Normal serialization will
+ * not load subclass fields until this object is setup. In other words the readObject
+ * on this class is performed before that on the subclass. Unfortunately, data setup in
+ * the subclass may affect the ability of methods such as put() to work properly.
+ * <p>
+ * The solution adopted here is to have a method called by this class as part of the
+ * serialization and deserialization process. Override this method if the subclass
+ * stores additional data needed for put() to work.
+ * A sub-subclass must call super.doWriteObject().
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ // do nothing
+ }
+
+ /**
+ * Read the data of subclasses.
+ * <p>
+ * Serialization is not one of the JDK's nicest topics. Normal serialization will
+ * not load subclass fields until this object is setup. In other words the readObject
+ * on this class is performed before that on the subclass. Unfortunately, data setup in
+ * the subclass may affect the ability of methods such as put() to work properly.
+ * <p>
+ * The solution adopted here is to have a method called by this class as part of the
+ * serialization and deserialization process. Override this method if the subclass
+ * stores additional data needed for put() to work.
+ * A sub-subclass must call super.doReadObject().
+ */
+ protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ // do nothing
+ }
+
+ /**
* Write the map out using a custom routine.
*/
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
+ out.writeFloat(loadFactor);
out.writeInt(data.length);
out.writeInt(size);
+ doWriteObject(out);
for (MapIterator it = mapIterator(); it.hasNext();) {
out.writeObject(it.next());
out.writeObject(it.getValue());
@@ -998,16 +1149,20 @@
*/
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
+ loadFactor = in.readFloat();
int capacity = in.readInt();
int size = in.readInt();
- data = new HashEntry[capacity];
+ doReadObject(in);
init();
+ data = new HashEntry[capacity];
for (int i = 0; i < size; i++) {
Object key = in.readObject();
Object value = in.readObject();
put(key, value);
}
+ threshold = calculateThreshold(data.length, loadFactor);
}
+
//-----------------------------------------------------------------------
/**
* Clones the map without cloning the keys or values.
1.3 +65 -46 jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java
Index: LinkedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- LinkedMap.java 6 Dec 2003 14:02:11 -0000 1.2
+++ LinkedMap.java 7 Dec 2003 01:23:54 -0000 1.3
@@ -71,7 +71,8 @@
/**
* A <code>Map</code> implementation that maintains the order of the entries.
- * The order maintained is by insertion.
+ * In this implementation order is maintained is by original insertion, but
+ * subclasses may work differently.
* <p>
* This implementation improves on the JDK1.4 LinkedHashMap by adding the
* {@link org.apache.commons.collections.iterators.MapIterator MapIterator}
@@ -84,6 +85,9 @@
* <p>
* All the available iterators can be reset back to the start by casting to
* <code>ResettableIterator</code> and calling <code>reset()</code>.
+ * <p>
+ * The implementation is also designed to be subclassed, with lots of useful
+ * methods exposed.
*
* @since Commons Collections 3.0
* @version $Revision$ $Date$
@@ -97,7 +101,7 @@
static final long serialVersionUID = -1954063410665686469L;
/** Header in the linked list */
- private transient LinkedEntry header;
+ protected transient LinkEntry header;
/**
* Constructs a new empty map with default size and load factor.
@@ -123,7 +127,7 @@
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is less than one
- * @throws IllegalArgumentException if the load factor is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
*/
public LinkedMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
@@ -143,7 +147,7 @@
* Initialise this subclass during construction.
*/
protected void init() {
- header = new LinkedEntry(null, -1, null, null);
+ header = new LinkEntry(null, -1, null, null);
header.before = header.after = header;
}
@@ -157,13 +161,13 @@
public boolean containsValue(Object value) {
// override uses faster iterator
if (value == null) {
- for (LinkedEntry entry = header.after; entry != header; entry = entry.after) {
+ for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
if (entry.getValue() == null) {
return true;
}
}
} else {
- for (LinkedEntry entry = header.after; entry != header; entry = entry.after) {
+ for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
if (isEqualValue(value, entry.getValue())) {
return true;
}
@@ -214,7 +218,7 @@
* @return the next key
*/
public Object nextKey(Object key) {
- LinkedEntry entry = (LinkedEntry) getEntry(key);
+ LinkEntry entry = (LinkEntry) getEntry(key);
return (entry == null || entry.after == header ? null : entry.after.getKey());
}
@@ -225,14 +229,33 @@
* @return the previous key
*/
public Object previousKey(Object key) {
- LinkedEntry entry = (LinkedEntry) getEntry(key);
+ LinkEntry entry = (LinkEntry) getEntry(key);
return (entry == null || entry.before == header ? null : entry.before.getKey());
}
//-----------------------------------------------------------------------
/**
+ * Adds an entry into this map, maintaining insertion order.
+ * <p>
+ * This implementation adds the entry to the data storage table and
+ * to the end of the linked list.
+ *
+ * @param entry the entry to add
+ * @param hashIndex the index into the data array to store at
+ */
+ protected void addEntry(HashEntry entry, int hashIndex) {
+ LinkEntry link = (LinkEntry) entry;
+ link.after = header;
+ link.before = header.before;
+ header.before.after = link;
+ header.before = link;
+ data[hashIndex] = entry;
+ }
+
+ /**
* Creates an entry to store the data.
- * This implementation creates a LinkEntry instance in the linked list.
+ * <p>
+ * This implementation creates a new LinkEntry instance.
*
* @param next the next entry in sequence
* @param hashCode the hash code to use
@@ -241,30 +264,26 @@
* @return the newly created entry
*/
protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
- LinkedEntry entry = new LinkedEntry(next, hashCode, key, value);
- entry.after = header;
- entry.before = header.before;
- header.before.after = entry;
- header.before = entry;
- return entry;
+ return new LinkEntry(next, hashCode, key, value);
}
/**
- * Kills an entry ready for the garbage collector.
- * This implementation manages the linked list and prepares the
- * LinkEntry for garbage collection.
+ * Removes an entry from the map and the linked list.
+ * <p>
+ * This implementation removes the entry from the linked list chain, then
+ * calls the superclass implementation.
*
- * @param entry the entry to destroy
- * @return the value from the entry
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
*/
- protected Object destroyEntry(HashEntry entry) {
- LinkedEntry link = (LinkedEntry) entry;
+ protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
+ LinkEntry link = (LinkEntry) entry;
link.before.after = link.after;
link.after.before = link.before;
- link.next = null;
link.after = null;
link.before = null;
- return entry.value;
+ super.removeEntry(entry, hashIndex, previous);
}
//-----------------------------------------------------------------------
@@ -283,7 +302,7 @@
if (size == 0) {
return IteratorUtils.EMPTY_ORDERED_MAP_ITERATOR;
}
- return new LinkedMapIterator(this);
+ return new LinkMapIterator(this);
}
/**
@@ -301,15 +320,15 @@
if (size == 0) {
return IteratorUtils.EMPTY_ORDERED_MAP_ITERATOR;
}
- return new LinkedMapIterator(this);
+ return new LinkMapIterator(this);
}
/**
* MapIterator
*/
- static class LinkedMapIterator extends LinkedIterator implements OrderedMapIterator {
+ static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
- LinkedMapIterator(LinkedMap map) {
+ LinkMapIterator(LinkedMap map) {
super(map);
}
@@ -363,7 +382,7 @@
/**
* EntrySetIterator and MapEntry
*/
- static class EntrySetIterator extends LinkedIterator {
+ static class EntrySetIterator extends LinkIterator {
EntrySetIterator(LinkedMap map) {
super(map);
@@ -427,7 +446,7 @@
/**
* ValuesIterator
*/
- static class ValuesIterator extends LinkedIterator {
+ static class ValuesIterator extends LinkIterator {
ValuesIterator(LinkedMap map) {
super(map);
@@ -446,12 +465,12 @@
/**
* LinkEntry
*/
- protected static class LinkedEntry extends HashEntry {
+ protected static class LinkEntry extends HashEntry {
- LinkedEntry before;
- LinkedEntry after;
+ protected LinkEntry before;
+ protected LinkEntry after;
- protected LinkedEntry(HashEntry next, int hashCode, Object key, Object value) {
+ protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
super(next, hashCode, key, value);
}
}
@@ -459,15 +478,15 @@
/**
* Base Iterator
*/
- protected static abstract class LinkedIterator
+ protected static abstract class LinkIterator
implements OrderedIterator, ResettableIterator {
- private final LinkedMap map;
- private LinkedEntry current;
- private LinkedEntry next;
- private int expectedModCount;
+ protected final LinkedMap map;
+ protected LinkEntry current;
+ protected LinkEntry next;
+ protected int expectedModCount;
- protected LinkedIterator(LinkedMap map) {
+ protected LinkIterator(LinkedMap map) {
super();
this.map = map;
this.next = map.header.after;
@@ -482,7 +501,7 @@
return (next.before != map.header);
}
- protected LinkedEntry nextEntry() {
+ protected LinkEntry nextEntry() {
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
@@ -494,11 +513,11 @@
return current;
}
- protected LinkedEntry previousEntry() {
+ protected LinkEntry previousEntry() {
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
- LinkedEntry previous = next.before;
+ LinkEntry previous = next.before;
if (previous == map.header) {
throw new NoSuchElementException(HashedMap.NO_PREVIOUS_ENTRY);
}
@@ -507,7 +526,7 @@
return current;
}
- protected LinkedEntry currentEntry() {
+ protected LinkEntry currentEntry() {
return current;
}
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/map/LRUMap.java
Index: LRUMap.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/LRUMap.java,v 1.1 2003/12/07 01:23:54 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-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 acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements 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 apache@apache.org.
*
* 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.map;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Map;
import org.apache.commons.collections.OrderedMap;
/**
* A <code>Map</code> implementation with a fixed maximum size which removes
* the least recently used entry if an entry is added when full.
* <p>
* The least recently used algorithm works on the get and put operations only.
* Iteration of any kind, including setting the value by iteration, does not
* change the order. Queries such as containsKey and containsValue or access
* via views also do not change the order.
* <p>
* The map implements <code>OrderedMap</code> and entries may be queried using
* the bidirectional <code>OrderedMapIterator</code>. The order returned is
* most recently used to least recently used. Iterators from map views can
* also be cast to <code>OrderedIterator</code> if required.
* <p>
* All the available iterators can be reset back to the start by casting to
* <code>ResettableIterator</code> and calling <code>reset()</code>.
* <p>
* NOTE: The order of the map has changed from the previous version located
* in the main collections package. The map is now ordered most recently used
* to least recently used.
*
* @since Commons Collections 3.0
* @version $Revision: 1.1 $ $Date: 2003/12/07 01:23:54 $
*
* @author James Strachan
* @author Morgan Delagrange
* @author Stephen Colebourne
*/
public class LRUMap extends LinkedMap implements OrderedMap {
/** Serialisation version */
static final long serialVersionUID = -2848625157350244215L;
/** Default maximum size */
protected static final int DEFAULT_MAX_SIZE = 100;
/** Maximum size */
private transient int maxSize;
/**
* Constructs a new empty map with a maximum size of 100.
*/
public LRUMap() {
this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs a new, empty map with the specified maximum size.
*
* @param maxSize the maximum size of the map
* @throws IllegalArgumentException if the maximum size is less than one
*/
public LRUMap(int maxSize) {
this(maxSize, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs a new, empty map with the specified initial capacity and
* load factor.
*
* @param maxSize the maximum size of the map, -1 for no limit,
* @param loadFactor the load factor
* @throws IllegalArgumentException if the maximum size is less than one
* @throws IllegalArgumentException if the load factor is less than zero
*/
public LRUMap(int maxSize, float loadFactor) {
super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
if (maxSize < 1) {
throw new IllegalArgumentException("LRUMap max size must be greater than 0");
}
this.maxSize = maxSize;
}
/**
* Constructor copying elements from another map.
* <p>
* The maximum size is set from the map's size.
*
* @param map the map to copy
* @throws NullPointerException if the map is null
* @throws IllegalArgumentException if the map is empty
*/
public LRUMap(Map map) {
this(map.size(), DEFAULT_LOAD_FACTOR);
putAll(map);
}
//-----------------------------------------------------------------------
/**
* Gets the value mapped to the key specified.
* <p>
* This operation changes the position of the key in the map to the
* most recently used position (first).
*
* @param key the key
* @return the mapped value, null if no match
*/
public Object get(Object key) {
LinkEntry entry = (LinkEntry) getEntry(key);
if (entry == null) {
return null;
}
moveFirst(entry);
return entry.getValue();
}
//-----------------------------------------------------------------------
/**
* Updates an existing key-value mapping.
* This implementation moves the updated entry to the top of the list.
*
* @param entry the entry to update
* @param newValue the new value to store
* @return value the previous value
*/
protected void moveFirst(LinkEntry entry) {
if (entry.before != header) {
modCount++;
// remove
entry.after.before = entry.before;
entry.before.after = entry.after;
// add first
entry.before = header;
entry.after = header.after;
header.after.before = entry;
header.after = entry;
}
}
/**
* Updates an existing key-value mapping.
* This implementation moves the updated entry to the top of the list.
*
* @param entry the entry to update
* @param newValue the new value to store
* @return value the previous value
*/
protected void updateEntry(HashEntry entry, Object newValue) {
moveFirst((LinkEntry) entry); // handles modCount
entry.setValue(newValue);
}
/**
* Adds a new key-value mapping into this map.
* This implementation checks the LRU size and determines whether to
* discard an entry or not.
*
* @param hashIndex the index into the data array to store at
* @param hashCode the hash code of the key to add
* @param key the key to add
* @param value the value to add
* @return the value previously mapped to this key, null if none
*/
protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
if (size >= maxSize && removeLRU(header.before)) {
LinkEntry entry = header.before;
// remove from current location
int removeIndex = hashIndex(entry.hashCode, data.length);
HashEntry loop = data[removeIndex];
HashEntry previous = null;
while (loop != entry) {
previous = loop;
loop = loop.next;
}
modCount++;
removeEntry(entry, removeIndex, previous);
reuseEntry(entry, hashIndex, hashCode, key, value);
addEntry(entry, hashIndex);
} else {
super.addMapping(hashIndex, hashCode, key, value);
}
}
/**
* Adds a new entry into this map using access order.
* <p>
* This implementation adds the entry to the data storage table and
* to the start of the linked list.
*
* @param entry the entry to add
* @param hashIndex the index into the data array to store at
*/
protected void addEntry(HashEntry entry, int hashIndex) {
LinkEntry link = (LinkEntry) entry;
link.before = header;
link.after = header.after;
header.after.before = link;
header.after = link;
data[hashIndex] = entry;
}
/**
* Subclass method to control removal of the least recently used entry from the map.
* <p>
* This method exists for subclasses to override. A subclass may wish to
* provide cleanup of resources when an entry is removed. For example:
* <pre>
* protected boolean removeLRU(LinkEntry entry) {
* releaseResources(entry.getValue()); // release resources held by entry
* return true; // actually delete entry
* }
* </pre>
* <p>
* Alternatively, a subclass may choose to not remove the entry or selectively
* keep certain LRU entries. For example:
* <pre>
* protected boolean removeLRU(LinkEntry entry) {
* if (entry.getKey().toString().startsWith("System.")) {
* return false; // entry not removed from LRUMap
* } else {
* return true; // actually delete entry
* }
* }
* </pre>
* Note that the effect of not removing an LRU is for the Map to exceed the maximum size.
*
* @param entry the entry to be removed
*/
protected boolean removeLRU(LinkEntry entry) {
return true;
}
//-----------------------------------------------------------------------
/**
* Returns true if this map is full and no new mappings can be added.
*
* @return <code>true</code> if the map is full
*/
public boolean isFull() {
return (size >= maxSize);
}
/**
* Gets the maximum size of the map (the bound).
*
* @return the maximum number of elements the map can hold
*/
public int maxSize() {
return maxSize;
}
//-----------------------------------------------------------------------
/**
* Write the data of subclasses.
* A sub-subclass must call super.doWriteObject().
*/
protected void doWriteObject(ObjectOutputStream out) throws IOException {
out.writeInt(maxSize);
super.doWriteObject(out);
}
/**
* Read the data of subclasses.
* A sub-subclass must call super.doReadObject().
*/
protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
maxSize = in.readInt();
super.doReadObject(in);
}
}
1.10 +3 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- TestAll.java 3 Dec 2003 19:04:41 -0000 1.9
+++ TestAll.java 7 Dec 2003 01:23:54 -0000 1.10
@@ -87,6 +87,7 @@
suite.addTest(TestHashedMap.suite());
suite.addTest(TestIdentityMap.suite());
suite.addTest(TestLinkedMap.suite());
+ suite.addTest(TestLRUMap.suite());
suite.addTest(TestReferenceMap.suite());
suite.addTest(TestStaticBucketMap.suite());
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLRUMap.java
Index: TestLRUMap.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLRUMap.java,v 1.1 2003/12/07 01:23:54 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-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 acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements 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 apache@apache.org.
*
* 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.map;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import junit.framework.Test;
import junit.textui.TestRunner;
import org.apache.commons.collections.BulkTest;
import org.apache.commons.collections.OrderedMap;
import org.apache.commons.collections.ResettableIterator;
/**
* JUnit tests.
*
* @version $Revision: 1.1 $ $Date: 2003/12/07 01:23:54 $
*
* @author Stephen Colebourne
*/
public class TestLRUMap extends AbstractTestOrderedMap {
public TestLRUMap(String testName) {
super(testName);
}
public static void main(String[] args) {
TestRunner.run(suite());
}
public static Test suite() {
return BulkTest.makeSuite(TestLRUMap.class);
}
public Map makeEmptyMap() {
return new LRUMap();
}
public boolean isGetStructuralModify() {
return true;
}
public String getCompatibilityVersion() {
return "3";
}
//-----------------------------------------------------------------------
public void testLRU() {
if (isPutAddSupported() == false || isPutChangeSupported() == false) return;
Object[] keys = getSampleKeys();
Object[] values = getSampleValues();
Iterator it = null;
LRUMap map = new LRUMap(2);
assertEquals(0, map.size());
assertEquals(false, map.isFull());
assertEquals(2, map.maxSize());
map.put(keys[0], values[0]);
assertEquals(1, map.size());
assertEquals(false, map.isFull());
assertEquals(2, map.maxSize());
map.put(keys[1], values[1]);
assertEquals(2, map.size());
assertEquals(true, map.isFull());
assertEquals(2, map.maxSize());
it = map.keySet().iterator();
assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
it = map.values().iterator();
assertSame(values[1], it.next());
assertSame(values[0], it.next());
map.put(keys[2], values[2]);
assertEquals(2, map.size());
assertEquals(true, map.isFull());
assertEquals(2, map.maxSize());
it = map.keySet().iterator();
assertSame(keys[2], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[2], it.next());
assertSame(values[1], it.next());
map.put(keys[2], values[0]);
assertEquals(2, map.size());
assertEquals(true, map.isFull());
assertEquals(2, map.maxSize());
it = map.keySet().iterator();
assertSame(keys[2], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[0], it.next());
assertSame(values[1], it.next());
map.put(keys[1], values[3]);
assertEquals(2, map.size());
assertEquals(true, map.isFull());
assertEquals(2, map.maxSize());
it = map.keySet().iterator();
assertSame(keys[1], it.next());
assertSame(keys[2], it.next());
it = map.values().iterator();
assertSame(values[3], it.next());
assertSame(values[0], it.next());
}
//-----------------------------------------------------------------------
public void testReset() {
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
((ResettableIterator) ordered.mapIterator()).reset();
resetFull();
ordered = (OrderedMap) map;
List list = new ArrayList(ordered.keySet());
ResettableIterator it = (ResettableIterator) ordered.mapIterator();
assertSame(list.get(0), it.next());
assertSame(list.get(1), it.next());
it.reset();
assertSame(list.get(0), it.next());
}
//-----------------------------------------------------------------------
public void testAccessOrder() {
if (isPutAddSupported() == false || isPutChangeSupported() == false) return;
Object[] keys = getSampleKeys();
Object[] values = getSampleValues();
Iterator it = null;
resetEmpty();
map.put(keys[1], values[1]);
map.put(keys[0], values[0]);
it = map.keySet().iterator();
assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[0], it.next());
assertSame(values[1], it.next());
// change to order
map.put(keys[1], values[1]);
it = map.keySet().iterator();
assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
it = map.values().iterator();
assertSame(values[1], it.next());
assertSame(values[0], it.next());
// no change to order
map.put(keys[1], values[2]);
it = map.keySet().iterator();
assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
it = map.values().iterator();
assertSame(values[2], it.next());
assertSame(values[0], it.next());
// change to order
map.put(keys[0], values[3]);
it = map.keySet().iterator();
assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[3], it.next());
assertSame(values[2], it.next());
// change to order
map.get(keys[1]);
it = map.keySet().iterator();
assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
it = map.values().iterator();
assertSame(values[2], it.next());
assertSame(values[3], it.next());
// change to order
map.get(keys[0]);
it = map.keySet().iterator();
assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[3], it.next());
assertSame(values[2], it.next());
// no change to order
map.get(keys[0]);
it = map.keySet().iterator();
assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
it = map.values().iterator();
assertSame(values[3], it.next());
assertSame(values[2], it.next());
}
//-----------------------------------------------------------------------
public void testFirstKey() { // override
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
try {
ordered.firstKey();
fail();
} catch (NoSuchElementException ex) {}
resetFull();
ordered = (OrderedMap) map;
Object confirmedFirst = confirmed.keySet().iterator().next();
ordered.get(confirmedFirst);
assertEquals(confirmedFirst, ordered.firstKey());
}
public void testLastKey() { // override
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
try {
ordered.lastKey();
fail();
} catch (NoSuchElementException ex) {}
resetFull();
ordered = (OrderedMap) map;
Object confirmedFirst = confirmed.keySet().iterator().next();
// access order, thus first in is now in last place
assertEquals(confirmedFirst, ordered.lastKey());
}
//-----------------------------------------------------------------------
public void testNextKey() { // override
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
assertEquals(null, ordered.nextKey(getOtherKeys()[0]));
if (isAllowNullKey() == false) {
try {
assertEquals(null, ordered.nextKey(null)); // this is allowed too
} catch (NullPointerException ex) {}
} else {
assertEquals(null, ordered.nextKey(null));
}
resetFull();
ordered = (OrderedMap) map;
List list = new ArrayList(confirmed.keySet());
Collections.reverse(list); // first into map is eldest
Iterator it = list.iterator();
Object confirmedLast = it.next();
while (it.hasNext()) {
Object confirmedObject = it.next();
assertEquals(confirmedObject, ordered.nextKey(confirmedLast));
confirmedLast = confirmedObject;
}
assertEquals(null, ordered.nextKey(confirmedLast));
}
public void testPreviousKey() { // override
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
assertEquals(null, ordered.previousKey(getOtherKeys()[0]));
if (isAllowNullKey() == false) {
try {
assertEquals(null, ordered.previousKey(null)); // this is allowed too
} catch (NullPointerException ex) {}
} else {
assertEquals(null, ordered.previousKey(null));
}
resetFull();
ordered = (OrderedMap) map;
List list = new ArrayList(confirmed.keySet());
Iterator it = list.iterator();
Object confirmedLast = it.next();
while (it.hasNext()) {
Object confirmedObject = it.next();
assertEquals(confirmedObject, ordered.previousKey(confirmedLast));
confirmedLast = confirmedObject;
}
assertEquals(null, ordered.previousKey(confirmedLast));
}
// public void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk((Serializable) map, "D:/dev/collections/data/test/LRUMap.emptyCollection.version3.obj");
// resetFull();
// writeExternalFormToDisk((Serializable) map, "D:/dev/collections/data/test/LRUMap.fullCollection.version3.obj");
// }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org