Initial commit from Gmail's Cache system.

Change-Id: I14168ab3bc02b77399a1812f62bd77ac797232c5

1 files changed, 231 insertions, 0 deletions

diff --git a/src/com/android/bitmap/UnrefedPooledCache.java b/src/com/android/bitmap/UnrefedPooledCache.java
new file mode 100644
index 0000000..ff0ab7b
--- /dev/null
+++ b/src/com/android/bitmap/UnrefedPooledCache.java
@@ -0,0 +1,231 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.bitmap;
+
+import com.android.bitmap.util.Trace;
+
+import android.util.Log;
+import android.util.LruCache;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.concurrent.LinkedBlockingQueue;
+
+/**
+ * An alternative implementation of a pool+cache. This implementation only counts
+ * unreferenced objects in its size calculation. Internally, it never evicts from
+ * its cache, and instead {@link #poll()} is allowed to return unreferenced cache
+ * entries.
+ * <p>
+ * You would only use this kind of cache if your objects are interchangeable and
+ * have significant allocation cost, and if your memory footprint is somewhat
+ * flexible.
+ * <p>
+ * Because this class only counts unreferenced objects toward targetSize,
+ * it will have a total memory footprint of:
+ * <code>(targetSize) + (# of threads concurrently writing to cache) +
+ * (total size of still-referenced entries)</code>
+ *
+ */
+public class UnrefedPooledCache<K, V extends Poolable> implements PooledCache<K, V> {
+
+    private final LinkedHashMap<K, V> mCache;
+    private final LinkedBlockingQueue<V> mPool;
+    private final int mTargetSize;
+    private final LruCache<K, V> mNonPooledCache;
+
+    private static final boolean DEBUG = false;
+    private static final String TAG = UnrefedPooledCache.class.getSimpleName();
+
+    /**
+     * @param targetSize not exactly a max size in practice
+     * @param nonPooledFraction the fractional portion in the range [0.0,1.0] of targetSize to
+     * dedicate to non-poolable entries
+     */
+    public UnrefedPooledCache(int targetSize, float nonPooledFraction) {
+        mCache = new LinkedHashMap<K, V>(0, 0.75f, true);
+        mPool = new LinkedBlockingQueue<V>();
+        final int nonPooledSize = Math.round(targetSize * nonPooledFraction);
+        if (nonPooledSize > 0) {
+            mNonPooledCache = new NonPooledCache(nonPooledSize);
+        } else {
+            mNonPooledCache = null;
+        }
+        mTargetSize = targetSize - nonPooledSize;
+    }
+
+    @Override
+    public V get(K key, boolean incrementRefCount) {
+        Trace.beginSection("cache get");
+        synchronized (mCache) {
+            V result = mCache.get(key);
+            if (result == null && mNonPooledCache != null) {
+                result = mNonPooledCache.get(key);
+            }
+            if (incrementRefCount && result != null) {
+                result.acquireReference();
+            }
+            Trace.endSection();
+            return result;
+        }
+    }
+
+    @Override
+    public V put(K key, V value) {
+        Trace.beginSection("cache put");
+        synchronized (mCache) {
+            final V prev;
+            if (value.isEligibleForPooling()) {
+                prev = mCache.put(key, value);
+            } else if (mNonPooledCache != null) {
+                prev = mNonPooledCache.put(key, value);
+            } else {
+                prev = null;
+            }
+            Trace.endSection();
+            return prev;
+        }
+    }
+
+    @Override
+    public void offer(V value) {
+        Trace.beginSection("pool offer");
+        if (value.getRefCount() != 0 || !value.isEligibleForPooling()) {
+            throw new IllegalArgumentException("unexpected offer of an invalid object: " + value);
+        }
+        mPool.offer(value);
+        Trace.endSection();
+    }
+
+    @Override
+    public V poll() {
+        Trace.beginSection("pool poll");
+        final V pooled = mPool.poll();
+        if (pooled != null) {
+            Trace.endSection();
+            return pooled;
+        }
+
+        synchronized (mCache) {
+            int unrefSize = 0;
+            Map.Entry<K, V> eldestUnref = null;
+            for (Map.Entry<K, V> entry : mCache.entrySet()) {
+                final V value = entry.getValue();
+                if (value.getRefCount() > 0 || !value.isEligibleForPooling()) {
+                    continue;
+                }
+                if (eldestUnref == null) {
+                    eldestUnref = entry;
+                }
+                unrefSize += sizeOf(value);
+                if (unrefSize > mTargetSize) {
+                    break;
+                }
+            }
+            // only return a scavenged cache entry if the cache has enough
+            // eligible (unreferenced) items
+            if (unrefSize <= mTargetSize) {
+                if (DEBUG) {
+                    Log.e(TAG, "POOL SCAVENGE FAILED, cache not fully warm yet. szDelta="
+                            + (mTargetSize-unrefSize));
+                }
+                Trace.endSection();
+                return null;
+            } else {
+                mCache.remove(eldestUnref.getKey());
+                if (DEBUG) {
+                    Log.e(TAG, "POOL SCAVENGE SUCCESS, oldKey=" + eldestUnref.getKey());
+                }
+                Trace.endSection();
+                return eldestUnref.getValue();
+            }
+        }
+    }
+
+    protected int sizeOf(V value) {
+        return 1;
+    }
+
+    @Override
+    public String toDebugString() {
+        if (DEBUG) {
+            final StringBuilder sb = new StringBuilder("[");
+            sb.append(super.toString());
+            int size = 0;
+            synchronized (mCache) {
+                sb.append(" poolCount=");
+                sb.append(mPool.size());
+                sb.append(" cacheSize=");
+                sb.append(mCache.size());
+                if (mNonPooledCache != null) {
+                    sb.append(" nonPooledCacheSize=");
+                    sb.append(mNonPooledCache.size());
+                }
+                sb.append("\n---------------------");
+                for (V val : mPool) {
+                    size += sizeOf(val);
+                    sb.append("\n\tpool item: ");
+                    sb.append(val);
+                }
+                sb.append("\n---------------------");
+                for (Map.Entry<K, V> item : mCache.entrySet()) {
+                    final V val = item.getValue();
+                    sb.append("\n\tcache key=");
+                    sb.append(item.getKey());
+                    sb.append(" val=");
+                    sb.append(val);
+                    size += sizeOf(val);
+                }
+                sb.append("\n---------------------");
+                if (mNonPooledCache != null) {
+                    for (Map.Entry<K, V> item : mNonPooledCache.snapshot().entrySet()) {
+                        final V val = item.getValue();
+                        sb.append("\n\tnon-pooled cache key=");
+                        sb.append(item.getKey());
+                        sb.append(" val=");
+                        sb.append(val);
+                        size += sizeOf(val);
+                    }
+                    sb.append("\n---------------------");
+                }
+                sb.append("\nTOTAL SIZE=" + size);
+            }
+            sb.append("]");
+            return sb.toString();
+        } else {
+            return null;
+        }
+    }
+
+    private class NonPooledCache extends LruCache<K, V> {
+
+        public NonPooledCache(int maxSize) {
+            super(maxSize);
+        }
+
+        @Override
+        protected int sizeOf(K key, V value) {
+            return UnrefedPooledCache.this.sizeOf(value);
+        }
+
+    }
+
+    @Override
+    public void clear() {
+        mCache.clear();
+        mPool.clear();
+    }
+}