// 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);
- }
-
}
-
-