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 */ 020package org.apache.directory.api.util; 021 022 023import 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 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 047 */ 048public final class SynchronizedLRUMap extends SequencedHashMap implements Externalizable 049{ 050 // add a serial version uid, so that if we change things in the future 051 // without changing the format, we can still deserialize properly. 052 private static final long serialVersionUID = 2197433140769957051L; 053 054 private int maximumSize = 0; 055 056 057 /** 058 * Default constructor, primarily for the purpose of de-externalization. 059 * This constructors sets a default LRU limit of 100 keys, but this value 060 * may be overridden internally as a result of de-externalization. 061 */ 062 public SynchronizedLRUMap() 063 { 064 this( 100 ); 065 } 066 067 068 /** 069 * Create a new LRUMap with a maximum capacity of <i>i</i>. Once <i>i</i> 070 * capacity is achieved, subsequent gets and puts will push keys out of the 071 * map. See . 072 * 073 * @param i 074 * Maximum capacity of the LRUMap 075 */ 076 public SynchronizedLRUMap( int i ) 077 { 078 super( i ); 079 maximumSize = i; 080 } 081 082 083 /** 084 * <p> 085 * Get the value for a key from the Map. The key will be promoted to the 086 * Most Recently Used position. Note that get(Object) operations will modify 087 * the underlying Collection. Calling get(Object) inside of an iteration 088 * over keys, values, etc. is currently unsupported. 089 * </p> 090 * 091 * @param key 092 * Key to retrieve 093 * @return Returns the value. Returns null if the key has a null value <i>or</i> 094 * if the key has no value. 095 */ 096 public synchronized Object get( Object key ) 097 { 098 if ( !containsKey( key ) ) 099 { 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}