commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/map LRUMap.java
Date Wed, 12 May 2004 19:51:28 GMT
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


Mime
View raw message