src/org/xwt/util/Cache.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 import java.util.*;
   5
   6 /**
   7  *  A Hash table with a fixed size; drops extraneous elements.  Uses
   8  *  LRU strategy.
   9  */
  10 public class Cache extends Hash {
  11
  12     /** head of list is the mru; tail is the lru */
  13     Node mru = null;
  14     Node lru = null;
  15
  16     private int maxSize;
  17     private Cache() { }
  18     public Cache(int maxSize) {
  19         super(maxSize * 2, 3);
  20         this.maxSize = maxSize;
  21     }
  22
  23     /** A doubly-linked list */
  24     private class Node {
  25         final Object val;
  26         final Object k1;
  27         final Object k2;
  28         public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
  29         Node next = null;
  30         Node prev = null;
  31         void remove() {
  32             if (this == lru) lru = prev;
  33             if (this == mru) mru = next;
  34             if (next != null) next.prev = prev;
  35             if (prev != null) prev.next = next;
  36             next = prev = null;
  37         }
  38         void placeAfter(Node n) {
  39             remove();
  40             if (n == null) return;
  41             next = n.next;
  42             if (n.next != null) n.next.prev = this;
  43             n.next = this;
  44             prev = n;
  45         }
  46         void placeBefore(Node n) {
  47             remove();
  48             if (n == null) return;
  49             next = n;
  50             prev = n.prev;
  51             n.prev = this;
  52             if (prev != null) prev.next = this;
  53         }
  54     }
  55
  56     public void clear() {
  57         lru = null;
  58         super.clear();
  59     }
  60
  61     public void remove(Object k1, Object k2) {
  62         Object o = super.get(k1, k2);
  63         if (o != null) ((Node)o).remove();
  64         super.remove(k1, k2);
  65     }
  66
  67     public Object get(Object k1, Object k2) {
  68         Node n = (Node)super.get(k1, k2);
  69         if (n == null) return null;
  70         n.remove();
  71         n.placeBefore(mru);
  72         mru = n;
  73         return n.val;
  74     }
  75
  76     public void put(Object k1, Object k2, Object v) {
  77         Node n = new Node(k1, k2, v);
  78         if (lru == null) {
  79             lru = mru = n;
  80         } else {
  81             n.placeBefore(mru);
  82             mru = n;
  83         }
  84         if (super.get(k1, k2) != null) remove(k1, k2);
  85         super.put(k1, k2, n);
  86         if (size > maxSize) remove(lru.k1, lru.k2);
  87     }
  88
  89 }
  90
  91