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 2004/05/12 21:51:28 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/map LRUMap.java
scolebourne 2004/05/12 12:51:28
Modified: collections/src/test/org/apache/commons/collections/map
TestLRUMap.java
collections/src/java/org/apache/commons/collections/map
LRUMap.java
Log:
Add behaviour to scan map to find a removable element when full
bug 28887, from Mario Ivankovits
Revision Changes Path
1.8 +51 -4 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.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- TestLRUMap.java 16 Apr 2004 23:53:59 -0000 1.7
+++ TestLRUMap.java 12 May 2004 19:51:28 -0000 1.8
@@ -240,9 +240,11 @@
LinkEntry entry;
Object key;
Object value;
+
MockLRUMapSubclass(int size) {
super(size);
}
+
protected boolean removeLRU(LinkEntry entry) {
this.entry = entry;
this.key = entry.getKey();
@@ -252,7 +254,22 @@
}
public void testRemoveLRUBlocksRemove() {
- MockLRUMapSubclassBlocksRemove map = new MockLRUMapSubclassBlocksRemove(2);
+ MockLRUMapSubclassBlocksRemove map = new MockLRUMapSubclassBlocksRemove(2, false);
+ assertEquals(0, map.size());
+ map.put("A", "a");
+ assertEquals(1, map.size());
+ map.put("B", "b");
+ assertEquals(2, map.size());
+ map.put("C", "c"); // should remove oldest, which is A=a, but this is blocked
+ assertEquals(3, map.size());
+ assertEquals(2, map.maxSize());
+ assertEquals(true, map.containsKey("A"));
+ assertEquals(true, map.containsKey("B"));
+ assertEquals(true, map.containsKey("C"));
+ }
+
+ public void testRemoveLRUBlocksRemoveScan() {
+ MockLRUMapSubclassBlocksRemove map = new MockLRUMapSubclassBlocksRemove(2, true);
assertEquals(0, map.size());
map.put("A", "a");
assertEquals(1, map.size());
@@ -267,14 +284,44 @@
}
static class MockLRUMapSubclassBlocksRemove extends LRUMap {
- MockLRUMapSubclassBlocksRemove(int size) {
- super(size);
+ MockLRUMapSubclassBlocksRemove(int size, boolean scanUntilRemove) {
+ super(size, scanUntilRemove);
}
+
protected boolean removeLRU(LinkEntry entry) {
return false;
}
}
+ public void testRemoveLRUFirstBlocksRemove() {
+ MockLRUMapSubclassFirstBlocksRemove map = new MockLRUMapSubclassFirstBlocksRemove(2);
+ assertEquals(0, map.size());
+ map.put("A", "a");
+ assertEquals(1, map.size());
+ map.put("B", "b");
+ assertEquals(2, map.size());
+ map.put("C", "c"); // should remove oldest, which is A=a but this is blocked - so advance to B=b
+ assertEquals(2, map.size());
+ assertEquals(2, map.maxSize());
+ assertEquals(true, map.containsKey("A"));
+ assertEquals(false, map.containsKey("B"));
+ assertEquals(true, map.containsKey("C"));
+ }
+
+ static class MockLRUMapSubclassFirstBlocksRemove extends LRUMap {
+ MockLRUMapSubclassFirstBlocksRemove(int size) {
+ super(size, true);
+ }
+
+ protected boolean removeLRU(LinkEntry entry) {
+ if ("a".equals(entry.getValue())) {
+ return false;
+ } else {
+ return true;
+ }
+ }
+ }
+
// public void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/LRUMap.emptyCollection.version3.obj");
1.13 +83 -6 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.12
retrieving revision 1.13
diff -u -r1.12 -r1.13
--- LRUMap.java 25 Apr 2004 23:30:07 -0000 1.12
+++ LRUMap.java 12 May 2004 19:51:28 -0000 1.13
@@ -47,6 +47,7 @@
* @author Morgan Delagrange
* @author Stephen Colebourne
* @author Mike Pettypiece
+ * @author Mario Ivankovits
*/
public class LRUMap
extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
@@ -55,15 +56,19 @@
static final long serialVersionUID = -612114643488955218L;
/** Default maximum size */
protected static final int DEFAULT_MAX_SIZE = 100;
+ /** Default scan behaviour */
+ protected static final boolean DEFAULT_SCAN_UNTIL_REMOVABLE = false;
/** Maximum size */
private transient int maxSize;
+ /** Scan behaviour */
+ private boolean scanUntilRemovable;
/**
* Constructs a new empty map with a maximum size of 100.
*/
public LRUMap() {
- this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR);
+ this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, DEFAULT_SCAN_UNTIL_REMOVABLE);
}
/**
@@ -77,6 +82,17 @@
}
/**
+ * Constructs a new, empty map with the specified maximum size.
+ *
+ * @param maxSize the maximum size of the map
+ * @param scanUntilRemovable scan until a removeable entry is found, default false
+ * @throws IllegalArgumentException if the maximum size is less than one
+ */
+ public LRUMap(int maxSize, boolean scanUntilRemovable) {
+ this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
+ }
+
+ /**
* Constructs a new, empty map with the specified initial capacity and
* load factor.
*
@@ -86,11 +102,26 @@
* @throws IllegalArgumentException if the load factor is less than zero
*/
public LRUMap(int maxSize, float loadFactor) {
+ this(maxSize, loadFactor, DEFAULT_SCAN_UNTIL_REMOVABLE);
+ }
+
+ /**
+ * 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
+ * @param scanUntilRemovable scan until a removeable entry is found, default false
+ * @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, boolean scanUntilRemovable) {
super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
if (maxSize < 1) {
throw new IllegalArgumentException("LRUMap max size must be greater than 0");
}
this.maxSize = maxSize;
+ this.scanUntilRemovable = scanUntilRemovable;
}
/**
@@ -103,7 +134,21 @@
* @throws IllegalArgumentException if the map is empty
*/
public LRUMap(Map map) {
- this(map.size(), DEFAULT_LOAD_FACTOR);
+ this(map, DEFAULT_SCAN_UNTIL_REMOVABLE);
+ }
+
+ /**
+ * Constructor copying elements from another map.
+ * <p/>
+ * The maximum size is set from the map's size.
+ *
+ * @param map the map to copy
+ * @param scanUntilRemovable scan until a removeable entry is found, default false
+ * @throws NullPointerException if the map is null
+ * @throws IllegalArgumentException if the map is empty
+ */
+ public LRUMap(Map map, boolean scanUntilRemovable) {
+ this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
putAll(map);
}
@@ -170,6 +215,7 @@
* <p>
* From Commons Collections 3.1 this method uses {@link #isFull()} rather
* than accessing <code>size</code> and <code>maxSize</code> directly.
+ * It also handles the scanUntilRemovable functionality.
*
* @param hashIndex the index into the data array to store at
* @param hashCode the hash code of the key to add
@@ -177,8 +223,26 @@
* @param value the value to add
*/
protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
- if (isFull() && removeLRU(header.after)) {
- reuseMapping(header.after, hashIndex, hashCode, key, value);
+ if (isFull()) {
+ LinkEntry reuse = header.after;
+ boolean removeLRUEntry = false;
+ if (scanUntilRemovable) {
+ while (reuse != header) {
+ if (removeLRU(reuse)) {
+ removeLRUEntry = true;
+ break;
+ }
+ reuse = reuse.after;
+ }
+ } else {
+ removeLRUEntry = removeLRU(reuse);
+ }
+
+ if (removeLRUEntry) {
+ reuseMapping(reuse, hashIndex, hashCode, key, value);
+ } else {
+ super.addMapping(hashIndex, hashCode, key, value);
+ }
} else {
super.addMapping(hashIndex, hashCode, key, value);
}
@@ -237,7 +301,10 @@
* }
* }
* </pre>
- * Note that the effect of not removing an LRU is for the Map to exceed the maximum size.
+ * The effect of returning false is dependent on the scanUntilRemovable flag.
+ * If the flag is true, the next LRU entry will be passed to this method and so on
+ * until one returns false and is removed, or every entry in the map has been passed.
+ * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
* <p>
* NOTE: Commons Collections 3.0 passed the wrong entry to this method.
* This is fixed in version 3.1 onwards.
@@ -265,6 +332,16 @@
*/
public int maxSize() {
return maxSize;
+ }
+
+ /**
+ * Whether this LRUMap will scan until a removable entry is found when the
+ * map is full.
+ *
+ * @return true if this map scans
+ */
+ public boolean scanUntilRemovable() {
+ return scanUntilRemovable;
}
//-----------------------------------------------------------------------
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org