001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.map;
018
019 import java.io.IOException;
020 import java.io.ObjectInputStream;
021 import java.io.ObjectOutputStream;
022 import java.io.Serializable;
023 import java.util.Map;
024
025 import org.apache.commons.collections.BoundedMap;
026
027 /**
028 * A <code>Map</code> implementation with a fixed maximum size which removes
029 * the least recently used entry if an entry is added when full.
030 * <p>
031 * The least recently used algorithm works on the get and put operations only.
032 * Iteration of any kind, including setting the value by iteration, does not
033 * change the order. Queries such as containsKey and containsValue or access
034 * via views also do not change the order.
035 * <p>
036 * The map implements <code>OrderedMap</code> and entries may be queried using
037 * the bidirectional <code>OrderedMapIterator</code>. The order returned is
038 * least recently used to most recently used. Iterators from map views can
039 * also be cast to <code>OrderedIterator</code> if required.
040 * <p>
041 * All the available iterators can be reset back to the start by casting to
042 * <code>ResettableIterator</code> and calling <code>reset()</code>.
043 * <p>
044 * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
045 * If you wish to use this map from multiple threads concurrently, you must use
046 * appropriate synchronization. The simplest approach is to wrap this map
047 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
048 * <code>NullPointerException</code>'s when accessed by concurrent threads.
049 *
050 * @since Commons Collections 3.0 (previously in main package v1.0)
051 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
052 *
053 * @author James Strachan
054 * @author Morgan Delagrange
055 * @author Stephen Colebourne
056 * @author Mike Pettypiece
057 * @author Mario Ivankovits
058 */
059 public class LRUMap
060 extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
061
062 /** Serialisation version */
063 private static final long serialVersionUID = -612114643488955218L;
064 /** Default maximum size */
065 protected static final int DEFAULT_MAX_SIZE = 100;
066
067 /** Maximum size */
068 private transient int maxSize;
069 /** Scan behaviour */
070 private boolean scanUntilRemovable;
071
072 /**
073 * Constructs a new empty map with a maximum size of 100.
074 */
075 public LRUMap() {
076 this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
077 }
078
079 /**
080 * Constructs a new, empty map with the specified maximum size.
081 *
082 * @param maxSize the maximum size of the map
083 * @throws IllegalArgumentException if the maximum size is less than one
084 */
085 public LRUMap(int maxSize) {
086 this(maxSize, DEFAULT_LOAD_FACTOR);
087 }
088
089 /**
090 * Constructs a new, empty map with the specified maximum size.
091 *
092 * @param maxSize the maximum size of the map
093 * @param scanUntilRemovable scan until a removeable entry is found, default false
094 * @throws IllegalArgumentException if the maximum size is less than one
095 * @since Commons Collections 3.1
096 */
097 public LRUMap(int maxSize, boolean scanUntilRemovable) {
098 this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
099 }
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 }