Cache


1   package com.quadcap.util.collections;
2   
3   /* Copyright 1997 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  import java.io.IOException  ;
42  import java.io.PrintWriter  ;
43  
44  import java.util.Enumeration  ;
45  import java.util.Hashtable  ;
46  
47  import com.quadcap.util.Debug;
48  import com.quadcap.util.DList;
49  import com.quadcap.util.DListItem;
50  import com.quadcap.util.ListException;
51  
52  /**
53   * This class manages a number of buffers on an underlying store.
54   * <p>
55   *
56   * What about write-through policies?
57   *
58   * @author Stan Bailes
59   */
60  public abstract class Cache {
61      Object            store;
62      Object            lock;
63      int             size;
64  
65      Hashtable                     t;
66      DList           lru = new DList();
67  
68      /**
69       * Initialize the cache.
70       *
71       * @param s the underlying store
72       * @param size the size of the cache
73       */
74      public void init(Object   store, int size) {
75      this.store = store;
76      this.size = size;
77      this.lock = this;
78      lru.resize(size);
79      t = new Hashtable  ();
80      }
81  
82      /**
83       * Specify the lock-object to be used to synchronize access to the
84       * cache.  If the lock isn't specified, it defaults to the cache
85       * object itself.
86       *
87       * @param lock the lock object
88       */
89      public void setLock(Object   lock) {
90      this.lock = lock;
91      }
92  
93      /**
94       * Search the cache for the specified key and return the associated
95       * cache item if one was found.  Otherwise, find a free cache item
96       * and initialize it from the underlying store.
97       *
98       * @param key the search key
99       * @return the cache item associated with the specified key.
100      */
101     public Cacheable getCacheable(Object   key) throws IOException   {
102     //Debug.println("getCacheable(" + key + ")");
103     synchronized (lock) {
104         // ---- check the cache first.
105         Cacheable c = (Cacheable)t.get(key);
106         if (c == null) {
107         // ---- if not in the cache, find a free cache slot and
108         // ----   fill it with this object.
109         c = getCacheable();
110         c.init(store, key);
111         t.put(key, c);
112         }
113 
114         // ---- move this object to the front of the LRU list.
115         try {
116         lru.moveFront(c.getDListItem());
117         } catch (ListException e) {
118         Debug.print(e);
119         }
120         c.incrRefCount();
121         //checkCache();
122         return c;
123     }
124     }
125 
126     void checkCache() {
127     synchronized (lock) {
128         Hashtable   s = new Hashtable  ();
129         // check that each item in the lru is in the hashtable
130         try {
131         boolean started = false;
132         for (DListItem d = lru.head(); !started || d != lru.head();
133              d = d.next) {
134             started = true;
135             Cacheable c = (Cacheable)d.obj;
136             if (c == null) continue;
137             Object   key = c.getKey();
138             Cacheable c1 = (Cacheable)t.get(key);
139             if (c1 != c) {
140             System.out.println("lru item not in hashtable: " +
141                        key);
142             }
143             s.put(key, c);
144         }
145         } catch (ListException e) {
146         Debug.print(e);
147         }
148     
149         // check that each item in the hashtable is actually in the lru
150         for (Enumeration   e = t.keys(); e.hasMoreElements(); ) {
151         Object   key = e.nextElement();
152         if (s.get(key) == null) {
153             System.out.println("hashtable item not in lru: " + key);
154         }
155         }
156     }
157     }
158 
159     /**
160      * Get the specified object from the cache, if available; from the
161      * underlying store if not.  In any case, the object (if found)
162      * should be in the cache after this call.<p>
163      *
164      * If the object isn't in the cache <b>OR</b> the underlying store,
165      * this method should return null, and the contents of both the cache
166      * and the underlying store should remain unchanged.<p>
167      *
168      * <b>This implementation doesn't change the underlying store, but
169      * the cache ends up holding a CacheItem with a null data component.</b>
170      * @param key the search key
171      * @param return the data associated with the key
172      */
173     public Object   get(Object   key) throws IOException   {
174     Object   data = null;
175     synchronized (lock) {
176         Cacheable c = getCacheable(key);
177         try {
178         data = c.getData();
179         } finally {
180         c.decrRefCount();
181         }
182     }
183     return data;
184     }
185 
186     /**
187      * Store the object in the cache.  The object will be marked <i>dirty</i>,
188      * and will eventually be written back to the underlying store.
189      */
190     public void put(Object   key, Object   val) throws IOException   {
191     synchronized (lock) {
192         Cacheable c = getCacheable(key);
193         try {
194         c.setData(val);
195         } finally {
196         c.decrRefCount();
197         }
198     }
199     }
200 
201     /**
202      * Factory to create an empty cache slot.  Only a fixed number of
203      * cache slots should be created, and they should then be recycled,
204      * never destroyed.
205      */
206     abstract public Cacheable makeCacheable();
207 
208     /**
209      * Find a free cache slot.  If necessary, seize an existing cache
210      * slot, with preference for the "least recently used" item.
211      * This function should only be called if the lock on the cache is
212      * held by this thread.
213      */
214     Cacheable getCacheable() throws IOException   {
215     Cacheable c = null;
216     DListItem d = lru.tail();
217         
218     while (d != null) {
219         c = (Cacheable)d.obj;       
220         if (c != null && c.getRefCount() > 0) {
221         if (d == lru.head()) {
222             show(new PrintWriter  (Debug.debugStream));
223             throw new RuntimeException  ("no free cache item");
224         }
225         d = d.prev;
226         } else {
227         break;  // 'c' contains the Cacheable we're looking for
228         }
229     }
230 
231     if (c == null) {
232         d.obj = c = makeCacheable();
233         c.setDListItem(d);
234     } else {
235         Object   key = c.getKey();
236         if (key != null) {
237         //Debug.println("Cache: remove(" + key + ")");
238         t.remove(key);
239         }
240         if (c.isDirty()) c.flush();
241     }
242     return c;
243     }
244 
245     /**
246      * Flush all modified items back to the underlying store.
247      */
248     public void flush() throws IOException   {
249     synchronized (lock) {
250         boolean started = false;
251         for (DListItem d = lru.head(); !started || d != lru.head();
252          d = d.next) {
253         started = true;
254         Cacheable c = (Cacheable)d.obj;
255         if (c != null) {
256             // XXX I'm not sure I should be synchronizing on this
257             // XXX abstract object here.  Maybe let the implementing
258             // XXX class take care of it's own mutual exclusion.
259             // synchronized (c)
260             c.flush();
261         }
262         }
263     }
264     }
265 
266     public void show(PrintWriter   os) {
267     synchronized (lock) {
268         lru.show(os, "\n");
269     }
270     }
271 }
272
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags