src/org/ibex/util/Cache.java

   1 // Copyright (C) 2003 Adam Megacz <adam@ibex.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 /*
   9
  10 Bug report from a user:
  11
  12 I looked at your Cache.java and tried to make good use of it, but I was
  13 out of luck - it wouldn't run here. Digging deeper into the code, I came
  14 across something that might be considered a bug. But maybe it's just a
  15 feature :-)
  16
  17
  18 Starting with an empty cache, Cache.put() immediately followed by
  19 Cache.get() on same keys / same object will set Node lru back to null in
  20 Node.remove() which is called in get().
  21
  22 Assuming this put()-get() sequence is fixed, it will fill the cache, but
  23 lru will remain null.
  24
  25 When cache is filled 100%, we have, at the end of the get(), where
  26 size>maxSize is checked, a state that mru == lru == n (from
  27 if(lru==null) thus deleteting the newly inserted object. Oops.
  28
  29
  30 Hope I made this clear enough. Maybe it's not a problem in xwt due to a
  31 different usage scheme of the cache.
  32
  33
  34
  35 */
  36
  37 package org.ibex.util;
  38
  39 // FIXME needs to be a weak hash
  40
  41 /**
  42  *  A Hash table with a fixed size; drops extraneous elements.  Uses
  43  *  LRU strategy.
  44  */
  45 public class Cache extends Hash {
  46
  47     /** head of list is the mru; tail is the lru */
  48     Node mru = null;
  49     Node lru = null;
  50
  51     private int maxSize;
  52     private Cache() { }
  53     public Cache(int maxSize) {
  54         super(maxSize * 2, 3);
  55         this.maxSize = maxSize;
  56     }
  57
  58     /** A doubly-linked list */
  59     private class Node {
  60         final Object val;
  61         final Object k1;
  62         final Object k2;
  63         public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; }
  64         Node next = null;
  65         Node prev = null;
  66         void remove() {
  67             if (this == lru) lru = prev;
  68             if (this == mru) mru = next;
  69             if (next != null) next.prev = prev;
  70             if (prev != null) prev.next = next;
  71             next = prev = null;
  72         }
  73         void placeAfter(Node n) {
  74             remove();
  75             if (n == null) return;
  76             next = n.next;
  77             if (n.next != null) n.next.prev = this;
  78             n.next = this;
  79             prev = n;
  80         }
  81         void placeBefore(Node n) {
  82             remove();
  83             if (n == null) return;
  84             next = n;
  85             prev = n.prev;
  86             n.prev = this;
  87             if (prev != null) prev.next = this;
  88         }
  89     }
  90
  91     public void clear() {
  92         lru = null;
  93         super.clear();
  94     }
  95
  96     public void remove(Object k1, Object k2) {
  97         Object o = super.get(k1, k2);
  98         if (o != null) ((Node)o).remove();
  99         super.remove(k1, k2);
 100     }
 101
 102     public Object get(Object k1, Object k2) {
 103         Node n = (Node)super.get(k1, k2);
 104         if (n == null) return null;
 105         n.remove();
 106         n.placeBefore(mru);
 107         mru = n;
 108         return n.val;
 109     }
 110
 111     public void put(Object k1, Object k2, Object v) {
 112         Node n = new Node(k1, k2, v);
 113         if (lru == null) {
 114             lru = mru = n;
 115         } else {
 116             n.placeBefore(mru);
 117             mru = n;
 118         }
 119         if (super.get(k1, k2) != null) remove(k1, k2);
 120         super.put(k1, k2, n);
 121         if (size > maxSize) remove(lru.k1, lru.k2);
 122     }
 123
 124 }
 125
 126