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/11 01:46:12 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/map LRUMap.java
scolebourne 2003/12/10 16:46:12
Modified: collections/data/test LRUMap.fullCollection.version3.obj
collections/src/test/org/apache/commons/collections/map
TestLRUMap.java
collections/src/java/org/apache/commons/collections/map
LRUMap.java
Log:
Change order of LRUMap to LRU to MRU
Revision Changes Path
1.3 +1 -1 jakarta-commons/collections/data/test/LRUMap.fullCollection.version3.obj
<<Binary file>>
1.3 +24 -109 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLRUMap.java
Index: TestLRUMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLRUMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- TestLRUMap.java 7 Dec 2003 23:59:12 -0000 1.2
+++ TestLRUMap.java 11 Dec 2003 00:46:12 -0000 1.3
@@ -58,11 +58,9 @@
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;
@@ -126,44 +124,44 @@
assertEquals(true, map.isFull());
assertEquals(2, map.maxSize());
it = map.keySet().iterator();
- assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
+ assertSame(keys[1], it.next());
it = map.values().iterator();
- assertSame(values[1], it.next());
assertSame(values[0], it.next());
+ assertSame(values[1], 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());
+ assertSame(keys[2], it.next());
it = map.values().iterator();
- assertSame(values[2], it.next());
assertSame(values[1], it.next());
+ assertSame(values[2], 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());
+ assertSame(keys[2], it.next());
it = map.values().iterator();
- assertSame(values[0], it.next());
assertSame(values[1], it.next());
+ assertSame(values[0], 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());
+ assertSame(keys[1], it.next());
it = map.values().iterator();
- assertSame(values[3], it.next());
assertSame(values[0], it.next());
+ assertSame(values[3], it.next());
}
//-----------------------------------------------------------------------
@@ -190,8 +188,8 @@
Iterator it = null;
resetEmpty();
- map.put(keys[1], values[1]);
map.put(keys[0], values[0]);
+ map.put(keys[1], values[1]);
it = map.keySet().iterator();
assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
@@ -199,142 +197,59 @@
assertSame(values[0], it.next());
assertSame(values[1], it.next());
- // change to order
+ // no change to order
map.put(keys[1], values[1]);
it = map.keySet().iterator();
- assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
+ assertSame(keys[1], it.next());
it = map.values().iterator();
- assertSame(values[1], it.next());
assertSame(values[0], it.next());
+ assertSame(values[1], 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());
+ assertSame(keys[1], it.next());
it = map.values().iterator();
- assertSame(values[2], it.next());
assertSame(values[0], it.next());
+ assertSame(values[2], 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());
+ assertSame(keys[0], it.next());
it = map.values().iterator();
- assertSame(values[3], it.next());
assertSame(values[2], it.next());
+ assertSame(values[3], it.next());
// change to order
map.get(keys[1]);
it = map.keySet().iterator();
- assertSame(keys[1], it.next());
assertSame(keys[0], it.next());
+ assertSame(keys[1], it.next());
it = map.values().iterator();
- assertSame(values[2], it.next());
assertSame(values[3], it.next());
+ assertSame(values[2], it.next());
// change to order
map.get(keys[0]);
it = map.keySet().iterator();
- assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
+ assertSame(keys[0], it.next());
it = map.values().iterator();
- assertSame(values[3], it.next());
assertSame(values[2], it.next());
+ assertSame(values[3], it.next());
// no change to order
map.get(keys[0]);
it = map.keySet().iterator();
- assertSame(keys[0], it.next());
assertSame(keys[1], it.next());
+ assertSame(keys[0], 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));
+ assertSame(values[3], it.next());
}
// public void testCreate() throws Exception {
1.3 +38 -44 jakarta-commons/collections/src/java/org/apache/commons/collections/map/LRUMap.java
Index: LRUMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/LRUMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- LRUMap.java 7 Dec 2003 23:59:13 -0000 1.2
+++ LRUMap.java 11 Dec 2003 00:46:12 -0000 1.3
@@ -74,15 +74,11 @@
* <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
+ * least recently used to most 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$ $Date$
@@ -164,30 +160,30 @@
if (entry == null) {
return null;
}
- moveFirst(entry);
+ moveToMRU(entry);
return entry.getValue();
}
//-----------------------------------------------------------------------
/**
- * Updates an existing key-value mapping.
- * This implementation moves the updated entry to the top of the list.
+ * Moves an entry to the MRU position at the end of the list.
+ * This implementation moves the updated entry to the end 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) {
+ protected void moveToMRU(LinkEntry entry) {
+ if (entry.after != header) {
modCount++;
// remove
- entry.after.before = entry.before;
entry.before.after = entry.after;
+ entry.after.before = entry.before;
// add first
- entry.before = header;
- entry.after = header.after;
- header.after.before = entry;
- header.after = entry;
+ entry.after = header;
+ entry.before = header.before;
+ header.before.after = entry;
+ header.before = entry;
}
}
@@ -200,7 +196,7 @@
* @return value the previous value
*/
protected void updateEntry(HashEntry entry, Object newValue) {
- moveFirst((LinkEntry) entry); // handles modCount
+ moveToMRU((LinkEntry) entry); // handles modCount
entry.setValue(newValue);
}
@@ -217,41 +213,39 @@
*/
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);
-
+ reuseMapping(header.after, hashIndex, hashCode, key, value);
} 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.
+ * Reuses an entry by removing it and moving it to a new place in the map.
*
- * @param entry the entry to add
+ * @param entry the entry to reuse
* @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) {
- LinkEntry link = (LinkEntry) entry;
- link.before = header;
- link.after = header.after;
- header.after.before = link;
- header.after = link;
- data[hashIndex] = entry;
+ protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
+ // find the entry before the entry specified in the hash table
+ // remember that the parameters (except the first) refer to the new entry,
+ // not the old one
+ int removeIndex = hashIndex(entry.hashCode, data.length);
+ HashEntry loop = data[removeIndex];
+ HashEntry previous = null;
+ while (loop != entry) {
+ previous = loop;
+ loop = loop.next;
+ }
+
+ // reuse the entry
+ modCount++;
+ removeEntry(entry, removeIndex, previous);
+ reuseEntry(entry, hashIndex, hashCode, key, value);
+ addEntry(entry, hashIndex);
}
/**
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org