Source code: org/apache/axis/collections/LRUMap.java
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.axis.collections;
17
18 import java.io.Externalizable;
19 import java.io.IOException;
20 import java.io.ObjectInput;
21 import java.io.ObjectOutput;
22 import java.util.Iterator;
23
24 /**
25 * <p>
26 * An implementation of a Map which has a maximum size and uses a Least Recently Used
27 * algorithm to remove items from the Map when the maximum size is reached and new items are added.
28 * </p>
29 *
30 * <p>
31 * A synchronized version can be obtained with:
32 * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
33 * If it will be accessed by multiple threads, you _must_ synchronize access
34 * to this Map. Even concurrent get(Object) operations produce indeterminate
35 * behaviour.
36 * </p>
37 *
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
41 * the list. LRUMap is now a subclass of SequencedHashMap, and the "LRU"
42 * key is now equivalent to LRUMap.getFirst().
43 * </p>
44 *
45 * @since Commons Collections 1.0
46 *
47 * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
48 * @author <a href="mailto:morgand@apache.org">Morgan Delagrange</a>
49 */
50 public class LRUMap extends SequencedHashMap implements Externalizable {
51
52 private int maximumSize = 0;
53
54 /**
55 * Default constructor, primarily for the purpose of
56 * de-externalization. This constructors sets a default
57 * LRU limit of 100 keys, but this value may be overridden
58 * internally as a result of de-externalization.
59 */
60 public LRUMap() {
61 this( 100 );
62 }
63
64 /**
65 * Create a new LRUMap with a maximum capacity of <i>i</i>.
66 * Once <i>i</i> capacity is achieved, subsequent gets
67 * and puts will push keys out of the map. See .
68 *
69 * @param i Maximum capacity of the LRUMap
70 */
71 public LRUMap(int i) {
72 super( i );
73 maximumSize = i;
74 }
75
76 /**
77 * <p>Get the value for a key from the Map. The key
78 * will be promoted to the Most Recently Used position.
79 * Note that get(Object) operations will modify
80 * the underlying Collection. Calling get(Object)
81 * inside of an iteration over keys, values, etc. is
82 * currently unsupported.</p>
83 *
84 * @param key Key to retrieve
85 * @return Returns the value. Returns null if the key has a
86 * null value <i>or</i> if the key has no value.
87 */
88 public Object get(Object key) {
89 if(!containsKey(key)) return null;
90
91 Object value = remove(key);
92 super.put(key,value);
93 return value;
94 }
95
96 /**
97 * <p>Removes the key and its Object from the Map.</p>
98 *
99 * <p>(Note: this may result in the "Least Recently Used"
100 * object being removed from the Map. In that case,
101 * the removeLRU() method is called. See javadoc for
102 * removeLRU() for more details.)</p>
103 *
104 * @param key Key of the Object to add.
105 * @param value Object to add
106 * @return Former value of the key
107 */
108 public Object put( Object key, Object value ) {
109
110 int mapSize = size();
111 Object retval = null;
112
113 if ( mapSize >= maximumSize ) {
114
115 // don't retire LRU if you are just
116 // updating an existing key
117 if (!containsKey(key)) {
118 // lets retire the least recently used item in the cache
119 removeLRU();
120 }
121 }
122
123 retval = super.put(key,value);
124
125 return retval;
126 }
127
128 /**
129 * This method is used internally by the class for
130 * finding and removing the LRU Object.
131 */
132 protected void removeLRU() {
133 Object key = getFirstKey();
134 // be sure to call super.get(key), or you're likely to
135 // get infinite promotion recursion
136 Object value = super.get(key);
137
138 remove(key);
139
140 processRemovedLRU(key,value);
141 }
142
143 /**
144 * Subclasses of LRUMap may hook into this method to
145 * provide specialized actions whenever an Object is
146 * automatically removed from the cache. By default,
147 * this method does nothing.
148 *
149 * @param key key that was removed
150 * @param value value of that key (can be null)
151 */
152 protected void processRemovedLRU(Object key, Object value) {
153 }
154
155 // Externalizable interface
156 //-------------------------------------------------------------------------
157 public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException {
158 maximumSize = in.readInt();
159 int size = in.readInt();
160
161 for( int i = 0; i < size; i++ ) {
162 Object key = in.readObject();
163 Object value = in.readObject();
164 put(key,value);
165 }
166 }
167
168 public void writeExternal( ObjectOutput out ) throws IOException {
169 out.writeInt( maximumSize );
170 out.writeInt( size() );
171 for( Iterator iterator = keySet().iterator(); iterator.hasNext(); ) {
172 Object key = iterator.next();
173 out.writeObject( key );
174 // be sure to call super.get(key), or you're likely to
175 // get infinite promotion recursion
176 Object value = super.get( key );
177 out.writeObject( value );
178 }
179 }
180
181
182 // Properties
183 //-------------------------------------------------------------------------
184 /** Getter for property maximumSize.
185 * @return Value of property maximumSize.
186 */
187 public int getMaximumSize() {
188 return maximumSize;
189 }
190 /** Setter for property maximumSize.
191 * @param maximumSize New value of property maximumSize.
192 */
193 public void setMaximumSize(int maximumSize) {
194 this.maximumSize = maximumSize;
195 while (size() > maximumSize) {
196 removeLRU();
197 }
198 }
199
200
201 // add a serial version uid, so that if we change things in the future
202 // without changing the format, we can still deserialize properly.
203 private static final long serialVersionUID = 2197433140769957051L;
204 }