diff options
Diffstat (limited to 'src/org/tukaani/xz/BasicArrayCache.java')
-rw-r--r-- | src/org/tukaani/xz/BasicArrayCache.java | 281 |
1 files changed, 281 insertions, 0 deletions
diff --git a/src/org/tukaani/xz/BasicArrayCache.java b/src/org/tukaani/xz/BasicArrayCache.java new file mode 100644 index 0000000..90ebe1f --- /dev/null +++ b/src/org/tukaani/xz/BasicArrayCache.java @@ -0,0 +1,281 @@ +/* + * 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); + } +} |