Add BasicArrayCache.

2 files changed, 282 insertions, 0 deletions

diff --git a/fileset-src.txt b/fileset-src.txt
index 4651750..684b6a7 100644
--- a/fileset-src.txt
+++ b/fileset-src.txt
@@ -7,6 +7,7 @@ src/XZSeekEncDemo.java
 src/org/tukaani/xz/ARMOptions.java
 src/org/tukaani/xz/ARMThumbOptions.java
 src/org/tukaani/xz/ArrayCache.java
+src/org/tukaani/xz/BasicArrayCache.java
 src/org/tukaani/xz/BCJCoder.java
 src/org/tukaani/xz/BCJDecoder.java
 src/org/tukaani/xz/BCJEncoder.java
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);
+    }
+}