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  ;
59  import java.io.IOException  ;
60  import java.io.ObjectInput  ;
61  import java.io.ObjectOutput  ;
62  import java.util.Iterator  ;
63  import java.util.Map  ;
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   {
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   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   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   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   get(Object   key) {
201         if(maximumSize == 0)
202           return null;
203         if(!containsKey(key))
204           return null;
205         Object   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   put( Object   key, Object   value ) {
226         if(maximumSize == 0)
227           return null;
228         int mapSize = size();
229         Object   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   t) {
255     Iterator   iter = t.entrySet().iterator();
256     while(iter.hasNext()) {
257       Map.Entry   entry = (Map.Entry  )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   key = getFirstKey();
268     // be sure to call super.get(key), or you're likely to
269     // get infinite promotion recursion
270     Object   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   key, Object   value) {
285     }
286 
287     // Externalizable interface
288     //-------------------------------------------------------------------------
289     public void readExternal( ObjectInput   in )  throws IOException  , ClassNotFoundException   {
290         maximumSize = in.readInt();
291         int size = in.readInt();
292 
293         for( int i = 0; i < size; i++ )  {
294             Object   key = in.readObject();
295             Object   value = in.readObject();
296             put(key,value);
297         }
298     }
299 
300     public void writeExternal( ObjectOutput   out ) throws IOException   {
301         out.writeInt( maximumSize );
302         out.writeInt( size() );
303         for( Iterator   iterator = keySet().iterator(); iterator.hasNext(); ) {
304             Object   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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags