001: /*
002: * Licensed under the X license (see http://www.x.org/terms.htm)
003: */
004: package org.ofbiz.minerva.pool.cache;
005:
006: import java.io.PrintWriter;
007: import java.util.*;
008:
009: /**
010: * A Least Recently Used cache implementation. The object in the
011: * cache that was least recently used is dropped when the cache is
012: * full and a new request comes in. The implementation uses a linked
013: * list (to track recentness) and a HashMap (to navigate quickly).
014: * @author Aaron Mulder ammulder@alumni.princeton.edu
015: */
016: public class LeastRecentlyUsedCache implements ObjectCache {
017:
018: private Object lock = new Object();
019: private HashMap keyMap = new HashMap();
020: private PrintWriter log = null;
021: private Node mostRecentNode, leastRecentNode;
022: private int size;
023: private int maxSize;
024: private CachedObjectFactory factory;
025:
026: public LeastRecentlyUsedCache(CachedObjectFactory factory,
027: int maxSize) {
028: this .factory = factory;
029: this .maxSize = maxSize;
030: }
031:
032: public Object getObject(Object key) {
033: return getObject(key, false);
034: }
035:
036: public Object useObject(Object key) {
037: return getObject(key, true);
038: }
039:
040: public void returnObject(Object key, Object value) {
041: Object pooled = keyMap.get(key);
042: Object source = factory.translateObject(value);
043:
044: if (pooled == null) {
045: factory.deleteObject(source);
046: } else if (pooled instanceof Node) {
047: Node node = (Node) pooled;
048: if (node.data == source) {
049: try {
050: node.setUsed(false);
051: } catch (ConcurrentModificationException e) {
052: }
053: } else {
054: factory.deleteObject(source);
055: }
056: } else if (pooled instanceof LinkedList) {
057: for (Iterator it = ((LinkedList) pooled).iterator(); it
058: .hasNext();) {
059: Node node = (Node) it.next();
060: if (node.data == source) {
061: try {
062: node.setUsed(false);
063: } catch (ConcurrentModificationException e) {
064: }
065: return;
066: }
067: }
068: factory.deleteObject(source);
069: } else
070: throw new Error(
071: "LRU Cache Assertion Failure: Wrong class '"
072: + pooled.getClass().getName()
073: + "' in keyMap!");
074: }
075:
076: public void removeObjects(Object key) {
077: synchronized (lock) {
078: Object value = keyMap.get(key);
079: if (value == null) {
080: return;
081: } else if (value instanceof Node) {
082: removeNode((Node) value);
083: } else if (value instanceof LinkedList) {
084: LinkedList list = (LinkedList) value;
085: int max = list.size();
086: for (int i = 0; i < max; i++) {
087: removeNode((Node) list.get(0));
088: }
089: }
090: }
091: }
092:
093: public void setSize(int maxSize) {
094: this .maxSize = maxSize;
095: checkMaxSize();
096: }
097:
098: public void close() {
099: synchronized (lock) {
100: Node current = leastRecentNode;
101: Node next = current == null ? null : current.moreRecent;
102: while (current != null) {
103: removeNode(current);
104: current = next;
105: next = current == null ? null : current.moreRecent;
106: }
107: }
108: }
109:
110: private Object getObject(Object key, boolean use) {
111: Node node = null;
112: try {
113: Object value = keyMap.get(key);
114: if (value == null) {
115: node = addObject(key);
116: } else if (value instanceof Node) {
117: node = (Node) value;
118: if (!node.used) {
119: makeMostRecent(node);
120: } else {
121: node = addObject(key);
122: }
123: } else if (value instanceof LinkedList) {
124: for (Iterator it = ((LinkedList) value).iterator(); it
125: .hasNext();) {
126: node = (Node) it.next();
127: if (!node.used) {
128: makeMostRecent(node);
129: break;
130: } else {
131: node = null;
132: }
133: }
134: if (node == null) {
135: node = addObject(key);
136: }
137: } else
138: throw new Error(
139: "LRU Cache Assertion Failure: Wrong class '"
140: + value.getClass().getName()
141: + "' in keyMap!");
142: if (use) {
143: node.setUsed(true);
144: }
145: } catch (ConcurrentModificationException e) {
146: return getObject(key, use);
147: }
148: return factory.prepareObject(node.data);
149: }
150:
151: private Node addObject(Object key) {
152: Object data;
153: try {
154: data = factory.createObject(key);
155: } catch (Exception e) {
156: if (log != null)
157: e.printStackTrace(log);
158: return null;
159: }
160: Node result;
161: synchronized (lock) {
162: if (mostRecentNode == null) {
163: result = new Node(null, null, data);
164: mostRecentNode = result;
165: leastRecentNode = result;
166: } else {
167: result = new Node(mostRecentNode, null, data);
168: mostRecentNode.moreRecent = result;
169: mostRecentNode = result;
170: }
171: ++size;
172: checkMaxSize();
173: }
174:
175: // Put the key/value(s) and node/key in the map
176: Object value = keyMap.get(key);
177: if (value == null) {
178: keyMap.put(key, result);
179: } else if (value instanceof LinkedList) {
180: ((LinkedList) value).add(result);
181: } else if (value instanceof Node) {
182: LinkedList list = new LinkedList();
183: list.add(value);
184: list.add(result);
185: keyMap.put(key, list);
186: } else
187: throw new Error(
188: "LRU Cache Assertion Failure: Wrong class '"
189: + value.getClass().getName()
190: + "' in keyMap!");
191: keyMap.put(result, key);
192: return result;
193: }
194:
195: private void checkMaxSize() {
196: if (maxSize <= 0)
197: return;
198: while (size > maxSize) {
199: Node drop = leastRecentNode;
200: leastRecentNode = drop.moreRecent;
201: leastRecentNode.lessRecent = null;
202: --size;
203:
204: removeNode(drop);
205: }
206: }
207:
208: private void makeMostRecent(Node node) {
209: synchronized (lock) {
210: if (node.moreRecent == null) {
211: if (mostRecentNode != node)
212: throw new ConcurrentModificationException();
213: return;
214: }
215:
216: // Prepare surrounding nodes
217: Node previous = node.moreRecent;
218: Node next = node.lessRecent;
219: previous.lessRecent = next;
220: if (next == null) {
221: leastRecentNode = previous;
222: } else {
223: next.moreRecent = previous;
224: }
225:
226: // Prepare node and new 2nd most recent
227: node.moreRecent = null;
228: node.lessRecent = mostRecentNode;
229: mostRecentNode.moreRecent = node;
230: mostRecentNode = node;
231: }
232: }
233:
234: // This should be called while holding the lock
235: private void removeNode(Node node) {
236: boolean used = node.used;
237: if (!used) {
238: node.used = true;
239: }
240: Object key = keyMap.remove(node);
241:
242: Object value = keyMap.get(key);
243: if (value instanceof Node) {
244: keyMap.remove(key);
245: } else if (value instanceof LinkedList) {
246: LinkedList list = (LinkedList) value;
247: Iterator it = list.iterator();
248: while (it.hasNext()) {
249: Node current = (Node) it.next();
250: if (current == node) {
251: it.remove();
252: break;
253: }
254: }
255: if (list.size() == 1) {
256: keyMap.put(key, list.get(0));
257: }
258: } else
259: throw new Error(
260: "LRU Cache Assertion Failure: Wrong class '"
261: + value.getClass().getName()
262: + "' in keyMap!");
263: if (!used) {
264: factory.deleteObject(node.data);
265: }
266: node.moreRecent = null;
267: node.lessRecent = null;
268: }
269:
270: private class Node {
271:
272: Node lessRecent;
273: Node moreRecent;
274: Object data;
275: boolean used = false;
276:
277: public Node(Node lessRecent, Node moreRecent, Object data) {
278: this (lessRecent, moreRecent, data, false);
279: }
280:
281: public Node(Node lessRecent, Node moreRecent, Object data,
282: boolean used) {
283: this .lessRecent = lessRecent;
284: this .moreRecent = moreRecent;
285: this .data = data;
286: this .used = used;
287: }
288:
289: public synchronized void setUsed(boolean used) {
290: if (this .used == used)
291: throw new ConcurrentModificationException();
292: this .used = used;
293: }
294: }
295:
296: /* This is for testing only
297:
298: private void printList() {
299: System.out.print("Fwd Nodes:");
300: Node node = mostRecentNode;
301: for(int i=0; i<size; i++) {
302: System.out.print(" "+node.data);
303: node = node.lessRecent;
304: }
305: System.out.println();
306: Stack stack = new Stack();
307: node = leastRecentNode;
308: for(int i=0; i<size; i++) {
309: stack.push(node.data);
310: node = node.moreRecent;
311: }
312: System.out.print("Rev Nodes:");
313: while(!stack.isEmpty())
314: System.out.print(" "+stack.pop());
315: System.out.println();
316: }
317:
318: public static void main(String args[]) {
319: try {
320: java.io.BufferedReader in = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
321: LeastRecentlyUsedCache cache = new LeastRecentlyUsedCache(new CachedObjectFactory() {
322: public Object createObject(Object identifier) {
323: return "v"+identifier;
324: }
325: public void deleteObject(Object object) {
326: System.out.println("Deleting Object "+object);
327: }
328: }, 5);
329:
330: * *** THIS TESTS getObject ****
331:
332: while(true) {
333: cache.printList();
334: System.out.print("> ");
335: System.out.flush();
336: String key = in.readLine();
337: if(key.equalsIgnoreCase("quit") || key.equalsIgnoreCase("exit"))
338: return;
339: Object value = cache.getObject(key);
340: System.out.println("Got Value: "+value);
341: }
342:
343: * ********* *
344:
345: **** THIS TESTS useObject AND returnObject ****
346:
347: Object lastKey = null, last = null;
348: while(true) {
349: cache.printList();
350: System.out.print("> ");
351: System.out.flush();
352: String key = in.readLine();
353: if(key.equalsIgnoreCase("quit") || key.equalsIgnoreCase("exit"))
354: return;
355: Object value = cache.useObject(key);
356: if(last != null) {
357: cache.returnObject(lastKey, last);
358: }
359: lastKey = key;
360: last = value;
361: System.out.println("Got Value: "+value);
362: }
363:
364: ********** *
365: } catch(Throwable e) {
366: e.printStackTrace();
367: }
368: }
369: */
370: }
|