1. /*
  2. * Copyright 2001-2004 The Apache Software Foundation
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. package org.apache.commons.collections.map;
  17. import java.io.IOException;
  18. import java.io.ObjectInputStream;
  19. import java.io.ObjectOutputStream;
  20. import java.io.Serializable;
  21. import java.util.Map;
  22. import org.apache.commons.collections.BoundedMap;
  23. /**
  24. * A <code>Map</code> implementation with a fixed maximum size which removes
  25. * the least recently used entry if an entry is added when full.
  26. * <p>
  27. * The least recently used algorithm works on the get and put operations only.
  28. * Iteration of any kind, including setting the value by iteration, does not
  29. * change the order. Queries such as containsKey and containsValue or access
  30. * via views also do not change the order.
  31. * <p>
  32. * The map implements <code>OrderedMap</code> and entries may be queried using
  33. * the bidirectional <code>OrderedMapIterator</code>. The order returned is
  34. * least recently used to most recently used. Iterators from map views can
  35. * also be cast to <code>OrderedIterator</code> if required.
  36. * <p>
  37. * All the available iterators can be reset back to the start by casting to
  38. * <code>ResettableIterator</code> and calling <code>reset()</code>.
  39. *
  40. * @since Commons Collections 3.0 (previously in main package v1.0)
  41. * @version $Revision: 1.14 $ $Date: 2004/06/07 22:13:53 $
  42. *
  43. * @author James Strachan
  44. * @author Morgan Delagrange
  45. * @author Stephen Colebourne
  46. * @author Mike Pettypiece
  47. * @author Mario Ivankovits
  48. */
  49. public class LRUMap
  50. extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
  51. /** Serialisation version */
  52. static final long serialVersionUID = -612114643488955218L;
  53. /** Default maximum size */
  54. protected static final int DEFAULT_MAX_SIZE = 100;
  55. /** Maximum size */
  56. private transient int maxSize;
  57. /** Scan behaviour */
  58. private boolean scanUntilRemovable;
  59. /**
  60. * Constructs a new empty map with a maximum size of 100.
  61. */
  62. public LRUMap() {
  63. this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
  64. }
  65. /**
  66. * Constructs a new, empty map with the specified maximum size.
  67. *
  68. * @param maxSize the maximum size of the map
  69. * @throws IllegalArgumentException if the maximum size is less than one
  70. */
  71. public LRUMap(int maxSize) {
  72. this(maxSize, DEFAULT_LOAD_FACTOR);
  73. }
  74. /**
  75. * Constructs a new, empty map with the specified maximum size.
  76. *
  77. * @param maxSize the maximum size of the map
  78. * @param scanUntilRemovable scan until a removeable entry is found, default false
  79. * @throws IllegalArgumentException if the maximum size is less than one
  80. * @since Commons Collections 3.1
  81. */
  82. public LRUMap(int maxSize, boolean scanUntilRemovable) {
  83. this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
  84. }
  85. /**
  86. * Constructs a new, empty map with the specified initial capacity and
  87. * load factor.
  88. *
  89. * @param maxSize the maximum size of the map, -1 for no limit,
  90. * @param loadFactor the load factor
  91. * @throws IllegalArgumentException if the maximum size is less than one
  92. * @throws IllegalArgumentException if the load factor is less than zero
  93. */
  94. public LRUMap(int maxSize, float loadFactor) {
  95. this(maxSize, loadFactor, false);
  96. }
  97. /**
  98. * Constructs a new, empty map with the specified initial capacity and
  99. * load factor.
  100. *
  101. * @param maxSize the maximum size of the map, -1 for no limit,
  102. * @param loadFactor the load factor
  103. * @param scanUntilRemovable scan until a removeable entry is found, default false
  104. * @throws IllegalArgumentException if the maximum size is less than one
  105. * @throws IllegalArgumentException if the load factor is less than zero
  106. * @since Commons Collections 3.1
  107. */
  108. public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) {
  109. super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
  110. if (maxSize < 1) {
  111. throw new IllegalArgumentException("LRUMap max size must be greater than 0");
  112. }
  113. this.maxSize = maxSize;
  114. this.scanUntilRemovable = scanUntilRemovable;
  115. }
  116. /**
  117. * Constructor copying elements from another map.
  118. * <p>
  119. * The maximum size is set from the map's size.
  120. *
  121. * @param map the map to copy
  122. * @throws NullPointerException if the map is null
  123. * @throws IllegalArgumentException if the map is empty
  124. */
  125. public LRUMap(Map map) {
  126. this(map, false);
  127. }
  128. /**
  129. * Constructor copying elements from another map.
  130. * <p/>
  131. * The maximum size is set from the map's size.
  132. *
  133. * @param map the map to copy
  134. * @param scanUntilRemovable scan until a removeable entry is found, default false
  135. * @throws NullPointerException if the map is null
  136. * @throws IllegalArgumentException if the map is empty
  137. * @since Commons Collections 3.1
  138. */
  139. public LRUMap(Map map, boolean scanUntilRemovable) {
  140. this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
  141. putAll(map);
  142. }
  143. //-----------------------------------------------------------------------
  144. /**
  145. * Gets the value mapped to the key specified.
  146. * <p>
  147. * This operation changes the position of the key in the map to the
  148. * most recently used position (first).
  149. *
  150. * @param key the key
  151. * @return the mapped value, null if no match
  152. */
  153. public Object get(Object key) {
  154. LinkEntry entry = (LinkEntry) getEntry(key);
  155. if (entry == null) {
  156. return null;
  157. }
  158. moveToMRU(entry);
  159. return entry.getValue();
  160. }
  161. //-----------------------------------------------------------------------
  162. /**
  163. * Moves an entry to the MRU position at the end of the list.
  164. * <p>
  165. * This implementation moves the updated entry to the end of the list.
  166. *
  167. * @param entry the entry to update
  168. */
  169. protected void moveToMRU(LinkEntry entry) {
  170. if (entry.after != header) {
  171. modCount++;
  172. // remove
  173. entry.before.after = entry.after;
  174. entry.after.before = entry.before;
  175. // add first
  176. entry.after = header;
  177. entry.before = header.before;
  178. header.before.after = entry;
  179. header.before = entry;
  180. }
  181. }
  182. /**
  183. * Updates an existing key-value mapping.
  184. * <p>
  185. * This implementation moves the updated entry to the top of the list
  186. * using {@link #moveToMRU(LinkEntry)}.
  187. *
  188. * @param entry the entry to update
  189. * @param newValue the new value to store
  190. */
  191. protected void updateEntry(HashEntry entry, Object newValue) {
  192. moveToMRU((LinkEntry) entry); // handles modCount
  193. entry.setValue(newValue);
  194. }
  195. /**
  196. * Adds a new key-value mapping into this map.
  197. * <p>
  198. * This implementation checks the LRU size and determines whether to
  199. * discard an entry or not using {@link #removeLRU(LinkEntry)}.
  200. * <p>
  201. * From Commons Collections 3.1 this method uses {@link #isFull()} rather
  202. * than accessing <code>size</code> and <code>maxSize</code> directly.
  203. * It also handles the scanUntilRemovable functionality.
  204. *
  205. * @param hashIndex the index into the data array to store at
  206. * @param hashCode the hash code of the key to add
  207. * @param key the key to add
  208. * @param value the value to add
  209. */
  210. protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
  211. if (isFull()) {
  212. LinkEntry reuse = header.after;
  213. boolean removeLRUEntry = false;
  214. if (scanUntilRemovable) {
  215. while (reuse != header) {
  216. if (removeLRU(reuse)) {
  217. removeLRUEntry = true;
  218. break;
  219. }
  220. reuse = reuse.after;
  221. }
  222. } else {
  223. removeLRUEntry = removeLRU(reuse);
  224. }
  225. if (removeLRUEntry) {
  226. reuseMapping(reuse, hashIndex, hashCode, key, value);
  227. } else {
  228. super.addMapping(hashIndex, hashCode, key, value);
  229. }
  230. } else {
  231. super.addMapping(hashIndex, hashCode, key, value);
  232. }
  233. }
  234. /**
  235. * Reuses an entry by removing it and moving it to a new place in the map.
  236. * <p>
  237. * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
  238. *
  239. * @param entry the entry to reuse
  240. * @param hashIndex the index into the data array to store at
  241. * @param hashCode the hash code of the key to add
  242. * @param key the key to add
  243. * @param value the value to add
  244. */
  245. protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
  246. // find the entry before the entry specified in the hash table
  247. // remember that the parameters (except the first) refer to the new entry,
  248. // not the old one
  249. int removeIndex = hashIndex(entry.hashCode, data.length);
  250. HashEntry loop = data[removeIndex];
  251. HashEntry previous = null;
  252. while (loop != entry) {
  253. previous = loop;
  254. loop = loop.next;
  255. }
  256. // reuse the entry
  257. modCount++;
  258. removeEntry(entry, removeIndex, previous);
  259. reuseEntry(entry, hashIndex, hashCode, key, value);
  260. addEntry(entry, hashIndex);
  261. }
  262. /**
  263. * Subclass method to control removal of the least recently used entry from the map.
  264. * <p>
  265. * This method exists for subclasses to override. A subclass may wish to
  266. * provide cleanup of resources when an entry is removed. For example:
  267. * <pre>
  268. * protected boolean removeLRU(LinkEntry entry) {
  269. * releaseResources(entry.getValue()); // release resources held by entry
  270. * return true; // actually delete entry
  271. * }
  272. * </pre>
  273. * <p>
  274. * Alternatively, a subclass may choose to not remove the entry or selectively
  275. * keep certain LRU entries. For example:
  276. * <pre>
  277. * protected boolean removeLRU(LinkEntry entry) {
  278. * if (entry.getKey().toString().startsWith("System.")) {
  279. * return false; // entry not removed from LRUMap
  280. * } else {
  281. * return true; // actually delete entry
  282. * }
  283. * }
  284. * </pre>
  285. * The effect of returning false is dependent on the scanUntilRemovable flag.
  286. * If the flag is true, the next LRU entry will be passed to this method and so on
  287. * until one returns false and is removed, or every entry in the map has been passed.
  288. * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
  289. * <p>
  290. * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
  291. * This is fixed in version 3.1 onwards.
  292. *
  293. * @param entry the entry to be removed
  294. */
  295. protected boolean removeLRU(LinkEntry entry) {
  296. return true;
  297. }
  298. //-----------------------------------------------------------------------
  299. /**
  300. * Returns true if this map is full and no new mappings can be added.
  301. *
  302. * @return <code>true</code> if the map is full
  303. */
  304. public boolean isFull() {
  305. return (size >= maxSize);
  306. }
  307. /**
  308. * Gets the maximum size of the map (the bound).
  309. *
  310. * @return the maximum number of elements the map can hold
  311. */
  312. public int maxSize() {
  313. return maxSize;
  314. }
  315. /**
  316. * Whether this LRUMap will scan until a removable entry is found when the
  317. * map is full.
  318. *
  319. * @return true if this map scans
  320. * @since Commons Collections 3.1
  321. */
  322. public boolean isScanUntilRemovable() {
  323. return scanUntilRemovable;
  324. }
  325. //-----------------------------------------------------------------------
  326. /**
  327. * Clones the map without cloning the keys or values.
  328. *
  329. * @return a shallow clone
  330. */
  331. public Object clone() {
  332. return super.clone();
  333. }
  334. /**
  335. * Write the map out using a custom routine.
  336. */
  337. private void writeObject(ObjectOutputStream out) throws IOException {
  338. out.defaultWriteObject();
  339. doWriteObject(out);
  340. }
  341. /**
  342. * Read the map in using a custom routine.
  343. */
  344. private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
  345. in.defaultReadObject();
  346. doReadObject(in);
  347. }
  348. /**
  349. * Writes the data necessary for <code>put()</code> to work in deserialization.
  350. */
  351. protected void doWriteObject(ObjectOutputStream out) throws IOException {
  352. out.writeInt(maxSize);
  353. super.doWriteObject(out);
  354. }
  355. /**
  356. * Reads the data necessary for <code>put()</code> to work in the superclass.
  357. */
  358. protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
  359. maxSize = in.readInt();
  360. super.doReadObject(in);
  361. }
  362. }