KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > enhydra > dods > util > LRUMap


1 /* ====================================================================
2  *
3  * The Apache Software License, Version 1.1
4  *
5  * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution, if
21  * any, must include the following acknowlegement:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowlegement may appear in the software itself,
25  * if and wherever such third-party acknowlegements normally appear.
26  *
27  * 4. The names "The Jakarta Project", "Commons", and "Apache Software
28  * Foundation" must not be used to endorse or promote products derived
29  * from this software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache"
33  * nor may "Apache" appear in their names without prior written
34  * permission of the Apache Group.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation. For more
52  * information on the Apache Software Foundation, please see
53  * <http://www.apache.org/>.
54  *
55  */

56 package org.enhydra.dods.util;
57
58 import java.io.Externalizable JavaDoc;
59 import java.io.IOException JavaDoc;
60 import java.io.ObjectInput JavaDoc;
61 import java.io.ObjectOutput JavaDoc;
62 import java.util.Iterator JavaDoc;
63 import java.util.Map JavaDoc;
64
65 /**
66  * <p>
67  * An implementation of a Map which has a maximum size and uses a Least Recently Used
68  * algorithm to remove items from the Map when the maximum size is reached and new items are added.
69  * </p>
70  *
71  * <p>
72  * A synchronized version can be obtained with:
73  * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
74  * If it will be accessed by multiple threads, you _must_ synchronize access
75  * to this Map. Even concurrent get(Object) operations produce indeterminate
76  * behaviour.
77  * </p>
78  *
79  * <p>
80  * Unlike the Collections 1.0 version, this version of LRUMap does use a true
81  * LRU algorithm. The keys for all gets and puts are moved to the front of
82  * the list. LRUMap is now a subclass of SequencedHashMap, and the "LRU"
83  * key is now equivalent to LRUMap.getFirst().
84  * </p>
85  *
86  * @since 1.0
87  * @author <a HREF="mailto:jstrachan@apache.org">James Strachan</a>
88  * @author <a HREF="mailto:morgand@apache.org">Morgan Delagrange</a>
89  */

