--- /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();
+            }
+        }
+    }
+}