Mercurial > hg > blitz_stable
diff src/com/go/trove/util/Depot.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/com/go/trove/util/Depot.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,618 @@ +/* ==================================================================== + * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group + * ==================================================================== + * The Tea Software License, Version 1.1 + * + * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. The end-user documentation included with the redistribution, + * if any, must include the following acknowledgment: + * "This product includes software developed by the + * Walt Disney Internet Group (http://opensource.go.com/)." + * Alternately, this acknowledgment may appear in the software itself, + * if and wherever such third-party acknowledgments normally appear. + * + * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must + * not be used to endorse or promote products derived from this + * software without prior written permission. For written + * permission, please contact opensource@dig.com. + * + * 5. Products derived from this software may not be called "Tea", + * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet", + * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior + * written permission of the Walt Disney Internet Group. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * For more information about Tea, please see http://opensource.go.com/. + */ + +package com.go.trove.util; + +import java.util.*; +import com.go.trove.util.tq.*; + +/****************************************************************************** + * Depot implements a simple and efficient caching strategy. It is thread-safe, + * and it allows requests of different objects to occur concurrently. Depot + * is best suited as a front-end for accessing objects from a remote device, + * like a database. If the remote device is not responding, the Depot will + * continue to serve invalidated objects so that the requester may continue + * as normal. + * <p> + * Depot is designed as a cache in front of an object {@link Factory factory}. + * Objects may be invalidated, but they are not explicitly removed from the + * cache until a replacement has been provided by the factory. The factory is + * invoked from another thread, allowing for the requester to timeout and use + * an invalidated object. When the factory eventually finishes, its object will + * be cached. + * <p> + * By allowing for eventual completion of the factory, Depot enables + * applications to dynamically adjust to the varying performance and + * reliability of remote data providers. + * <p> + * Depot will never return an object or null that did not originate from the + * factory. When retrieving an object that wasn't found cached, a call to the + * factory will block until it is finished. + * <p> + * Objects may be invalided from the Depot + * {@link PerishablesFactory automatically}. This approach is based on a fixed + * time expiration and is somewhat inflexible. An ideal invalidation strategy + * requires asynchronous notification from the actual data providers. + * + * @author Brian S O'Neill, Travis Greer + * @version + * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 01/07/09 <!-- $--> + * @see MultiKey + */ +public class Depot { + private Factory mDefaultFactory; + private Map mValidCache; + private Map mInvalidCache; + private TransactionQueue mQueue; + private long mTimeout; + + private Map mRetrievers; + + private final Object mExpireLock = new Object(); + private Map mExpirations; + + /** + * @param factory Default factory from which objects are obtained + * @param validCache Map to use for caching valid objects + * @param invalidCache Map to use for caching invalid objects + * @param tq TransactionQueue for scheduling factory invocations. + * @param timeout Default timeout (in milliseconds) to apply to "get" + * method. + */ + public Depot(Factory factory, Map validCache, Map invalidCache, + TransactionQueue tq, long timeout) { + init(factory, validCache, invalidCache, tq, timeout); + } + + /** + * @param factory Default factory from which objects are obtained + * @param cacheSize Number of items guaranteed to be in cache, if negative, + * cache is completely disabled. + * @param tq TransactionQueue for scheduling factory invocations. + * @param timeout Default timeout (in milliseconds) to apply to "get" + * method. + */ + public Depot(Factory factory, int cacheSize, + TransactionQueue tq, long timeout) { + Map valid, invalid; + + if (cacheSize < 0) { + valid = Utils.VOID_MAP; + invalid = Utils.VOID_MAP; + } + else { + valid = new Cache(cacheSize); + invalid = new Cache((Cache)valid); + } + + init(factory, valid, invalid, tq, timeout); + } + + private void init(Factory factory, Map validCache, Map invalidCache, + TransactionQueue tq, long timeout) { + mDefaultFactory = factory; + mValidCache = Collections.synchronizedMap(validCache); + mInvalidCache = Collections.synchronizedMap(invalidCache); + mQueue = tq; + mTimeout = timeout; + + mRetrievers = Collections.synchronizedMap(new HashMap()); + } + + /** + * Returns the total number objects in the Depot. + */ + public int size() { + synchronized (mValidCache) { + return mValidCache.size() + mInvalidCache.size(); + } + } + + public boolean isEmpty() { + synchronized (mValidCache) { + return mValidCache.isEmpty() && mInvalidCache.isEmpty(); + } + } + + /** + * Returns the number of valid objects in the Depot. + */ + public int validSize() { + return mValidCache.size(); + } + + /** + * Returns the number of invalid objects in the Depot. + */ + public int invalidSize() { + return mInvalidCache.size(); + } + + /** + * Retrieve an object from the Depot. If the requested object is in the + * cache of valid objects, it is returned immediately. If the object is + * found in the cache of invalid objects, then it will be returned only if + * the factory cannot create a replacement in a timely manner. If the + * requested object is not in any cache at all, the factory is called to + * create the object, and the calling thread will block until the factory + * has finished. + * + * @param key key of object to retrieve + */ + public Object get(Object key) { + return get(mDefaultFactory, key, mTimeout); + } + + /** + * Retrieve an object from the Depot. If the requested object is in the + * cache of valid objects, it is returned immediately. If the object is + * found in the cache of invalid objects, then it will be returned only if + * the factory cannot create a replacement in a timely manner. If the + * requested object is not in any cache at all, the factory is called to + * create the object, and the calling thread will block until the factory + * has finished. + * + * @param key key of object to retrieve + * @param timeout max time (in milliseconds) to wait for an invalid value + * to be replaced from the factory, if negative, wait forever. Ignored if + * no cached value exists at all. + */ + public Object get(Object key, long timeout) { + return get(mDefaultFactory, key, timeout); + } + + /** + * Retrieve an object from the Depot. If the requested object is in the + * cache of valid objects, it is returned immediately. If the object is + * found in the cache of invalid objects, then it will be returned only if + * the factory cannot create a replacement in a timely manner. If the + * requested object is not in any cache at all, the factory is called to + * create the object, and the calling thread will block until the factory + * has finished. + * + * @param factory factory to use to retrieve object if not cached + * @param key key of object to retrieve + */ + public Object get(Factory factory, Object key) { + return get(factory, key, mTimeout); + } + + /** + * Retrieve an object from the Depot. If the requested object is in the + * cache of valid objects, it is returned immediately. If the object is + * found in the cache of invalid objects, then it will be returned only if + * the factory cannot create a replacement in a timely manner. If the + * requested object is not in any cache at all, the factory is called to + * create the object, and the calling thread will block until the factory + * has finished. + * + * @param factory factory to use to retrieve object if not cached + * @param key key of object to retrieve + * @param timeout max time (in milliseconds) to wait for an invalid value + * to be replaced from the factory, if negative, wait forever. Ignored if + * no cached value exists at all. + */ + public Object get(Factory factory, Object key, long timeout) { + Retriever r; + + key = Utils.intern(key); + synchronized (key) { + Object value = mValidCache.get(key); + if (value != null || mValidCache.containsKey(key)) { + validTest: { + if (value instanceof Perishable) { + if (!((Perishable)value).isValid()) { + break validTest; + } + } + + synchronized (mExpireLock) { + if (mExpirations == null) { + return value; + } + Long expire = (Long)mExpirations.get(key); + if (expire == null || + System.currentTimeMillis() <= expire.longValue()) { + // Value is still valid. + return value; + } + + // Value has expired. + mExpirations.remove(key); + } + } + + mValidCache.remove(key); + mInvalidCache.put(key, value); + + r = retrieve(factory, key, value, false); + } + else { + value = mInvalidCache.get(key); + + if (value != null || mInvalidCache.containsKey(key)) { + r = retrieve(factory, key, value, false); + } + else { + // Wait forever since not even an invalid value exists. + timeout = -1; + r = retrieve(factory, key, value, true); + } + } + + if (r == null) { + return value; + } + else { + return r.waitForValue(timeout); + } + } + } + + /** + * Invalidate the object referenced by the given key, if it is already + * cached in this Depot. Invalidated objects are not removed from the + * Depot until a replacement object has been successfully created from the + * factory. + * + * @param key key of object to invalidate + */ + public void invalidate(Object key) { + key = Utils.intern(key); + synchronized (key) { + if (mValidCache.containsKey(key)) { + Object value = mValidCache.remove(key); + mInvalidCache.put(key, value); + } + } + } + + /** + * Invalidates objects in the Depot, using a filter. Each key that the + * filter accepts is invalidated. + */ + public void invalidateAll(Filter filter) { + synchronized (mValidCache) { + Iterator it = mValidCache.entrySet().iterator(); + while (it.hasNext()) { + Map.Entry entry = (Map.Entry)it.next(); + Object key = entry.getKey(); + if (filter.accept(key)) { + it.remove(); + mInvalidCache.put(key, entry.getValue()); + } + } + } + } + + /** + * Invalidates all the objects in the Depot. + */ + public void invalidateAll() { + synchronized (mValidCache) { + synchronized (mInvalidCache) { + mInvalidCache.putAll(mValidCache); + mValidCache.clear(); + } + } + } + + /** + * Put a value into the Depot, bypassing the factory. Invalidating an + * object and relying on the factory to produce a new value is generally + * preferred. This method will notify any threads waiting on a factory to + * produce a value, but it will not disrupt the behavior of the factory. + * + * @param key key with which to associate the value. + * @param value value to be associated with key. + */ + public void put(Object key, Object value) { + key = Utils.intern(key); + synchronized (key) { + mInvalidCache.remove(key); + mValidCache.put(key, value); + Retriever r = (Retriever)mRetrievers.get(key); + if (r != null) { + // Bypass the factory produced value so that any waiting + // threads are notified. + r.bypassValue(value); + } + } + } + + /** + * Completely removes an item from the Depot's caches. Invalidating an + * object is preferred, and remove should be called only if the object + * should absolutely never be used again. + */ + public Object remove(Object key) { + key = Utils.intern(key); + synchronized (key) { + if (mValidCache.containsKey(key)) { + return mValidCache.remove(key); + } + if (mInvalidCache.containsKey(key)) { + return mInvalidCache.remove(key); + } + } + return null; + } + + /** + * Completely removes all the items from the Depot that the given filter + * accepts. + */ + public void removeAll(Filter filter) { + synchronized (mValidCache) { + synchronized (mInvalidCache) { + Iterator it = mValidCache.keySet().iterator(); + while (it.hasNext()) { + Object key = it.next(); + if (filter.accept(key)) { + it.remove(); + } + } + it = mInvalidCache.keySet().iterator(); + while (it.hasNext()) { + Object key = it.next(); + if (filter.accept(key)) { + it.remove(); + } + } + } + } + } + + /** + * Completely removes all items from the Depot's caches. Invalidating all + * the objects is preferred, and clear should be called only if all the + * cached objects should absolutely never be used again. + */ + public void clear() { + synchronized (mValidCache) { + synchronized (mInvalidCache) { + mValidCache.clear(); + mInvalidCache.clear(); + } + } + } + + void setExpiration(Object key, long duration) { + Long expire = new Long + (System.currentTimeMillis() + duration); + synchronized (mExpireLock) { + if (mExpirations == null) { + mExpirations = new IdentityMap(); + } + mExpirations.put(key, expire); + } + } + + /** + * Caller must lock interned key. + */ + private Retriever retrieve(Factory factory, + Object key, + Object originalValue, + boolean priority) + { + Retriever r = (Retriever)mRetrievers.get(key); + + if (r == null) { + r = new Retriever(factory, key, originalValue); + if (mQueue.enqueue(r)) { + mRetrievers.put(key, r); + } + else if (priority) { + // Skip the queue, service it in this thread. + mRetrievers.put(key, r); + r.service(); + } + else { + return null; + } + } + + return r; + } + + /** + * Implement this interface in order for Depot to retrieve objects when + * needed, often in a thread other than the requester's. + * + * @see PerishablesFactory + */ + public interface Factory { + /** + * Create an object that is mapped by the given key. This method must + * be thread-safe, but simply making it synchronized may severely + * impact the Depot's support of concurrent activity. + * <p> + * Create may abort its operation by throwing an InterruptedException. + * This forces an invalid object to be used or null if none. If an + * InterruptedException is thrown, nether the invalid object or null + * will be cached. Null is cached only if the factory returns it + * directly. + * + * @throws InterruptedException explicitly throwing this exception + * allows the factory to abort creating an object. + */ + public Object create(Object key) throws InterruptedException; + } + + /** + * A special kind of Factory that creates objects that are considered + * invalid after a specific amount of time has elapsed. + */ + public interface PerishablesFactory extends Factory { + /** + * Returns the maximum amout of time (in milliseconds) that objects + * from this factory should remain valid. Returning a value less than + * or equal to zero causes objects to be immediately invalidated. + */ + public long getValidDuration(); + } + + /** + * Values returned from the Factories may implement this interface if they + * manually handle expiration. + */ + public interface Perishable { + /** + * If this Perishable is still valid, but it came from a + * PerishablesFactory, it may be considered invalid if the valid + * duration has elapsed. + */ + public boolean isValid(); + } + + public interface Filter { + /** + * Returns true if the given key should be included in an operation, + * such as invalidation. + */ + public boolean accept(Object key); + } + + private class Retriever implements Transaction { + private final Factory mFactory; + private final Object mKey; + private Object mValue; + private boolean mDone; + + /** + * @param key Key must already be interned. + */ + public Retriever(Factory factory, Object key, Object originalValue) { + mFactory = factory; + mKey = key; + mValue = originalValue; + } + + public Object waitForValue(long timeout) { + try { + synchronized (mKey) { + if (mDone || timeout == 0) { + return mValue; + } + + if (timeout < 0) { + timeout = 0; + } + + mKey.wait(timeout); + } + } + catch (InterruptedException e) { + } + + return mValue; + } + + public void bypassValue(Object value) { + synchronized (mKey) { + mValue = value; + mKey.notifyAll(); + } + } + + public void service() { + try { + Thread t = Thread.currentThread(); + String originalName = t.getName(); + t.setName(originalName + ' ' + mKey); + try { + mValue = mFactory.create(mKey); + synchronized (mKey) { + if (mFactory instanceof PerishablesFactory) { + long duration = ((PerishablesFactory)mFactory) + .getValidDuration(); + if (duration <= 0) { + mInvalidCache.put(mKey, mValue); + mValidCache.remove(mKey); + } + else { + mInvalidCache.remove(mKey); + mValidCache.put(mKey, mValue); + setExpiration(mKey, duration); + } + } + else { + mInvalidCache.remove(mKey); + mValidCache.put(mKey, mValue); + } + } + } + catch (InterruptedException e) { + } + finally { + t.setName(originalName); + } + } + finally { + done(); + } + } + + public void cancel() { + done(); + } + + private void done() { + mDone = true; + mRetrievers.remove(mKey); + synchronized (mKey) { + mKey.notifyAll(); + } + } + } +}