001: /*
002: * Copyright (c) 2003 The Visigoth Software Society. All rights
003: * reserved.
004: *
005: * Redistribution and use in source and binary forms, with or without
006: * modification, are permitted provided that the following conditions
007: * are met:
008: *
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: *
012: * 2. Redistributions in binary form must reproduce the above copyright
013: * notice, this list of conditions and the following disclaimer in
014: * the documentation and/or other materials provided with the
015: * distribution.
016: *
017: * 3. The end-user documentation included with the redistribution, if
018: * any, must include the following acknowledgement:
019: * "This product includes software developed by the
020: * Visigoth Software Society (http://www.visigoths.org/)."
021: * Alternately, this acknowledgement may appear in the software itself,
022: * if and wherever such third-party acknowledgements normally appear.
023: *
024: * 4. Neither the name "FreeMarker", "Visigoth", nor any of the names of the
025: * project contributors may be used to endorse or promote products derived
026: * from this software without prior written permission. For written
027: * permission, please contact visigoths@visigoths.org.
028: *
029: * 5. Products derived from this software may not be called "FreeMarker" or "Visigoth"
030: * nor may "FreeMarker" or "Visigoth" appear in their names
031: * without prior written permission of the Visigoth Software Society.
032: *
033: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
034: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
035: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
036: * DISCLAIMED. IN NO EVENT SHALL THE VISIGOTH SOFTWARE SOCIETY OR
037: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
038: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
039: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
040: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
041: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
042: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
043: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
044: * SUCH DAMAGE.
045: * ====================================================================
046: *
047: * This software consists of voluntary contributions made by many
048: * individuals on behalf of the Visigoth Software Society. For more
049: * information on the Visigoth Software Society, please see
050: * http://www.visigoths.org/
051: */
052:
053: package freemarker.cache;
054:
055: import java.lang.ref.ReferenceQueue;
056: import java.lang.ref.SoftReference;
057: import java.util.HashMap;
058: import java.util.Map;
059:
060: /**
061: * A cache storage that implements a two-level Most Recently Used cache. In the
062: * first level, items are strongly referenced up to the specified maximum. When
063: * the maximum is exceeded, the least recently used item is moved into the
064: * second level cache, where they are softly referenced, up to another specified
065: * maximum. When the second level maximum is also exceeded, the least recently
066: * used item is discarded altogether. This cache storage is a generalization of
067: * both {@link StrongCacheStorage} and {@link SoftCacheStorage} - the effect of
068: * both of them can be achieved by setting one maximum to zero and the other to
069: * the largest positive integer.
070: * This class is <em>NOT</em> thread-safe. If it is accessed from multiple
071: * threads concurrently, proper synchronization must be provided by the callers.
072: * Note that {@link TemplateCache}, the natural user of this class provides the
073: * necessary synchronizations when it uses the class.
074: * @author Attila Szegedi
075: * @version $Id: MruCacheStorage.java,v 1.7.2.1 2007/04/02 13:07:32 szegedia Exp $
076: */
077: public class MruCacheStorage implements CacheStorage {
078: private final MruEntry strongHead = new MruEntry();
079: private final MruEntry softHead = new MruEntry();
080: {
081: softHead.linkAfter(strongHead);
082: }
083: private final Map map = new HashMap();
084: private final ReferenceQueue refQueue = new ReferenceQueue();
085: private final int maxStrongSize;
086: private final int maxSoftSize;
087: private int strongSize = 0;
088: private int softSize = 0;
089:
090: /**
091: * Creates a new MRU cache storage with specified maximum cache sizes. Each
092: * cache size can vary between 0 and {@link Integer#MAX_VALUE}.
093: * @param maxStrongSize the maximum number of strongly referenced templates
094: * @param maxSoftSize the maximum number of softly referenced templates
095: */
096: public MruCacheStorage(int maxStrongSize, int maxSoftSize) {
097: if (maxStrongSize < 0)
098: throw new IllegalArgumentException("maxStrongSize < 0");
099: if (maxSoftSize < 0)
100: throw new IllegalArgumentException("maxSoftSize < 0");
101: this .maxStrongSize = maxStrongSize;
102: this .maxSoftSize = maxSoftSize;
103: }
104:
105: public Object get(Object key) {
106: removeClearedReferences();
107: MruEntry entry = (MruEntry) map.get(key);
108: if (entry == null) {
109: return null;
110: }
111: relinkEntryAfterStrongHead(entry, null);
112: Object value = entry.getValue();
113: if (value instanceof MruReference) {
114: // This can only happen with maxStrongSize == 0
115: return ((MruReference) value).get();
116: }
117: return value;
118: }
119:
120: public void put(Object key, Object value) {
121: removeClearedReferences();
122: MruEntry entry = (MruEntry) map.get(key);
123: if (entry == null) {
124: entry = new MruEntry(key, value);
125: map.put(key, entry);
126: linkAfterStrongHead(entry);
127: } else {
128: relinkEntryAfterStrongHead(entry, value);
129: }
130:
131: }
132:
133: public void remove(Object key) {
134: removeClearedReferences();
135: removeInternal(key);
136: }
137:
138: private void removeInternal(Object key) {
139: MruEntry entry = (MruEntry) map.remove(key);
140: if (entry != null) {
141: unlinkEntryAndInspectIfSoft(entry);
142: }
143: }
144:
145: public void clear() {
146: strongHead.makeHead();
147: softHead.linkAfter(strongHead);
148: map.clear();
149: strongSize = softSize = 0;
150: // Quick refQueue processing
151: while (refQueue.poll() != null)
152: ;
153: }
154:
155: private void relinkEntryAfterStrongHead(MruEntry entry,
156: Object newValue) {
157: if (unlinkEntryAndInspectIfSoft(entry) && newValue == null) {
158: // Turn soft reference into strong reference, unless is was cleared
159: MruReference mref = (MruReference) entry.getValue();
160: Object strongValue = mref.get();
161: if (strongValue != null) {
162: entry.setValue(strongValue);
163: linkAfterStrongHead(entry);
164: } else {
165: map.remove(mref.getKey());
166: }
167: } else {
168: if (newValue != null) {
169: entry.setValue(newValue);
170: }
171: linkAfterStrongHead(entry);
172: }
173: }
174:
175: private void linkAfterStrongHead(MruEntry entry) {
176: entry.linkAfter(strongHead);
177: if (strongSize == maxStrongSize) {
178: // softHead.previous is LRU strong entry
179: MruEntry lruStrong = softHead.getPrevious();
180: // Attila: This is equaivalent to maxStrongSize != 0
181: // DD: But entry.linkAfter(strongHead) was just excuted above, so
182: // lruStrong != strongHead is true even if maxStrongSize == 0.
183: if (lruStrong != strongHead) {
184: lruStrong.unlink();
185: if (maxSoftSize > 0) {
186: lruStrong.linkAfter(softHead);
187: lruStrong.setValue(new MruReference(lruStrong,
188: refQueue));
189: if (softSize == maxSoftSize) {
190: // List is circular, so strongHead.previous is LRU soft entry
191: MruEntry lruSoft = strongHead.getPrevious();
192: lruSoft.unlink();
193: map.remove(lruSoft.getKey());
194: } else {
195: ++softSize;
196: }
197: } else {
198: map.remove(lruStrong.getKey());
199: }
200: }
201: } else {
202: ++strongSize;
203: }
204: }
205:
206: private boolean unlinkEntryAndInspectIfSoft(MruEntry entry) {
207: entry.unlink();
208: if (entry.getValue() instanceof MruReference) {
209: --softSize;
210: return true;
211: } else {
212: --strongSize;
213: return false;
214: }
215: }
216:
217: private void removeClearedReferences() {
218: for (;;) {
219: MruReference ref = (MruReference) refQueue.poll();
220: if (ref == null) {
221: break;
222: }
223: removeInternal(ref.getKey());
224: }
225: }
226:
227: private static final class MruEntry {
228: private MruEntry prev;
229: private MruEntry next;
230: private final Object key;
231: private Object value;
232:
233: /**
234: * Used solely to construct the head element
235: */
236: MruEntry() {
237: makeHead();
238: key = value = null;
239: }
240:
241: MruEntry(Object key, Object value) {
242: this .key = key;
243: this .value = value;
244: }
245:
246: Object getKey() {
247: return key;
248: }
249:
250: Object getValue() {
251: return value;
252: }
253:
254: void setValue(Object value) {
255: this .value = value;
256: }
257:
258: MruEntry getPrevious() {
259: return prev;
260: }
261:
262: void linkAfter(MruEntry entry) {
263: next = entry.next;
264: entry.next = this ;
265: prev = entry;
266: next.prev = this ;
267: }
268:
269: void unlink() {
270: next.prev = prev;
271: prev.next = next;
272: prev = null;
273: next = null;
274: }
275:
276: void makeHead() {
277: prev = next = this ;
278: }
279: }
280:
281: private static class MruReference extends SoftReference {
282: private final Object key;
283:
284: MruReference(MruEntry entry, ReferenceQueue queue) {
285: super (entry.getValue(), queue);
286: this .key = entry.getKey();
287: }
288:
289: Object getKey() {
290: return key;
291: }
292: }
293: }
|