ShinyCache.java

/*******************************************************************************
 * Copyright (c) 2004, 2013 Steve Flasby
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * <ul>
 *     <li>Redistributions of source code must retain the above copyright notice,
 *         this list of conditions and the following disclaimer.</li>
 *     <li>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.</li>
 * </ul>
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS 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 COPYRIGHT HOLDER OR 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.
 ******************************************************************************/

package org.flasby.util;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

/**
 * is a cache which handles entry expiry and will ensure that multiple simultaneous requests
 * using the same key will only make a single request to get the missing value.
 * Simultaneous requests will be queued until the value is returned.
 * 
 * Cached entries may have a NULL value.
 * 
 * @author Steve Flasby
 * 21 Sep 2012
 */

public abstract class ShinyCache<Key,Value> implements BlockingCache<Key, Value>{
    
    protected static class ItemHolder<VV> {
        VV value;
        long createdTimestamp = System.nanoTime()/1000000;
        final Semaphore sema = new Semaphore(0, true);
    }

    protected static class ExpiryPolicy {
        protected boolean hasExpired(ItemHolder<?> holder) {
            return false;
        }
    }
    
    private static final class NeverExpires extends ExpiryPolicy {
        public NeverExpires() {
        }}

    private static final class ExpiresAfter extends ExpiryPolicy {
        private final long expiresAfter;
        ExpiresAfter(long expiresAfter) {
            this.expiresAfter = expiresAfter;
        }
        @Override
        protected boolean hasExpired(ItemHolder<?> holder) {
            return (holder.createdTimestamp+expiresAfter <= System.nanoTime()/1000000);
        }
    }

    private static final NeverExpires NEVER = new NeverExpires();
    public static ExpiryPolicy never() {
        return NEVER;
    }
    
    public static ExpiryPolicy expireAfterMillis(long periodInMillis) {
        return new ExpiresAfter(periodInMillis);
    }
    
    public enum EvictionPolicy { LRU, OLDEST }

    final LinkedHashMap<Key, ItemHolder<Value>> cache;
    private final Semaphore entry = new Semaphore(1, true);
    private final ExpiryPolicy expiryPolicy;

    /**
     * simple, ever growing, cache
     */
    public ShinyCache() {
        this(never());
    }
    
    /**
     * cache which expires entries after a fixed lifetime.
     * 
     * @param expiryPolicy
     */
    public ShinyCache(ExpiryPolicy expiryPolicy) {
        this(expiryPolicy, 0, EvictionPolicy.OLDEST);
    }
    
    public ShinyCache(int capacity, EvictionPolicy evictionPolicy) {
        this( never(), capacity, evictionPolicy);
    }
    
    public ShinyCache(final ExpiryPolicy expiryPolicy, final int capacity, final EvictionPolicy evictionPolicy) {
        this.expiryPolicy = expiryPolicy;
        
        cache = new LinkedHashMap<Key, ItemHolder<Value>>( 16, 0.75f, evictionPolicy==EvictionPolicy.LRU){
            private static final long serialVersionUID = 1L;
            @Override
            protected boolean removeEldestEntry( Map.Entry<Key, ItemHolder<Value>> eldest) {
                return ( capacity != 0 && cache.size()>capacity );
            }
        };
    }
    
    /**
     * gets the key form the cache or returns NULL if the Thread was interrupted.
     */
    @Override
    public Value get(Key key) {
        try {
            return getAndWait(key);
        } catch (InterruptedException e) {
            return null;
        }
    }
    
    @Override
    public Value getAndWait(Key key) throws InterruptedException {
        return getAndWait(key, Integer.MAX_VALUE);
    }
    
    @Override
    public Value getAndWait(Key key, long maxWaitMillis) throws InterruptedException {
        long t = System.nanoTime();
        if ( ! entry.tryAcquire(maxWaitMillis, TimeUnit.MILLISECONDS) ) {
            return null;
        }
        
        // See if weve already waited too long & calculate how much longer to wait
        t = maxWaitMillis - (System.nanoTime()-t)/1000000;
        if ( t<=0 ) return null;
        
        ItemHolder<Value> holder = getCache().get(key);
        
        
        if ( holder != null ) {
            boolean acquired = false;
            try {
                acquired = holder.sema.tryAcquire(t, TimeUnit.MILLISECONDS);
                if ( expiryPolicy.hasExpired(holder) ) {
                    // Re-acquire the value
                    holder.value = getValueFor(key);
                    holder.createdTimestamp = System.nanoTime()/1000000;
                }
                return holder.value;
            } finally {
                entry.release();
                if ( acquired ) {
                    holder.sema.release();
                }
            } 
        }
        
        holder = new ItemHolder<Value>();
        getCache().put(key, holder );
        
        holder.value = getValueFor(key);
        holder.sema.release();
        
        entry.release();
        
        return holder.value;
    }

    @Override
    public int size() {
        return getCache().size();
    }
    
    @Override
    public Iterator<Value> iterator() {
        return new Iterator<Value>() {
            private final Iterator<ItemHolder<Value>> iter = getCache().values().iterator();
            @Override
            public boolean hasNext() {
                return iter.hasNext();
            }

            @Override
            public Value next() {
                return iter.next().value;
            }

            @Override
            public void remove() {
                iter.remove();
            }
        };
    }
    
    protected abstract Value getValueFor(Key key);

    LinkedHashMap<Key, ItemHolder<Value>> getCache() {
        return cache;
    }
    
}