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