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