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