LRUMap


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