src/org/ibex/util/Cache.java

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