Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
BiLevelCacheMap |
|
| 1.6470588235294117;1.647 |
1 | /* | |
2 | * Licensed to the Apache Software Foundation (ASF) under one | |
3 | * or more contributor license agreements. See the NOTICE file | |
4 | * distributed with this work for additional information | |
5 | * regarding copyright ownership. The ASF licenses this file | |
6 | * to you under the Apache License, Version 2.0 (the | |
7 | * "License"); you may not use this file except in compliance | |
8 | * with the License. You may obtain a copy of the License at | |
9 | * | |
10 | * http://www.apache.org/licenses/LICENSE-2.0 | |
11 | * | |
12 | * Unless required by applicable law or agreed to in writing, | |
13 | * software distributed under the License is distributed on an | |
14 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | |
15 | * KIND, either express or implied. See the License for the | |
16 | * specific language governing permissions and limitations | |
17 | * under the License. | |
18 | */ | |
19 | package org.apache.myfaces.shared_impl.util; | |
20 | ||
21 | import java.util.Collection; | |
22 | import java.util.Collections; | |
23 | import java.util.HashMap; | |
24 | import java.util.Map; | |
25 | import java.util.Set; | |
26 | ||
27 | /** | |
28 | * A bi-level cache based on HashMap for caching objects with minimal sychronization | |
29 | * overhead. The limitation is that <code>remove()</code> is very expensive. | |
30 | * <p> | |
31 | * Access to L1 map is not sychronized, to L2 map is synchronized. New values | |
32 | * are first stored in L2. Once there have been more that a specified mumber of | |
33 | * misses on L1, L1 and L2 maps are merged and the new map assigned to L1 | |
34 | * and L2 cleared. | |
35 | * </p> | |
36 | * <p> | |
37 | * IMPORTANT:entrySet(), keySet(), and values() return unmodifiable snapshot collections. | |
38 | * </p> | |
39 | * | |
40 | * @author Anton Koinov (latest modification by $Author: matzew $) | |
41 | * @version $Revision: 557350 $ $Date: 2007-07-18 13:19:50 -0500 (Wed, 18 Jul 2007) $ | |
42 | */ | |
43 | public abstract class BiLevelCacheMap implements Map | |
44 | { | |
45 | //~ Instance fields ---------------------------------------------------------------------------- | |
46 | ||
47 | private static final int INITIAL_SIZE_L1 = 32; | |
48 | ||
49 | /** To preinitialize <code>_cacheL1</code> with default values use an initialization block */ | |
50 | protected Map _cacheL1; | |
51 | ||
52 | /** Must be final because it is used for synchronization */ | |
53 | private final Map _cacheL2; | |
54 | private final int _mergeThreshold; | |
55 | private int _missCount; | |
56 | ||
57 | //~ Constructors ------------------------------------------------------------------------------- | |
58 | ||
59 | public BiLevelCacheMap(int mergeThreshold) | |
60 | 0 | { |
61 | 0 | _cacheL1 = new HashMap(INITIAL_SIZE_L1); |
62 | 0 | _cacheL2 = new HashMap(HashMapUtils.calcCapacity(mergeThreshold)); |
63 | 0 | _mergeThreshold = mergeThreshold; |
64 | 0 | } |
65 | ||
66 | //~ Methods ------------------------------------------------------------------------------------ | |
67 | ||
68 | public boolean isEmpty() | |
69 | { | |
70 | 0 | synchronized (_cacheL2) { |
71 | 0 | return _cacheL1.isEmpty() && _cacheL2.isEmpty(); |
72 | 0 | } |
73 | } | |
74 | ||
75 | public void clear() | |
76 | { | |
77 | 0 | synchronized (_cacheL2) { |
78 | 0 | _cacheL1 = new HashMap(); // dafault size |
79 | 0 | _cacheL2.clear(); |
80 | 0 | } |
81 | 0 | } |
82 | ||
83 | public boolean containsKey(Object key) | |
84 | { | |
85 | 0 | synchronized (_cacheL2) { |
86 | 0 | return _cacheL1.containsKey(key) || _cacheL2.containsKey(key); |
87 | 0 | } |
88 | } | |
89 | ||
90 | public boolean containsValue(Object value) | |
91 | { | |
92 | 0 | synchronized (_cacheL2) { |
93 | 0 | return _cacheL1.containsValue(value) || _cacheL2.containsValue(value); |
94 | 0 | } |
95 | } | |
96 | ||
97 | public Set entrySet() | |
98 | { | |
99 | 0 | synchronized (_cacheL2) |
100 | { | |
101 | 0 | mergeIfL2NotEmpty(); |
102 | 0 | return Collections.unmodifiableSet(_cacheL1.entrySet()); |
103 | 0 | } |
104 | } | |
105 | ||
106 | public Object get(Object key) | |
107 | { | |
108 | 0 | Map cacheL1 = _cacheL1; |
109 | 0 | Object retval = cacheL1.get(key); |
110 | 0 | if (retval != null) |
111 | { | |
112 | 0 | return retval; |
113 | } | |
114 | ||
115 | 0 | synchronized (_cacheL2) |
116 | { | |
117 | // Has another thread merged caches while we were waiting on the mutex? Then check L1 again | |
118 | 0 | if (cacheL1 != _cacheL1) |
119 | { | |
120 | 0 | if ((retval = _cacheL1.get(key)) != null) |
121 | { | |
122 | // do not update miss count (it is not a miss anymore) | |
123 | 0 | return retval; |
124 | } | |
125 | } | |
126 | ||
127 | 0 | if ((retval = _cacheL2.get(key)) == null) |
128 | { | |
129 | 0 | retval = newInstance(key); |
130 | 0 | if (retval != null) |
131 | { | |
132 | 0 | put(key, retval); |
133 | 0 | mergeIfNeeded(); |
134 | } | |
135 | } | |
136 | else | |
137 | { | |
138 | 0 | mergeIfNeeded(); |
139 | } | |
140 | 0 | } |
141 | ||
142 | 0 | return retval; |
143 | } | |
144 | ||
145 | public Set keySet() | |
146 | { | |
147 | 0 | synchronized (_cacheL2) |
148 | { | |
149 | 0 | mergeIfL2NotEmpty(); |
150 | 0 | return Collections.unmodifiableSet(_cacheL1.keySet()); |
151 | 0 | } |
152 | } | |
153 | ||
154 | /** | |
155 | * If key is already in cacheL1, the new value will show with a delay, | |
156 | * since merge L2->L1 may not happen immediately. To force the merge sooner, | |
157 | * call <code>size()<code>. | |
158 | */ | |
159 | public Object put(Object key, Object value) | |
160 | { | |
161 | 0 | synchronized (_cacheL2) |
162 | { | |
163 | 0 | _cacheL2.put(key, value); |
164 | ||
165 | // not really a miss, but merge to avoid big increase in L2 size | |
166 | // (it cannot be reallocated, it is final) | |
167 | 0 | mergeIfNeeded(); |
168 | 0 | } |
169 | ||
170 | 0 | return value; |
171 | } | |
172 | ||
173 | public void putAll(Map map) | |
174 | { | |
175 | 0 | synchronized (_cacheL2) |
176 | { | |
177 | 0 | mergeIfL2NotEmpty(); |
178 | ||
179 | // sepatare merge to avoid increasing L2 size too much | |
180 | // (it cannot be reallocated, it is final) | |
181 | 0 | merge(map); |
182 | 0 | } |
183 | 0 | } |
184 | ||
185 | /** This operation is very expensive. A full copy of the Map is created */ | |
186 | public Object remove(Object key) | |
187 | { | |
188 | 0 | synchronized (_cacheL2) |
189 | { | |
190 | 0 | if (!_cacheL1.containsKey(key) && !_cacheL2.containsKey(key)) |
191 | { | |
192 | // nothing to remove | |
193 | 0 | return null; |
194 | } | |
195 | ||
196 | Object retval; | |
197 | Map newMap; | |
198 | 0 | synchronized (_cacheL1) |
199 | { | |
200 | // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized | |
201 | // at least until JVM 1.5 where this should be guaranteed by the volatile keyword | |
202 | 0 | newMap = HashMapUtils.merge(_cacheL1, _cacheL2); |
203 | 0 | retval = newMap.remove(key); |
204 | 0 | } |
205 | ||
206 | 0 | _cacheL1 = newMap; |
207 | 0 | _cacheL2.clear(); |
208 | 0 | _missCount = 0; |
209 | 0 | return retval; |
210 | 0 | } |
211 | } | |
212 | ||
213 | public int size() | |
214 | { | |
215 | // Note: cannot simply return L1.size + L2.size | |
216 | // because there might be overlaping of keys | |
217 | 0 | synchronized (_cacheL2) |
218 | { | |
219 | 0 | mergeIfL2NotEmpty(); |
220 | 0 | return _cacheL1.size(); |
221 | 0 | } |
222 | } | |
223 | ||
224 | public Collection values() | |
225 | { | |
226 | 0 | synchronized (_cacheL2) |
227 | { | |
228 | 0 | mergeIfL2NotEmpty(); |
229 | 0 | return Collections.unmodifiableCollection(_cacheL1.values()); |
230 | 0 | } |
231 | } | |
232 | ||
233 | private void mergeIfL2NotEmpty() | |
234 | { | |
235 | 0 | if (!_cacheL2.isEmpty()) |
236 | { | |
237 | 0 | merge(_cacheL2); |
238 | } | |
239 | 0 | } |
240 | ||
241 | private void mergeIfNeeded() | |
242 | { | |
243 | 0 | if (++_missCount >= _mergeThreshold) |
244 | { | |
245 | 0 | merge(_cacheL2); |
246 | } | |
247 | 0 | } |
248 | ||
249 | private void merge(Map map) | |
250 | { | |
251 | Map newMap; | |
252 | 0 | synchronized (_cacheL1) |
253 | { | |
254 | // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized | |
255 | // at least until JVM 1.5 where this should be guaranteed by the volatile keyword | |
256 | // But is this enough (in our particular case) to resolve the issues with DCL? | |
257 | 0 | newMap = HashMapUtils.merge(_cacheL1, map); |
258 | 0 | } |
259 | 0 | _cacheL1 = newMap; |
260 | 0 | _cacheL2.clear(); |
261 | 0 | _missCount = 0; |
262 | 0 | } |
263 | ||
264 | /** | |
265 | * Subclasses must implement to have automatic creation of new instances | |
266 | * or alternatively can use <code>put<code> to add new items to the cache.<br> | |
267 | * | |
268 | * Implementing this method is prefered to guarantee that there will be only | |
269 | * one instance per key ever created. Calling put() to add items in a multi- | |
270 | * threaded situation will require external synchronization to prevent two | |
271 | * instances for the same key, which defeats the purpose of this cache | |
272 | * (put() is useful when initialization is done during startup and items | |
273 | * are not added during execution or when (temporarily) having possibly two | |
274 | * or more instances of the same key is not of concern).<br> | |
275 | * | |
276 | * @param key lookup key | |
277 | * @return new instace for the requested key | |
278 | */ | |
279 | protected abstract Object newInstance(Object key); | |
280 | } |