src/org/xwt/util/Cache.java

   1 // Copyright 2002 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     /** A doubly-linked list */
  17     private class Node {
  18         final Object val;
  19         public Node(Object val) { this.val = val; }
  20         Node next = null;
  21         Node prev = null;
  22         void remove() {
  23             if (this == lru) lru = prev;
  24             if (this == mru) mru = next;
  25             if (next != null) next.prev = prev;
  26             if (prev != null) prev.next = next;
  27             next = prev = null;
  28         }
  29         void placeAfter(Node n) {
  30             remove();
  31             if (n == null) return;
  32             next = n.next;
  33             if (n.next != null) n.next.prev = this;
  34             n.next = this;
  35             prev = n;
  36         }
  37         void placeBefore(Node n) {
  38             remove();
  39             if (n == null) return;
  40             next = n;
  41             prev = n.prev;
  42             n.prev = this;
  43             if (prev != null) prev.next = this;
  44         }
  45     }
  46
  47     public void clear() {
  48         lru = null;
  49         super.clear();
  50     }
  51
  52     public void remove(Object k1, Object k2) {
  53         Object o = super.get(k1, k2);
  54         if (o != null) ((Node)o).remove();
  55         super.remove(k1, k2);
  56     }
  57
  58     public Object get(Object k1, Object k2) {
  59         Node n = (Node)super.get(k1, k2);
  60         if (n == null) return null;
  61         n.remove();
  62         n.placeBefore(mru);
  63         mru = n;
  64         return n.val;
  65     }
  66
  67     public void put(Object k1, Object k2, Object v) {
  68         Node n = new Node(v);
  69         if (lru == null) {
  70             lru = mru = n;
  71         } else {
  72             n.placeBefore(mru);
  73             mru = n;
  74         }
  75         if (super.get(k1, k2) != null) remove(k1, k2);
  76         super.put(k1, k2, n);
  77     }
  78
  79 }
  80
  81