001: /*
002: * LRUCache.java
003: *
004: * Copyright (c) 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
005: *
006: * See the file "LICENSE.txt" for information on usage and redistribution
007: * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
008: */
009: package org.pnuts.util;
010:
011: import java.util.*;
012:
013: /**
014: * An implementation of LRU cache
015: */
016: public class LRUCache implements Cache {
017:
018: private Cell[] cells;
019:
020: private int size;
021:
022: private Cell head;
023:
024: private Cell tail;
025:
026: private int count = 0;
027:
028: static class Cell implements Map.Entry {
029: Cell next;
030: Cell prev;
031: Cell chain;
032: Object key;
033: Object value;
034: int index;
035:
036: Cell(int index, Cell prev, Cell chain, Object key, Object value) {
037: this .index = index;
038: this .prev = prev;
039: this .chain = chain;
040: this .key = key;
041: this .value = value;
042: }
043:
044: public Object getKey() {
045: return key;
046: }
047:
048: public Object getValue() {
049: return value;
050: }
051:
052: public Object setValue(Object value) {
053: Object old = this .value;
054: this .value = value;
055: return old;
056: }
057:
058: public int hashCode() {
059: return key.hashCode() + value.hashCode();
060: }
061:
062: public boolean equals(Object obj) {
063: if (obj instanceof Cell) {
064: Cell c = (Cell) obj;
065: return (key == null && c.key == null || key
066: .equals(c.key))
067: && (value == null && c.value == null || value
068: .equals(c.value));
069: } else {
070: return false;
071: }
072: }
073:
074: public String toString() {
075: return key + "=" + value;
076: }
077: }
078:
079: protected LRUCache() {
080: }
081:
082: /**
083: * @param size
084: * cache size
085: */
086: public LRUCache(int size) {
087: cells = new Cell[size];
088: this .size = size;
089: }
090:
091: void update(Cell b) {
092: if (b != tail) {
093: if (b.prev != null) {
094: b.prev.next = b.next;
095: }
096: if (b.next != null) {
097: b.next.prev = b.prev;
098: }
099: tail.next = b;
100: b.prev = tail;
101: tail = b;
102: }
103: if (b == head) {
104: head = b.next;
105: }
106: b.next = null;
107: }
108:
109: private Cell findCell(Object key) {
110: int index = (key.hashCode() & 0x7FFFFFFF) % size;
111: Cell b = cells[index];
112: while (b != null) {
113: if (b.key.equals(key)) {
114: update(b);
115: return b;
116: }
117: b = b.chain;
118: }
119: return null;
120: }
121:
122: /**
123: * If key is in the cache it returns value, otherwise null.
124: */
125: public Object get(Object key) {
126: Cell cell = findCell(key);
127: if (cell != null) {
128: return cell.value;
129: } else {
130: return null;
131: }
132: }
133:
134: /**
135: * Register key and its value into the cache.
136: */
137: public Object put(Object key, Object value) {
138: int index = (key.hashCode() & 0x7FFFFFFF) % size;
139:
140: Cell b = cells[index];
141: Cell n = null;
142: Object old = null;
143: while (b != null) {
144: if (b.key.equals(key)) {
145: old = b.value;
146: b.value = value;
147: update(b);
148: return old;
149: }
150: b = b.chain;
151: }
152: if (head != null) {
153: if (count >= size) {
154: Cell second = head.next;
155: n = head;
156: expired(n.value);
157: n.prev = tail;
158: tail.next = n;
159: n.next = null;
160: n.key = key;
161: n.value = value;
162: if (n.index == index) {
163: if (n != cells[index]) {
164: for (Cell x = cells[index];; x = x.chain) {
165: if (x.chain == null) {
166: throw new RuntimeException(
167: "[BUG] Reused cell must be found in the chain of index="
168: + index);
169: } else if (x.chain == n) {
170: x.chain = n.chain;
171: break;
172: }
173: }
174: n.chain = cells[index];
175: cells[index] = n;
176: }
177: } else {
178: Cell t = cells[n.index];
179: if (t == n) {
180: cells[n.index] = n.chain;
181: } else {
182: while (t != null && t.chain != null) {
183: if (t.chain == n) {
184: t.chain = n.chain;
185: break;
186: }
187: t = t.chain;
188: }
189: }
190: n.chain = cells[index];
191: cells[index] = n;
192: }
193: n.index = index;
194: head = second;
195: if (head == null) {
196: head = n;
197: }
198: tail = n;
199: } else {
200: count++;
201: n = new Cell(index, tail, cells[index], key, value);
202: cells[index] = n;
203: tail.next = n;
204: tail = n;
205: }
206: } else {
207: count++;
208: n = new Cell(index, null, cells[index], key, value);
209: n.prev = n;
210: n.next = n;
211: cells[index] = n;
212: head = n;
213: tail = n;
214: }
215: return old;
216: }
217:
218: /**
219: * Called when an object is expired from the cache
220: *
221: * @param old an expired object
222: */
223: public void expired(Object old) {
224: // skip
225: }
226:
227: /**
228: * Initializes the cache
229: */
230: public void reset() {
231: head = tail = null;
232: cells = new Cell[size];
233: count = 0;
234: }
235:
236: /**
237: * Returns the number of items in the cache
238: */
239: public int size() {
240: return count;
241: }
242:
243: public Set keySet() {
244: Set keys = new HashSet();
245: for (Iterator it = new Itr(0); it.hasNext();) {
246: keys.add(it.next());
247: }
248: return keys;
249: }
250:
251: public Set entrySet() {
252: Set entries = new HashSet();
253: for (Iterator it = new Itr(2); it.hasNext();) {
254: entries.add(it.next());
255: }
256: return entries;
257: }
258:
259: public Collection values() {
260: ArrayList v = new ArrayList();
261: for (Iterator it = new Itr(1); it.hasNext();) {
262: v.add(it.next());
263: }
264: return v;
265: }
266:
267: class Itr implements Iterator {
268: Cell ref = head;
269: int kind;
270:
271: Itr(int kind) {
272: this .kind = kind;
273: }
274:
275: public boolean hasNext() {
276: return ref != null;
277: }
278:
279: public Object next() {
280: switch (kind) {
281: case 0:
282: Object key = ref.key;
283: ref = ref.next;
284: return key;
285: case 1:
286: Object value = ref.value;
287: ref = ref.next;
288: return value;
289: case 2:
290: Object entry = ref;
291: ref = ref.next;
292: return entry;
293: default:
294: throw new RuntimeException();
295: }
296: }
297:
298: public void remove() {
299: throw new UnsupportedOperationException();
300: }
301: }
302: }
|