View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.api.util;
21  
22  
23  import java.io.Externalizable;
24  
25  
26  /**
27   * <p>
28   * An implementation of a Map which has a maximum size and uses a Least Recently
29   * Used algorithm to remove items from the Map when the maximum size is reached
30   * and new items are added.
31   * </p>
32   * <p>
33   * A synchronized version can be obtained with:
34   * <code>Collections.synchronizedMap( theMapToSynchronize )</code> If it will
35   * be accessed by multiple threads, you _must_ synchronize access to this Map.
36   * Even concurrent get(Object) operations produce indeterminate behaviour.
37   * </p>
38   * <p>
39   * Unlike the Collections 1.0 version, this version of LRUMap does use a true
40   * LRU algorithm. The keys for all gets and puts are moved to the front of the
41   * list. LRUMap is now a subclass of SequencedHashMap, and the "LRU" key is now
42   * equivalent to LRUMap.getFirst().
43   * </p>
44   * 
45   * @since Commons Collections 1.0
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   */
48  public final class SynchronizedLRUMap extends SequencedHashMap implements Externalizable
49  {
50      // add a serial version uid, so that if we change things in the future
51      // without changing the format, we can still deserialize properly.
52      private static final long serialVersionUID = 2197433140769957051L;
53  
54      private int maximumSize = 0;
55  
56  
57      /**
58       * Default constructor, primarily for the purpose of de-externalization.
59       * This constructors sets a default LRU limit of 100 keys, but this value
60       * may be overridden internally as a result of de-externalization.
61       */
62      public SynchronizedLRUMap()
63      {
64          this( 100 );
65      }
66  
67  
68      /**
69       * Create a new LRUMap with a maximum capacity of <i>i</i>. Once <i>i</i>
70       * capacity is achieved, subsequent gets and puts will push keys out of the
71       * map. See .
72       * 
73       * @param i
74       *            Maximum capacity of the LRUMap
75       */
76      public SynchronizedLRUMap( int i )
77      {
78          super( i );
79          maximumSize = i;
80      }
81  
82  
83      /**
84       * <p>
85       * Get the value for a key from the Map. The key will be promoted to the
86       * Most Recently Used position. Note that get(Object) operations will modify
87       * the underlying Collection. Calling get(Object) inside of an iteration
88       * over keys, values, etc. is currently unsupported.
89       * </p>
90       * 
91       * @param key
92       *            Key to retrieve
93       * @return Returns the value. Returns null if the key has a null value <i>or</i>
94       *         if the key has no value.
95       */
96      public synchronized Object get( Object key )
97      {
98          if ( !containsKey( key ) )
99          {
100             return null;
101         }
102 
103         Object value = remove( key );
104         super.put( key, value );
105         return value;
106     }
107 
108 
109     /**
110      * <p>
111      * Removes the key and its Object from the Map.
112      * </p>
113      * <p>
114      * (Note: this may result in the "Least Recently Used" object being removed
115      * from the Map. In that case, the removeLRU() method is called. See javadoc
116      * for removeLRU() for more details.)
117      * </p>
118      * 
119      * @param key
120      *            Key of the Object to add.
121      * @param value
122      *            Object to add
123      * @return Former value of the key
124      */
125     public Object put( Object key, Object value )
126     {
127 
128         int mapSize = size();
129         Object retval = null;
130 
131         if ( mapSize >= maximumSize )
132         {
133             synchronized ( this )
134             {
135                 // don't retire LRU if you are just
136                 // updating an existing key
137                 if ( !containsKey( key ) )
138                 {
139                     // lets retire the least recently used item in the cache
140                     removeLRU();
141                 }
142 
143                 retval = super.put( key, value );
144             }
145         }
146         else
147         {
148             synchronized ( this )
149             {
150                 retval = super.put( key, value );
151             }
152         }
153 
154         return retval;
155     }
156 
157 
158     /**
159      * This method is used internally by the class for finding and removing the
160      * LRU Object.
161      */
162     private void removeLRU()
163     {
164         Object key = getFirstKey();
165         // be sure to call super.get(key), or you're likely to
166         // get infinite promotion recursion
167         super.get( key );
168 
169         remove( key );
170     }
171 
172 
173     // Properties
174     // -------------------------------------------------------------------------
175     /**
176      * Getter for property maximumSize.
177      * 
178      * @return Value of property maximumSize.
179      */
180     public int getMaximumSize()
181     {
182         return maximumSize;
183     }
184 
185 
186     /**
187      * Setter for property maximumSize.
188      * 
189      * @param maximumSize
190      *            New value of property maximumSize.
191      */
192     public void setMaximumSize( int maximumSize )
193     {
194         synchronized ( this )
195         {
196             this.maximumSize = maximumSize;
197 
198             while ( size() > maximumSize )
199             {
200                 removeLRU();
201             }
202         }
203     }
204 }