1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.apache.myfaces.util;
17
18 import java.util.*;
19
20
21 /***
22 * A bi-level cache based on HashMap for caching objects with minimal sychronization
23 * overhead. The limitation is that <code>remove()</code> is very expensive.
24 * <p>
25 * Access to L1 map is not sychronized, to L2 map is synchronized. New values
26 * are first stored in L2. Once there have been more that a specified mumber of
27 * misses on L1, L1 and L2 maps are merged and the new map assigned to L1
28 * and L2 cleared.
29 * </p>
30 * <p>
31 * IMPORTANT:entrySet(), keySet(), and values() return unmodifiable snapshot collections.
32 * </p>
33 *
34 * @author Anton Koinov (latest modification by $Author: grantsmith $)
35 * @version $Revision: 169655 $ $Date: 2005-05-11 16:45:06 +0000 (Wed, 11 May 2005) $
36 */
37 public abstract class BiLevelCacheMap implements Map
38 {
39
40
41 private static final int INITIAL_SIZE_L1 = 32;
42
43 /*** To preinitialize <code>_cacheL1</code> with default values use an initialization block */
44 protected Map _cacheL1;
45
46 /*** Must be final because it is used for synchronization */
47 private final Map _cacheL2;
48 private final int _mergeThreshold;
49 private int _missCount;
50
51
52
53 public BiLevelCacheMap(int mergeThreshold)
54 {
55 _cacheL1 = new HashMap(INITIAL_SIZE_L1);
56 _cacheL2 = new HashMap(HashMapUtils.calcCapacity(mergeThreshold));
57 _mergeThreshold = mergeThreshold;
58 }
59
60
61
62 public boolean isEmpty()
63 {
64 synchronized (_cacheL2) {
65 return _cacheL1.isEmpty() && _cacheL2.isEmpty();
66 }
67 }
68
69 public void clear()
70 {
71 synchronized (_cacheL2) {
72 _cacheL1 = new HashMap();
73 _cacheL2.clear();
74 }
75 }
76
77 public boolean containsKey(Object key)
78 {
79 synchronized (_cacheL2) {
80 return _cacheL1.containsKey(key) || _cacheL2.containsKey(key);
81 }
82 }
83
84 public boolean containsValue(Object value)
85 {
86 synchronized (_cacheL2) {
87 return _cacheL1.containsValue(value) || _cacheL2.containsValue(value);
88 }
89 }
90
91 public Set entrySet()
92 {
93 synchronized (_cacheL2)
94 {
95 mergeIfL2NotEmpty();
96 return Collections.unmodifiableSet(_cacheL1.entrySet());
97 }
98 }
99
100 public Object get(Object key)
101 {
102 Map cacheL1 = _cacheL1;
103 Object retval = cacheL1.get(key);
104 if (retval != null)
105 {
106 return retval;
107 }
108
109 synchronized (_cacheL2)
110 {
111
112 if (cacheL1 != _cacheL1)
113 {
114 if ((retval = _cacheL1.get(key)) != null)
115 {
116
117 return retval;
118 }
119 }
120
121 if ((retval = _cacheL2.get(key)) == null)
122 {
123 retval = newInstance(key);
124 if (retval != null)
125 {
126 put(key, retval);
127 mergeIfNeeded();
128 }
129 }
130 else
131 {
132 mergeIfNeeded();
133 }
134 }
135
136 return retval;
137 }
138
139 public Set keySet()
140 {
141 synchronized (_cacheL2)
142 {
143 mergeIfL2NotEmpty();
144 return Collections.unmodifiableSet(_cacheL1.keySet());
145 }
146 }
147
148 /***
149 * If key is already in cacheL1, the new value will show with a delay,
150 * since merge L2->L1 may not happen immediately. To force the merge sooner,
151 * call <code>size()<code>.
152 */
153 public Object put(Object key, Object value)
154 {
155 synchronized (_cacheL2)
156 {
157 _cacheL2.put(key, value);
158
159
160
161 mergeIfNeeded();
162 }
163
164 return value;
165 }
166
167 public void putAll(Map map)
168 {
169 synchronized (_cacheL2)
170 {
171 mergeIfL2NotEmpty();
172
173
174
175 merge(map);
176 }
177 }
178
179 /*** This operation is very expensive. A full copy of the Map is created */
180 public Object remove(Object key)
181 {
182 synchronized (_cacheL2)
183 {
184 if (!_cacheL1.containsKey(key) && !_cacheL2.containsKey(key))
185 {
186
187 return null;
188 }
189
190 Object retval;
191 Map newMap;
192 synchronized (_cacheL1)
193 {
194
195
196 newMap = HashMapUtils.merge(_cacheL1, _cacheL2);
197 retval = newMap.remove(key);
198 }
199
200 _cacheL1 = newMap;
201 _cacheL2.clear();
202 _missCount = 0;
203 return retval;
204 }
205 }
206
207 public int size()
208 {
209
210
211 synchronized (_cacheL2)
212 {
213 mergeIfL2NotEmpty();
214 return _cacheL1.size();
215 }
216 }
217
218 public Collection values()
219 {
220 synchronized (_cacheL2)
221 {
222 mergeIfL2NotEmpty();
223 return Collections.unmodifiableCollection(_cacheL1.values());
224 }
225 }
226
227 private void mergeIfL2NotEmpty()
228 {
229 if (!_cacheL2.isEmpty())
230 {
231 merge(_cacheL2);
232 }
233 }
234
235 private void mergeIfNeeded()
236 {
237 if (++_missCount >= _mergeThreshold)
238 {
239 merge(_cacheL2);
240 }
241 }
242
243 private void merge(Map map)
244 {
245 Map newMap;
246 synchronized (_cacheL1)
247 {
248
249
250
251 newMap = HashMapUtils.merge(_cacheL1, map);
252 }
253 _cacheL1 = newMap;
254 _cacheL2.clear();
255 _missCount = 0;
256 }
257
258 /***
259 * Subclasses must implement to have automatic creation of new instances
260 * or alternatively can use <code>put<code> to add new items to the cache.<br>
261 *
262 * Implementing this method is prefered to guarantee that there will be only
263 * one instance per key ever created. Calling put() to add items in a multi-
264 * threaded situation will require external synchronization to prevent two
265 * instances for the same key, which defeats the purpose of this cache
266 * (put() is useful when initialization is done during startup and items
267 * are not added during execution or when (temporarily) having possibly two
268 * or more instances of the same key is not of concern).<br>
269 *
270 * @param key lookup key
271 * @return new instace for the requested key
272 */
273 protected abstract Object newInstance(Object key);
274 }