1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.dbcp.datasources;
18
19 import java.io.Externalizable;
20 import java.io.IOException;
21 import java.io.ObjectInput;
22 import java.io.ObjectOutput;
23 import java.util.Iterator;
24
25 /**
26 * <p>
27 * This class has been copied from Commons Collections, version 2.1 in order
28 * to eliminate the dependency of dbcp on collections. It has package scope
29 * to prevent its inclusion in the dbcp public API. The class declaration below
30 * should *not* be changed to public.
31 * </p>
32 * <p>
33 * An implementation of a Map which has a maximum size and uses a Least Recently Used
34 * algorithm to remove items from the Map when the maximum size is reached and new items are added.
35 * </p>
36 *
37 * <p>
38 * A synchronized version can be obtained with:
39 * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
40 * If it will be accessed by multiple threads, you _must_ synchronize access
41 * to this Map. Even concurrent get(Object) operations produce indeterminate
42 * behaviour.
43 * </p>
44 *
45 * <p>
46 * Unlike the Collections 1.0 version, this version of LRUMap does use a true
47 * LRU algorithm. The keys for all gets and puts are moved to the front of
48 * the list. LRUMap is now a subclass of SequencedHashMap, and the "LRU"
49 * key is now equivalent to LRUMap.getFirst().
50 * </p>
51 *
52 * @since 1.0
53 * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
54 * @author <a href="mailto:morgand@apache.org">Morgan Delagrange</a>
55 */
56 class LRUMap extends SequencedHashMap implements Externalizable {
57
58 private int maximumSize = 0;
59
60 /**
61 * Default constructor, primarily for the purpose of
62 * de-externalization. This constructors sets a default
63 * LRU limit of 100 keys, but this value may be overridden
64 * internally as a result of de-externalization.
65 */
66 public LRUMap() {
67 this( 100 );
68 }
69
70 /**
71 * Create a new LRUMap with a maximum capacity of <i>i</i>.
72 * Once <i>i</i> capacity is achieved, subsequent gets
73 * and puts will push keys out of the map. See .
74 *
75 * @param i Maximum capacity of the LRUMap
76 */
77 public LRUMap(int i) {
78 super( i );
79 maximumSize = i;
80 }
81
82 /**
83 * <p>Get the value for a key from the Map. The key
84 * will be promoted to the Most Recently Used position.
85 * Note that get(Object) operations will modify
86 * the underlying Collection. Calling get(Object)
87 * inside of an iteration over keys, values, etc. is
88 * currently unsupported.</p>
89 *
90 * @param key Key to retrieve
91 * @return Returns the value. Returns null if the key has a
92 * null value <i>or</i> if the key has no value.
93 */
94 public Object get(Object key) {
95 if(!containsKey(key)) return null;
96
97 Object value = remove(key);
98 super.put(key,value);
99 return value;
100 }
101
102 /**
103 * <p>Removes the key and its Object from the Map.</p>
104 *
105 * <p>(Note: this may result in the "Least Recently Used"
106 * object being removed from the Map. In that case,
107 * the removeLRU() method is called. See javadoc for
108 * removeLRU() for more details.)</p>
109 *
110 * @param key Key of the Object to add.
111 * @param value Object to add
112 * @return Former value of the key
113 * @see #removeLRU
114 */
115 public Object put( Object key, Object value ) {
116
117 int mapSize = size();
118 Object retval = null;
119
120 if ( mapSize >= maximumSize ) {
121
122 // don't retire LRU if you are just
123 // updating an existing key
124 if (!containsKey(key)) {
125 // lets retire the least recently used item in the cache
126 removeLRU();
127 }
128 }
129
130 retval = super.put(key,value);
131
132 return retval;
133 }
134
135 /**
136 * This method is used internally by the class for
137 * finding and removing the LRU Object.
138 */
139 protected void removeLRU() {
140 Object key = getFirstKey();
141 // be sure to call super.get(key), or you're likely to
142 // get infinite promotion recursion
143 Object value = super.get(key);
144
145 remove(key);
146
147 processRemovedLRU(key,value);
148 }
149
150 /**
151 * Subclasses of LRUMap may hook into this method to
152 * provide specialized actions whenever an Object is
153 * automatically removed from the cache. By default,
154 * this method does nothing.
155 *
156 * @param key key that was removed
157 * @param value value of that key (can be null)
158 */
159 protected void processRemovedLRU(Object key, Object value) {
160 }
161
162 // Externalizable interface
163 //-------------------------------------------------------------------------
164 public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException {
165 maximumSize = in.readInt();
166 int size = in.readInt();
167
168 for( int i = 0; i < size; i++ ) {
169 Object key = in.readObject();
170 Object value = in.readObject();
171 put(key,value);
172 }
173 }
174
175 public void writeExternal( ObjectOutput out ) throws IOException {
176 out.writeInt( maximumSize );
177 out.writeInt( size() );
178 for( Iterator iterator = keySet().iterator(); iterator.hasNext();) {
179 Object key = iterator.next();
180 out.writeObject( key );
181 // be sure to call super.get(key), or you're likely to
182 // get infinite promotion recursion
183 Object value = super.get( key );
184 out.writeObject( value );
185 }
186 }
187
188
189 // Properties
190 //-------------------------------------------------------------------------
191 /** Getter for property maximumSize.
192 * @return Value of property maximumSize.
193 */
194 public int getMaximumSize() {
195 return maximumSize;
196 }
197 /** Setter for property maximumSize.
198 * @param maximumSize New value of property maximumSize.
199 */
200 public void setMaximumSize(int maximumSize) {
201 this.maximumSize = maximumSize;
202 while (size() > maximumSize) {
203 removeLRU();
204 }
205 }
206
207
208 // add a serial version uid, so that if we change things in the future
209 // without changing the format, we can still deserialize properly.
210 private static final long serialVersionUID = 2197433140769957051L;
211 }