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    }