001 package org.rakeshv.utils;
002
003 import java.util.Formatter;
004 import java.util.logging.Logger;
005
006 /**
007 * A sub-class of <code>java.util.LinkedHashMap</code> used to
008 * implement a size controlled <code>Map</code>. Implements the
009 * {@link #removeEldestEntry( Map.Entry )} method to remove the
010 * oldest entries if <code>Map.size() > maxEntries</code>.
011 *
012 * <p>Copyright 2004-2006 Rakesh Vidyadharan</p>
013 * @author Rakesh Vidyadharan 2004 September 1
014 * @version $Id: LinkedHashMap.java,v 1.12 2006/03/11 16:30:57 rakesh Exp $
015 */
016 class LinkedHashMap<K,V> extends java.util.LinkedHashMap<K,V>
017 implements Map<K,V>
018 {
019 /**
020 * An instance of <code>Logger</code> used to log informational
021 * messages. All logs are created using the <code>Logger.info()
022 * </code> method.
023 */
024 private static final Logger logger =
025 Logger.getLogger( "org.rakeshv.utils.LinkedHashMap" );
026
027 /**
028 * The default size for the map.
029 */
030 static final int DEFAULT_CAPACITY = 16;
031
032 /**
033 * The default load-factor value.
034 */
035 static final float DEFAULT_LOAD_FACTOR = 1.0f;
036
037 /**
038 * Flag to indicate access-order policy.
039 */
040 static final boolean LRU_CACHE = true;
041
042 /**
043 * Flag to indicate insertion-order policy.
044 */
045 static final boolean FIFO_CACHE = true;
046
047 /**
048 * A variable used to keep track of the maximum number of entries to
049 * keep in the Map.
050 */
051 private volatile int maxEntries;
052
053 /**
054 * An instance of {@link LinkedHashMap.Statistics} that is used to
055 * track usage of the cache.
056 */
057 private Statistics statistics;
058
059 /**
060 * Default constructor. Creates a new Map with using the super
061 * class constructor. If this form of the constructor is used,
062 * the cache size will <b>not</b> be controlled.
063 */
064 LinkedHashMap()
065 {
066 super();
067 init( Integer.MAX_VALUE );
068 }
069
070 /**
071 * Constructs a new instance with the specified initial capacity.
072 *
073 * @param capacity The maximum size for this map.
074 */
075 LinkedHashMap( int capacity )
076 {
077 super( capacity );
078 init( capacity );
079 }
080
081 /**
082 * Constructs a new instance with the specified initial capacity and
083 * load factor.
084 *
085 * @param capacity The maximum size for this map.
086 * @param loadFactor The load-factor to use.
087 */
088 LinkedHashMap( int capacity, float loadFactor )
089 {
090 super( capacity, loadFactor );
091 init( capacity );
092 }
093
094 /**
095 * Constructs an empty LinkedHashMap instance with the specified
096 * initial capacity, load factor and ordering mode.
097 *
098 * @param capacity The maximum size for this map.
099 * @param loadFactor The load-factor to use.
100 * @param accessOrder The ordering mode - {@link #LRU_CACHE} for
101 * access-order, {@link #FIFO_CACHE} for insertion-order.
102 */
103 LinkedHashMap( int capacity, float loadFactor,
104 boolean accessOrder )
105 {
106 super( capacity, loadFactor, accessOrder );
107 init( capacity );
108 }
109
110 /**
111 * Constructs an ordered LinkedHashMap instance with the same
112 * mappings as the specified map. The maximum size of this map
113 * is set to the size of the specified map.
114 *
115 * @param map The map to use to create the new instance.
116 * @throws NullPointerException If the specified map is null.
117 */
118 LinkedHashMap( java.util.Map<K,V> map )
119 {
120 super( map );
121 init( map.size() );
122 }
123
124 /**
125 * Initialise the {@link #maxEntries} and {@link #statistics}.
126 */
127 private void init( int capacity )
128 {
129 maxEntries = capacity;
130 statistics = new Statistics();
131 }
132
133 /**
134 * Over-ridden to increment the values of {@link
135 * Statistics#totalRequests} and if necessary, {@link
136 * Statistics#successfulRequests}.
137 *
138 * @param key <code>key</code> whose associated value is to be
139 * returned.
140 * @return Object - The <code>value</code> to which this map maps the
141 * specified <code>key</code>, or <code>null</code> if the map
142 * contains no mapping for this <code>key</code>.
143 */
144 public V get( Object key )
145 {
146 statistics.updateTotalRequests();
147
148 V result = super.get( key );
149 if ( result != null )
150 {
151 statistics.updateSuccessfulRequests();
152 }
153
154 return result;
155 }
156
157 /**
158 * Removes all mappings from this map. Resets {@link #statistics}.
159 */
160 public void clear()
161 {
162 super.clear();
163 statistics = new Statistics();
164 }
165
166 /**
167 * Returns <code>true</code> if this map should remove its eldest
168 * entry. This method is invoked by put and putAll after inserting a
169 * new entry into the map. Checks the {@link #size()} of the map
170 * against {@link #maxEntries} to determine the return value.
171 *
172 * @param eldest The least recently accessed entry. This is the
173 * entry that will be removed it this method returns
174 * <code>true</code>. If the map was empty prior to the <code>put
175 * </code> or <code>putAll</code> invocation resulting in this
176 * invocation, this will be the entry that was just inserted; in
177 * other words, if the map contains a single entry, the eldest
178 * entry is also the newest.
179 */
180 protected boolean removeEldestEntry( Map.Entry eldest )
181 {
182 boolean status = false;
183
184 if ( size() >= getMaxEntries() )
185 {
186 status = true;
187 statistics.updateTotalRemoved();
188 logger.fine( "Removing item with key " + eldest.getKey() );
189 }
190
191 return status;
192 }
193
194 /**
195 * Returns {@link #maxEntries}.
196 *
197 * @return int The value/reference of/to maxEntries.
198 */
199 public final int getMaxEntries()
200 {
201 return maxEntries;
202 }
203
204 /**
205 * Set {@link #maxEntries}. This can be used to dynamically change
206 * the size of the cache.
207 *
208 * @param maxEntries The value to set.
209 */
210 public final void setMaxEntries( int maxEntries )
211 {
212 this.maxEntries = maxEntries;
213 }
214
215 /**
216 * Returns {@link #statistics}. This may be used by client
217 * applications to monitor cache usage.
218 *
219 * @return Statistics The value/reference of/to statistics.
220 */
221 public final Map.Statistics getStatistics()
222 {
223 return statistics;
224 }
225
226 /**
227 * An implementation of {@link LinkedHashMap.Statistics} used to
228 * track cache performance.
229 */
230 static class Statistics implements Map.Statistics
231 {
232 /**
233 * A variable used to keep track of the number of requests received
234 * by the map.
235 */
236 private volatile int totalRequests = 0;
237
238 /**
239 * A variable used to keep track of the number of successful
240 * requests received by the map. This number indicates the number
241 * of times items stored in the map was successfully retrieved.
242 */
243 private volatile int successfulRequests = 0;
244
245 /**
246 * A variable used to keep track of the number of entries that are
247 * removed from the map. This applies only to entries that are
248 * automatically evicted from the cache due to size limitation.
249 * Evictions triggered by client invoking the <code>remove</code>
250 * method is not tracked.
251 */
252 private volatile int totalRemoved = 0;
253
254 /**
255 * Increments the value of {@link #totalRequests}.
256 */
257 final void updateTotalRequests()
258 {
259 ++totalRequests;
260 }
261
262 /**
263 * Increments the value of {@link #successfulRequests}.
264 */
265 final void updateSuccessfulRequests()
266 {
267 ++successfulRequests;
268 }
269
270 /**
271 * Increments the value of {@link #totalRemoved}.
272 */
273 final void updateTotalRemoved()
274 {
275 ++totalRemoved;
276 }
277
278 /**
279 * Returns {@link #totalRequests}.
280 *
281 * @return int The value/reference of/to totalRequests.
282 */
283 public final int getTotalRequests()
284 {
285 return totalRequests;
286 }
287
288 /**
289 * Returns {@link #successfulRequests}.
290 *
291 * @return int The value/reference of/to successfulRequests.
292 */
293 public final int getSuccessfulRequests()
294 {
295 return successfulRequests;
296 }
297
298 /**
299 * Returns {@link #totalRemoved}.
300 *
301 * @return int The value/reference of/to totalRemoved.
302 */
303 public final int getTotalRemoved()
304 {
305 return totalRemoved;
306 }
307
308 /**
309 * Return a string representation of this object.
310 *
311 * @return String The string representation.
312 */
313 @Override
314 public String toString()
315 {
316 StringBuilder builder = new StringBuilder( 128 );
317 Formatter formatter = new Formatter( builder );
318 formatter.format( "%s totalRequests=%d successfulRequests=%d totalRemoved=%d%n",
319 LinkedHashMap.Statistics.this.getClass().getName(),
320 totalRequests, successfulRequests, totalRemoved );
321
322 return builder.toString();
323 }
324 }
325 }