--- /dev/null
+// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
+package org.xwt.util;
+
+import java.util.*;
+
+/**
+ * A Hash table with a fixed size; drops extraneous elements. Uses
+ * LRU strategy.
+ */
+public class Cache extends Hash {
+
+ /** head of list is the mru; tail is the lru */
+ Node mru = null;
+ Node lru = null;
+
+ /** A doubly-linked list */
+ private class Node {
+ final Object val;
+ public Node(Object val) { 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 void clear() {
+ lru = null;
+ super.clear();
+ }
+
+ public void remove(Object k1, Object k2) {
+ Object o = super.get(k1, k2);
+ if (o != null) ((Node)o).remove();
+ super.remove(k1, k2);
+ }
+
+ 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;
+ }
+
+ public void put(Object k1, Object k2, Object v) {
+ Node n = new Node(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);
+ }
+
+}
+
+