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;
	}
	
}