KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > map > 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 JavaDoc;
19 import java.io.ObjectInputStream JavaDoc;
20 import java.io.ObjectOutputStream JavaDoc;
21 import java.io.Serializable JavaDoc;
22 import java.util.Map JavaDoc;
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 JavaDoc, Cloneable JavaDoc {
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 JavaDoc("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 JavaDoc 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 JavaDoc 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 JavaDoc get(Object JavaDoc 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 JavaDoc 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 JavaDoc key, Object JavaDoc 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 JavaDoc key, Object JavaDoc 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 JavaDoc clone() {
356         return super.clone();
357     }
358     
359     /**
360      * Write the map out using a custom routine.
361      */

362     private void writeObject(ObjectOutputStream JavaDoc out) throws IOException JavaDoc {
363         out.defaultWriteObject();
364         doWriteObject(out);
365     }
366
367     /**
368      * Read the map in using a custom routine.
369      */

370     private void readObject(ObjectInputStream JavaDoc in) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
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 JavaDoc out) throws IOException JavaDoc {
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 JavaDoc in) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
387         maxSize = in.readInt();
388         super.doReadObject(in);
389     }
390     
391 }
392
Popular Tags