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.
7 /** A HashMap with a fixed size; drops extraneous elements. Uses an
8 * LRU strategy, either ordering elements based on insertion order
11 * @author crawshaw@ibex.org
13 public class Cache extends Basket.HashMap {
14 private static final long serialVersionUID = 23498092L;
16 private final int maxSize;
17 private final boolean accessOrder;
21 private int first = -1, last = -1;
23 public Cache(int maxSize, boolean accessOrder) {
24 super(maxSize * 2, 0.75F);
26 prev = new int[maxSize];
27 next = new int[maxSize];
28 for (int i=0; i < maxSize; i++) { prev[i] = next[i] = -1; }
30 this.maxSize = maxSize;
31 this.accessOrder = accessOrder;
34 public Object get(Object k) {
36 if (i < 0) return null;
37 if (accessOrder) { // move to front of linked list
40 if (first >= 0) prev[first] = i;
44 return entries[i + 1];
47 protected void entryAdded(int i) {
48 if (last >= 0) next[last] = i;
49 prev[i] = last >= 0 ? last : -1;
51 int ourlast = accessOrder ? last : first;
53 if (first < 0) first = last;
54 if (ourlast >= 0 && size > maxSize) remove(ourlast);
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;
64 protected void entryUpdated(int i) {
65 if (!accessOrder) { entryRemoved(i); entryAdded(i); }