src/org/tukaani/xz/BasicArrayCache.java - platform/external/xz-java - Git at Google

 /*
  * BasicArrayCache
  *
  * Author: Lasse Collin <lasse.collin@tukaani.org>
  *
  * This file has been put into the public domain.
  * You can do whatever you want with this file.
  */

 package org.tukaani.xz;

 import java.lang.ref.Reference;
 import java.lang.ref.SoftReference;
 import java.util.Arrays;
 import java.util.LinkedHashMap;
 import java.util.Map;

 /**
  * A basic {@link ArrayCache} implementation.
  * <p>
  * This caches exact array sizes, that is, {@code getByteArray} will return
  * an array whose size is exactly the requested size. A limited number
  * of different array sizes are cached at the same time; least recently used
  * sizes will be dropped from the cache if needed (can happen if several
  * different (de)compression options are used with the same cache).
  * <p>
  * The current implementation uses
  * {@link java.util.LinkedHashMap LinkedHashMap} to map different array sizes
  * to separate array-based data structures which hold
  * {@link java.lang.ref.SoftReference SoftReferences} to the cached arrays.
  * In the common case this should give good performance and fairly low
  * memory usage overhead.
  * <p>
  * A statically allocated global {@code BasicArrayCache} instance is
  * available via {@link #getInstance()} which is a good choice in most
  * situations where caching is wanted.
  *
  * @since 1.7
  */
 public class BasicArrayCache extends ArrayCache {
     /**
      * Arrays smaller than this many elements will not be cached.
      */
     private static final int CACHEABLE_SIZE_MIN = 32 << 10;

     /**
      * Number of stacks i.e. how many different array sizes to cache.
      */
     private static final int STACKS_MAX = 32;

     /**
      * Number of arrays of the same type and size to keep in the cache.
      * (ELEMENTS_PER_STACK - 1) is used as a bit mask so ELEMENTS_PER_STACK
      * must be a power of two!
      */
     private static final int ELEMENTS_PER_STACK = 512;

     /**
      * A thread-safe stack-like data structure whose {@code push} method
      * overwrites the oldest element in the stack if the stack is full.
      */
     private static class CyclicStack<T> {
         /**
          * Array that holds the elements in the cyclic stack.
          */
         @SuppressWarnings("unchecked")
         private final T[] elements = (T[])new Object[ELEMENTS_PER_STACK];

         /**
          * Read-write position in the {@code refs} array.
          * The most recently added element is in {@code refs[pos]}.
          * If it is {@code null}, then the stack is empty and all
          * elements in {@code refs} are {@code null}.
          * <p>
          * Note that {@code pop()} always modifies {@code pos}, even if
          * the stack is empty. This means that when the first element is
          * added by {@code push(T)}, it can get added in any position in
          * {@code refs} and the stack will start growing from there.
          */
         private int pos = 0;

         /**
          * Gets the most recently added element from the stack.
          * If the stack is empty, {@code null} is returned.
          */
         public synchronized T pop() {
             T e = elements[pos];
             elements[pos] = null;
             pos = (pos - 1) & (ELEMENTS_PER_STACK - 1);
             return e;
         }

         /**
          * Adds a new element to the stack. If the stack is full, the oldest
          * element is overwritten.
          */
         public synchronized void push(T e) {
             pos = (pos + 1) & (ELEMENTS_PER_STACK - 1);
             elements[pos] = e;
         }
     }

     /**
      * Maps Integer (array size) to stacks of references to arrays. At most
      * STACKS_MAX number of stacks are kept in the map (LRU cache).
      */
     private static class CacheMap<T>
             extends LinkedHashMap<Integer, CyclicStack<Reference<T>>> {
         /**
          * This class won't be serialized but this is needed
          * to silence a compiler warning.
          */
         private static final long serialVersionUID = 1L;

         /**
          * Creates a new CacheMap.
          */
         public CacheMap() {
             // The map may momentarily have at most STACKS_MAX + 1 entries
             // when put(K,V) has inserted a new entry but hasn't called
             // removeEldestEntry yet. Using 2 * STACKS_MAX as the initial
             // (and the final) capacity should give good performance. 0.75 is
             // the default load factor and in this case it guarantees that
             // the map will never need to be rehashed because
             // (STACKS_MAX + 1) / 0.75 < 2 * STACKS_MAX.
             //
             // That last argument is true to get LRU cache behavior together
             // with the overriden removeEldestEntry method.
             super(2 * STACKS_MAX, 0.75f, true);
         }

         /**
          * Returns true if the map is full and the least recently used stack
          * should be removed.
          */
         protected boolean removeEldestEntry(
                 Map.Entry<Integer, CyclicStack<Reference<T>>> eldest) {
             return size() > STACKS_MAX;
         }
     }

     /**
      * Helper class for the singleton instance.
      * This is allocated only if {@code getInstance()} is called.
      */
     private static final class LazyHolder {
         static final BasicArrayCache INSTANCE = new BasicArrayCache();
     }

     /**
      * Returns a statically-allocated {@code BasicArrayCache} instance.
      * This is often a good choice when a cache is needed.
      */
     public static BasicArrayCache getInstance() {
         return LazyHolder.INSTANCE;
     }

     /**
      * Stacks for cached byte arrays.
      */
     private final CacheMap<byte[]> byteArrayCache = new CacheMap<byte[]>();

     /**
      * Stacks for cached int arrays.
      */
     private final CacheMap<int[]> intArrayCache = new CacheMap<int[]>();

     /**
      * Gets {@code T[size]} from the given {@code cache}.
      * If no such array is found, {@code null} is returned.
      */
     private static <T> T getArray(CacheMap<T> cache, int size) {
         // putArray doesn't add small arrays to the cache and so it's
         // pointless to look for small arrays here.
         if (size < CACHEABLE_SIZE_MIN)
             return null;

         // Try to find a stack that holds arrays of T[size].
         CyclicStack<Reference<T>> stack;
         synchronized(cache) {
             stack = cache.get(size);
         }

         if (stack == null)
             return null;

         // Try to find a non-cleared Reference from the stack.
         T array;
         do {
             Reference<T> r = stack.pop();
             if (r == null)
                 return null;

             array = r.get();
         } while (array == null);

         return array;
     }

     /**
      * Puts the {@code array} of {@code size} elements long into
      * the {@code cache}.
      */
     private static <T> void putArray(CacheMap<T> cache, T array, int size) {
         // Small arrays aren't cached.
         if (size < CACHEABLE_SIZE_MIN)
             return;

         CyclicStack<Reference<T>> stack;

         synchronized(cache) {
             // Get a stack that holds arrays of T[size]. If no such stack
             // exists, allocate a new one. If the cache already had STACKS_MAX
             // number of stacks, the least recently used stack is removed by
             // cache.put (it calls removeEldestEntry).
             stack = cache.get(size);
             if (stack == null) {
                 stack = new CyclicStack<Reference<T>>();
                 cache.put(size, stack);
             }
         }

         stack.push(new SoftReference<T>(array));
     }

     /**
      * Allocates a new byte array, hopefully reusing an existing
      * array from the cache.
      *
      * @param       size        size of the array to allocate
      *
      * @param       fillWithZeros
      *                          if true, all the elements of the returned
      *                          array will be zero; if false, the contents
      *                          of the returned array is undefined
      */
     public byte[] getByteArray(int size, boolean fillWithZeros) {
         byte[] array = getArray(byteArrayCache, size);

         if (array == null)
             array = new byte[size];
         else if (fillWithZeros)
             Arrays.fill(array, (byte)0x00);

         return array;
     }

     /**
      * Puts the given byte array to the cache. The caller must no longer
      * use the array.
      * <p>
      * Small arrays aren't cached and will be ignored by this method.
      */
     public void putArray(byte[] array) {
         putArray(byteArrayCache, array, array.length);
     }

     /**
      * This is like getByteArray but for int arrays.
      */
     public int[] getIntArray(int size, boolean fillWithZeros) {
         int[] array = getArray(intArrayCache, size);

         if (array == null)
             array = new int[size];
         else if (fillWithZeros)
             Arrays.fill(array, 0);

         return array;
     }

     /**
      * Puts the given int array to the cache. The caller must no longer
      * use the array.
      * <p>
      * Small arrays aren't cached and will be ignored by this method.
      */
     public void putArray(int[] array) {
         putArray(intArrayCache, array, array.length);
     }
 }
	/*
	* BasicArrayCache
	*
	* Author: Lasse Collin <lasse.collin@tukaani.org>
	*
	* This file has been put into the public domain.
	* You can do whatever you want with this file.
	*/

	package org.tukaani.xz;

	import java.lang.ref.Reference;
	import java.lang.ref.SoftReference;
	import java.util.Arrays;
	import java.util.LinkedHashMap;
	import java.util.Map;

	/**
	* A basic {@link ArrayCache} implementation.
	* <p>
	* This caches exact array sizes, that is, {@code getByteArray} will return
	* an array whose size is exactly the requested size. A limited number
	* of different array sizes are cached at the same time; least recently used
	* sizes will be dropped from the cache if needed (can happen if several
	* different (de)compression options are used with the same cache).
	* <p>
	* The current implementation uses
	* {@link java.util.LinkedHashMap LinkedHashMap} to map different array sizes
	* to separate array-based data structures which hold
	* {@link java.lang.ref.SoftReference SoftReferences} to the cached arrays.
	* In the common case this should give good performance and fairly low
	* memory usage overhead.
	* <p>
	* A statically allocated global {@code BasicArrayCache} instance is
	* available via {@link #getInstance()} which is a good choice in most
	* situations where caching is wanted.
	*
	* @since 1.7
	*/
	public class BasicArrayCache extends ArrayCache {
	/**
	* Arrays smaller than this many elements will not be cached.
	*/
	private static final int CACHEABLE_SIZE_MIN = 32 << 10;

	/**
	* Number of stacks i.e. how many different array sizes to cache.
	*/
	private static final int STACKS_MAX = 32;

	/**
	* Number of arrays of the same type and size to keep in the cache.
	* (ELEMENTS_PER_STACK - 1) is used as a bit mask so ELEMENTS_PER_STACK
	* must be a power of two!
	*/
	private static final int ELEMENTS_PER_STACK = 512;

	/**
	* A thread-safe stack-like data structure whose {@code push} method
	* overwrites the oldest element in the stack if the stack is full.
	*/
	private static class CyclicStack<T> {
	/**
	* Array that holds the elements in the cyclic stack.
	*/
	@SuppressWarnings("unchecked")
	private final T[] elements = (T[])new Object[ELEMENTS_PER_STACK];

	/**
	* Read-write position in the {@code refs} array.
	* The most recently added element is in {@code refs[pos]}.
	* If it is {@code null}, then the stack is empty and all
	* elements in {@code refs} are {@code null}.
	* <p>
	* Note that {@code pop()} always modifies {@code pos}, even if
	* the stack is empty. This means that when the first element is
	* added by {@code push(T)}, it can get added in any position in
	* {@code refs} and the stack will start growing from there.
	*/
	private int pos = 0;

	/**
	* Gets the most recently added element from the stack.
	* If the stack is empty, {@code null} is returned.
	*/
	public synchronized T pop() {
	T e = elements[pos];
	elements[pos] = null;
	pos = (pos - 1) & (ELEMENTS_PER_STACK - 1);
	return e;
	}

	/**
	* Adds a new element to the stack. If the stack is full, the oldest
	* element is overwritten.
	*/
	public synchronized void push(T e) {
	pos = (pos + 1) & (ELEMENTS_PER_STACK - 1);
	elements[pos] = e;
	}
	}

	/**
	* Maps Integer (array size) to stacks of references to arrays. At most
	* STACKS_MAX number of stacks are kept in the map (LRU cache).
	*/
	private static class CacheMap<T>
	extends LinkedHashMap<Integer, CyclicStack<Reference<T>>> {
	/**
	* This class won't be serialized but this is needed
	* to silence a compiler warning.
	*/
	private static final long serialVersionUID = 1L;

	/**
	* Creates a new CacheMap.
	*/
	public CacheMap() {
	// The map may momentarily have at most STACKS_MAX + 1 entries
	// when put(K,V) has inserted a new entry but hasn't called
	// removeEldestEntry yet. Using 2 * STACKS_MAX as the initial
	// (and the final) capacity should give good performance. 0.75 is
	// the default load factor and in this case it guarantees that
	// the map will never need to be rehashed because
	// (STACKS_MAX + 1) / 0.75 < 2 * STACKS_MAX.
	//
	// That last argument is true to get LRU cache behavior together
	// with the overriden removeEldestEntry method.
	super(2 * STACKS_MAX, 0.75f, true);
	}

	/**
	* Returns true if the map is full and the least recently used stack
	* should be removed.
	*/
	protected boolean removeEldestEntry(
	Map.Entry<Integer, CyclicStack<Reference<T>>> eldest) {
	return size() > STACKS_MAX;
	}
	}

	/**
	* Helper class for the singleton instance.
	* This is allocated only if {@code getInstance()} is called.
	*/
	private static final class LazyHolder {
	static final BasicArrayCache INSTANCE = new BasicArrayCache();
	}

	/**
	* Returns a statically-allocated {@code BasicArrayCache} instance.
	* This is often a good choice when a cache is needed.
	*/
	public static BasicArrayCache getInstance() {
	return LazyHolder.INSTANCE;
	}

	/**
	* Stacks for cached byte arrays.
	*/
	private final CacheMap<byte[]> byteArrayCache = new CacheMap<byte[]>();

	/**
	* Stacks for cached int arrays.
	*/
	private final CacheMap<int[]> intArrayCache = new CacheMap<int[]>();

	/**
	* Gets {@code T[size]} from the given {@code cache}.
	* If no such array is found, {@code null} is returned.
	*/
	private static <T> T getArray(CacheMap<T> cache, int size) {
	// putArray doesn't add small arrays to the cache and so it's
	// pointless to look for small arrays here.
	if (size < CACHEABLE_SIZE_MIN)
	return null;

	// Try to find a stack that holds arrays of T[size].
	CyclicStack<Reference<T>> stack;
	synchronized(cache) {
	stack = cache.get(size);
	}

	if (stack == null)
	return null;

	// Try to find a non-cleared Reference from the stack.
	T array;
	do {
	Reference<T> r = stack.pop();
	if (r == null)
	return null;

	array = r.get();
	} while (array == null);

	return array;
	}

	/**
	* Puts the {@code array} of {@code size} elements long into
	* the {@code cache}.
	*/
	private static <T> void putArray(CacheMap<T> cache, T array, int size) {
	// Small arrays aren't cached.
	if (size < CACHEABLE_SIZE_MIN)
	return;

	CyclicStack<Reference<T>> stack;

	synchronized(cache) {
	// Get a stack that holds arrays of T[size]. If no such stack
	// exists, allocate a new one. If the cache already had STACKS_MAX
	// number of stacks, the least recently used stack is removed by
	// cache.put (it calls removeEldestEntry).
	stack = cache.get(size);
	if (stack == null) {
	stack = new CyclicStack<Reference<T>>();
	cache.put(size, stack);
	}
	}

	stack.push(new SoftReference<T>(array));
	}

	/**
	* Allocates a new byte array, hopefully reusing an existing
	* array from the cache.
	*
	* @param size size of the array to allocate
	*
	* @param fillWithZeros
	* if true, all the elements of the returned
	* array will be zero; if false, the contents
	* of the returned array is undefined
	*/
	public byte[] getByteArray(int size, boolean fillWithZeros) {
	byte[] array = getArray(byteArrayCache, size);

	if (array == null)
	array = new byte[size];
	else if (fillWithZeros)
	Arrays.fill(array, (byte)0x00);

	return array;
	}

	/**
	* Puts the given byte array to the cache. The caller must no longer
	* use the array.
	* <p>
	* Small arrays aren't cached and will be ignored by this method.
	*/
	public void putArray(byte[] array) {
	putArray(byteArrayCache, array, array.length);
	}

	/**
	* This is like getByteArray but for int arrays.
	*/
	public int[] getIntArray(int size, boolean fillWithZeros) {
	int[] array = getArray(intArrayCache, size);

	if (array == null)
	array = new int[size];
	else if (fillWithZeros)
	Arrays.fill(array, 0);

	return array;
	}

	/**
	* Puts the given int array to the cache. The caller must no longer
	* use the array.
	* <p>
	* Small arrays aren't cached and will be ignored by this method.
	*/
	public void putArray(int[] array) {
	putArray(intArrayCache, array, array.length);
	}
	}