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 }