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