Initial commit from Gmail's Cache system.

Change-Id: I14168ab3bc02b77399a1812f62bd77ac797232c5

1 files changed, 313 insertions, 0 deletions

diff --git a/src/com/android/bitmap/ContiguousFIFOAggregator.java b/src/com/android/bitmap/ContiguousFIFOAggregator.java
new file mode 100644
index 0000000..9716fb8
--- /dev/null
+++ b/src/com/android/bitmap/ContiguousFIFOAggregator.java
@@ -0,0 +1,313 @@
+/*
+ * 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 android.util.Log;
+import android.util.SparseArray;
+
+import com.android.bitmap.util.Trace;
+
+import java.util.ArrayDeque;
+import java.util.Iterator;
+import java.util.Queue;
+
+/**
+ * An implementation of a task aggregator that executes tasks in the order that they are expected
+ * . All tasks that is given to {@link #execute(Object, Runnable)} must correspond to a key. This
+ * key must have been previously declared with {@link #expect(Object, Callback)}.
+ * The task will be scheduled to run when its corresponding key becomes the first expected key
+ * amongst the other keys in this aggregator.
+ * <p/>
+ * If on {@link #execute(Object, Runnable)} the key is not expected, the task will be executed
+ * immediately as an edge case.
+ * <p/>
+ * A characteristic scenario is as follows:
+ * <ol>
+ * <li>Expect keys <b>A</b>, <b>B</b>, <b>C</b>, and <b>Z</b>, in that order. Key <b>A</b> is now
+ * the first expected key.</li>
+ * <li>Execute task <b>2</b> for key <b>B</b>. The first expected key is <b>A</b>,
+ * which has no task associated with it, so we store task <b>2</b>. </li>
+ * <li>Execute task <b>4</b> for key <b>Z</b>. We store task <b>4</b>. </li>
+ * <li>Execute task <b>1</b> for key <b>A</b>. We run task <b>1</b> because its key <b>A</b> is
+ * the first expected, then we remove key <b>A</b> from the list of keys that we expect.</li>
+ * <li>This causes key <b>B</b> to be the first expected key, and we see that we have previously
+ * stored task <b>2</b> for that key. We run task <b>2</b> and remove key <b>B</b>. </li>
+ * <li>Key <b>C</b> is now the first expected key, but it has no task,
+ * so nothing happens. Task <b>4</b>, which was previously stored,
+ * cannot run until its corresponding key <b>Z</b> becomes the first expected key. This can
+ * happen if a task comes in for key <b>C</b> or if forget is called on key <b>C</b>.</li>
+ * </ol>
+ * <p/>
+ * ContiguousFIFOAggregator is not thread safe.
+ */
+public class ContiguousFIFOAggregator<T> {
+    private final Queue<T> mExpected;
+    private final SparseArray<Value> mTasks;
+
+    private static final String TAG = ContiguousFIFOAggregator.class.getSimpleName();
+    private static final boolean DEBUG = false;
+
+    /**
+     * Create a new ContiguousFIFOAggregator.
+     * <p/>
+     * The nature of the prioritization means that the number of stored keys and tasks may grow
+     * unbounded. This may happen, for instance, if the top priority key is never given a task to
+     * {@link #execute(Object, Runnable)}. However, in practice, if you are generating tasks in
+     * response to UI elements appearing on the screen, you will only have a bounded set of keys.
+     * UI elements that scroll off the screen will call {@link #forget(Object)} while new elements
+     * will call {@link #expect(Object, Callback)}. This means that the expected
+     * number of keys and tasks is
+     * the maximum number of UI elements that you expect to show on the screen at any time.
+     */
+    public ContiguousFIFOAggregator() {
+        mExpected = new ArrayDeque<T>();
+        mTasks = new SparseArray<Value>();
+    }
+
+    /**
+     * Declare a key to be expected in the future. The order in which you expect keys is very
+     * important. Keys that are declared first are guaranteed to have their tasks run first. You
+     * must call either {@link #forget(Object)} or {@link #execute(Object, Runnable)}
+     * with this key in the future, or you will leak the key.
+     *
+     * If you call expect with a previously expected key, the key will be placed at the back of
+     * the expected queue and its callback will be replaced with this one.
+     *
+     * @param key      the key to expect a task for. Use the same key when setting the task later
+     *                 with {@link #execute (Object, Runnable)}.
+     * @param callback the callback to notify when the key becomes the first expected key, or null.
+     */
+    public void expect(final T key, final Callback<T> callback) {
+        if (key == null) {
+            throw new IllegalArgumentException("Do not use null keys.");
+        }
+
+        Trace.beginSection("pool expect");
+        final int hash = key.hashCode();
+        if (contains(key)) {
+            mExpected.remove(key);
+            mTasks.remove(hash);
+        }
+        final boolean isFirst = mExpected.isEmpty();
+        mExpected.offer(key);
+        mTasks.put(hash, new Value(callback, null));
+        if (DEBUG) {
+            Log.d(TAG, String.format("ContiguousFIFOAggregator >> tasks: %s", prettyPrint()));
+        }
+
+        if (isFirst) {
+            onFirstExpectedChanged(key);
+        }
+        Trace.endSection();
+    }
+
+    /**
+     * Remove a previously declared key that we no longer expect to execute a task for. This
+     * potentially allows another key to now become the first expected key,
+     * and so this may trigger one or more tasks to be executed.
+     *
+     * @param key the key previously declared in {@link #expect(Object, Callback)}.
+     *
+     */
+    public void forget(final T key) {
+        if (key == null) {
+            throw new IllegalArgumentException("Do not use null keys.");
+        }
+
+        if (!contains(key)) {
+            return;
+        }
+
+        Trace.beginSection("pool forget");
+        final boolean removedFirst = key.equals(mExpected.peek());
+        mExpected.remove(key);
+        mTasks.delete(key.hashCode());
+        if (DEBUG) {
+            Log.d(TAG, String.format("ContiguousFIFOAggregator  < tasks: %s", prettyPrint()));
+        }
+
+        final T second;
+        if (removedFirst && (second = mExpected.peek()) != null) {
+            // We removed the first key. The second key is now first.
+            onFirstExpectedChanged(second);
+        }
+
+        maybeExecuteNow();
+        Trace.endSection();
+    }
+
+    /**
+     * Attempt to execute a task corresponding to a previously declared key. If the key is the
+     * first expected key, the task will be executed immediately. Otherwise, the task is stored
+     * until its key becomes the first expected key. Execution of a task results in the removal
+     * of that key, which potentially allows another key to now become the first expected key,
+     * and may cause one or more other tasks to be executed.
+     * <p/>
+     * If the key is not expected, the task will be executed immediately as an edge case.
+     *
+     * @param key  the key previously declared in {@link #expect(Object, Callback)}.
+     * @param task the task to execute or store, depending on its corresponding key.
+     */
+    public void execute(final T key, final Runnable task) {
+        Trace.beginSection("pool execute");
+        final int hash = key.hashCode();
+        final Value value = mTasks.get(hash);
+        if (value == null || task == null) {
+            if (task != null) {
+                task.run();
+            }
+            Trace.endSection();
+            return;
+        }
+        value.task = task;
+        if (DEBUG) {
+            Log.d(TAG, String.format("ContiguousFIFOAggregator ++ tasks: %s", prettyPrint()));
+        }
+        maybeExecuteNow();
+        Trace.endSection();
+    }
+
+    /**
+     * Triggered by {@link #execute(Object, Runnable)} and {@link #forget(Object)}. The keys or
+     * tasks have changed, which may cause one or more tasks to be executed. This method will
+     * continue to execute tasks associated with the first expected key to the last expected key,
+     * stopping when it finds that the first expected key has not yet been assigned a task.
+     */
+    private void maybeExecuteNow() {
+        T first;
+        int count = 0;
+        while (!mExpected.isEmpty()) {
+            Trace.beginSection("pool maybeExecuteNow loop");
+            first = mExpected.peek();
+            if (count > 0) {
+                // When count == 0, the key is already first.
+                onFirstExpectedChanged(first);
+            }
+
+            final int hash = first.hashCode();
+            final Value value = mTasks.get(hash);
+            if (value.task == null) {
+                Trace.endSection();
+                break;
+            }
+
+            mExpected.poll();
+            mTasks.delete(hash);
+            if (DEBUG) {
+                Log.d(TAG, String.format("ContiguousFIFOAggregator  - tasks: %s", prettyPrint()));
+            }
+            value.task.run();
+            count++;
+            Trace.endSection();
+        }
+    }
+
+    /**
+     * This method should only be called once for any key.
+     * @param key The key that has become the new first expected key.
+     */
+    private void onFirstExpectedChanged(final T key) {
+        final int hash = key.hashCode();
+        final Value value = mTasks.get(hash);
+        if (value == null) {
+            return;
+        }
+        final Callback<T> callback = value.callback;
+        if (callback == null) {
+            return;
+        }
+        if (DEBUG) {
+            Log.d(TAG, String.format("ContiguousFIFOAggregator    first: %d", hash));
+        }
+        callback.onBecomeFirstExpected(key);
+    }
+
+    private boolean contains(final T key) {
+        return mTasks.get(key.hashCode()) != null;
+    }
+
+    /**
+     * Get a pretty string representing the internal data.
+     * @return  a String for the internal data.
+     */
+    private String prettyPrint() {
+        if (mExpected.isEmpty()) {
+            return "{}";
+        }
+
+        StringBuilder buffer = new StringBuilder(mExpected.size() * 28);
+        buffer.append('{');
+        Iterator<T> it = mExpected.iterator();
+        while (it.hasNext()) {
+            final T key = it.next();
+            final int hash = key.hashCode();
+            buffer.append(hash);
+            buffer.append('=');
+            final Value value = mTasks.get(hash);
+            buffer.append(value);
+            if (it.hasNext()) {
+                buffer.append(", ");
+            }
+        }
+        buffer.append('}');
+        if (mExpected.size() != mTasks.size()) {
+            buffer.append(" error");
+        }
+        return buffer.toString();
+    }
+
+    /**
+     * Implement this interface if you want to be notified when the key becomes the first
+     * expected key.
+     * @param <T> The type of the key used for the aggregator.
+     */
+    public interface Callback<T> {
+
+        /**
+         * The key you declared as expected has become the first expected key in this aggregator.
+         *
+         * We don't need a noLongerFirstExpected() method because this aggregator strictly adds
+         * additional to the end of the queue. For a first expected key to no longer be the first
+         * expected, it would either have to be forgotten with {@link #forget(Object)} or a task
+         * assigned and executed with {@link #execute(Object, Runnable)}.
+         *
+         * @param key The key that became first. We provide the key so the callback can either not
+         *            keep state, or it can keep state which may have changed so the callback can do
+         *            a comparison.
+         */
+        void onBecomeFirstExpected(final T key);
+    }
+
+    /**
+     * Holds the callback and task for when a key later becomes the first expected key.
+     */
+    private class Value {
+
+        final Callback<T> callback;
+        Runnable task;
+
+        Value(final Callback<T> callback, final Runnable task) {
+            this.callback = callback;
+            this.task = task;
+        }
+
+        @Override
+        public String toString() {
+            return String.valueOf(task);
+        }
+    }
+}