001: /*
002: * @(#)HashCache.java
003: *
004: * Copyright (C) 2003 Matt Albrecht
005: * groboclown@users.sourceforge.net
006: * http://groboutils.sourceforge.net
007: *
008: * Permission is hereby granted, free of charge, to any person obtaining a
009: * copy of this software and associated documentation files (the "Software"),
010: * to deal in the Software without restriction, including without limitation
011: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
012: * and/or sell copies of the Software, and to permit persons to whom the
013: * Software is furnished to do so, subject to the following conditions:
014: *
015: * The above copyright notice and this permission notice shall be included in
016: * all copies or substantial portions of the Software.
017: *
018: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
019: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
020: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
021: * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
022: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
023: * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
024: * DEALINGS IN THE SOFTWARE.
025: */
026:
027: package net.sourceforge.groboutils.util.datastruct.v1;
028:
029: import java.util.Hashtable;
030: import java.util.Enumeration;
031:
032: /**
033: * Stores objects that are created via a unique key in a limited-sized
034: * cache. The objects are retrieved and created through the key. If the
035: * object with a requested key exists in the cache, then it is returned
036: * and the object is marked as the latest accessed object. If a request
037: * is made for an object whose key is not in the cache, then the object
038: * is created, put into the cache, and returned. If the cache is full
039: * when a new object is created, then the oldest item in the cache is
040: * removed.
041: * <P>
042: * This class is NOT thread safe. All thread safety issues will need to
043: * be covered by the calling class.
044: * <P>
045: * Future versions should use the ObjectCache to cache the node instances.
046: *
047: * @author Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
048: * @since May 23, 2003
049: * @version $Date: 2003/05/23 22:37:57 $
050: */
051: public class HashCache {
052: /**
053: * An interface which needs to be implemented and given to the
054: * cache in order to create new instances. It also allows for
055: * created objects to be cleaned up.
056: */
057: public static interface ObjectManager {
058: /**
059: * Called when a new object needs to be created.
060: *
061: * @param key the key associated with the created object.
062: * @return the newly created object
063: */
064: public Object createObject(Object key);
065:
066: /**
067: * Called when the given object is being removed from the cache.
068: *
069: * @param key the key associated with the object.
070: * @param obj the object being cleaned up.
071: */
072: public void cleanUpObject(Object key, Object obj);
073: }
074:
075: /**
076: * An inner class used for maintaining the chain of ownership.
077: * Uses a doubly-linked list, so that each node can remove itself.
078: */
079: private static class Node {
080: public Object key;
081: public Object value;
082:
083: public Node next;
084: public Node prev;
085:
086: public Node(Object key, Object value) {
087: this .key = key;
088: this .value = value;
089: }
090:
091: /* used with the printChain method below
092: public String toString()
093: {
094: return "node ["+this.value+"]";
095: }
096: */
097: }
098:
099: /**
100: * We also need to keep the object created.
101: */
102: private ObjectManager mgr;
103:
104: /**
105: * Maximum size of the cache.
106: */
107: private int maxSize;
108:
109: /**
110: * The head of our list of cached elements.
111: */
112: private Node head;
113:
114: /**
115: * The tail of our list of cached elements.
116: */
117: private Node tail;
118:
119: /**
120: * Our quick-reference to the list elements.
121: */
122: private Hashtable keyToNode = new Hashtable();
123:
124: /**
125: * For metrics.
126: */
127: private int overflowCount = 0;
128:
129: //-----------------------------------------------------
130: // Constructors
131:
132: /**
133: * Create a new HashCache.
134: *
135: * @param om the manager for creating and cleaning up the objects. This
136: * cannot be null.
137: * @param maxSize the maximum size of the cache. This must be > 1
138: * (this is for performance reasons).
139: */
140: public HashCache(ObjectManager om, int maxSize) {
141: if (om == null) {
142: throw new IllegalArgumentException("no null args");
143: }
144: if (maxSize <= 1) {
145: throw new IllegalArgumentException("size must be > 1");
146: }
147:
148: this .mgr = om;
149: this .maxSize = maxSize;
150: }
151:
152: //-----------------------------------------------------
153: // Public methods
154:
155: /**
156: * Retrieves an item from the cache with the given key. If the
157: * object doesn't exist, then it is created, added to the cache,
158: * and returned. If it does exist, the cached version is returned
159: * and marked as the most recently found. If it was created,
160: * and the cache is full, then the oldest retrieved object is
161: * removed and cleaned up.
162: */
163: public Object get(Object key) {
164: Node n = (Node) this .keyToNode.get(key);
165: if (n == null) {
166: // must include the equals, because we're going to add
167: // another element to the list. An "if" statement would
168: // take roughly the same amount of time, but is less safe.
169: while (getSize() >= getMaxSize()) {
170: Node last = removeTail();
171: this .keyToNode.remove(last.key);
172: cleanup(last);
173: ++this .overflowCount;
174: }
175: n = createObject(key);
176: this .keyToNode.put(key, n);
177: }
178: freshenNode(n);
179: return n.value;
180: }
181:
182: /**
183: * Retrieves the current number of elements in the cache.
184: *
185: * @return the current size of the cache.
186: */
187: public int getSize() {
188: //System.out.println("size = "+this.keyToNode.size());
189: return this .keyToNode.size();
190: }
191:
192: /**
193: * Retrieves the maximum cache size.
194: *
195: * @return the maximum cache size.
196: */
197: public int getMaxSize() {
198: //System.out.println("maxsize = "+this.maxSize);
199: return this .maxSize;
200: }
201:
202: /**
203: * Retrieves the metric that corresponds to the number of objects
204: * that were removed from the cache.
205: *
206: * @return the overflow count.
207: */
208: public int getOverflowCount() {
209: return this .overflowCount;
210: }
211:
212: /**
213: * Resets the overflow count metric.
214: */
215: public void resetOverflowCount() {
216: this .overflowCount = 0;
217: }
218:
219: /**
220: * Cleans out the data structure, calling the clean-up on all items.
221: * The manager and max size will not be changed, nor will the overflow
222: * count.
223: */
224: public void clear()
225: {
226: this .head = null;
227: this .tail = null;
228: Enumeration enum = this .keyToNode.keys();
229: while (enum.hasMoreElements())
230: {
231: Object key = enum.nextElement();
232: Node n = (Node)this .keyToNode.remove( key );
233: cleanup( n );
234: }
235: }
236:
237: //-----------------------------------------------------
238: // Protected methods
239:
240: /**
241: * Generates an Object for the cache, but does not add it to the
242: * hashtable or lists.
243: */
244: private Node createObject(Object key) {
245: Object o = this .mgr.createObject(key);
246: Node n = new Node(key, o);
247: return n;
248: }
249:
250: /**
251: * Call the cleanup on the given node.
252: */
253: private void cleanup(Node n) {
254: this .mgr.cleanUpObject(n.key, n.value);
255: }
256:
257: /**
258: * Removes the tail node. If the list is empty or has 1 element, then an
259: * IllegalStateException is thrown.
260: *
261: * @return the last node in the list.
262: */
263: private Node removeTail() {
264: /*
265: // temp test code
266: if (this.tail == null)
267: {
268: throw new IllegalStateException("list is empty");
269: }
270: */
271:
272: Node n = this .tail;
273: this .tail = n.prev;
274: n.prev = null;
275: tail.next = null;
276:
277: /*
278: // temp test code
279: if (this.tail == null)
280: {
281: throw new IllegalStateException("invalid tail setup: size < 1");
282: }
283: if (n.next != null)
284: {
285: throw new IllegalStateException("next of old tail node "+n+" is not null, but "+n.next);
286: }
287: */
288:
289: return n;
290: }
291:
292: /**
293: * Move the given node to the top of the list. This works even if the
294: * given node is not in the list.
295: */
296: private void freshenNode(Node n) {
297: /*
298: // temp test code
299: if (n == null)
300: {
301: throw new IllegalArgumentException("no null args");
302: }
303: */
304:
305: if (n == this .head) {
306: // we're done!
307: return;
308: }
309:
310: if (this .head == null) {
311: // n's next and prev better be null!
312: this .head = n;
313: this .tail = n;
314:
315: /*
316: // temp test code
317: if (n.next != null || n.prev != null)
318: {
319: throw new IllegalStateException("new head&tail node "+n+" next is "+n.next+", prev is "+n.prev);
320: }
321: */
322: } else {
323: // setup tail, and next and prev of n's next and prev
324: if (n.prev != null) {
325: n.prev.next = n.next;
326: }
327:
328: if (n.next != null) {
329: n.next.prev = n.prev;
330: } else if (this .tail == n) {
331: this .tail = n.prev;
332:
333: // n.prev better not be null! that should have been trapped
334: // above.
335: /*
336: // temp test code
337: if (n.prev == null)
338: {
339: throw new IllegalStateException("new tail's previous is null!");
340: }
341: */
342: }
343:
344: n.prev = null;
345:
346: // the head is going to be not null, due to the if block above
347: this .head.prev = n;
348: n.next = this .head;
349:
350: this .head = n;
351: }
352: }
353:
354: /* Integrety check. Uncomment when doing testing.
355: protected void printChain()
356: {
357: if (this.head == null)
358: {
359: System.out.println("[Empty chain]");
360: return;
361: }
362: Hashtable seen = new Hashtable();
363:
364: System.out.println("Chain:");
365: Node n = this.head;
366: while (n != null)
367: {
368: seen.put( n, new Object() );
369: System.out.println(" "+n);
370: Node n2 = n.next;
371: if (n2 != null && n2.prev != n)
372: {
373: throw new IllegalStateException("Bad back chain! next = "+n2+
374: ", but its prev = "+n2.prev);
375: }
376: else
377: if (n2 == null && n != this.tail)
378: {
379: throw new IllegalStateException("Broken Chain! next is null but tail isn't this node (it's "+this.tail+")");
380: }
381: else
382: if (n2 != null && seen.contains( n2 ))
383: {
384: throw new IllegalStateException("node "+n2+" in the list twice.");
385: }
386: if (n2 != null && n == this.tail)
387: {
388: throw new IllegalStateException("Tail in a loop!");
389: }
390: n = n2;
391: }
392: System.out.println("[End chain]");
393: }
394: */
395: }
|