0N/A/*
2362N/A * Copyright (c) 2002, 2009, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage sun.security.util;
0N/A
0N/Aimport java.util.*;
0N/Aimport java.lang.ref.*;
0N/A
0N/A/**
0N/A * Abstract base class and factory for caches. A cache is a key-value mapping.
0N/A * It has properties that make it more suitable for caching than a Map.
0N/A *
0N/A * The factory methods can be used to obtain two different implementations.
0N/A * They have the following properties:
0N/A *
0N/A * . keys and values reside in memory
0N/A *
0N/A * . keys and values must be non-null
0N/A *
0N/A * . maximum size. Replacements are made in LRU order.
0N/A *
0N/A * . optional lifetime, specified in seconds.
0N/A *
0N/A * . save for concurrent use by multiple threads
0N/A *
0N/A * . values are held by either standard references or via SoftReferences.
0N/A * SoftReferences have the advantage that they are automatically cleared
0N/A * by the garbage collector in response to memory demand. This makes it
0N/A * possible to simple set the maximum size to a very large value and let
0N/A * the GC automatically size the cache dynamically depending on the
0N/A * amount of available memory.
0N/A *
0N/A * However, note that because of the way SoftReferences are implemented in
0N/A * HotSpot at the moment, this may not work perfectly as it clears them fairly
0N/A * eagerly. Performance may be improved if the Java heap size is set to larger
0N/A * value using e.g. java -ms64M -mx128M foo.Test
0N/A *
0N/A * Cache sizing: the memory cache is implemented on top of a LinkedHashMap.
0N/A * In its current implementation, the number of buckets (NOT entries) in
0N/A * (Linked)HashMaps is always a power of two. It is recommended to set the
0N/A * maximum cache size to value that uses those buckets fully. For example,
0N/A * if a cache with somewhere between 500 and 1000 entries is desired, a
0N/A * maximum size of 750 would be a good choice: try 1024 buckets, with a
0N/A * load factor of 0.75f, the number of entries can be calculated as
0N/A * buckets / 4 * 3. As mentioned above, with a SoftReference cache, it is
0N/A * generally reasonable to set the size to a fairly large value.
0N/A *
0N/A * @author Andreas Sterbenz
0N/A */
0N/Apublic abstract class Cache {
0N/A
0N/A protected Cache() {
0N/A // empty
0N/A }
0N/A
0N/A /**
0N/A * Return the number of currently valid entries in the cache.
0N/A */
0N/A public abstract int size();
0N/A
0N/A /**
0N/A * Remove all entries from the cache.
0N/A */
0N/A public abstract void clear();
0N/A
0N/A /**
0N/A * Add an entry to the cache.
0N/A */
0N/A public abstract void put(Object key, Object value);
0N/A
0N/A /**
0N/A * Get a value from the cache.
0N/A */
0N/A public abstract Object get(Object key);
0N/A
0N/A /**
0N/A * Remove an entry from the cache.
0N/A */
0N/A public abstract void remove(Object key);
0N/A
0N/A /**
896N/A * Set the maximum size.
896N/A */
896N/A public abstract void setCapacity(int size);
896N/A
896N/A /**
896N/A * Set the timeout(in seconds).
896N/A */
896N/A public abstract void setTimeout(int timeout);
896N/A
896N/A /**
896N/A * accept a visitor
896N/A */
896N/A public abstract void accept(CacheVisitor visitor);
896N/A
896N/A /**
0N/A * Return a new memory cache with the specified maximum size, unlimited
0N/A * lifetime for entries, with the values held by SoftReferences.
0N/A */
0N/A public static Cache newSoftMemoryCache(int size) {
0N/A return new MemoryCache(true, size);
0N/A }
0N/A
0N/A /**
0N/A * Return a new memory cache with the specified maximum size, the
0N/A * specified maximum lifetime (in seconds), with the values held
0N/A * by SoftReferences.
0N/A */
0N/A public static Cache newSoftMemoryCache(int size, int timeout) {
0N/A return new MemoryCache(true, size, timeout);
0N/A }
0N/A
0N/A /**
0N/A * Return a new memory cache with the specified maximum size, unlimited
0N/A * lifetime for entries, with the values held by standard references.
0N/A */
0N/A public static Cache newHardMemoryCache(int size) {
0N/A return new MemoryCache(false, size);
0N/A }
0N/A
0N/A /**
0N/A * Return a dummy cache that does nothing.
0N/A */
0N/A public static Cache newNullCache() {
0N/A return NullCache.INSTANCE;
0N/A }
0N/A
0N/A /**
0N/A * Return a new memory cache with the specified maximum size, the
0N/A * specified maximum lifetime (in seconds), with the values held
0N/A * by standard references.
0N/A */
0N/A public static Cache newHardMemoryCache(int size, int timeout) {
0N/A return new MemoryCache(false, size, timeout);
0N/A }
0N/A
0N/A /**
0N/A * Utility class that wraps a byte array and implements the equals()
0N/A * and hashCode() contract in a way suitable for Maps and caches.
0N/A */
0N/A public static class EqualByteArray {
0N/A
0N/A private final byte[] b;
0N/A private volatile int hash;
0N/A
0N/A public EqualByteArray(byte[] b) {
0N/A this.b = b;
0N/A }
0N/A
0N/A public int hashCode() {
0N/A int h = hash;
0N/A if (h == 0) {
0N/A h = b.length + 1;
0N/A for (int i = 0; i < b.length; i++) {
0N/A h += (b[i] & 0xff) * 37;
0N/A }
0N/A hash = h;
0N/A }
0N/A return h;
0N/A }
0N/A
0N/A public boolean equals(Object obj) {
0N/A if (this == obj) {
0N/A return true;
0N/A }
0N/A if (obj instanceof EqualByteArray == false) {
0N/A return false;
0N/A }
0N/A EqualByteArray other = (EqualByteArray)obj;
0N/A return Arrays.equals(this.b, other.b);
0N/A }
0N/A }
0N/A
896N/A public interface CacheVisitor {
896N/A public void visit(Map<Object, Object> map);
896N/A }
896N/A
0N/A}
0N/A
0N/Aclass NullCache extends Cache {
0N/A
0N/A final static Cache INSTANCE = new NullCache();
0N/A
0N/A private NullCache() {
0N/A // empty
0N/A }
0N/A
0N/A public int size() {
0N/A return 0;
0N/A }
0N/A
0N/A public void clear() {
0N/A // empty
0N/A }
0N/A
0N/A public void put(Object key, Object value) {
0N/A // empty
0N/A }
0N/A
0N/A public Object get(Object key) {
0N/A return null;
0N/A }
0N/A
0N/A public void remove(Object key) {
0N/A // empty
0N/A }
0N/A
896N/A public void setCapacity(int size) {
896N/A // empty
896N/A }
896N/A
896N/A public void setTimeout(int timeout) {
896N/A // empty
896N/A }
896N/A
896N/A public void accept(CacheVisitor visitor) {
896N/A // empty
896N/A }
896N/A
0N/A}
0N/A
0N/Aclass MemoryCache extends Cache {
0N/A
0N/A private final static float LOAD_FACTOR = 0.75f;
0N/A
0N/A // XXXX
0N/A private final static boolean DEBUG = false;
0N/A
0N/A private final Map<Object, CacheEntry> cacheMap;
896N/A private int maxSize;
896N/A private long lifetime;
0N/A private final ReferenceQueue queue;
0N/A
0N/A public MemoryCache(boolean soft, int maxSize) {
0N/A this(soft, maxSize, 0);
0N/A }
0N/A
0N/A public MemoryCache(boolean soft, int maxSize, int lifetime) {
0N/A this.maxSize = maxSize;
0N/A this.lifetime = lifetime * 1000;
0N/A this.queue = soft ? new ReferenceQueue() : null;
0N/A int buckets = (int)(maxSize / LOAD_FACTOR) + 1;
0N/A cacheMap = new LinkedHashMap<Object, CacheEntry>(buckets,
0N/A LOAD_FACTOR, true);
0N/A }
0N/A
0N/A /**
0N/A * Empty the reference queue and remove all corresponding entries
0N/A * from the cache.
0N/A *
0N/A * This method should be called at the beginning of each public
0N/A * method.
0N/A */
0N/A private void emptyQueue() {
0N/A if (queue == null) {
0N/A return;
0N/A }
0N/A int startSize = cacheMap.size();
0N/A while (true) {
0N/A CacheEntry entry = (CacheEntry)queue.poll();
0N/A if (entry == null) {
0N/A break;
0N/A }
0N/A Object key = entry.getKey();
0N/A if (key == null) {
0N/A // key is null, entry has already been removed
0N/A continue;
0N/A }
0N/A CacheEntry currentEntry = cacheMap.remove(key);
0N/A // check if the entry in the map corresponds to the expired
0N/A // entry. If not, readd the entry
0N/A if ((currentEntry != null) && (entry != currentEntry)) {
0N/A cacheMap.put(key, currentEntry);
0N/A }
0N/A }
0N/A if (DEBUG) {
0N/A int endSize = cacheMap.size();
0N/A if (startSize != endSize) {
0N/A System.out.println("*** Expunged " + (startSize - endSize)
0N/A + " entries, " + endSize + " entries left");
0N/A }
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Scan all entries and remove all expired ones.
0N/A */
0N/A private void expungeExpiredEntries() {
0N/A emptyQueue();
0N/A if (lifetime == 0) {
0N/A return;
0N/A }
0N/A int cnt = 0;
0N/A long time = System.currentTimeMillis();
0N/A for (Iterator<CacheEntry> t = cacheMap.values().iterator();
0N/A t.hasNext(); ) {
0N/A CacheEntry entry = t.next();
0N/A if (entry.isValid(time) == false) {
0N/A t.remove();
0N/A cnt++;
0N/A }
0N/A }
0N/A if (DEBUG) {
0N/A if (cnt != 0) {
0N/A System.out.println("Removed " + cnt
0N/A + " expired entries, remaining " + cacheMap.size());
0N/A }
0N/A }
0N/A }
0N/A
0N/A public synchronized int size() {
0N/A expungeExpiredEntries();
0N/A return cacheMap.size();
0N/A }
0N/A
0N/A public synchronized void clear() {
0N/A if (queue != null) {
0N/A // if this is a SoftReference cache, first invalidate() all
0N/A // entries so that GC does not have to enqueue them
0N/A for (CacheEntry entry : cacheMap.values()) {
0N/A entry.invalidate();
0N/A }
0N/A while (queue.poll() != null) {
0N/A // empty
0N/A }
0N/A }
0N/A cacheMap.clear();
0N/A }
0N/A
0N/A public synchronized void put(Object key, Object value) {
0N/A emptyQueue();
0N/A long expirationTime = (lifetime == 0) ? 0 :
0N/A System.currentTimeMillis() + lifetime;
0N/A CacheEntry newEntry = newEntry(key, value, expirationTime, queue);
0N/A CacheEntry oldEntry = cacheMap.put(key, newEntry);
0N/A if (oldEntry != null) {
0N/A oldEntry.invalidate();
0N/A return;
0N/A }
896N/A if (maxSize > 0 && cacheMap.size() > maxSize) {
0N/A expungeExpiredEntries();
0N/A if (cacheMap.size() > maxSize) { // still too large?
0N/A Iterator<CacheEntry> t = cacheMap.values().iterator();
0N/A CacheEntry lruEntry = t.next();
0N/A if (DEBUG) {
0N/A System.out.println("** Overflow removal "
0N/A + lruEntry.getKey() + " | " + lruEntry.getValue());
0N/A }
0N/A t.remove();
0N/A lruEntry.invalidate();
0N/A }
0N/A }
0N/A }
0N/A
0N/A public synchronized Object get(Object key) {
0N/A emptyQueue();
0N/A CacheEntry entry = cacheMap.get(key);
0N/A if (entry == null) {
0N/A return null;
0N/A }
0N/A long time = (lifetime == 0) ? 0 : System.currentTimeMillis();
0N/A if (entry.isValid(time) == false) {
0N/A if (DEBUG) {
0N/A System.out.println("Ignoring expired entry");
0N/A }
0N/A cacheMap.remove(key);
0N/A return null;
0N/A }
0N/A return entry.getValue();
0N/A }
0N/A
0N/A public synchronized void remove(Object key) {
0N/A emptyQueue();
0N/A CacheEntry entry = cacheMap.remove(key);
0N/A if (entry != null) {
0N/A entry.invalidate();
0N/A }
0N/A }
0N/A
896N/A public synchronized void setCapacity(int size) {
896N/A expungeExpiredEntries();
896N/A if (size > 0 && cacheMap.size() > size) {
896N/A Iterator<CacheEntry> t = cacheMap.values().iterator();
896N/A for (int i = cacheMap.size() - size; i > 0; i--) {
896N/A CacheEntry lruEntry = t.next();
896N/A if (DEBUG) {
896N/A System.out.println("** capacity reset removal "
896N/A + lruEntry.getKey() + " | " + lruEntry.getValue());
896N/A }
896N/A t.remove();
896N/A lruEntry.invalidate();
896N/A }
896N/A }
896N/A
896N/A maxSize = size > 0 ? size : 0;
896N/A
896N/A if (DEBUG) {
896N/A System.out.println("** capacity reset to " + size);
896N/A }
896N/A }
896N/A
896N/A public synchronized void setTimeout(int timeout) {
896N/A emptyQueue();
896N/A lifetime = timeout > 0 ? timeout * 1000L : 0L;
896N/A
896N/A if (DEBUG) {
896N/A System.out.println("** lifetime reset to " + timeout);
896N/A }
896N/A }
896N/A
896N/A // it is a heavyweight method.
896N/A public synchronized void accept(CacheVisitor visitor) {
896N/A expungeExpiredEntries();
896N/A Map<Object, Object> cached = getCachedEntries();
896N/A
896N/A visitor.visit(cached);
896N/A }
896N/A
896N/A private Map<Object, Object> getCachedEntries() {
896N/A Map<Object,Object> kvmap = new HashMap<Object,Object>(cacheMap.size());
896N/A
896N/A for (CacheEntry entry : cacheMap.values()) {
896N/A kvmap.put(entry.getKey(), entry.getValue());
896N/A }
896N/A
896N/A return kvmap;
896N/A }
896N/A
0N/A protected CacheEntry newEntry(Object key, Object value,
0N/A long expirationTime, ReferenceQueue queue) {
0N/A if (queue != null) {
0N/A return new SoftCacheEntry(key, value, expirationTime, queue);
0N/A } else {
0N/A return new HardCacheEntry(key, value, expirationTime);
0N/A }
0N/A }
0N/A
0N/A private static interface CacheEntry {
0N/A
0N/A boolean isValid(long currentTime);
0N/A
0N/A void invalidate();
0N/A
0N/A Object getKey();
0N/A
0N/A Object getValue();
0N/A
0N/A }
0N/A
0N/A private static class HardCacheEntry implements CacheEntry {
0N/A
0N/A private Object key, value;
0N/A private long expirationTime;
0N/A
0N/A HardCacheEntry(Object key, Object value, long expirationTime) {
0N/A this.key = key;
0N/A this.value = value;
0N/A this.expirationTime = expirationTime;
0N/A }
0N/A
0N/A public Object getKey() {
0N/A return key;
0N/A }
0N/A
0N/A public Object getValue() {
0N/A return value;
0N/A }
0N/A
0N/A public boolean isValid(long currentTime) {
0N/A boolean valid = (currentTime <= expirationTime);
0N/A if (valid == false) {
0N/A invalidate();
0N/A }
0N/A return valid;
0N/A }
0N/A
0N/A public void invalidate() {
0N/A key = null;
0N/A value = null;
0N/A expirationTime = -1;
0N/A }
0N/A }
0N/A
0N/A private static class SoftCacheEntry
0N/A extends SoftReference implements CacheEntry {
0N/A
0N/A private Object key;
0N/A private long expirationTime;
0N/A
0N/A SoftCacheEntry(Object key, Object value, long expirationTime,
0N/A ReferenceQueue queue) {
0N/A super(value, queue);
0N/A this.key = key;
0N/A this.expirationTime = expirationTime;
0N/A }
0N/A
0N/A public Object getKey() {
0N/A return key;
0N/A }
0N/A
0N/A public Object getValue() {
0N/A return get();
0N/A }
0N/A
0N/A public boolean isValid(long currentTime) {
0N/A boolean valid = (currentTime <= expirationTime) && (get() != null);
0N/A if (valid == false) {
0N/A invalidate();
0N/A }
0N/A return valid;
0N/A }
0N/A
0N/A public void invalidate() {
0N/A clear();
0N/A key = null;
0N/A expirationTime = -1;
0N/A }
0N/A }
0N/A
0N/A}