remake Cache on top of Basket.Hash

darcs-hash:20050106164246-2eb37-46f7bbfd7c51ff7dcc872998d6d074da2d832ef6.gz

diff --git a/src/org/ibex/util/Cache.java b/src/org/ibex/util/Cache.java
index efb8707..3662cf3 100644 (file)
--- a/src/org/ibex/util/Cache.java
+++ b/src/org/ibex/util/Cache.java
@@ -2,122 +2,66 @@
 // Licensed under the Apache Public Source License 2.0 ("the License").
 // You may not use this file except in compliance with the License.
 
-/*
-
-Bug report from a user:
-
-I looked at your Cache.java and tried to make good use of it, but I was
-out of luck - it wouldn't run here. Digging deeper into the code, I came
-across something that might be considered a bug. But maybe it's just a
-feature :-)
-
-
-Starting with an empty cache, Cache.put() immediately followed by
-Cache.get() on same keys / same object will set Node lru back to null in
-Node.remove() which is called in get().
-
-Assuming this put()-get() sequence is fixed, it will fill the cache, but
-lru will remain null.
-
-When cache is filled 100%, we have, at the end of the get(), where
-size>maxSize is checked, a state that mru == lru == n (from
-if(lru==null) thus deleteting the newly inserted object. Oops.
-
-
-Hope I made this clear enough. Maybe it's not a problem in xwt due to a
-different usage scheme of the cache.
-
-
+package org.ibex.util;
 
-*/
+/** A HashMap with a fixed size; drops extraneous elements. Uses an
+ *  LRU strategy, either ordering elements based on insertion order
+ *  or access order.
+ *
+ *  @author crawshaw@ibex.org
+ */
+public class Cache extends Basket.HashMap {
+    private static final long serialVersionUID = 23498092L;
 
-package org.ibex.util;
+    private final int maxSize;
+    private final boolean accessOrder;
 
-// FIXME needs to be a weak hash
+    private int[] prev;
+    private int[] next;
+    private int first = -1, last = -1;
 
-/**
- *  A Hash table with a fixed size; drops extraneous elements.  Uses
- *  LRU strategy.
- */
-public class Cache extends Hash {
+    public Cache(int maxSize, boolean accessOrder) {
+        super(maxSize * 2, 0.75F);
 
-    /** head of list is the mru; tail is the lru */
-    Node mru = null;
-    Node lru = null;
+        prev = new int[maxSize];
+        next = new int[maxSize];
+        for (int i=0; i < maxSize; i++) { prev[i] = next[i] = -1; }
 
-    private int maxSize;
-    private Cache() { }
-    public Cache(int maxSize) {
-        super(maxSize * 2, 3);
         this.maxSize = maxSize;
+        this.accessOrder = accessOrder;
     }
 
-    /** A doubly-linked list */
-    private class Node {
-        final Object val;
-        final Object k1;
-        final Object k2;
-        public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
-        Node next = null;
-        Node prev = null;
-        void remove() {
-            if (this == lru) lru = prev;
-            if (this == mru) mru = next;
-            if (next != null) next.prev = prev;
-            if (prev != null) prev.next = next;
-            next = prev = null;
-        }
-        void placeAfter(Node n) {
-            remove();
-            if (n == null) return;
-            next = n.next;
-            if (n.next != null) n.next.prev = this;
-            n.next = this;
-            prev = n;
-        }
-        void placeBefore(Node n) {
-            remove();
-            if (n == null) return;
-            next = n;
-            prev = n.prev;
-            n.prev = this;
-            if (prev != null) prev.next = this;
+    public Object get(Object k) {
+        int i = indexOf(k);
+        if (i < 0) return null;
+        if (accessOrder) { // move to front of linked list
+            entryRemoved(i);
+            prev[i] = -1;
+            if (first >= 0) prev[first] = i;
+            next[i] = first;
+            first = i;
         }
+        return entries[i + 1];
     }
 
-    public void clear() {
-        lru = null;
-        super.clear();
+    protected void entryAdded(int i) {
+        if (last >= 0) next[last] = i;
+        prev[i] = last >= 0 ? last : -1;
+        next[i] = -1;
+        int ourlast = accessOrder ? last : first;
+        last = i;
+        if (first < 0) first = last;
+        if (ourlast >= 0 && size > maxSize) remove(ourlast);
     }
 
-    public void remove(Object k1, Object k2) {
-        Object o = super.get(k1, k2);
-        if (o != null) ((Node)o).remove();
-        super.remove(k1, k2);
+    protected void entryRemoved(int i) {
+        if (prev[i] >= 0) next[prev[i]] = next[i];
+        if (next[i] >= 0) prev[next[i]] = prev[i];
+        if (last == i) last = prev[i] >= 0 ? prev[i] : -1;
+        if (first == i) first = next[i] >= 0 ? next[i] : -1;
     }
 
-    public Object get(Object k1, Object k2) {
-        Node n = (Node)super.get(k1, k2);
-        if (n == null) return null;
-        n.remove();
-        n.placeBefore(mru);
-        mru = n;
-        return n.val;
+    protected void entryUpdated(int i) {
+        if (!accessOrder) { entryRemoved(i); entryAdded(i); }
     }
-
-    public void put(Object k1, Object k2, Object v) {
-        Node n = new Node(k1, k2, v);
-        if (lru == null) {
-            lru = mru = n;
-        } else {
-            n.placeBefore(mru);
-            mru = n;
-        }
-        if (super.get(k1, k2) != null) remove(k1, k2);
-        super.put(k1, k2, n);
-        if (size > maxSize) remove(lru.k1, lru.k2);
-    }
-
 }
-
-