From 26f1c6fb636081c311dcdc20b76890483b9b6054 Mon Sep 17 00:00:00 2001
From: megacz <megacz@xwt.org>
Date: Fri, 30 Jan 2004 07:35:44 +0000
Subject: [PATCH] 2003/09/17 07:12:24

darcs-hash:20040130073544-2ba56-f0c06a30127f99a2b6e935df2f73329409228d0b.gz
---
 src/org/xwt/util/Cache.java |   81 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)
 create mode 100644 src/org/xwt/util/Cache.java

diff --git a/src/org/xwt/util/Cache.java b/src/org/xwt/util/Cache.java
new file mode 100644
index 0000000..27647d6
--- /dev/null
+++ b/src/org/xwt/util/Cache.java
@@ -0,0 +1,81 @@
+// 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);
+    }
+
+}
+
+
-- 
1.7.10.4