Mercurial > hg > blitz_condensed
view 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 source
/* ==================================================================== * 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(); } } } }