001: /*
002: * Copyright 2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.myfaces.shared_impl.util;
017:
018: import java.util.*;
019:
020: /**
021: * A bi-level cache based on HashMap for caching objects with minimal sychronization
022: * overhead. The limitation is that <code>remove()</code> is very expensive.
023: * <p>
024: * Access to L1 map is not sychronized, to L2 map is synchronized. New values
025: * are first stored in L2. Once there have been more that a specified mumber of
026: * misses on L1, L1 and L2 maps are merged and the new map assigned to L1
027: * and L2 cleared.
028: * </p>
029: * <p>
030: * IMPORTANT:entrySet(), keySet(), and values() return unmodifiable snapshot collections.
031: * </p>
032: *
033: * @author Anton Koinov (latest modification by $Author: manolito $)
034: * @version $Revision: 380686 $ $Date: 2006-02-24 16:19:28 +0100 (Fr, 24 Feb 2006) $
035: */
036: public abstract class BiLevelCacheMap implements Map {
037: //~ Instance fields ----------------------------------------------------------------------------
038:
039: private static final int INITIAL_SIZE_L1 = 32;
040:
041: /** To preinitialize <code>_cacheL1</code> with default values use an initialization block */
042: protected Map _cacheL1;
043:
044: /** Must be final because it is used for synchronization */
045: private final Map _cacheL2;
046: private final int _mergeThreshold;
047: private int _missCount;
048:
049: //~ Constructors -------------------------------------------------------------------------------
050:
051: public BiLevelCacheMap(int mergeThreshold) {
052: _cacheL1 = new HashMap(INITIAL_SIZE_L1);
053: _cacheL2 = new HashMap(HashMapUtils
054: .calcCapacity(mergeThreshold));
055: _mergeThreshold = mergeThreshold;
056: }
057:
058: //~ Methods ------------------------------------------------------------------------------------
059:
060: public boolean isEmpty() {
061: synchronized (_cacheL2) {
062: return _cacheL1.isEmpty() && _cacheL2.isEmpty();
063: }
064: }
065:
066: public void clear() {
067: synchronized (_cacheL2) {
068: _cacheL1 = new HashMap(); // dafault size
069: _cacheL2.clear();
070: }
071: }
072:
073: public boolean containsKey(Object key) {
074: synchronized (_cacheL2) {
075: return _cacheL1.containsKey(key)
076: || _cacheL2.containsKey(key);
077: }
078: }
079:
080: public boolean containsValue(Object value) {
081: synchronized (_cacheL2) {
082: return _cacheL1.containsValue(value)
083: || _cacheL2.containsValue(value);
084: }
085: }
086:
087: public Set entrySet() {
088: synchronized (_cacheL2) {
089: mergeIfL2NotEmpty();
090: return Collections.unmodifiableSet(_cacheL1.entrySet());
091: }
092: }
093:
094: public Object get(Object key) {
095: Map cacheL1 = _cacheL1;
096: Object retval = cacheL1.get(key);
097: if (retval != null) {
098: return retval;
099: }
100:
101: synchronized (_cacheL2) {
102: // Has another thread merged caches while we were waiting on the mutex? Then check L1 again
103: if (cacheL1 != _cacheL1) {
104: if ((retval = _cacheL1.get(key)) != null) {
105: // do not update miss count (it is not a miss anymore)
106: return retval;
107: }
108: }
109:
110: if ((retval = _cacheL2.get(key)) == null) {
111: retval = newInstance(key);
112: if (retval != null) {
113: put(key, retval);
114: mergeIfNeeded();
115: }
116: } else {
117: mergeIfNeeded();
118: }
119: }
120:
121: return retval;
122: }
123:
124: public Set keySet() {
125: synchronized (_cacheL2) {
126: mergeIfL2NotEmpty();
127: return Collections.unmodifiableSet(_cacheL1.keySet());
128: }
129: }
130:
131: /**
132: * If key is already in cacheL1, the new value will show with a delay,
133: * since merge L2->L1 may not happen immediately. To force the merge sooner,
134: * call <code>size()<code>.
135: */
136: public Object put(Object key, Object value) {
137: synchronized (_cacheL2) {
138: _cacheL2.put(key, value);
139:
140: // not really a miss, but merge to avoid big increase in L2 size
141: // (it cannot be reallocated, it is final)
142: mergeIfNeeded();
143: }
144:
145: return value;
146: }
147:
148: public void putAll(Map map) {
149: synchronized (_cacheL2) {
150: mergeIfL2NotEmpty();
151:
152: // sepatare merge to avoid increasing L2 size too much
153: // (it cannot be reallocated, it is final)
154: merge(map);
155: }
156: }
157:
158: /** This operation is very expensive. A full copy of the Map is created */
159: public Object remove(Object key) {
160: synchronized (_cacheL2) {
161: if (!_cacheL1.containsKey(key)
162: && !_cacheL2.containsKey(key)) {
163: // nothing to remove
164: return null;
165: }
166:
167: Object retval;
168: Map newMap;
169: synchronized (_cacheL1) {
170: // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
171: // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
172: newMap = HashMapUtils.merge(_cacheL1, _cacheL2);
173: retval = newMap.remove(key);
174: }
175:
176: _cacheL1 = newMap;
177: _cacheL2.clear();
178: _missCount = 0;
179: return retval;
180: }
181: }
182:
183: public int size() {
184: // Note: cannot simply return L1.size + L2.size
185: // because there might be overlaping of keys
186: synchronized (_cacheL2) {
187: mergeIfL2NotEmpty();
188: return _cacheL1.size();
189: }
190: }
191:
192: public Collection values() {
193: synchronized (_cacheL2) {
194: mergeIfL2NotEmpty();
195: return Collections
196: .unmodifiableCollection(_cacheL1.values());
197: }
198: }
199:
200: private void mergeIfL2NotEmpty() {
201: if (!_cacheL2.isEmpty()) {
202: merge(_cacheL2);
203: }
204: }
205:
206: private void mergeIfNeeded() {
207: if (++_missCount >= _mergeThreshold) {
208: merge(_cacheL2);
209: }
210: }
211:
212: private void merge(Map map) {
213: Map newMap;
214: synchronized (_cacheL1) {
215: // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
216: // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
217: // But is this enough (in our particular case) to resolve the issues with DCL?
218: newMap = HashMapUtils.merge(_cacheL1, map);
219: }
220: _cacheL1 = newMap;
221: _cacheL2.clear();
222: _missCount = 0;
223: }
224:
225: /**
226: * Subclasses must implement to have automatic creation of new instances
227: * or alternatively can use <code>put<code> to add new items to the cache.<br>
228: *
229: * Implementing this method is prefered to guarantee that there will be only
230: * one instance per key ever created. Calling put() to add items in a multi-
231: * threaded situation will require external synchronization to prevent two
232: * instances for the same key, which defeats the purpose of this cache
233: * (put() is useful when initialization is done during startup and items
234: * are not added during execution or when (temporarily) having possibly two
235: * or more instances of the same key is not of concern).<br>
236: *
237: * @param key lookup key
238: * @return new instace for the requested key
239: */
240: protected abstract Object newInstance(Object key);
241: }
|