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 package org.ibex.util;
   6
   7 /** A HashMap with a fixed size; drops extraneous elements. Uses an
   8  *  LRU strategy, either ordering elements based on insertion order
   9  *  or access order.
  10  *
  11  *  @author crawshaw@ibex.org
  12  */
  13 public class Cache extends Basket.HashMap {
  14     private static final long serialVersionUID = 23498092L;
  15
  16     private final int maxSize;
  17     private final boolean accessOrder;
  18
  19     private int[] prev;
  20     private int[] next;
  21     private int first = -1, last = -1;
  22
  23     public Cache(int maxSize, boolean accessOrder) {
  24         super(maxSize * 2, 0.75F);
  25
  26         prev = new int[entries.length];
  27         next = new int[entries.length];
  28         for (int i=0; i < maxSize; i++) { prev[i] = next[i] = -1; }
  29
  30         this.maxSize = maxSize;
  31         this.accessOrder = accessOrder;
  32     }
  33
  34     public Object get(Object k) {
  35         int i = indexOf(k);
  36         if (i < 0) return null;
  37         if (accessOrder) { // move to front of linked list
  38             entryRemoved(i);
  39             prev[i] = -1;
  40             if (first >= 0) prev[first] = i;
  41             next[i] = first;
  42             first = i;
  43         }
  44         return entries[i + 1];
  45     }
  46
  47     protected void entryAdded(int i) {
  48         if (last >= 0) next[last] = i;
  49         prev[i] = last >= 0 ? last : -1;
  50         next[i] = -1;
  51         int ourlast = accessOrder ? last : first;
  52         last = i;
  53         if (first < 0) first = last;
  54         if (ourlast >= 0 && size > maxSize) remove(ourlast);
  55     }
  56
  57     protected void entryRemoved(int i) {
  58         if (prev[i] >= 0) next[prev[i]] = next[i];
  59         if (next[i] >= 0) prev[next[i]] = prev[i];
  60         if (last == i) last = prev[i] >= 0 ? prev[i] : -1;
  61         if (first == i) first = next[i] >= 0 ? next[i] : -1;
  62     }
  63
  64     protected void entryUpdated(int i) {
  65         if (!accessOrder) { entryRemoved(i); entryAdded(i); }
  66     }
  67 }