KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > myfaces > util > BiLevelCacheMap


1 /*
2  * Copyright 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.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: matze $)
35  * @version $Revision: 1.6 $ $Date: 2004/10/13 11:51:01 $
36  * $Log: BiLevelCacheMap.java,v $
37  * Revision 1.6 2004/10/13 11:51:01 matze
38  * renamed packages to org.apache
39  *
40  * Revision 1.5 2004/08/10 08:23:13 manolito
41  * trivial javadoc changes only
42  *
43  * Revision 1.4 2004/07/01 22:01:13 mwessendorf
44  * ASF switch
45  *
46  * Revision 1.3 2004/04/26 05:54:59 dave0000
47  * Add coercion to ValueBinding (and related changes)
48  *
49  * Revision 1.2 2004/04/01 05:37:34 dave0000
50  * Correct L2->L1 merge condition
51  *
52  */
53 public abstract class BiLevelCacheMap implements Map
54 {
55     //~ Instance fields ----------------------------------------------------------------------------
56
57     private static final int INITIAL_SIZE_L1 = 32;
58
59     /** To preinitialize <code>_cacheL1</code> with default values use an initialization block */
60     protected Map _cacheL1;
61     
62     /** Must be final because it is used for synchronization */
63     private final Map _cacheL2;
64     private final int _mergeThreshold;
65     private int _missCount;
66
67     //~ Constructors -------------------------------------------------------------------------------
68
69     public BiLevelCacheMap(int mergeThreshold)
70     {
71         _cacheL1 = new HashMap(INITIAL_SIZE_L1);
72         _cacheL2 = new HashMap(HashMapUtils.calcCapacity(mergeThreshold));
73         _mergeThreshold = mergeThreshold;
74     }
75
76     //~ Methods ------------------------------------------------------------------------------------
77
78     public boolean isEmpty()
79     {
80         synchronized (_cacheL2) {
81             return _cacheL1.isEmpty() && _cacheL2.isEmpty();
82         }
83     }
84
85     public void clear()
86     {
87         synchronized (_cacheL2) {
88             _cacheL1 = new HashMap(); // dafault size
89 _cacheL2.clear();
90         }
91     }
92
93     public boolean containsKey(Object JavaDoc key)
94     {
95         synchronized (_cacheL2) {
96             return _cacheL1.containsKey(key) || _cacheL2.containsKey(key);
97         }
98     }
99
100     public boolean containsValue(Object JavaDoc value)
101     {
102         synchronized (_cacheL2) {
103             return _cacheL1.containsValue(value) || _cacheL2.containsValue(value);
104         }
105     }
106
107     public Set entrySet()
108     {
109         synchronized (_cacheL2)
110         {
111             mergeIfL2NotEmpty();
112             return Collections.unmodifiableSet(_cacheL1.entrySet());
113         }
114     }
115
116     public Object JavaDoc get(Object JavaDoc key)
117     {
118         Map cacheL1 = _cacheL1;
119         Object JavaDoc retval = cacheL1.get(key);
120         if (retval != null)
121         {
122             return retval;
123         }
124
125         synchronized (_cacheL2)
126         {
127             // Has another thread merged caches while we were waiting on the mutex? Then check L1 again
128 if (cacheL1 != _cacheL1)
129             {
130                 if ((retval = _cacheL1.get(key)) != null)
131                 {
132                     // do not update miss count (it is not a miss anymore)
133 return retval;
134                 }
135             }
136
137             if ((retval = _cacheL2.get(key)) == null)
138             {
139                 retval = newInstance(key);
140                 if (retval != null)
141                 {
142                     put(key, retval);
143                     mergeIfNeeded();
144                 }
145             }
146             else
147             {
148                 mergeIfNeeded();
149             }
150         }
151         
152         return retval;
153     }
154
155     public Set keySet()
156     {
157         synchronized (_cacheL2)
158         {
159             mergeIfL2NotEmpty();
160             return Collections.unmodifiableSet(_cacheL1.keySet());
161         }
162     }
163
164     /**
165      * If key is already in cacheL1, the new value will show with a delay,
166      * since merge L2->L1 may not happen immediately. To force the merge sooner,
167      * call <code>size()<code>.
168      */
169     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value)
170     {
171         synchronized (_cacheL2)
172         {
173             _cacheL2.put(key, value);
174             
175             // not really a miss, but merge to avoid big increase in L2 size
176 // (it cannot be reallocated, it is final)
177 mergeIfNeeded();
178         }
179         
180         return value;
181     }
182
183     public void putAll(Map map)
184     {
185         synchronized (_cacheL2)
186         {
187             mergeIfL2NotEmpty();
188             
189             // sepatare merge to avoid increasing L2 size too much
190 // (it cannot be reallocated, it is final)
191 merge(map);
192         }
193     }
194
195     /** This operation is very expensive. A full copy of the Map is created */
196     public Object JavaDoc remove(Object JavaDoc key)
197     {
198         synchronized (_cacheL2)
199         {
200             if (!_cacheL1.containsKey(key) && !_cacheL2.containsKey(key))
201             {
202                 // nothing to remove
203 return null;
204             }
205             
206             Object JavaDoc retval;
207             Map newMap;
208             synchronized (_cacheL1)
209             {
210                 // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
211 // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
212 newMap = HashMapUtils.merge(_cacheL1, _cacheL2);
213                 retval = newMap.remove(key);
214             }
215             
216             _cacheL1 = newMap;
217             _cacheL2.clear();
218             _missCount = 0;
219             return retval;
220         }
221     }
222
223     public int size()
224     {
225         // Note: cannot simply return L1.size + L2.size
226 // because there might be overlaping of keys
227 synchronized (_cacheL2)
228         {
229             mergeIfL2NotEmpty();
230             return _cacheL1.size();
231         }
232     }
233
234     public Collection values()
235     {
236         synchronized (_cacheL2)
237         {
238             mergeIfL2NotEmpty();
239             return Collections.unmodifiableCollection(_cacheL1.values());
240         }
241     }
242     
243     private void mergeIfL2NotEmpty()
244     {
245         if (!_cacheL2.isEmpty())
246         {
247             merge(_cacheL2);
248         }
249     }
250     
251     private void mergeIfNeeded()
252     {
253         if (++_missCount >= _mergeThreshold)
254         {
255             merge(_cacheL2);
256         }
257     }
258     
259     private void merge(Map map)
260     {
261         Map newMap;
262         synchronized (_cacheL1)
263         {
264             // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
265 // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
266 // But is this enough (in our particular case) to resolve the issues with DCL?
267 newMap = HashMapUtils.merge(_cacheL1, map);
268         }
269         _cacheL1 = newMap;
270         _cacheL2.clear();
271         _missCount = 0;
272     }
273
274     /**
275      * Subclasses must implement to have automatic creation of new instances
276      * or alternatively can use <code>put<code> to add new items to the cache.<br>
277      *
278      * Implementing this method is prefered to guarantee that there will be only
279      * one instance per key ever created. Calling put() to add items in a multi-
280      * threaded situation will require external synchronization to prevent two
281      * instances for the same key, which defeats the purpose of this cache
282      * (put() is useful when initialization is done during startup and items
283      * are not added during execution or when (temporarily) having possibly two
284      * or more instances of the same key is not of concern).<br>
285      *
286      * @param key lookup key
287      * @return new instace for the requested key
288      */
289     protected abstract Object JavaDoc newInstance(Object JavaDoc key);
290 }
291
Popular Tags