001: /**
002: * JDBM LICENSE v1.00
003: *
004: * Redistribution and use of this software and associated documentation
005: * ("Software"), with or without modification, are permitted provided
006: * that the following conditions are met:
007: *
008: * 1. Redistributions of source code must retain copyright
009: * statements and notices. Redistributions must also contain a
010: * copy of this document.
011: *
012: * 2. Redistributions in binary form must reproduce the
013: * above copyright notice, this list of conditions and the
014: * following disclaimer in the documentation and/or other
015: * materials provided with the distribution.
016: *
017: * 3. The name "JDBM" must not be used to endorse or promote
018: * products derived from this Software without prior written
019: * permission of Cees de Groot. For written permission,
020: * please contact cg@cdegroot.com.
021: *
022: * 4. Products derived from this Software may not be called "JDBM"
023: * nor may "JDBM" appear in their names without prior written
024: * permission of Cees de Groot.
025: *
026: * 5. Due credit should be given to the JDBM Project
027: * (http://jdbm.sourceforge.net/).
028: *
029: * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
033: * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040: * OF THE POSSIBILITY OF SUCH DAMAGE.
041: *
042: * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
043: * Contributions are Copyright (C) 2000 by their associated contributors.
044: *
045: * $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
046: */package jdbm.helper;
047:
048: import java.util.Enumeration;
049: import java.util.Hashtable;
050: import java.util.Vector;
051:
052: /**
053: * MRU - Most Recently Used cache policy.
054: *
055: * Methods are *not* synchronized, so no concurrent access is allowed.
056: *
057: * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
058: * @version $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
059: */
060: public class MRU implements CachePolicy {
061:
062: /** Cached object hashtable */
063: Hashtable _hash = new Hashtable();
064:
065: /**
066: * Maximum number of objects in the cache.
067: */
068: int _max;
069:
070: /**
071: * Beginning of linked-list of cache elements. First entry is element
072: * which has been used least recently.
073: */
074: CacheEntry _first;
075:
076: /**
077: * End of linked-list of cache elements. Last entry is element
078: * which has been used most recently.
079: */
080: CacheEntry _last;
081:
082: /**
083: * Cache eviction listeners
084: */
085: Vector listeners = new Vector();
086:
087: /**
088: * Construct an MRU with a given maximum number of objects.
089: */
090: public MRU(int max) {
091: if (max <= 0) {
092: throw new IllegalArgumentException(
093: "MRU cache must contain at least one entry");
094: }
095: _max = max;
096: }
097:
098: /**
099: * Place an object in the cache.
100: */
101: public void put(Object key, Object value)
102: throws CacheEvictionException {
103: CacheEntry entry = (CacheEntry) _hash.get(key);
104: if (entry != null) {
105: entry.setValue(value);
106: touchEntry(entry);
107: } else {
108:
109: if (_hash.size() == _max) {
110: // purge and recycle entry
111: entry = purgeEntry();
112: entry.setKey(key);
113: entry.setValue(value);
114: } else {
115: entry = new CacheEntry(key, value);
116: }
117: addEntry(entry);
118: _hash.put(entry.getKey(), entry);
119: }
120: }
121:
122: /**
123: * Obtain an object in the cache
124: */
125: public Object get(Object key) {
126: CacheEntry entry = (CacheEntry) _hash.get(key);
127: if (entry != null) {
128: touchEntry(entry);
129: return entry.getValue();
130: } else {
131: return null;
132: }
133: }
134:
135: /**
136: * Remove an object from the cache
137: */
138: public void remove(Object key) {
139: CacheEntry entry = (CacheEntry) _hash.get(key);
140: if (entry != null) {
141: removeEntry(entry);
142: _hash.remove(entry.getKey());
143: }
144: }
145:
146: /**
147: * Remove all objects from the cache
148: */
149: public void removeAll() {
150: _hash = new Hashtable();
151: _first = null;
152: _last = null;
153: }
154:
155: /**
156: * Enumerate elements' values in the cache
157: */
158: public Enumeration elements() {
159: return new MRUEnumeration(_hash.elements());
160: }
161:
162: /**
163: * Add a listener to this cache policy
164: *
165: * @param listener Listener to add to this policy
166: */
167: public void addListener(CachePolicyListener listener) {
168: if (listener == null) {
169: throw new IllegalArgumentException(
170: "Cannot add null listener.");
171: }
172: if (!listeners.contains(listener)) {
173: listeners.addElement(listener);
174: }
175: }
176:
177: /**
178: * Remove a listener from this cache policy
179: *
180: * @param listener Listener to remove from this policy
181: */
182: public void removeListener(CachePolicyListener listener) {
183: listeners.removeElement(listener);
184: }
185:
186: /**
187: * Add a CacheEntry. Entry goes at the end of the list.
188: */
189: protected void addEntry(CacheEntry entry) {
190: if (_first == null) {
191: _first = entry;
192: _last = entry;
193: } else {
194: _last.setNext(entry);
195: entry.setPrevious(_last);
196: _last = entry;
197: }
198: }
199:
200: /**
201: * Remove a CacheEntry from linked list
202: */
203: protected void removeEntry(CacheEntry entry) {
204: if (entry == _first) {
205: _first = entry.getNext();
206: }
207: if (_last == entry) {
208: _last = entry.getPrevious();
209: }
210: CacheEntry previous = entry.getPrevious();
211: CacheEntry next = entry.getNext();
212: if (previous != null) {
213: previous.setNext(next);
214: }
215: if (next != null) {
216: next.setPrevious(previous);
217: }
218: entry.setPrevious(null);
219: entry.setNext(null);
220: }
221:
222: /**
223: * Place entry at the end of linked list -- Most Recently Used
224: */
225: protected void touchEntry(CacheEntry entry) {
226: if (_last == entry) {
227: return;
228: }
229: removeEntry(entry);
230: addEntry(entry);
231: }
232:
233: /**
234: * Purge least recently used object from the cache
235: *
236: * @return recyclable CacheEntry
237: */
238: protected CacheEntry purgeEntry() throws CacheEvictionException {
239: CacheEntry entry = _first;
240:
241: // Notify policy listeners first. if any of them throw an
242: // eviction exception, then the internal data structure
243: // remains untouched.
244: CachePolicyListener listener;
245: for (int i = 0; i < listeners.size(); i++) {
246: listener = (CachePolicyListener) listeners.elementAt(i);
247: listener.cacheObjectEvicted(entry.getValue());
248: }
249:
250: removeEntry(entry);
251: _hash.remove(entry.getKey());
252:
253: entry.setValue(null);
254: return entry;
255: }
256:
257: }
258:
259: /**
260: * State information for cache entries.
261: */
262: class CacheEntry {
263: private Object _key;
264: private Object _value;
265:
266: private CacheEntry _previous;
267: private CacheEntry _next;
268:
269: CacheEntry(Object key, Object value) {
270: _key = key;
271: _value = value;
272: }
273:
274: Object getKey() {
275: return _key;
276: }
277:
278: void setKey(Object obj) {
279: _key = obj;
280: }
281:
282: Object getValue() {
283: return _value;
284: }
285:
286: void setValue(Object obj) {
287: _value = obj;
288: }
289:
290: CacheEntry getPrevious() {
291: return _previous;
292: }
293:
294: void setPrevious(CacheEntry entry) {
295: _previous = entry;
296: }
297:
298: CacheEntry getNext() {
299: return _next;
300: }
301:
302: void setNext(CacheEntry entry) {
303: _next = entry;
304: }
305: }
306:
307: /**
308: * Enumeration wrapper to return actual user objects instead of
309: * CacheEntries.
310: */
311: class MRUEnumeration implements Enumeration {
312: Enumeration _enum;
313:
314: MRUEnumeration(Enumeration enume) {
315: _enum = enume;
316: }
317:
318: public boolean hasMoreElements() {
319: return _enum.hasMoreElements();
320: }
321:
322: public Object nextElement() {
323: CacheEntry entry = (CacheEntry) _enum.nextElement();
324: return entry.getValue();
325: }
326: }
|