001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections.map; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.io.Serializable; 023 import java.util.Map; 024 025 import org.apache.commons.collections.BoundedMap; 026 027 /** 028 * A <code>Map</code> implementation with a fixed maximum size which removes 029 * the least recently used entry if an entry is added when full. 030 * <p> 031 * The least recently used algorithm works on the get and put operations only. 032 * Iteration of any kind, including setting the value by iteration, does not 033 * change the order. Queries such as containsKey and containsValue or access 034 * via views also do not change the order. 035 * <p> 036 * The map implements <code>OrderedMap</code> and entries may be queried using 037 * the bidirectional <code>OrderedMapIterator</code>. The order returned is 038 * least recently used to most recently used. Iterators from map views can 039 * also be cast to <code>OrderedIterator</code> if required. 040 * <p> 041 * All the available iterators can be reset back to the start by casting to 042 * <code>ResettableIterator</code> and calling <code>reset()</code>. 043 * <p> 044 * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong> 045 * If you wish to use this map from multiple threads concurrently, you must use 046 * appropriate synchronization. The simplest approach is to wrap this map 047 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 048 * <code>NullPointerException</code>'s when accessed by concurrent threads. 049 * 050 * @since Commons Collections 3.0 (previously in main package v1.0) 051 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 052 * 053 * @author James Strachan 054 * @author Morgan Delagrange 055 * @author Stephen Colebourne 056 * @author Mike Pettypiece 057 * @author Mario Ivankovits 058 */ 059 public class LRUMap 060 extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable { 061 062 /** Serialisation version */ 063 private static final long serialVersionUID = -612114643488955218L; 064 /** Default maximum size */ 065 protected static final int DEFAULT_MAX_SIZE = 100; 066 067 /** Maximum size */ 068 private transient int maxSize; 069 /** Scan behaviour */ 070 private boolean scanUntilRemovable; 071 072 /** 073 * Constructs a new empty map with a maximum size of 100. 074 */ 075 public LRUMap() { 076 this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false); 077 } 078 079 /** 080 * Constructs a new, empty map with the specified maximum size. 081 * 082 * @param maxSize the maximum size of the map 083 * @throws IllegalArgumentException if the maximum size is less than one 084 */ 085 public LRUMap(int maxSize) { 086 this(maxSize, DEFAULT_LOAD_FACTOR); 087 } 088 089 /** 090 * Constructs a new, empty map with the specified maximum size. 091 * 092 * @param maxSize the maximum size of the map 093 * @param scanUntilRemovable scan until a removeable entry is found, default false 094 * @throws IllegalArgumentException if the maximum size is less than one 095 * @since Commons Collections 3.1 096 */ 097 public LRUMap(int maxSize, boolean scanUntilRemovable) { 098 this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable); 099 } 100 101 /** 102 * Constructs a new, empty map with the specified initial capacity and 103 * load factor. 104 * 105 * @param maxSize the maximum size of the map, -1 for no limit, 106 * @param loadFactor the load factor 107 * @throws IllegalArgumentException if the maximum size is less than one 108 * @throws IllegalArgumentException if the load factor is less than zero 109 */ 110 public LRUMap(int maxSize, float loadFactor) { 111 this(maxSize, loadFactor, false); 112 } 113 114 /** 115 * Constructs a new, empty map with the specified initial capacity and 116 * load factor. 117 * 118 * @param maxSize the maximum size of the map, -1 for no limit, 119 * @param loadFactor the load factor 120 * @param scanUntilRemovable scan until a removeable entry is found, default false 121 * @throws IllegalArgumentException if the maximum size is less than one 122 * @throws IllegalArgumentException if the load factor is less than zero 123 * @since Commons Collections 3.1 124 */ 125 public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) { 126 super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor); 127 if (maxSize < 1) { 128 throw new IllegalArgumentException("LRUMap max size must be greater than 0"); 129 } 130 this.maxSize = maxSize; 131 this.scanUntilRemovable = scanUntilRemovable; 132 } 133 134 /** 135 * Constructor copying elements from another map. 136 * <p> 137 * The maximum size is set from the map's size. 138 * 139 * @param map the map to copy 140 * @throws NullPointerException if the map is null 141 * @throws IllegalArgumentException if the map is empty 142 */ 143 public LRUMap(Map map) { 144 this(map, false); 145 } 146 147 /** 148 * Constructor copying elements from another map. 149 * <p/> 150 * The maximum size is set from the map's size. 151 * 152 * @param map the map to copy 153 * @param scanUntilRemovable scan until a removeable entry is found, default false 154 * @throws NullPointerException if the map is null 155 * @throws IllegalArgumentException if the map is empty 156 * @since Commons Collections 3.1 157 */ 158 public LRUMap(Map map, boolean scanUntilRemovable) { 159 this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable); 160 putAll(map); 161 } 162 163 //----------------------------------------------------------------------- 164 /** 165 * Gets the value mapped to the key specified. 166 * <p> 167 * This operation changes the position of the key in the map to the 168 * most recently used position (first). 169 * 170 * @param key the key 171 * @return the mapped value, null if no match 172 */ 173 public Object get(Object key) { 174 LinkEntry entry = (LinkEntry) getEntry(key); 175 if (entry == null) { 176 return null; 177 } 178 moveToMRU(entry); 179 return entry.getValue(); 180 } 181 182 //----------------------------------------------------------------------- 183 /** 184 * Moves an entry to the MRU position at the end of the list. 185 * <p> 186 * This implementation moves the updated entry to the end of the list. 187 * 188 * @param entry the entry to update 189 */ 190 protected void moveToMRU(LinkEntry entry) { 191 if (entry.after != header) { 192 modCount++; 193 // remove 194 entry.before.after = entry.after; 195 entry.after.before = entry.before; 196 // add first 197 entry.after = header; 198 entry.before = header.before; 199 header.before.after = entry; 200 header.before = entry; 201 } else if (entry == header) { 202 throw new IllegalStateException("Can't move header to MRU" + 203 " (please report this to commons-dev@jakarta.apache.org)"); 204 } 205 } 206 207 /** 208 * Updates an existing key-value mapping. 209 * <p> 210 * This implementation moves the updated entry to the top of the list 211 * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}. 212 * 213 * @param entry the entry to update 214 * @param newValue the new value to store 215 */ 216 protected void updateEntry(HashEntry entry, Object newValue) { 217 moveToMRU((LinkEntry) entry); // handles modCount 218 entry.setValue(newValue); 219 } 220 221 /** 222 * Adds a new key-value mapping into this map. 223 * <p> 224 * This implementation checks the LRU size and determines whether to 225 * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}. 226 * <p> 227 * From Commons Collections 3.1 this method uses {@link #isFull()} rather 228 * than accessing <code>size</code> and <code>maxSize</code> directly. 229 * It also handles the scanUntilRemovable functionality. 230 * 231 * @param hashIndex the index into the data array to store at 232 * @param hashCode the hash code of the key to add 233 * @param key the key to add 234 * @param value the value to add 235 */ 236 protected void addMapping(int hashIndex, int hashCode, Object key, Object value) { 237 if (isFull()) { 238 LinkEntry reuse = header.after; 239 boolean removeLRUEntry = false; 240 if (scanUntilRemovable) { 241 while (reuse != header && reuse != null) { 242 if (removeLRU(reuse)) { 243 removeLRUEntry = true; 244 break; 245 } 246 reuse = reuse.after; 247 } 248 if (reuse == null) { 249 throw new IllegalStateException( 250 "Entry.after=null, header.after" + header.after + " header.before" + header.before + 251 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 252 " Please check that your keys are immutable, and that you have used synchronization properly." + 253 " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); 254 } 255 } else { 256 removeLRUEntry = removeLRU(reuse); 257 } 258 259 if (removeLRUEntry) { 260 if (reuse == null) { 261 throw new IllegalStateException( 262 "reuse=null, header.after=" + header.after + " header.before" + header.before + 263 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 264 " Please check that your keys are immutable, and that you have used synchronization properly." + 265 " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); 266 } 267 reuseMapping(reuse, hashIndex, hashCode, key, value); 268 } else { 269 super.addMapping(hashIndex, hashCode, key, value); 270 } 271 } else { 272 super.addMapping(hashIndex, hashCode, key, value); 273 } 274 } 275 276 /** 277 * Reuses an entry by removing it and moving it to a new place in the map. 278 * <p> 279 * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}. 280 * 281 * @param entry the entry to reuse 282 * @param hashIndex the index into the data array to store at 283 * @param hashCode the hash code of the key to add 284 * @param key the key to add 285 * @param value the value to add 286 */ 287 protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) { 288 // find the entry before the entry specified in the hash table 289 // remember that the parameters (except the first) refer to the new entry, 290 // not the old one 291 try { 292 int removeIndex = hashIndex(entry.hashCode, data.length); 293 HashEntry[] tmp = data; // may protect against some sync issues 294 HashEntry loop = tmp[removeIndex]; 295 HashEntry previous = null; 296 while (loop != entry && loop != null) { 297 previous = loop; 298 loop = loop.next; 299 } 300 if (loop == null) { 301 throw new IllegalStateException( 302 "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous + 303 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 304 " Please check that your keys are immutable, and that you have used synchronization properly." + 305 " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); 306 } 307 308 // reuse the entry 309 modCount++; 310 removeEntry(entry, removeIndex, previous); 311 reuseEntry(entry, hashIndex, hashCode, key, value); 312 addEntry(entry, hashIndex); 313 } catch (NullPointerException ex) { 314 throw new IllegalStateException( 315 "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) + 316 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 317 " Please check that your keys are immutable, and that you have used synchronization properly." + 318 " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); 319 } 320 } 321 322 /** 323 * Subclass method to control removal of the least recently used entry from the map. 324 * <p> 325 * This method exists for subclasses to override. A subclass may wish to 326 * provide cleanup of resources when an entry is removed. For example: 327 * <pre> 328 * protected boolean removeLRU(LinkEntry entry) { 329 * releaseResources(entry.getValue()); // release resources held by entry 330 * return true; // actually delete entry 331 * } 332 * </pre> 333 * <p> 334 * Alternatively, a subclass may choose to not remove the entry or selectively 335 * keep certain LRU entries. For example: 336 * <pre> 337 * protected boolean removeLRU(LinkEntry entry) { 338 * if (entry.getKey().toString().startsWith("System.")) { 339 * return false; // entry not removed from LRUMap 340 * } else { 341 * return true; // actually delete entry 342 * } 343 * } 344 * </pre> 345 * The effect of returning false is dependent on the scanUntilRemovable flag. 346 * If the flag is true, the next LRU entry will be passed to this method and so on 347 * until one returns false and is removed, or every entry in the map has been passed. 348 * If the scanUntilRemovable flag is false, the map will exceed the maximum size. 349 * <p> 350 * NOTE: Commons Collections 3.0 passed the wrong entry to this method. 351 * This is fixed in version 3.1 onwards. 352 * 353 * @param entry the entry to be removed 354 */ 355 protected boolean removeLRU(LinkEntry entry) { 356 return true; 357 } 358 359 //----------------------------------------------------------------------- 360 /** 361 * Returns true if this map is full and no new mappings can be added. 362 * 363 * @return <code>true</code> if the map is full 364 */ 365 public boolean isFull() { 366 return (size >= maxSize); 367 } 368 369 /** 370 * Gets the maximum size of the map (the bound). 371 * 372 * @return the maximum number of elements the map can hold 373 */ 374 public int maxSize() { 375 return maxSize; 376 } 377 378 /** 379 * Whether this LRUMap will scan until a removable entry is found when the 380 * map is full. 381 * 382 * @return true if this map scans 383 * @since Commons Collections 3.1 384 */ 385 public boolean isScanUntilRemovable() { 386 return scanUntilRemovable; 387 } 388 389 //----------------------------------------------------------------------- 390 /** 391 * Clones the map without cloning the keys or values. 392 * 393 * @return a shallow clone 394 */ 395 public Object clone() { 396 return super.clone(); 397 } 398 399 /** 400 * Write the map out using a custom routine. 401 */ 402 private void writeObject(ObjectOutputStream out) throws IOException { 403 out.defaultWriteObject(); 404 doWriteObject(out); 405 } 406 407 /** 408 * Read the map in using a custom routine. 409 */ 410 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 411 in.defaultReadObject(); 412 doReadObject(in); 413 } 414 415 /** 416 * Writes the data necessary for <code>put()</code> to work in deserialization. 417 */ 418 protected void doWriteObject(ObjectOutputStream out) throws IOException { 419 out.writeInt(maxSize); 420 super.doWriteObject(out); 421 } 422 423 /** 424 * Reads the data necessary for <code>put()</code> to work in the superclass. 425 */ 426 protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 427 maxSize = in.readInt(); 428 super.doReadObject(in); 429 } 430 431 }