001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one
003     *  or more contributor license agreements.  See the NOTICE file
004     *  distributed with this work for additional information
005     *  regarding copyright ownership.  The ASF licenses this file
006     *  to you under the Apache License, Version 2.0 (the
007     *  "License"); you may not use this file except in compliance
008     *  with the License.  You may obtain a copy of the License at
009     *  
010     *    http://www.apache.org/licenses/LICENSE-2.0
011     *  
012     *  Unless required by applicable law or agreed to in writing,
013     *  software distributed under the License is distributed on an
014     *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     *  KIND, either express or implied.  See the License for the
016     *  specific language governing permissions and limitations
017     *  under the License. 
018     *  
019     */
020    package org.apache.directory.shared.ldap.util;
021    
022    
023    import java.io.Externalizable;
024    
025    
026    /**
027     * <p>
028     * An implementation of a Map which has a maximum size and uses a Least Recently
029     * Used algorithm to remove items from the Map when the maximum size is reached
030     * and new items are added.
031     * </p>
032     * <p>
033     * A synchronized version can be obtained with:
034     * <code>Collections.synchronizedMap( theMapToSynchronize )</code> If it will
035     * be accessed by multiple threads, you _must_ synchronize access to this Map.
036     * Even concurrent get(Object) operations produce indeterminate behaviour.
037     * </p>
038     * <p>
039     * Unlike the Collections 1.0 version, this version of LRUMap does use a true
040     * LRU algorithm. The keys for all gets and puts are moved to the front of the
041     * list. LRUMap is now a subclass of SequencedHashMap, and the "LRU" key is now
042     * equivalent to LRUMap.getFirst().
043     * </p>
044     * 
045     * @since Commons Collections 1.0
046     * @version $Revision: 437007 $ $Date: 2006-08-26 01:06:17 +0200 (Sat, 26 Aug 2006) $
047     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
048     */
049    public final class SynchronizedLRUMap extends SequencedHashMap implements Externalizable
050    {
051        // add a serial version uid, so that if we change things in the future
052        // without changing the format, we can still deserialize properly.
053        private static final long serialVersionUID = 2197433140769957051L;
054    
055        private int maximumSize = 0;
056    
057    
058        /**
059         * Default constructor, primarily for the purpose of de-externalization.
060         * This constructors sets a default LRU limit of 100 keys, but this value
061         * may be overridden internally as a result of de-externalization.
062         */
063        public SynchronizedLRUMap()
064        {
065            this( 100 );
066        }
067    
068    
069        /**
070         * Create a new LRUMap with a maximum capacity of <i>i</i>. Once <i>i</i>
071         * capacity is achieved, subsequent gets and puts will push keys out of the
072         * map. See .
073         * 
074         * @param i
075         *            Maximum capacity of the LRUMap
076         */
077        public SynchronizedLRUMap(int i)
078        {
079            super( i );
080            maximumSize = i;
081        }
082    
083    
084        /**
085         * <p>
086         * Get the value for a key from the Map. The key will be promoted to the
087         * Most Recently Used position. Note that get(Object) operations will modify
088         * the underlying Collection. Calling get(Object) inside of an iteration
089         * over keys, values, etc. is currently unsupported.
090         * </p>
091         * 
092         * @param key
093         *            Key to retrieve
094         * @return Returns the value. Returns null if the key has a null value <i>or</i>
095         *         if the key has no value.
096         */
097        public synchronized Object get( Object key )
098        {
099            if ( !containsKey( key ) )
100            {
101                return null;
102            }
103    
104            Object value = remove( key );
105            super.put( key, value );
106            return value;
107        }
108    
109    
110        /**
111         * <p>
112         * Removes the key and its Object from the Map.
113         * </p>
114         * <p>
115         * (Note: this may result in the "Least Recently Used" object being removed
116         * from the Map. In that case, the removeLRU() method is called. See javadoc
117         * for removeLRU() for more details.)
118         * </p>
119         * 
120         * @param key
121         *            Key of the Object to add.
122         * @param value
123         *            Object to add
124         * @return Former value of the key
125         */
126        public Object put( Object key, Object value )
127        {
128    
129            int mapSize = size();
130            Object retval = null;
131    
132            if ( mapSize >= maximumSize )
133            {
134                synchronized ( this )
135                {
136                    // don't retire LRU if you are just
137                    // updating an existing key
138                    if ( !containsKey( key ) )
139                    {
140                        // lets retire the least recently used item in the cache
141                        removeLRU();
142                    }
143    
144                    retval = super.put( key, value );
145                }
146            }
147            else
148            {
149                synchronized ( this )
150                {
151                    retval = super.put( key, value );
152                }
153            }
154    
155            return retval;
156        }
157    
158    
159        /**
160         * This method is used internally by the class for finding and removing the
161         * LRU Object.
162         */
163        private void removeLRU()
164        {
165            Object key = getFirstKey();
166            // be sure to call super.get(key), or you're likely to
167            // get infinite promotion recursion
168            super.get( key );
169    
170            remove( key );
171        }
172    
173    
174        // Properties
175        // -------------------------------------------------------------------------
176        /**
177         * Getter for property maximumSize.
178         * 
179         * @return Value of property maximumSize.
180         */
181        public int getMaximumSize()
182        {
183            return maximumSize;
184        }
185    
186    
187        /**
188         * Setter for property maximumSize.
189         * 
190         * @param maximumSize
191         *            New value of property maximumSize.
192         */
193        public void setMaximumSize( int maximumSize )
194        {
195            synchronized ( this )
196            {
197                this.maximumSize = maximumSize;
198    
199                while ( size() > maximumSize )
200                {
201                    removeLRU();
202                }
203            }
204        }
205    }