001: package com.quadcap.util.collections;
002:
003: /* Copyright 1997 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.IOException;
042: import java.io.PrintWriter;
043:
044: import java.util.Enumeration;
045: import java.util.Hashtable;
046:
047: import com.quadcap.util.Debug;
048: import com.quadcap.util.DList;
049: import com.quadcap.util.DListItem;
050: import com.quadcap.util.ListException;
051:
052: /**
053: * This class manages a number of buffers on an underlying store.
054: * <p>
055: *
056: * What about write-through policies?
057: *
058: * @author Stan Bailes
059: */
060: public abstract class Cache {
061: Object store;
062: Object lock;
063: int size;
064:
065: Hashtable t;
066: DList lru = new DList();
067:
068: /**
069: * Initialize the cache.
070: *
071: * @param s the underlying store
072: * @param size the size of the cache
073: */
074: public void init(Object store, int size) {
075: this .store = store;
076: this .size = size;
077: this .lock = this ;
078: lru.resize(size);
079: t = new Hashtable();
080: }
081:
082: /**
083: * Specify the lock-object to be used to synchronize access to the
084: * cache. If the lock isn't specified, it defaults to the cache
085: * object itself.
086: *
087: * @param lock the lock object
088: */
089: public void setLock(Object lock) {
090: this .lock = lock;
091: }
092:
093: /**
094: * Search the cache for the specified key and return the associated
095: * cache item if one was found. Otherwise, find a free cache item
096: * and initialize it from the underlying store.
097: *
098: * @param key the search key
099: * @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
133: || d != lru.head(); d = d.next) {
134: started = true;
135: Cacheable c = (Cacheable) d.obj;
136: if (c == null)
137: continue;
138: Object key = c.getKey();
139: Cacheable c1 = (Cacheable) t.get(key);
140: if (c1 != c) {
141: System.out
142: .println("lru item not in hashtable: "
143: + key);
144: }
145: s.put(key, c);
146: }
147: } catch (ListException e) {
148: Debug.print(e);
149: }
150:
151: // check that each item in the hashtable is actually in the lru
152: for (Enumeration e = t.keys(); e.hasMoreElements();) {
153: Object key = e.nextElement();
154: if (s.get(key) == null) {
155: System.out.println("hashtable item not in lru: "
156: + key);
157: }
158: }
159: }
160: }
161:
162: /**
163: * Get the specified object from the cache, if available; from the
164: * underlying store if not. In any case, the object (if found)
165: * should be in the cache after this call.<p>
166: *
167: * If the object isn't in the cache <b>OR</b> the underlying store,
168: * this method should return null, and the contents of both the cache
169: * and the underlying store should remain unchanged.<p>
170: *
171: * <b>This implementation doesn't change the underlying store, but
172: * the cache ends up holding a CacheItem with a null data component.</b>
173: * @param key the search key
174: * @param return the data associated with the key
175: */
176: public Object get(Object key) throws IOException {
177: Object data = null;
178: synchronized (lock) {
179: Cacheable c = getCacheable(key);
180: try {
181: data = c.getData();
182: } finally {
183: c.decrRefCount();
184: }
185: }
186: return data;
187: }
188:
189: /**
190: * Store the object in the cache. The object will be marked <i>dirty</i>,
191: * and will eventually be written back to the underlying store.
192: */
193: public void put(Object key, Object val) throws IOException {
194: synchronized (lock) {
195: Cacheable c = getCacheable(key);
196: try {
197: c.setData(val);
198: } finally {
199: c.decrRefCount();
200: }
201: }
202: }
203:
204: /**
205: * Factory to create an empty cache slot. Only a fixed number of
206: * cache slots should be created, and they should then be recycled,
207: * never destroyed.
208: */
209: abstract public Cacheable makeCacheable();
210:
211: /**
212: * Find a free cache slot. If necessary, seize an existing cache
213: * slot, with preference for the "least recently used" item.
214: * This function should only be called if the lock on the cache is
215: * held by this thread.
216: */
217: Cacheable getCacheable() throws IOException {
218: Cacheable c = null;
219: DListItem d = lru.tail();
220:
221: while (d != null) {
222: c = (Cacheable) d.obj;
223: if (c != null && c.getRefCount() > 0) {
224: if (d == lru.head()) {
225: show(new PrintWriter(Debug.debugStream));
226: throw new RuntimeException("no free cache item");
227: }
228: d = d.prev;
229: } else {
230: break; // 'c' contains the Cacheable we're looking for
231: }
232: }
233:
234: if (c == null) {
235: d.obj = c = makeCacheable();
236: c.setDListItem(d);
237: } else {
238: Object key = c.getKey();
239: if (key != null) {
240: //Debug.println("Cache: remove(" + key + ")");
241: t.remove(key);
242: }
243: if (c.isDirty())
244: c.flush();
245: }
246: return c;
247: }
248:
249: /**
250: * Flush all modified items back to the underlying store.
251: */
252: public void flush() throws IOException {
253: synchronized (lock) {
254: boolean started = false;
255: for (DListItem d = lru.head(); !started || d != lru.head(); d = d.next) {
256: started = true;
257: Cacheable c = (Cacheable) d.obj;
258: if (c != null) {
259: // XXX I'm not sure I should be synchronizing on this
260: // XXX abstract object here. Maybe let the implementing
261: // XXX class take care of it's own mutual exclusion.
262: // synchronized (c)
263: c.flush();
264: }
265: }
266: }
267: }
268:
269: public void show(PrintWriter os) {
270: synchronized (lock) {
271: lru.show(os, "\n");
272: }
273: }
274: }
|