Cache


1   /**
2    * com.mckoi.util.Cache  21 Mar 1998
3    *
4    * Mckoi SQL Database ( http://www.mckoi.com/database )
5    * Copyright (C) 2000, 2001, 2002  Diehl and Associates, Inc.
6    *
7    * This program is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * Version 2 as published by the Free Software Foundation.
10   *
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License Version 2 for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * Version 2 along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19   *
20   * Change Log:
21   * 
22   * 
23   */
24  
25  package com.mckoi.util;
26  
27  /**
28   * Represents a cache of Objects.  A Cache is similar to a Hashtable, in that
29   * you can 'add' and 'get' objects from the container given some key.  However
30   * a cache may remove objects from the container when it becomes too full.
31   * <p>
32   * The cache scheme uses a doubly linked-list hashtable.  The most recently
33   * accessed objects are moved to the start of the list.  The end elements in
34   * the list are wiped if the cache becomes too full.
35   * <p>
36   * @author Tobias Downer
37   */
38  
39  public class Cache {
40  
41    /**
42     * The maximum number of DataCell objects that can be stored in the cache
43     * at any one time.
44     */
45    private int max_cache_size;
46  
47    /**
48     * The current cache size.
49     */
50    private int current_cache_size;
51  
52    /**
53     * The number of nodes that should be left available when the cache becomes
54     * too full and a clean up operation occurs.
55     */
56    private int wipe_to;
57  
58    /**
59     * The array of ListNode objects arranged by hashing value.
60     */
61    private final ListNode[] node_hash;
62  
63    /**
64     * A pointer to the start of the list.
65     */
66    private ListNode list_start;
67  
68    /**
69     * A pointer to the end of the list.
70     */
71    private ListNode list_end;
72  
73    /**
74     * The Constructors.  It takes a maximum size the cache can grow to, and the
75     * percentage of the cache that is wiped when it becomes too full.
76     */
77    public Cache(int hash_size, int max_size, int clean_percentage) {
78      if (clean_percentage >= 85) {
79        throw new RuntimeException  (
80                  "Can't set to wipe more than 85% of the cache during clean.");
81      }
82      max_cache_size = max_size;
83      current_cache_size = 0;
84      wipe_to = max_size - ((clean_percentage * max_size) / 100);
85  
86      node_hash = new ListNode[hash_size];
87  
88      list_start = null;
89      list_end = null;
90    }
91  
92    public Cache(int max_size, int clean_percentage) {
93      this((max_size * 2) + 1, max_size, 20);
94    }
95  
96    public Cache(int max_size) {
97      this(max_size, 20);
98    }
99  
100   public Cache() {
101     this(50);
102   }
103 
104   /**
105    * Creates the HashMap object to store objects in this cache.  This is
106    * available to be overwritten.
107    * @deprecated
108    */
109   protected final int getHashSize() {
110     return (int) (max_cache_size * 2) + 1;
111   }
112 
113 
114   /**
115    * This is called whenever at Object is put into the cache.  This method
116    * should determine if the cache should be cleaned and call the clean
117    * method if appropriate.
118    */
119   protected void checkClean() {
120     // If we have reached maximum cache size, remove some elements from the
121     // end of the list
122     if (current_cache_size >= max_cache_size) {
123       clean();
124     }
125   }
126 
127   /**
128    * Returns true if the clean-up method that periodically cleans up the
129    * cache, should clean up more elements from the cache.
130    */
131   protected boolean shouldWipeMoreNodes() {
132     return (current_cache_size >= wipe_to);
133   }
134 
135   /**
136    * Notifies that the given object has been wiped from the cache by the
137    * clean up procedure.
138    */
139   protected void notifyWipingNode(Object   ob) {
140   }
141 
142   /**
143    * Notifies that some statistical information about the hash map has
144    * updated.  This should be used to compile statistical information about
145    * the number of walks a 'get' operation takes to retreive an entry from
146    * the hash.
147    * <p>
148    * This method is called every 8192 gets.
149    */
150   protected void notifyGetWalks(long total_walks, long total_get_ops) {
151   }
152 
153   // ---------- Hashing methods ----------
154 
155   /**
156    * Some statistics about the hashing algorithm.
157    */
158   private long total_gets = 0;
159   private long get_total = 0;
160 
161   /**
162    * Finds the node with the given key in the hash table and returns it.
163    * Returns 'null' if the value isn't in the hash table.
164    */
165   private ListNode getFromHash(Object   key) {
166     int hash = key.hashCode();
167     int index = (hash & 0x7FFFFFFF) % node_hash.length;
168     int get_count = 1;
169 
170     for (ListNode e = node_hash[index]; e != null; e = e.next_hash_entry) {
171       if (key.equals(e.key)) {
172         ++total_gets;
173         get_total += get_count;
174 
175         // Every 8192 gets, call the 'notifyGetWalks' method with the
176         // statistical info.
177         if ((total_gets & 0x01FFF) == 0) {
178           try {
179             notifyGetWalks(get_total, total_gets);
180             // Reset stats if we overflow on an int
181             if (get_total > (65536 * 65536)) {
182               get_total = 0;
183               total_gets = 0;
184             }
185           }
186           catch (Throwable   except) { /* ignore */ }
187         }
188 
189         // Bring to head if get_count > 1
190         if (get_count > 1) {
191           bringToHead(e);
192         }
193         return e;
194       }
195       ++get_count;
196     }
197     return null;
198   }
199 
200   /**
201    * Puts the node with the given key into the hash table.
202    */
203   private ListNode putIntoHash(ListNode node) {
204     // Makes sure the key is not already in the HashMap.
205     int hash = node.key.hashCode();
206     int index = (hash & 0x7FFFFFFF) % node_hash.length;
207     Object   key = node.key;
208     for (ListNode e = node_hash[index] ; e != null ; e = e.next_hash_entry) {
209       if (key.equals(e.key)) {
210         throw new Error  (
211                 "ListNode with same key already in the hash - remove first.");
212       }
213     }
214 
215     // Stick it in the hash list.
216     node.next_hash_entry = node_hash[index];
217     node_hash[index] = node;
218 
219     return node;
220   }
221 
222   /**
223    * Removes the given node from the hash table.  Returns 'null' if the entry
224    * wasn't found in the hash.
225    */
226   private ListNode removeFromHash(Object   key) {
227     // Makes sure the key is not already in the HashMap.
228     int hash = key.hashCode();
229     int index = (hash & 0x7FFFFFFF) % node_hash.length;
230     ListNode prev = null;
231     for (ListNode e = node_hash[index] ; e != null ; e = e.next_hash_entry) {
232       if (key.equals(e.key)) {
233         // Found entry, so remove it baby!
234         if (prev == null) {
235           node_hash[index] = e.next_hash_entry;
236         }
237         else {
238           prev.next_hash_entry = e.next_hash_entry;
239         }
240         return e;
241       }
242       prev = e;
243     }
244 
245     // Not found so return 'null'
246     return null;
247   }
248 
249   /**
250    * Clears the entire hashtable of all entries.
251    */
252   private void clearHash() {
253     for (int i = node_hash.length - 1; i >= 0; --i) {
254       node_hash[i] = null;
255     }
256   }
257 
258 
259   // ---------- Public cache methods ----------
260 
261   /**
262    * Returns the number of nodes that are currently being stored in the
263    * cache.
264    */
265   public final int nodeCount() {
266     return current_cache_size;
267   }
268 
269   /**
270    * Puts an Object into the cache with the given key.
271    */
272   public final void put(Object   key, Object   ob) {
273 
274     // Do we need to clean any cache elements out?
275     checkClean();
276 
277     // Check whether the given key is already in the Hashtable.
278 
279     ListNode node = getFromHash(key);
280     if (node == null) {
281 
282       node = createListNode();
283       node.key = key;
284       node.contents = ob;
285 
286       // Add node to top.
287       node.next = list_start;
288       node.previous = null;
289       list_start = node;
290       if (node.next == null) {
291         list_end = node;
292       }
293       else {
294         node.next.previous = node;
295       }
296 
297       ++current_cache_size;
298 
299       // Add node to key mapping
300       putIntoHash(node);
301 
302     }
303     else {
304 
305       // If key already in Hashtable, all we need to do is set node with
306       // the new contents and bring the node to the start of the list.
307 
308       node.contents = ob;
309       bringToHead(node);
310 
311     }
312 
313   }
314 
315   /**
316    * If the cache contains the cell with the given key, this method will
317    * return the object.  If the cell is not in the cache, it returns null.
318    */
319   public final Object   get(Object   key) {
320     ListNode node = getFromHash(key);
321 
322     if (node != null) {
323       // Bring node to start of list.
324 //      bringToHead(node);
325 
326       return node.contents;
327     }
328 
329     return null;
330   }
331 
332   /**
333    * Ensures that there is no cell with the given key in the cache.  This is
334    * useful for ensuring the cache does not contain out-dated information.
335    */
336   public final Object   remove(Object   key) {
337     ListNode node = removeFromHash(key);
338 
339     if (node != null) {
340       // If removed node at head.
341       if (list_start == node) {
342         list_start = node.next;
343         if (list_start != null) {
344           list_start.previous = null;
345         }
346         else {
347           list_end = null;
348         }
349       }
350       // If removed node at end.
351       else if (list_end == node) {
352         list_end = node.previous;
353         if (list_end != null) {
354           list_end.next = null;
355         }
356         else {
357           list_start = null;
358         }
359       }
360       else {
361         node.previous.next = node.next;
362         node.next.previous = node.previous;
363       }
364 
365       --current_cache_size;
366 
367       Object   contents = node.contents;
368 
369       // Set internals to null to ensure objects get gc'd
370       node.contents = null;
371       node.key = null;
372 
373       return contents;
374     }
375 
376     return null;
377   }
378 
379   /**
380    * Clear the cache of all the entries.
381    */
382   public void removeAll() {
383     if (current_cache_size != 0) {
384       current_cache_size = 0;
385       clearHash();
386     }
387     list_start = null;
388     list_end = null;
389   }
390 
391   public void clear() {
392     removeAll();
393   }
394 
395 
396   /**
397    * Creates a new ListNode.  If there is a free ListNode on the
398    * 'recycled_nodes' then it obtains one from there, else it creates a new
399    * blank one.
400    */
401   private final ListNode createListNode() {
402     return new ListNode();
403   }
404 
405   /**
406    * Cleans away some old elements in the cache.  This method walks from the
407    * end, back 'wipe_count' elements putting each object on the recycle stack.
408    *
409    * @returns the number entries that were cleaned.
410    */
411   protected final int clean() {
412 
413     ListNode node = list_end;
414     if (node == null) {
415       return 0;
416     }
417 
418     int actual_count = 0;
419     while (node != null && shouldWipeMoreNodes()) {
420       notifyWipingNode(node.contents);
421 
422       removeFromHash(node.key);
423       // Help garbage collector with old objects
424       node.contents = null;
425       node.key = null;
426       ListNode old_node = node;
427       // Move to previous node
428       node = node.previous;
429 
430       // Help the GC by clearing away the linked list nodes
431       old_node.next = null;
432       old_node.previous = null;
433 
434       --current_cache_size;
435       ++actual_count;
436     }
437 
438     if (node != null) {
439       node.next = null;
440       list_end = node;
441     }
442     else {
443       list_start = null;
444       list_end = null;
445     }
446 
447     return actual_count;
448   }
449 
450   /**
451    * Brings 'node' to the start of the list.  Only nodes at the end of the
452    * list are cleaned.
453    */
454   private final void bringToHead(ListNode node) {
455     if (list_start != node) {
456 
457       ListNode next_node = node.next;
458       ListNode previous_node = node.previous;
459 
460       node.next = list_start;
461       node.previous = null;
462       list_start = node;
463       node.next.previous = node;
464 
465       if (next_node != null) {
466         next_node.previous = previous_node;
467       }
468       else {
469         list_end = previous_node;
470       }
471       previous_node.next = next_node;
472 
473     }
474   }
475 
476 
477   // ---------- Inner classes ----------
478 
479   /**
480    * An element in the linked list structure.
481    */
482   static final class ListNode {
483 
484     /**
485      * Links to the next and previous nodes.  The ends of the list are 'null'
486      */
487     ListNode next;
488     ListNode previous;
489 
490     /**
491      * The next node in the hash link on this hash value, or 'null' if last
492      * hash entry.
493      */
494     ListNode next_hash_entry;
495 
496 
497     /**
498      * The key in the Hashtable for this object.
499      */
500     Object   key;
501 
502     /**
503      * The object contents for this element.
504      */
505     Object   contents;
506 
507   }
508 
509 }
510
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags