001: /**
002: * com.mckoi.util.Cache 21 Mar 1998
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.util;
024:
025: /**
026: * Represents a cache of Objects. A Cache is similar to a Hashtable, in that
027: * you can 'add' and 'get' objects from the container given some key. However
028: * a cache may remove objects from the container when it becomes too full.
029: * <p>
030: * The cache scheme uses a doubly linked-list hashtable. The most recently
031: * accessed objects are moved to the start of the list. The end elements in
032: * the list are wiped if the cache becomes too full.
033: * <p>
034: * @author Tobias Downer
035: */
036:
037: public class Cache {
038:
039: /**
040: * The maximum number of DataCell objects that can be stored in the cache
041: * at any one time.
042: */
043: private int max_cache_size;
044:
045: /**
046: * The current cache size.
047: */
048: private int current_cache_size;
049:
050: /**
051: * The number of nodes that should be left available when the cache becomes
052: * too full and a clean up operation occurs.
053: */
054: private int wipe_to;
055:
056: /**
057: * The array of ListNode objects arranged by hashing value.
058: */
059: private final ListNode[] node_hash;
060:
061: /**
062: * A pointer to the start of the list.
063: */
064: private ListNode list_start;
065:
066: /**
067: * A pointer to the end of the list.
068: */
069: private ListNode list_end;
070:
071: /**
072: * The Constructors. It takes a maximum size the cache can grow to, and the
073: * percentage of the cache that is wiped when it becomes too full.
074: */
075: public Cache(int hash_size, int max_size, int clean_percentage) {
076: if (clean_percentage >= 85) {
077: throw new RuntimeException(
078: "Can't set to wipe more than 85% of the cache during clean.");
079: }
080: max_cache_size = max_size;
081: current_cache_size = 0;
082: wipe_to = max_size - ((clean_percentage * max_size) / 100);
083:
084: node_hash = new ListNode[hash_size];
085:
086: list_start = null;
087: list_end = null;
088: }
089:
090: public Cache(int max_size, int clean_percentage) {
091: this ((max_size * 2) + 1, max_size, 20);
092: }
093:
094: public Cache(int max_size) {
095: this (max_size, 20);
096: }
097:
098: public Cache() {
099: this (50);
100: }
101:
102: /**
103: * Creates the HashMap object to store objects in this cache. This is
104: * available to be overwritten.
105: * @deprecated
106: */
107: protected final int getHashSize() {
108: return (int) (max_cache_size * 2) + 1;
109: }
110:
111: /**
112: * This is called whenever at Object is put into the cache. This method
113: * should determine if the cache should be cleaned and call the clean
114: * method if appropriate.
115: */
116: protected void checkClean() {
117: // If we have reached maximum cache size, remove some elements from the
118: // end of the list
119: if (current_cache_size >= max_cache_size) {
120: clean();
121: }
122: }
123:
124: /**
125: * Returns true if the clean-up method that periodically cleans up the
126: * cache, should clean up more elements from the cache.
127: */
128: protected boolean shouldWipeMoreNodes() {
129: return (current_cache_size >= wipe_to);
130: }
131:
132: /**
133: * Notifies that the given object has been wiped from the cache by the
134: * clean up procedure.
135: */
136: protected void notifyWipingNode(Object ob) {
137: }
138:
139: /**
140: * Notifies that some statistical information about the hash map has
141: * updated. This should be used to compile statistical information about
142: * the number of walks a 'get' operation takes to retreive an entry from
143: * the hash.
144: * <p>
145: * This method is called every 8192 gets.
146: */
147: protected void notifyGetWalks(long total_walks, long total_get_ops) {
148: }
149:
150: // ---------- Hashing methods ----------
151:
152: /**
153: * Some statistics about the hashing algorithm.
154: */
155: private long total_gets = 0;
156: private long get_total = 0;
157:
158: /**
159: * Finds the node with the given key in the hash table and returns it.
160: * Returns 'null' if the value isn't in the hash table.
161: */
162: private ListNode getFromHash(Object key) {
163: int hash = key.hashCode();
164: int index = (hash & 0x7FFFFFFF) % node_hash.length;
165: int get_count = 1;
166:
167: for (ListNode e = node_hash[index]; e != null; e = e.next_hash_entry) {
168: if (key.equals(e.key)) {
169: ++total_gets;
170: get_total += get_count;
171:
172: // Every 8192 gets, call the 'notifyGetWalks' method with the
173: // statistical info.
174: if ((total_gets & 0x01FFF) == 0) {
175: try {
176: notifyGetWalks(get_total, total_gets);
177: // Reset stats if we overflow on an int
178: if (get_total > (65536 * 65536)) {
179: get_total = 0;
180: total_gets = 0;
181: }
182: } catch (Throwable except) { /* ignore */
183: }
184: }
185:
186: // Bring to head if get_count > 1
187: if (get_count > 1) {
188: bringToHead(e);
189: }
190: return e;
191: }
192: ++get_count;
193: }
194: return null;
195: }
196:
197: /**
198: * Puts the node with the given key into the hash table.
199: */
200: private ListNode putIntoHash(ListNode node) {
201: // Makes sure the key is not already in the HashMap.
202: int hash = node.key.hashCode();
203: int index = (hash & 0x7FFFFFFF) % node_hash.length;
204: Object key = node.key;
205: for (ListNode e = node_hash[index]; e != null; e = e.next_hash_entry) {
206: if (key.equals(e.key)) {
207: throw new Error(
208: "ListNode with same key already in the hash - remove first.");
209: }
210: }
211:
212: // Stick it in the hash list.
213: node.next_hash_entry = node_hash[index];
214: node_hash[index] = node;
215:
216: return node;
217: }
218:
219: /**
220: * Removes the given node from the hash table. Returns 'null' if the entry
221: * wasn't found in the hash.
222: */
223: private ListNode removeFromHash(Object key) {
224: // Makes sure the key is not already in the HashMap.
225: int hash = key.hashCode();
226: int index = (hash & 0x7FFFFFFF) % node_hash.length;
227: ListNode prev = null;
228: for (ListNode e = node_hash[index]; e != null; e = e.next_hash_entry) {
229: if (key.equals(e.key)) {
230: // Found entry, so remove it baby!
231: if (prev == null) {
232: node_hash[index] = e.next_hash_entry;
233: } else {
234: prev.next_hash_entry = e.next_hash_entry;
235: }
236: return e;
237: }
238: prev = e;
239: }
240:
241: // Not found so return 'null'
242: return null;
243: }
244:
245: /**
246: * Clears the entire hashtable of all entries.
247: */
248: private void clearHash() {
249: for (int i = node_hash.length - 1; i >= 0; --i) {
250: node_hash[i] = null;
251: }
252: }
253:
254: // ---------- Public cache methods ----------
255:
256: /**
257: * Returns the number of nodes that are currently being stored in the
258: * cache.
259: */
260: public final int nodeCount() {
261: return current_cache_size;
262: }
263:
264: /**
265: * Puts an Object into the cache with the given key.
266: */
267: public final void put(Object key, Object ob) {
268:
269: // Do we need to clean any cache elements out?
270: checkClean();
271:
272: // Check whether the given key is already in the Hashtable.
273:
274: ListNode node = getFromHash(key);
275: if (node == null) {
276:
277: node = createListNode();
278: node.key = key;
279: node.contents = ob;
280:
281: // Add node to top.
282: node.next = list_start;
283: node.previous = null;
284: list_start = node;
285: if (node.next == null) {
286: list_end = node;
287: } else {
288: node.next.previous = node;
289: }
290:
291: ++current_cache_size;
292:
293: // Add node to key mapping
294: putIntoHash(node);
295:
296: } else {
297:
298: // If key already in Hashtable, all we need to do is set node with
299: // the new contents and bring the node to the start of the list.
300:
301: node.contents = ob;
302: bringToHead(node);
303:
304: }
305:
306: }
307:
308: /**
309: * If the cache contains the cell with the given key, this method will
310: * return the object. If the cell is not in the cache, it returns null.
311: */
312: public final Object get(Object key) {
313: ListNode node = getFromHash(key);
314:
315: if (node != null) {
316: // Bring node to start of list.
317: // bringToHead(node);
318:
319: return node.contents;
320: }
321:
322: return null;
323: }
324:
325: /**
326: * Ensures that there is no cell with the given key in the cache. This is
327: * useful for ensuring the cache does not contain out-dated information.
328: */
329: public final Object remove(Object key) {
330: ListNode node = removeFromHash(key);
331:
332: if (node != null) {
333: // If removed node at head.
334: if (list_start == node) {
335: list_start = node.next;
336: if (list_start != null) {
337: list_start.previous = null;
338: } else {
339: list_end = null;
340: }
341: }
342: // If removed node at end.
343: else if (list_end == node) {
344: list_end = node.previous;
345: if (list_end != null) {
346: list_end.next = null;
347: } else {
348: list_start = null;
349: }
350: } else {
351: node.previous.next = node.next;
352: node.next.previous = node.previous;
353: }
354:
355: --current_cache_size;
356:
357: Object contents = node.contents;
358:
359: // Set internals to null to ensure objects get gc'd
360: node.contents = null;
361: node.key = null;
362:
363: return contents;
364: }
365:
366: return null;
367: }
368:
369: /**
370: * Clear the cache of all the entries.
371: */
372: public void removeAll() {
373: if (current_cache_size != 0) {
374: current_cache_size = 0;
375: clearHash();
376: }
377: list_start = null;
378: list_end = null;
379: }
380:
381: public void clear() {
382: removeAll();
383: }
384:
385: /**
386: * Creates a new ListNode. If there is a free ListNode on the
387: * 'recycled_nodes' then it obtains one from there, else it creates a new
388: * blank one.
389: */
390: private final ListNode createListNode() {
391: return new ListNode();
392: }
393:
394: /**
395: * Cleans away some old elements in the cache. This method walks from the
396: * end, back 'wipe_count' elements putting each object on the recycle stack.
397: *
398: * @returns the number entries that were cleaned.
399: */
400: protected final int clean() {
401:
402: ListNode node = list_end;
403: if (node == null) {
404: return 0;
405: }
406:
407: int actual_count = 0;
408: while (node != null && shouldWipeMoreNodes()) {
409: notifyWipingNode(node.contents);
410:
411: removeFromHash(node.key);
412: // Help garbage collector with old objects
413: node.contents = null;
414: node.key = null;
415: ListNode old_node = node;
416: // Move to previous node
417: node = node.previous;
418:
419: // Help the GC by clearing away the linked list nodes
420: old_node.next = null;
421: old_node.previous = null;
422:
423: --current_cache_size;
424: ++actual_count;
425: }
426:
427: if (node != null) {
428: node.next = null;
429: list_end = node;
430: } else {
431: list_start = null;
432: list_end = null;
433: }
434:
435: return actual_count;
436: }
437:
438: /**
439: * Brings 'node' to the start of the list. Only nodes at the end of the
440: * list are cleaned.
441: */
442: private final void bringToHead(ListNode node) {
443: if (list_start != node) {
444:
445: ListNode next_node = node.next;
446: ListNode previous_node = node.previous;
447:
448: node.next = list_start;
449: node.previous = null;
450: list_start = node;
451: node.next.previous = node;
452:
453: if (next_node != null) {
454: next_node.previous = previous_node;
455: } else {
456: list_end = previous_node;
457: }
458: previous_node.next = next_node;
459:
460: }
461: }
462:
463: // ---------- Inner classes ----------
464:
465: /**
466: * An element in the linked list structure.
467: */
468: static final class ListNode {
469:
470: /**
471: * Links to the next and previous nodes. The ends of the list are 'null'
472: */
473: ListNode next;
474: ListNode previous;
475:
476: /**
477: * The next node in the hash link on this hash value, or 'null' if last
478: * hash entry.
479: */
480: ListNode next_hash_entry;
481:
482: /**
483: * The key in the Hashtable for this object.
484: */
485: Object key;
486:
487: /**
488: * The object contents for this element.
489: */
490: Object contents;
491:
492: }
493:
494: }
|