001: /*
002: * @(#)Cache.java 1.6 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: */
026:
027: package sun.security.util;
028:
029: import java.util.*;
030: import java.lang.ref.*;
031:
032: /**
033: * Abstract base class and factory for caches. A cache is a key-value mapping.
034: * It has properties that make it more suitable for caching than a Map.
035: *
036: * The factory methods can be used to obtain two different implementations.
037: * They have the following properties:
038: *
039: * . keys and values reside in memory
040: *
041: * . keys and values must be non-null
042: *
043: * . maximum size. Replacements are made in LRU order.
044: *
045: * . optional lifetime, specified in seconds.
046: *
047: * . save for concurrent use by multiple threads
048: *
049: * . values are held by either standard references or via SoftReferences.
050: * SoftReferences have the advantage that they are automatically cleared
051: * by the garbage collector in response to memory demand. This makes it
052: * possible to simple set the maximum size to a very large value and let
053: * the GC automatically size the cache dynamically depending on the
054: * amount of available memory.
055: *
056: * However, note that because of the way SoftReferences are implemented in
057: * HotSpot at the moment, this may not work perfectly as it clears them fairly
058: * eagerly. Performance may be improved if the Java heap size is set to larger
059: * value using e.g. java -ms64M -mx128M foo.Test
060: *
061: * Cache sizing: the memory cache is implemented on top of a LinkedHashMap.
062: * In its current implementation, the number of buckets (NOT entries) in
063: * (Linked)HashMaps is always a power of two. It is recommended to set the
064: * maximum cache size to value that uses those buckets fully. For example,
065: * if a cache with somewhere between 500 and 1000 entries is desired, a
066: * maximum size of 750 would be a good choice: try 1024 buckets, with a
067: * load factor of 0.75f, the number of entries can be calculated as
068: * buckets / 4 * 3. As mentioned above, with a SoftReference cache, it is
069: * generally reasonable to set the size to a fairly large value.
070: *
071: * @version 1.6, 10/10/06
072: * @author Andreas Sterbenz
073: */
074: public abstract class Cache {
075:
076: protected Cache() {
077: // empty
078: }
079:
080: /**
081: * Return the number of currently valid entries in the cache.
082: */
083: public abstract int size();
084:
085: /**
086: * Remove all entries from the cache.
087: */
088: public abstract void clear();
089:
090: /**
091: * Add an entry to the cache.
092: */
093: public abstract void put(Object key, Object value);
094:
095: /**
096: * Get a value from the cache.
097: */
098: public abstract Object get(Object key);
099:
100: /**
101: * Remove an entry from the cache.
102: */
103: public abstract void remove(Object key);
104:
105: /**
106: * Return a new memory cache with the specified maximum size, unlimited
107: * lifetime for entries, with the values held by SoftReferences.
108: */
109: public static Cache newSoftMemoryCache(int size) {
110: return new MemoryCache(true, size);
111: }
112:
113: /**
114: * Return a new memory cache with the specified maximum size, the
115: * specified maximum lifetime (in seconds), with the values held
116: * by SoftReferences.
117: */
118: public static Cache newSoftMemoryCache(int size, int timeout) {
119: return new MemoryCache(true, size, timeout);
120: }
121:
122: /**
123: * Return a new memory cache with the specified maximum size, unlimited
124: * lifetime for entries, with the values held by standard references.
125: */
126: public static Cache newHardMemoryCache(int size) {
127: return new MemoryCache(false, size);
128: }
129:
130: /**
131: * Return a dummy cache that does nothing.
132: */
133: public static Cache newNullCache() {
134: return NullCache.INSTANCE;
135: }
136:
137: /**
138: * Return a new memory cache with the specified maximum size, the
139: * specified maximum lifetime (in seconds), with the values held
140: * by standard references.
141: */
142: public static Cache newHardMemoryCache(int size, int timeout) {
143: return new MemoryCache(false, size, timeout);
144: }
145:
146: /**
147: * Utility class that wraps a byte array and implements the equals()
148: * and hashCode() contract in a way suitable for Maps and caches.
149: */
150: public static class EqualByteArray {
151:
152: private final byte[] b;
153: private volatile int hash;
154:
155: public EqualByteArray(byte[] b) {
156: this .b = b;
157: }
158:
159: public int hashCode() {
160: int h = hash;
161: if (h == 0) {
162: h = b.length + 1;
163: for (int i = 0; i < b.length; i++) {
164: h += (b[i] & 0xff) * 37;
165: }
166: hash = h;
167: }
168: return h;
169: }
170:
171: public boolean equals(Object obj) {
172: if (this == obj) {
173: return true;
174: }
175: if (obj instanceof EqualByteArray == false) {
176: return false;
177: }
178: EqualByteArray other = (EqualByteArray) obj;
179: return Arrays.equals(this .b, other.b);
180: }
181: }
182:
183: }
184:
185: class NullCache extends Cache {
186:
187: final static Cache INSTANCE = new NullCache();
188:
189: private NullCache() {
190: // empty
191: }
192:
193: public int size() {
194: return 0;
195: }
196:
197: public void clear() {
198: // empty
199: }
200:
201: public void put(Object key, Object value) {
202: // empty
203: }
204:
205: public Object get(Object key) {
206: return null;
207: }
208:
209: public void remove(Object key) {
210: // empty
211: }
212:
213: }
214:
215: class MemoryCache extends Cache {
216:
217: private final static float LOAD_FACTOR = 0.75f;
218:
219: private final static boolean DEBUG = false;
220:
221: private final Map cacheMap;
222: private final int maxSize;
223: private final int lifetime;
224: private final ReferenceQueue queue;
225:
226: public MemoryCache(boolean soft, int maxSize) {
227: this (soft, maxSize, 0);
228: }
229:
230: public MemoryCache(boolean soft, int maxSize, int lifetime) {
231: this .maxSize = maxSize;
232: this .lifetime = lifetime * 1000;
233: this .queue = soft ? new ReferenceQueue() : null;
234: int buckets = (int) (maxSize / LOAD_FACTOR) + 1;
235: cacheMap = new LinkedHashMap(buckets, LOAD_FACTOR, true);
236: }
237:
238: /**
239: * Empty the reference queue and remove all corresponding entries
240: * from the cache.
241: *
242: * This method should be called at the beginning of each public
243: * method.
244: */
245: private void emptyQueue() {
246: if (queue == null) {
247: return;
248: }
249: int startSize = cacheMap.size();
250: while (true) {
251: CacheEntry entry = (CacheEntry) queue.poll();
252: if (entry == null) {
253: break;
254: }
255: Object key = entry.getKey();
256: if (key == null) {
257: // key is null, entry has already been removed
258: continue;
259: }
260: CacheEntry currentEntry = (CacheEntry) cacheMap.remove(key);
261: // check if the entry in the map corresponds to the expired
262: // entry. If not, readd the entry
263: if ((currentEntry != null) && (entry != currentEntry)) {
264: cacheMap.put(key, currentEntry);
265: }
266: }
267: if (DEBUG) {
268: int endSize = cacheMap.size();
269: if (startSize != endSize) {
270: System.out.println("*** Expunged "
271: + (startSize - endSize) + " entries, "
272: + endSize + " entries left");
273: }
274: }
275: }
276:
277: /**
278: * Scan all entries and remove all expired ones.
279: */
280: private void expungeExpiredEntries() {
281: emptyQueue();
282: if (lifetime == 0) {
283: return;
284: }
285: int cnt = 0;
286: long time = System.currentTimeMillis();
287: for (Iterator t = cacheMap.values().iterator(); t.hasNext();) {
288: CacheEntry entry = (CacheEntry) t.next();
289: if (entry.isValid(time) == false) {
290: t.remove();
291: cnt++;
292: }
293: }
294: if (DEBUG) {
295: if (cnt != 0) {
296: System.out.println("Removed " + cnt
297: + " expired entries, remaining "
298: + cacheMap.size());
299: }
300: }
301: }
302:
303: public synchronized int size() {
304: expungeExpiredEntries();
305: return cacheMap.size();
306: }
307:
308: public synchronized void clear() {
309: if (queue != null) {
310: // if this is a SoftReference cache, first invalidate() all
311: // entries so that GC does not have to enqueue them
312: for (Iterator t = cacheMap.values().iterator(); t.hasNext();) {
313: CacheEntry entry = (CacheEntry) t.next();
314: entry.invalidate();
315: }
316: while (queue.poll() != null) {
317: // empty
318: }
319: }
320: cacheMap.clear();
321: }
322:
323: public synchronized void put(Object key, Object value) {
324: emptyQueue();
325: long expirationTime = (lifetime == 0) ? 0 : System
326: .currentTimeMillis()
327: + lifetime;
328: CacheEntry newEntry = newEntry(key, value, expirationTime,
329: queue);
330: CacheEntry oldEntry = (CacheEntry) cacheMap.put(key, newEntry);
331: if (oldEntry != null) {
332: oldEntry.invalidate();
333: return;
334: }
335: if (cacheMap.size() > maxSize) {
336: expungeExpiredEntries();
337: if (cacheMap.size() > maxSize) { // still too large?
338: Iterator t = cacheMap.values().iterator();
339: CacheEntry lruEntry = (CacheEntry) t.next();
340: if (DEBUG) {
341: System.out.println("** Overflow removal "
342: + lruEntry.getKey() + " | "
343: + lruEntry.getValue());
344: }
345: t.remove();
346: lruEntry.invalidate();
347: }
348: }
349: }
350:
351: public synchronized Object get(Object key) {
352: emptyQueue();
353: CacheEntry entry = (CacheEntry) cacheMap.get(key);
354: if (entry == null) {
355: return null;
356: }
357: long time = (lifetime == 0) ? 0 : System.currentTimeMillis();
358: if (entry.isValid(time) == false) {
359: if (DEBUG) {
360: System.out.println("Ignoring expired entry");
361: }
362: cacheMap.remove(key);
363: return null;
364: }
365: return entry.getValue();
366: }
367:
368: public synchronized void remove(Object key) {
369: emptyQueue();
370: CacheEntry entry = (CacheEntry) cacheMap.remove(key);
371: if (entry != null) {
372: entry.invalidate();
373: }
374: }
375:
376: protected CacheEntry newEntry(Object key, Object value,
377: long expirationTime, ReferenceQueue queue) {
378: if (queue != null) {
379: return new SoftCacheEntry(key, value, expirationTime, queue);
380: } else {
381: return new HardCacheEntry(key, value, expirationTime);
382: }
383: }
384:
385: private static interface CacheEntry {
386:
387: boolean isValid(long currentTime);
388:
389: void invalidate();
390:
391: Object getKey();
392:
393: Object getValue();
394:
395: }
396:
397: private static class HardCacheEntry implements CacheEntry {
398:
399: private Object key, value;
400: private long expirationTime;
401:
402: HardCacheEntry(Object key, Object value, long expirationTime) {
403: this .key = key;
404: this .value = value;
405: this .expirationTime = expirationTime;
406: }
407:
408: public Object getKey() {
409: return key;
410: }
411:
412: public Object getValue() {
413: return value;
414: }
415:
416: public boolean isValid(long currentTime) {
417: boolean valid = (currentTime <= expirationTime);
418: if (valid == false) {
419: invalidate();
420: }
421: return valid;
422: }
423:
424: public void invalidate() {
425: key = null;
426: value = null;
427: expirationTime = -1;
428: }
429: }
430:
431: private static class SoftCacheEntry extends SoftReference implements
432: CacheEntry {
433:
434: private Object key;
435: private long expirationTime;
436:
437: SoftCacheEntry(Object key, Object value, long expirationTime,
438: ReferenceQueue queue) {
439: super (value, queue);
440: this .key = key;
441: this .expirationTime = expirationTime;
442: }
443:
444: public Object getKey() {
445: return key;
446: }
447:
448: public Object getValue() {
449: return get();
450: }
451:
452: public boolean isValid(long currentTime) {
453: boolean valid = (currentTime <= expirationTime)
454: && (get() != null);
455: if (valid == false) {
456: invalidate();
457: }
458: return valid;
459: }
460:
461: public void invalidate() {
462: clear();
463: key = null;
464: expirationTime = -1;
465: }
466: }
467:
468: }
|