90 public class LRUMap extends SequencedHashMap implements Externalizable JavaDoc {
91
92     private int maximumSize = 0;
93
94     /**
95      * Default constructor, primarily for the purpose of
96      * de-externalization. This constructors sets a default
97      * cache with maximum size set to 0 (cache is not used at the moment) and
98      * with a default capacity (16) and load factor (0.75).
99      */

100     public LRUMap() {
101         super();
102     }
103
104     /**
105      * Creates a new LRUMap with a maximum capacity of <i>maxSize</i> and
106      * with a default capacity (16) and load factor (0.75). Once <i>maxSize</i>
107      * capacity is achieved, subsequent gets and puts will push keys out of
108      * the map.
109      *
110      * @param maxSize Maximum capacity of the LRUMap.
111      */

112     public LRUMap(int maxSize) {
113         this();
114         maximumSize = maxSize;
115     }
116
117     /**
118      * Create a new LRUMap with a default maximum capacity (0) and
119      * with the capacity <i>initialCapacity</i> and load factor <i>loadFactor</i>.
120      *
121      * @param initialCapacity The initial capacity.
122      * @param loadFactor The load factor.
123      */

124     public LRUMap(int initialCapacity, float loadFactor) {
125         super(initialCapacity, loadFactor);
126     }
127
128     /**
129      * Create a new LRUMap with a maximum capacity of <i>maxSize</i> and
130      * with the capacity <i>initialCapacity</i> and load factor <i>loadFactor</i>.
131      * Once <i>maxSize</i> capacity is achieved, subsequent gets and puts will
132      * push keys out of the map.
133      *
134      * @param initialCapacity The initial capacity.
135      * @param loadFactor The load factor.
136      * @param maxSize Maximum capacity of the LRUMap.
137      */

138
139     public LRUMap(int initialCapacity, float loadFactor, int maxSize) {
140         this(initialCapacity, loadFactor);
141         maximumSize = maxSize;
142     }
143
144    /**
145     * Create a new LRUMap with the same mappings as the specified map <i>m</i>.
146     * The <tt>LRUMap</tt> instance is created with default load factor (0.75)
147     * and an initial capacity sufficient to hold the mappings in the specified
148     * map.
149     *
150     * @param m The map whose mappings are to be placed in this LRUMap.
151     */

152
153     public LRUMap(Map JavaDoc m) {
154         maximumSize = m.size()+1;
155 // super(m);
156
putAll(m);
157     }
158
159    /**
160     * Create a new LRUMap with the same mappings as the specified map <i>m</i>.
161     * The <tt>LRUMap</tt> instance is created with default load factor (0.75)
162     * and an initial capacity sufficient to hold the mappings in the specified
163     * map. The attribute <i>maximumSize</i> is set to value <i>maxSize</i> if
164     * that value is greater than the size of the map <i>m</i>.
165     *
166     * @param m The map whose mappings are to be placed in this LRUMap.
167     * @param maxSize Maximum capacity of the LRUMap.
168     */

169     public LRUMap(Map JavaDoc m, int maxSize) {
170         this(m);
171         if ( (maxSize < 0) || (maxSize>m.size()+1))
172           maximumSize = maxSize;
173     }
174
175     /**
176      * Returns true if this LRUMap contains a mapping for the specified key.
177      *
178      * @param key The key whose presence in this LRUMap is to be tested.
179      *
180      * @return true if this LRUMap contains a mapping for the specified key.
181      */

182     public boolean containsKey(Object JavaDoc key) {
183       if(maximumSize == 0)
184         return false;
185       return super.containsKey(key);
186     }
187
188     /**
189      * Returns the value to which the specified key is mapped in this LRUMap,
190      * or null if the map contains no mapping for this key. If found, the key
191      * will be promoted to the Most Recently Used position.
192      * Note that get(Object) operations will modify the underlying Collection.
193      * Calling get(Object) inside of an iteration over keys, values, etc. is
194      * currently unsupported.</p>
195      *
196      * @param key Key to retrieve.
197      * @return Returns the value. Returns null if the key has a null value <i>or</i>
198      * if the key has no value.
199      */

200     public Object JavaDoc get(Object JavaDoc key) {
201         if(maximumSize == 0)
202           return null;
203         if(!containsKey(key))
204           return null;
205         Object JavaDoc value = remove(key);
206         super.put(key,value);
207         return value;
208     }
209
210      /**
211       * Associates the specified value with the specified key in this LRUMap.
212       * If the map previously contained a mapping for this key, the old value
213       * is replaced.
214       * <p>(Note: this may result in the "Least Recently Used"
215       * object being removed from the Map. In that case,
216       * the removeLRU() method is called. See javadoc for
217       * removeLRU() for more details.)</p>
218       *
219       * @param key Key with which the specified value is to be associated.
220       * @param value Value to be associated with the specified key.
221       * @return Former value of the key.
222       */

223
224
225     public Object JavaDoc put( Object JavaDoc key, Object JavaDoc value ) {
226         if(maximumSize == 0)
227           return null;
228         int mapSize = size();
229         Object JavaDoc retval = null;
230
231         if ((maximumSize > 0) && (mapSize >= maximumSize )) {
232
233             // don't retire LRU if you are just
234
// updating an existing key
235
if (!containsKey(key)) {
236                 // lets retire the least recently used item in the cache
237
removeLRU();
238             }
239         }
240         retval = super.put(key,value);
241         return retval;
242     }
243
244   /**
245    * Adds all the mappings in the specified map to this map, replacing any
246    * mappings that already exist (as per {@link Map#putAll(Map)}). The order
247    * in which the entries are added is determined by the iterator returned
248    * from {@link Map#entrySet()} for the specified map.
249    *
250    * @param t the mappings that should be added to this map.
251    *
252    * @exception NullPointerException if <code>t</code> is <code>null</code>.
253    **/

254   public void putAll(Map JavaDoc t) {
255     Iterator JavaDoc iter = t.entrySet().iterator();
256     while(iter.hasNext()) {
257       Map.Entry JavaDoc entry = (Map.Entry JavaDoc)iter.next();
258       this.put(entry.getKey(), entry.getValue());
259     }
260   }
261
262     /**
263      * This method is used internally by the class for finding and removing
264      * the LRU Object.
265      */

266     protected void removeLRU() {
267     Object JavaDoc key = getFirstKey();
268     // be sure to call super.get(key), or you're likely to
269
// get infinite promotion recursion
270
Object JavaDoc value = super.get(key);
271     remove(key);
272     processRemovedLRU(key,value);
273     }
274
275     /**
276      * Subclasses of LRUMap may hook into this method to
277      * provide specialized actions whenever an Object is
278      * automatically removed from the cache. By default,
279      * this method does nothing.
280      *
281      * @param key Key that was removed.
282      * @param value Value of that key (can be null).
283      */

284     protected void processRemovedLRU(Object JavaDoc key, Object JavaDoc value) {
285     }
286
287     // Externalizable interface
288
//-------------------------------------------------------------------------
289
public void readExternal( ObjectInput JavaDoc in ) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
290         maximumSize = in.readInt();
291         int size = in.readInt();
292
293         for( int i = 0; i < size; i++ ) {
294             Object JavaDoc key = in.readObject();
295             Object JavaDoc value = in.readObject();
296             put(key,value);
297         }
298     }
299
300     public void writeExternal( ObjectOutput JavaDoc out ) throws IOException JavaDoc {
301         out.writeInt( maximumSize );
302         out.writeInt( size() );
303         for( Iterator JavaDoc iterator = keySet().iterator(); iterator.hasNext(); ) {
304             Object JavaDoc key = iterator.next();
305             out.writeObject( key );
306             // be sure to call super.get(key), or you're likely to
307
// get infinite promotion recursion
308
Object JavaDoc value = super.get( key );
309             out.writeObject( value );
310         }
311     }
312
313
314     // Properties
315
//-------------------------------------------------------------------------
316
/**
317      * Getter for property maximumSize.
318      *
319      * @return Value of property maximumSize.
320      */

321     public int getMaximumSize() {
322         return maximumSize;
323     }
324     /**
325      * Setter for property maximumSize.
326      *
327      * @param maxSize New value of property maximumSize.
328      */

329     public void setMaximumSize(int maxSize) {
330         this.maximumSize = maxSize;
331         if(maxSize >= 0) {
332             while (size() > maximumSize) {
333                 removeLRU();
334             }
335         }
336     }
337
338
339     // add a serial version uid, so that if we change things in the future
340
// without changing the format, we can still deserialize properly.
341
// private static final long serialVersionUID = 2197433140769957051L;
342
}
343
Popular Tags