src/org/xwt/util/Cache.java

   1 // Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
   2 //
   3 // You may modify, copy, and redistribute this code under the terms of
   4 // the GNU Library Public License version 2.1, with the exception of
   5 // the portion of clause 6a after the semicolon (aka the "obnoxious
   6 // relink clause")
   7
   8 package org.xwt.util;
   9
  10 import java.util.*;
  11
  12 // FIXME needs to be a weak hash
  13
  14 /**
  15  *  A Hash table with a fixed size; drops extraneous elements.  Uses
  16  *  LRU strategy.
  17  */
  18 public class Cache extends Hash {
  19
  20     /** head of list is the mru; tail is the lru */
  21     Node mru = null;
  22     Node lru = null;
  23
  24     private int maxSize;
  25     private Cache() { }
  26     public Cache(int maxSize) {
  27         super(maxSize * 2, 3);
  28         this.maxSize = maxSize;
  29     }
  30
  31     /** A doubly-linked list */
  32     private class Node {
  33         final Object val;
  34         final Object k1;
  35         final Object k2;
  36         public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
  37         Node next = null;
  38         Node prev = null;
  39         void remove() {
  40             if (this == lru) lru = prev;
  41             if (this == mru) mru = next;
  42             if (next != null) next.prev = prev;
  43             if (prev != null) prev.next = next;
  44             next = prev = null;
  45         }
  46         void placeAfter(Node n) {
  47             remove();
  48             if (n == null) return;
  49             next = n.next;
  50             if (n.next != null) n.next.prev = this;
  51             n.next = this;
  52             prev = n;
  53         }
  54         void placeBefore(Node n) {
  55             remove();
  56             if (n == null) return;
  57             next = n;
  58             prev = n.prev;
  59             n.prev = this;
  60             if (prev != null) prev.next = this;
  61         }
  62     }
  63
  64     public void clear() {
  65         lru = null;
  66         super.clear();
  67     }
  68
  69     public void remove(Object k1, Object k2) {
  70         Object o = super.get(k1, k2);
  71         if (o != null) ((Node)o).remove();
  72         super.remove(k1, k2);
  73     }
  74
  75     public Object get(Object k1, Object k2) {
  76         Node n = (Node)super.get(k1, k2);
  77         if (n == null) return null;
  78         n.remove();
  79         n.placeBefore(mru);
  80         mru = n;
  81         return n.val;
  82     }
  83
  84     public void put(Object k1, Object k2, Object v) {
  85         Node n = new Node(k1, k2, v);
  86         if (lru == null) {
  87             lru = mru = n;
  88         } else {
  89             n.placeBefore(mru);
  90             mru = n;
  91         }
  92         if (super.get(k1, k2) != null) remove(k1, k2);
  93         super.put(k1, k2, n);
  94         if (size > maxSize) remove(lru.k1, lru.k2);
  95     }
  96
  97 }
  98
  99