1: /*
2: * Licensed to the Apache Software Foundation (ASF) under one or more
3: * contributor license agreements. See the NOTICE file distributed with
4: * this work for additional information regarding copyright ownership.
5: * The ASF licenses this file to You under the Apache License, Version 2.0
6: * (the "License"); you may not use this file except in compliance with
7: * the License. You may obtain a copy of the License at
8: *
9: * http://www.apache.org/licenses/LICENSE-2.0
10: *
11: * Unless required by applicable law or agreed to in writing, software
12: * distributed under the License is distributed on an "AS IS" BASIS,
13: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14: * See the License for the specific language governing permissions and
15: * limitations under the License.
16: */
17: package org.apache.commons.collections.map;
18:
19: import java.io.IOException;
20: import java.io.ObjectInputStream;
21: import java.io.ObjectOutputStream;
22: import java.io.Serializable;
23: import java.util.Map;
24:
25: import org.apache.commons.collections.BoundedMap;
26:
27: /**
28: * A <code>Map</code> implementation with a fixed maximum size which removes
29: * the least recently used entry if an entry is added when full.
30: * <p>
31: * The least recently used algorithm works on the get and put operations only.
32: * Iteration of any kind, including setting the value by iteration, does not
33: * change the order. Queries such as containsKey and containsValue or access
34: * via views also do not change the order.
35: * <p>
36: * The map implements <code>OrderedMap</code> and entries may be queried using
37: * the bidirectional <code>OrderedMapIterator</code>. The order returned is
38: * least recently used to most recently used. Iterators from map views can
39: * also be cast to <code>OrderedIterator</code> if required.
40: * <p>
41: * All the available iterators can be reset back to the start by casting to
42: * <code>ResettableIterator</code> and calling <code>reset()</code>.
43: * <p>
44: * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
45: * If you wish to use this map from multiple threads concurrently, you must use
46: * appropriate synchronization. The simplest approach is to wrap this map
47: * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 48: * <code>NullPointerException</code>'s when accessed by concurrent threads.
49: *
50: * @since Commons Collections 3.0 (previously in main package v1.0)
51: * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
52: *
53: * @author James Strachan
54: * @author Morgan Delagrange
55: * @author Stephen Colebourne
56: * @author Mike Pettypiece
57: * @author Mario Ivankovits
58: */
59: public class LRUMap
60: extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable { 61:
62: /** Serialisation version */
63: private static final long serialVersionUID = -612114643488955218L;
64: /** Default maximum size */
65: protected static final int DEFAULT_MAX_SIZE = 100;
66:
67: /** Maximum size */
68: private transient int maxSize;
69: /** Scan behaviour */
70: private boolean scanUntilRemovable;
71:
72: /**
73: * Constructs a new empty map with a maximum size of 100.
74: */
75: public LRUMap() { 76: this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
77: }
78:
79: /**
80: * Constructs a new, empty map with the specified maximum size.
81: *
82: * @param maxSize the maximum size of the map
83: * @throws IllegalArgumentException if the maximum size is less than one
84: */
85: public LRUMap(int maxSize) { 86: this(maxSize, DEFAULT_LOAD_FACTOR);
87: }
88:
89: /**
90: * Constructs a new, empty map with the specified maximum size.
91: *
92: * @param maxSize the maximum size of the map
93: * @param scanUntilRemovable scan until a removeable entry is found, default false
94: * @throws IllegalArgumentException if the maximum size is less than one
95: * @since Commons Collections 3.1
96: */
97: public LRUMap(int maxSize, boolean scanUntilRemovable) { 98: this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
99: }
100:
101: /**
102: * Constructs a new, empty map with the specified initial capacity and
103: * load factor.
104: *
105: * @param maxSize the maximum size of the map, -1 for no limit,
106: * @param loadFactor the load factor
107: * @throws IllegalArgumentException if the maximum size is less than one
108: * @throws IllegalArgumentException if the load factor is less than zero
109: */
110: public LRUMap(int maxSize, float loadFactor) { 111: this(maxSize, loadFactor, false);
112: }
113:
114: /**
115: * Constructs a new, empty map with the specified initial capacity and
116: * load factor.
117: *
118: * @param maxSize the maximum size of the map, -1 for no limit,
119: * @param loadFactor the load factor
120: * @param scanUntilRemovable scan until a removeable entry is found, default false
121: * @throws IllegalArgumentException if the maximum size is less than one
122: * @throws IllegalArgumentException if the load factor is less than zero
123: * @since Commons Collections 3.1
124: */
125: public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) { 126: super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
127: if (maxSize < 1) { 128: throw new IllegalArgumentException("LRUMap max size must be greater than 0"); 129: }
130: this.maxSize = maxSize;
131: this.scanUntilRemovable = scanUntilRemovable;
132: }
133:
134: /**
135: * Constructor copying elements from another map.
136: * <p>
137: * The maximum size is set from the map's size.
138: *
139: * @param map the map to copy
140: * @throws NullPointerException if the map is null
141: * @throws IllegalArgumentException if the map is empty
142: */
143: public LRUMap(Map map) { 144: this(map, false);
145: }
146:
147: /**
148: * Constructor copying elements from another map.
149: * <p/>
150: * The maximum size is set from the map's size.
151: *
152: * @param map the map to copy
153: * @param scanUntilRemovable scan until a removeable entry is found, default false
154: * @throws NullPointerException if the map is null
155: * @throws IllegalArgumentException if the map is empty
156: * @since Commons Collections 3.1
157: */
158: public LRUMap(Map map, boolean scanUntilRemovable) { 159: this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
160: putAll(map);
161: }
162:
163: //-----------------------------------------------------------------------
164: /**
165: * Gets the value mapped to the key specified.
166: * <p>
167: * This operation changes the position of the key in the map to the
168: * most recently used position (first).
169: *
170: * @param key the key
171: * @return the mapped value, null if no match
172: */
173: public Object get(Object key) { 174: LinkEntry entry = (LinkEntry) getEntry(key);
175: if (entry == null) { 176: return null;
177: }
178: moveToMRU(entry);
179: return entry.getValue();
180: }
181:
182: //-----------------------------------------------------------------------
183: /**
184: * Moves an entry to the MRU position at the end of the list.
185: * <p>
186: * This implementation moves the updated entry to the end of the list.
187: *
188: * @param entry the entry to update
189: */
190: protected void moveToMRU(LinkEntry entry) { 191: if (entry.after != header) { 192: modCount++;
193: // remove
194: entry.before.after = entry.after;
195: entry.after.before = entry.before;
196: // add first
197: entry.after = header;
198: entry.before = header.before;
199: header.before.after = entry;
200: header.before = entry;
201: } else if (entry == header) { 202: throw new IllegalStateException("Can't move header to MRU" + 203: " (please report this to commons-dev@jakarta.apache.org)");
204: }
205: }
206:
207: /**
208: * Updates an existing key-value mapping.
209: * <p>
210: * This implementation moves the updated entry to the top of the list
211: * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}. 212: *
213: * @param entry the entry to update
214: * @param newValue the new value to store
215: */
216: protected void updateEntry(HashEntry entry, Object newValue) { 217: moveToMRU((LinkEntry) entry); // handles modCount
218: entry.setValue(newValue);
219: }
220:
221: /**
222: * Adds a new key-value mapping into this map.
223: * <p>
224: * This implementation checks the LRU size and determines whether to
225: * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}. 226: * <p>
227: * From Commons Collections 3.1 this method uses {@link #isFull()} rather 228: * than accessing <code>size</code> and <code>maxSize</code> directly.
229: * It also handles the scanUntilRemovable functionality.
230: *
231: * @param hashIndex the index into the data array to store at
232: * @param hashCode the hash code of the key to add
233: * @param key the key to add
234: * @param value the value to add
235: */
236: protected void addMapping(int hashIndex, int hashCode, Object key, Object value) { 237: if (isFull()) { 238: LinkEntry reuse = header.after;
239: boolean removeLRUEntry = false;
240: if (scanUntilRemovable) { 241: while (reuse != header && reuse != null) { 242: if (removeLRU(reuse)) { 243: removeLRUEntry = true;
244: break;
245: }
246: reuse = reuse.after;
247: }
248: if (reuse == null) { 249: throw new IllegalStateException(
250: "Entry.after=null, header.after" + header.after + " header.before" + header.before +
251: " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
252: " Please check that your keys are immutable, and that you have used synchronization properly." +
253: " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
254: }
255: } else { 256: removeLRUEntry = removeLRU(reuse);
257: }
258:
259: if (removeLRUEntry) { 260: if (reuse == null) { 261: throw new IllegalStateException(
262: "reuse=null, header.after=" + header.after + " header.before" + header.before +
263: " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
264: " Please check that your keys are immutable, and that you have used synchronization properly." +
265: " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
266: }
267: reuseMapping(reuse, hashIndex, hashCode, key, value);
268: } else { 269: super.addMapping(hashIndex, hashCode, key, value);
270: }
271: } else { 272: super.addMapping(hashIndex, hashCode, key, value);
273: }
274: }
275:
276: /**
277: * Reuses an entry by removing it and moving it to a new place in the map.
278: * <p>
279: * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}. 280: *
281: * @param entry the entry to reuse
282: * @param hashIndex the index into the data array to store at
283: * @param hashCode the hash code of the key to add
284: * @param key the key to add
285: * @param value the value to add
286: */
287: protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) { 288: // find the entry before the entry specified in the hash table
289: // remember that the parameters (except the first) refer to the new entry,
290: // not the old one
291: try { 292: int removeIndex = hashIndex(entry.hashCode, data.length);
293: HashEntry[] tmp = data; // may protect against some sync issues
294: HashEntry loop = tmp[removeIndex];
295: HashEntry previous = null;
296: while (loop != entry && loop != null) { 297: previous = loop;
298: loop = loop.next;
299: }
300: if (loop == null) { 301: throw new IllegalStateException(
302: "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
303: " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
304: " Please check that your keys are immutable, and that you have used synchronization properly." +
305: " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
306: }
307:
308: // reuse the entry
309: modCount++;
310: removeEntry(entry, removeIndex, previous);
311: reuseEntry(entry, hashIndex, hashCode, key, value);
312: addEntry(entry, hashIndex);
313: } catch (NullPointerException ex) { 314: throw new IllegalStateException(
315: "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
316: " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
317: " Please check that your keys are immutable, and that you have used synchronization properly." +
318: " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
319: }
320: }
321:
322: /**
323: * Subclass method to control removal of the least recently used entry from the map.
324: * <p>
325: * This method exists for subclasses to override. A subclass may wish to
326: * provide cleanup of resources when an entry is removed. For example:
327: * <pre>
328: * protected boolean removeLRU(LinkEntry entry) { 329: * releaseResources(entry.getValue()); // release resources held by entry
330: * return true; // actually delete entry
331: * }
332: * </pre>
333: * <p>
334: * Alternatively, a subclass may choose to not remove the entry or selectively
335: * keep certain LRU entries. For example:
336: * <pre>
337: * protected boolean removeLRU(LinkEntry entry) { 338: * if (entry.getKey().toString().startsWith("System.")) { 339: * return false; // entry not removed from LRUMap
340: * } else { 341: * return true; // actually delete entry
342: * }
343: * }
344: * </pre>
345: * The effect of returning false is dependent on the scanUntilRemovable flag.
346: * If the flag is true, the next LRU entry will be passed to this method and so on
347: * until one returns false and is removed, or every entry in the map has been passed.
348: * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
349: * <p>
350: * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
351: * This is fixed in version 3.1 onwards.
352: *
353: * @param entry the entry to be removed
354: */
355: protected boolean removeLRU(LinkEntry entry) { 356: return true;
357: }
358:
359: //-----------------------------------------------------------------------
360: /**
361: * Returns true if this map is full and no new mappings can be added.
362: *
363: * @return <code>true</code> if the map is full
364: */
365: public boolean isFull() { 366: return (size >= maxSize);
367: }
368:
369: /**
370: * Gets the maximum size of the map (the bound).
371: *
372: * @return the maximum number of elements the map can hold
373: */
374: public int maxSize() { 375: return maxSize;
376: }
377:
378: /**
379: * Whether this LRUMap will scan until a removable entry is found when the
380: * map is full.
381: *
382: * @return true if this map scans
383: * @since Commons Collections 3.1
384: */
385: public boolean isScanUntilRemovable() { 386: return scanUntilRemovable;
387: }
388:
389: //-----------------------------------------------------------------------
390: /**
391: * Clones the map without cloning the keys or values.
392: *
393: * @return a shallow clone
394: */
395: public Object clone() { 396: return super.clone();
397: }
398:
399: /**
400: * Write the map out using a custom routine.
401: */
402: private void writeObject(ObjectOutputStream out) throws IOException { 403: out.defaultWriteObject();
404: doWriteObject(out);
405: }
406:
407: /**
408: * Read the map in using a custom routine.
409: */
410: private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 411: in.defaultReadObject();
412: doReadObject(in);
413: }
414:
415: /**
416: * Writes the data necessary for <code>put()</code> to work in deserialization.
417: */
418: protected void doWriteObject(ObjectOutputStream out) throws IOException { 419: out.writeInt(maxSize);
420: super.doWriteObject(out);
421: }
422:
423: /**
424: * Reads the data necessary for <code>put()</code> to work in the superclass.
425: */
426: protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 427: maxSize = in.readInt();
428: super.doReadObject(in);
429: }
430:
431: }