001: /*
002: * Copyright 2001-2005 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.map;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.util.Map;
023:
024: import org.apache.commons.collections.BoundedMap;
025:
026: /**
027: * A <code>Map</code> implementation with a fixed maximum size which removes
028: * the least recently used entry if an entry is added when full.
029: * <p>
030: * The least recently used algorithm works on the get and put operations only.
031: * Iteration of any kind, including setting the value by iteration, does not
032: * change the order. Queries such as containsKey and containsValue or access
033: * via views also do not change the order.
034: * <p>
035: * The map implements <code>OrderedMap</code> and entries may be queried using
036: * the bidirectional <code>OrderedMapIterator</code>. The order returned is
037: * least recently used to most recently used. Iterators from map views can
038: * also be cast to <code>OrderedIterator</code> if required.
039: * <p>
040: * All the available iterators can be reset back to the start by casting to
041: * <code>ResettableIterator</code> and calling <code>reset()</code>.
042: * <p>
043: * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
044: * If you wish to use this map from multiple threads concurrently, you must use
045: * appropriate synchronization. The simplest approach is to wrap this map
046: * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
047: * <code>NullPointerException</code>'s when accessed by concurrent threads.
048: *
049: * @since Commons Collections 3.0 (previously in main package v1.0)
050: * @version $Revision: 348299 $ $Date: 2005-11-22 23:51:45 +0000 (Tue, 22 Nov 2005) $
051: *
052: * @author James Strachan
053: * @author Morgan Delagrange
054: * @author Stephen Colebourne
055: * @author Mike Pettypiece
056: * @author Mario Ivankovits
057: */
058: public class LRUMap extends AbstractLinkedMap implements BoundedMap,
059: Serializable, Cloneable {
060:
061: /** Serialisation version */
062: private static final long serialVersionUID = -612114643488955218L;
063: /** Default maximum size */
064: protected static final int DEFAULT_MAX_SIZE = 100;
065:
066: /** Maximum size */
067: private transient int maxSize;
068: /** Scan behaviour */
069: private boolean scanUntilRemovable;
070:
071: /**
072: * Constructs a new empty map with a maximum size of 100.
073: */
074: public LRUMap() {
075: this (DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
076: }
077:
078: /**
079: * Constructs a new, empty map with the specified maximum size.
080: *
081: * @param maxSize the maximum size of the map
082: * @throws IllegalArgumentException if the maximum size is less than one
083: */
084: public LRUMap(int maxSize) {
085: this (maxSize, DEFAULT_LOAD_FACTOR);
086: }
087:
088: /**
089: * Constructs a new, empty map with the specified maximum size.
090: *
091: * @param maxSize the maximum size of the map
092: * @param scanUntilRemovable scan until a removeable entry is found, default false
093: * @throws IllegalArgumentException if the maximum size is less than one
094: * @since Commons Collections 3.1
095: */
096: public LRUMap(int maxSize, boolean scanUntilRemovable) {
097: this (maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
098: }
099:
100: /**
101: * Constructs a new, empty map with the specified initial capacity and
102: * load factor.
103: *
104: * @param maxSize the maximum size of the map, -1 for no limit,
105: * @param loadFactor the load factor
106: * @throws IllegalArgumentException if the maximum size is less than one
107: * @throws IllegalArgumentException if the load factor is less than zero
108: */
109: public LRUMap(int maxSize, float loadFactor) {
110: this (maxSize, loadFactor, false);
111: }
112:
113: /**
114: * Constructs a new, empty map with the specified initial capacity and
115: * load factor.
116: *
117: * @param maxSize the maximum size of the map, -1 for no limit,
118: * @param loadFactor the load factor
119: * @param scanUntilRemovable scan until a removeable entry is found, default false
120: * @throws IllegalArgumentException if the maximum size is less than one
121: * @throws IllegalArgumentException if the load factor is less than zero
122: * @since Commons Collections 3.1
123: */
124: public LRUMap(int maxSize, float loadFactor,
125: boolean scanUntilRemovable) {
126: super ((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
127: if (maxSize < 1) {
128: throw new IllegalArgumentException(
129: "LRUMap max size must be greater than 0");
130: }
131: this .maxSize = maxSize;
132: this .scanUntilRemovable = scanUntilRemovable;
133: }
134:
135: /**
136: * Constructor copying elements from another map.
137: * <p>
138: * The maximum size is set from the map's size.
139: *
140: * @param map the map to copy
141: * @throws NullPointerException if the map is null
142: * @throws IllegalArgumentException if the map is empty
143: */
144: public LRUMap(Map map) {
145: this (map, false);
146: }
147:
148: /**
149: * Constructor copying elements from another map.
150: * <p/>
151: * The maximum size is set from the map's size.
152: *
153: * @param map the map to copy
154: * @param scanUntilRemovable scan until a removeable entry is found, default false
155: * @throws NullPointerException if the map is null
156: * @throws IllegalArgumentException if the map is empty
157: * @since Commons Collections 3.1
158: */
159: public LRUMap(Map map, boolean scanUntilRemovable) {
160: this (map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
161: putAll(map);
162: }
163:
164: //-----------------------------------------------------------------------
165: /**
166: * Gets the value mapped to the key specified.
167: * <p>
168: * This operation changes the position of the key in the map to the
169: * most recently used position (first).
170: *
171: * @param key the key
172: * @return the mapped value, null if no match
173: */
174: public Object get(Object key) {
175: LinkEntry entry = (LinkEntry) getEntry(key);
176: if (entry == null) {
177: return null;
178: }
179: moveToMRU(entry);
180: return entry.getValue();
181: }
182:
183: //-----------------------------------------------------------------------
184: /**
185: * Moves an entry to the MRU position at the end of the list.
186: * <p>
187: * This implementation moves the updated entry to the end of the list.
188: *
189: * @param entry the entry to update
190: */
191: protected void moveToMRU(LinkEntry entry) {
192: if (entry.after != header) {
193: modCount++;
194: // remove
195: entry.before.after = entry.after;
196: entry.after.before = entry.before;
197: // add first
198: entry.after = header;
199: entry.before = header.before;
200: header.before.after = entry;
201: header.before = entry;
202: } else if (entry == header) {
203: throw new IllegalStateException(
204: "Can't move header to MRU"
205: + " (please report this to commons-dev@jakarta.apache.org)");
206: }
207: }
208:
209: /**
210: * Updates an existing key-value mapping.
211: * <p>
212: * This implementation moves the updated entry to the top of the list
213: * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
214: *
215: * @param entry the entry to update
216: * @param newValue the new value to store
217: */
218: protected void updateEntry(HashEntry entry, Object newValue) {
219: moveToMRU((LinkEntry) entry); // handles modCount
220: entry.setValue(newValue);
221: }
222:
223: /**
224: * Adds a new key-value mapping into this map.
225: * <p>
226: * This implementation checks the LRU size and determines whether to
227: * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
228: * <p>
229: * From Commons Collections 3.1 this method uses {@link #isFull()} rather
230: * than accessing <code>size</code> and <code>maxSize</code> directly.
231: * It also handles the scanUntilRemovable functionality.
232: *
233: * @param hashIndex the index into the data array to store at
234: * @param hashCode the hash code of the key to add
235: * @param key the key to add
236: * @param value the value to add
237: */
238: protected void addMapping(int hashIndex, int hashCode, Object key,
239: Object value) {
240: if (isFull()) {
241: LinkEntry reuse = header.after;
242: boolean removeLRUEntry = false;
243: if (scanUntilRemovable) {
244: while (reuse != header && reuse != null) {
245: if (removeLRU(reuse)) {
246: removeLRUEntry = true;
247: break;
248: }
249: reuse = reuse.after;
250: }
251: if (reuse == null) {
252: throw new IllegalStateException(
253: "Entry.after=null, header.after"
254: + header.after
255: + " header.before"
256: + header.before
257: + " key="
258: + key
259: + " value="
260: + value
261: + " size="
262: + size
263: + " maxSize="
264: + maxSize
265: + " Please check that your keys are immutable, and that you have used synchronization properly."
266: + " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
267: }
268: } else {
269: removeLRUEntry = removeLRU(reuse);
270: }
271:
272: if (removeLRUEntry) {
273: if (reuse == null) {
274: throw new IllegalStateException(
275: "reuse=null, header.after="
276: + header.after
277: + " header.before"
278: + header.before
279: + " key="
280: + key
281: + " value="
282: + value
283: + " size="
284: + size
285: + " maxSize="
286: + maxSize
287: + " Please check that your keys are immutable, and that you have used synchronization properly."
288: + " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
289: }
290: reuseMapping(reuse, hashIndex, hashCode, key, value);
291: } else {
292: super .addMapping(hashIndex, hashCode, key, value);
293: }
294: } else {
295: super .addMapping(hashIndex, hashCode, key, value);
296: }
297: }
298:
299: /**
300: * Reuses an entry by removing it and moving it to a new place in the map.
301: * <p>
302: * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
303: *
304: * @param entry the entry to reuse
305: * @param hashIndex the index into the data array to store at
306: * @param hashCode the hash code of the key to add
307: * @param key the key to add
308: * @param value the value to add
309: */
310: protected void reuseMapping(LinkEntry entry, int hashIndex,
311: int hashCode, Object key, Object value) {
312: // find the entry before the entry specified in the hash table
313: // remember that the parameters (except the first) refer to the new entry,
314: // not the old one
315: try {
316: int removeIndex = hashIndex(entry.hashCode, data.length);
317: HashEntry[] tmp = data; // may protect against some sync issues
318: HashEntry loop = tmp[removeIndex];
319: HashEntry previous = null;
320: while (loop != entry && loop != null) {
321: previous = loop;
322: loop = loop.next;
323: }
324: if (loop == null) {
325: throw new IllegalStateException(
326: "Entry.next=null, data[removeIndex]="
327: + data[removeIndex]
328: + " previous="
329: + previous
330: + " key="
331: + key
332: + " value="
333: + value
334: + " size="
335: + size
336: + " maxSize="
337: + maxSize
338: + " Please check that your keys are immutable, and that you have used synchronization properly."
339: + " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
340: }
341:
342: // reuse the entry
343: modCount++;
344: removeEntry(entry, removeIndex, previous);
345: reuseEntry(entry, hashIndex, hashCode, key, value);
346: addEntry(entry, hashIndex);
347: } catch (NullPointerException ex) {
348: throw new IllegalStateException(
349: "NPE, entry="
350: + entry
351: + " entryIsHeader="
352: + (entry == header)
353: + " key="
354: + key
355: + " value="
356: + value
357: + " size="
358: + size
359: + " maxSize="
360: + maxSize
361: + " Please check that your keys are immutable, and that you have used synchronization properly."
362: + " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
363: }
364: }
365:
366: /**
367: * Subclass method to control removal of the least recently used entry from the map.
368: * <p>
369: * This method exists for subclasses to override. A subclass may wish to
370: * provide cleanup of resources when an entry is removed. For example:
371: * <pre>
372: * protected boolean removeLRU(LinkEntry entry) {
373: * releaseResources(entry.getValue()); // release resources held by entry
374: * return true; // actually delete entry
375: * }
376: * </pre>
377: * <p>
378: * Alternatively, a subclass may choose to not remove the entry or selectively
379: * keep certain LRU entries. For example:
380: * <pre>
381: * protected boolean removeLRU(LinkEntry entry) {
382: * if (entry.getKey().toString().startsWith("System.")) {
383: * return false; // entry not removed from LRUMap
384: * } else {
385: * return true; // actually delete entry
386: * }
387: * }
388: * </pre>
389: * The effect of returning false is dependent on the scanUntilRemovable flag.
390: * If the flag is true, the next LRU entry will be passed to this method and so on
391: * until one returns false and is removed, or every entry in the map has been passed.
392: * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
393: * <p>
394: * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
395: * This is fixed in version 3.1 onwards.
396: *
397: * @param entry the entry to be removed
398: */
399: protected boolean removeLRU(LinkEntry entry) {
400: return true;
401: }
402:
403: //-----------------------------------------------------------------------
404: /**
405: * Returns true if this map is full and no new mappings can be added.
406: *
407: * @return <code>true</code> if the map is full
408: */
409: public boolean isFull() {
410: return (size >= maxSize);
411: }
412:
413: /**
414: * Gets the maximum size of the map (the bound).
415: *
416: * @return the maximum number of elements the map can hold
417: */
418: public int maxSize() {
419: return maxSize;
420: }
421:
422: /**
423: * Whether this LRUMap will scan until a removable entry is found when the
424: * map is full.
425: *
426: * @return true if this map scans
427: * @since Commons Collections 3.1
428: */
429: public boolean isScanUntilRemovable() {
430: return scanUntilRemovable;
431: }
432:
433: //-----------------------------------------------------------------------
434: /**
435: * Clones the map without cloning the keys or values.
436: *
437: * @return a shallow clone
438: */
439: public Object clone() {
440: return super .clone();
441: }
442:
443: /**
444: * Write the map out using a custom routine.
445: */
446: private void writeObject(ObjectOutputStream out) throws IOException {
447: out.defaultWriteObject();
448: doWriteObject(out);
449: }
450:
451: /**
452: * Read the map in using a custom routine.
453: */
454: private void readObject(ObjectInputStream in) throws IOException,
455: ClassNotFoundException {
456: in.defaultReadObject();
457: doReadObject(in);
458: }
459:
460: /**
461: * Writes the data necessary for <code>put()</code> to work in deserialization.
462: */
463: protected void doWriteObject(ObjectOutputStream out)
464: throws IOException {
465: out.writeInt(maxSize);
466: super .doWriteObject(out);
467: }
468:
469: /**
470: * Reads the data necessary for <code>put()</code> to work in the superclass.
471: */
472: protected void doReadObject(ObjectInputStream in)
473: throws IOException, ClassNotFoundException {
474: maxSize = in.readInt();
475: super.doReadObject(in);
476: }
477:
478: }
|