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   *    https://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      /** Maximum size */
55      private int maximumSize = 0;
56  
57      /** Default maximum size */
58      protected static final int DEFAULT_MAX_SIZE = 100;
59  
60      /**
61       * Default constructor, primarily for the purpose of de-externalization.
62       * This constructors sets a default LRU limit of 100 keys, but this value
63       * may be overridden internally as a result of de-externalization.
64       */
65      public SynchronizedLRUMap()
66      {
67          this( DEFAULT_MAX_SIZE );
68      }
69  
70  
71      /**
72       * Create a new LRUMap with a maximum capacity of <i>i</i>. Once <i>i</i>
73       * capacity is achieved, subsequent gets and puts will push keys out of the
74       * map. See .
75       * 
76       * @param maxSize Maximum capacity of the LRUMap
77       */
78      public SynchronizedLRUMap( int maxSize )
79      {
80          super( maxSize );
81          maximumSize = maxSize;
82      }
83  
84  
85      /**
86       * <p>
87       * Get the value for a key from the Map. The key will be promoted to the
88       * Most Recently Used position. Note that get(Object) operations will modify
89       * the underlying Collection. Calling get(Object) inside of an iteration
90       * over keys, values, etc. is currently unsupported.
91       * </p>
92       * 
93       * @param key Key to retrieve
94       * @return Returns the value. Returns null if the key has a null value <i>or</i>
95       *         if the key has no value.
96       */
97      @Override
98      public synchronized Object get( Object key )
99      {
100         if ( !containsKey( key ) )
101         {
102             return null;
103         }
104 
105         Object value = remove( key );
106         super.put( key, value );
107         
108         return value;
109     }
110 
111 
112     /**
113      * <p>
114      * Removes the key and its Object from the Map.
115      * </p>
116      * <p>
117      * (Note: this may result in the "Least Recently Used" object being removed
118      * from the Map. In that case, the removeLRU() method is called. See javadoc
119      * for removeLRU() for more details.)
120      * </p>
121      * 
122      * @param key Key of the Object to add.
123      * @param value Object to add
124      * @return Former value of the key
125      */
126     @Override
127     public synchronized Object put( Object key, Object value )
128     {
129         // don't retire LRU if you are just
130         // updating an existing key
131         if ( ( maximumSize <= size() ) && ( !containsKey( key ) ) )
132         {
133             // lets retire the least recently used item in the cache
134             removeLRU();
135         }
136 
137         return super.put( key, value );
138     }
139 
140 
141     /**
142      * This method is used internally by the class for finding and removing the
143      * LRU Object.
144      */
145     private void removeLRU()
146     {
147         Object key = getFirstKey();
148         // be sure to call super.get(key), or you're likely to
149         // get infinite promotion recursion
150         super.get( key );
151 
152         remove( key );
153     }
154 
155 
156     /**
157      * Getter for property maximumSize.
158      * 
159      * @return Value of property maximumSize.
160      */
161     public synchronized int getMaximumSize()
162     {
163         return maximumSize;
164     }
165 
166 
167     /**
168      * Setter for property maximumSize.
169      * 
170      * @param maximumSize New value of property maximumSize.
171      */
172     public synchronized void setMaximumSize( int maximumSize )
173     {
174         this.maximumSize = maximumSize;
175 
176         while ( size() > maximumSize )
177         {
178             removeLRU();
179         }
180     }
181 }