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 }