1 /*
2  * Copyright (C) 2013 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.bitmap;
18 
19 import android.util.Log;
20 import android.util.SparseArray;
21 
22 import com.android.bitmap.util.Trace;
23 
24 import java.util.ArrayDeque;
25 import java.util.Iterator;
26 import java.util.Queue;
27 
28 /**
29  * An implementation of a task aggregator that executes tasks in the order that they are expected
30  * . All tasks that is given to {@link #execute(Object, Runnable)} must correspond to a key. This
31  * key must have been previously declared with {@link #expect(Object, Callback)}.
32  * The task will be scheduled to run when its corresponding key becomes the first expected key
33  * amongst the other keys in this aggregator.
34  * <p/>
35  * If on {@link #execute(Object, Runnable)} the key is not expected, the task will be executed
36  * immediately as an edge case.
37  * <p/>
38  * A characteristic scenario is as follows:
39  * <ol>
40  * <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
41  * the first expected key.</li>
42  * <li>Execute task <b>2</b> for key <b>B</b>. The first expected key is <b>A</b>,
43  * which has no task associated with it, so we store task <b>2</b>. </li>
44  * <li>Execute task <b>4</b> for key <b>Z</b>. We store task <b>4</b>. </li>
45  * <li>Execute task <b>1</b> for key <b>A</b>. We run task <b>1</b> because its key <b>A</b> is
46  * the first expected, then we remove key <b>A</b> from the list of keys that we expect.</li>
47  * <li>This causes key <b>B</b> to be the first expected key, and we see that we have previously
48  * stored task <b>2</b> for that key. We run task <b>2</b> and remove key <b>B</b>. </li>
49  * <li>Key <b>C</b> is now the first expected key, but it has no task,
50  * so nothing happens. Task <b>4</b>, which was previously stored,
51  * cannot run until its corresponding key <b>Z</b> becomes the first expected key. This can
52  * happen if a task comes in for key <b>C</b> or if forget is called on key <b>C</b>.</li>
53  * </ol>
54  * <p/>
55  * ContiguousFIFOAggregator is not thread safe.
56  */
57 public class ContiguousFIFOAggregator<T> {
58     private final Queue<T> mExpected;
59     private final SparseArray<Value> mTasks;
60 
61     private static final String TAG = ContiguousFIFOAggregator.class.getSimpleName();
62     private static final boolean DEBUG = false;
63 
64     /**
65      * Create a new ContiguousFIFOAggregator.
66      * <p/>
67      * The nature of the prioritization means that the number of stored keys and tasks may grow
68      * unbounded. This may happen, for instance, if the top priority key is never given a task to
69      * {@link #execute(Object, Runnable)}. However, in practice, if you are generating tasks in
70      * response to UI elements appearing on the screen, you will only have a bounded set of keys.
71      * UI elements that scroll off the screen will call {@link #forget(Object)} while new elements
72      * will call {@link #expect(Object, Callback)}. This means that the expected
73      * number of keys and tasks is
74      * the maximum number of UI elements that you expect to show on the screen at any time.
75      */
ContiguousFIFOAggregator()76     public ContiguousFIFOAggregator() {
77         mExpected = new ArrayDeque<T>();
78         mTasks = new SparseArray<Value>();
79     }
80 
81     /**
82      * Declare a key to be expected in the future. The order in which you expect keys is very
83      * important. Keys that are declared first are guaranteed to have their tasks run first. You
84      * must call either {@link #forget(Object)} or {@link #execute(Object, Runnable)}
85      * with this key in the future, or you will leak the key.
86      *
87      * If you call expect with a previously expected key, the key will be placed at the back of
88      * the expected queue and its callback will be replaced with this one.
89      *
90      * @param key      the key to expect a task for. Use the same key when setting the task later
91      *                 with {@link #execute (Object, Runnable)}.
92      * @param callback the callback to notify when the key becomes the first expected key, or null.
93      */
expect(final T key, final Callback<T> callback)94     public void expect(final T key, final Callback<T> callback) {
95         if (key == null) {
96             throw new IllegalArgumentException("Do not use null keys.");
97         }
98 
99         Trace.beginSection("pool expect");
100         final int hash = key.hashCode();
101         if (contains(key)) {
102             mExpected.remove(key);
103             mTasks.remove(hash);
104         }
105         final boolean isFirst = mExpected.isEmpty();
106         mExpected.offer(key);
107         mTasks.put(hash, new Value(callback, null));
108         if (DEBUG) {
109             Log.d(TAG, String.format("ContiguousFIFOAggregator >> tasks: %s", prettyPrint()));
110         }
111 
112         if (isFirst) {
113             onFirstExpectedChanged(key);
114         }
115         Trace.endSection();
116     }
117 
118     /**
119      * Remove a previously declared key that we no longer expect to execute a task for. This
120      * potentially allows another key to now become the first expected key,
121      * and so this may trigger one or more tasks to be executed.
122      *
123      * @param key the key previously declared in {@link #expect(Object, Callback)}.
124      *
125      */
forget(final T key)126     public void forget(final T key) {
127         if (key == null) {
128             throw new IllegalArgumentException("Do not use null keys.");
129         }
130 
131         if (!contains(key)) {
132             return;
133         }
134 
135         Trace.beginSection("pool forget");
136         final boolean removedFirst = key.equals(mExpected.peek());
137         mExpected.remove(key);
138         mTasks.delete(key.hashCode());
139         if (DEBUG) {
140             Log.d(TAG, String.format("ContiguousFIFOAggregator  < tasks: %s", prettyPrint()));
141         }
142 
143         final T second;
144         if (removedFirst && (second = mExpected.peek()) != null) {
145             // We removed the first key. The second key is now first.
146             onFirstExpectedChanged(second);
147         }
148 
149         maybeExecuteNow();
150         Trace.endSection();
151     }
152 
153     /**
154      * Attempt to execute a task corresponding to a previously declared key. If the key is the
155      * first expected key, the task will be executed immediately. Otherwise, the task is stored
156      * until its key becomes the first expected key. Execution of a task results in the removal
157      * of that key, which potentially allows another key to now become the first expected key,
158      * and may cause one or more other tasks to be executed.
159      * <p/>
160      * If the key is not expected, the task will be executed immediately as an edge case.
161      *
162      * @param key  the key previously declared in {@link #expect(Object, Callback)}.
163      * @param task the task to execute or store, depending on its corresponding key.
164      */
execute(final T key, final Runnable task)165     public void execute(final T key, final Runnable task) {
166         Trace.beginSection("pool execute");
167         final int hash = key.hashCode();
168         final Value value = mTasks.get(hash);
169         if (value == null || task == null) {
170             if (task != null) {
171                 task.run();
172             }
173             Trace.endSection();
174             return;
175         }
176         value.task = task;
177         if (DEBUG) {
178             Log.d(TAG, String.format("ContiguousFIFOAggregator ++ tasks: %s", prettyPrint()));
179         }
180         maybeExecuteNow();
181         Trace.endSection();
182     }
183 
184     /**
185      * Triggered by {@link #execute(Object, Runnable)} and {@link #forget(Object)}. The keys or
186      * tasks have changed, which may cause one or more tasks to be executed. This method will
187      * continue to execute tasks associated with the first expected key to the last expected key,
188      * stopping when it finds that the first expected key has not yet been assigned a task.
189      */
maybeExecuteNow()190     private void maybeExecuteNow() {
191         T first;
192         int count = 0;
193         while (!mExpected.isEmpty()) {
194             Trace.beginSection("pool maybeExecuteNow loop");
195             first = mExpected.peek();
196             if (count > 0) {
197                 // When count == 0, the key is already first.
198                 onFirstExpectedChanged(first);
199             }
200 
201             final int hash = first.hashCode();
202             final Value value = mTasks.get(hash);
203             if (value.task == null) {
204                 Trace.endSection();
205                 break;
206             }
207 
208             mExpected.poll();
209             mTasks.delete(hash);
210             if (DEBUG) {
211                 Log.d(TAG, String.format("ContiguousFIFOAggregator  - tasks: %s", prettyPrint()));
212             }
213             value.task.run();
214             count++;
215             Trace.endSection();
216         }
217     }
218 
219     /**
220      * This method should only be called once for any key.
221      * @param key The key that has become the new first expected key.
222      */
onFirstExpectedChanged(final T key)223     private void onFirstExpectedChanged(final T key) {
224         final int hash = key.hashCode();
225         final Value value = mTasks.get(hash);
226         if (value == null) {
227             return;
228         }
229         final Callback<T> callback = value.callback;
230         if (callback == null) {
231             return;
232         }
233         if (DEBUG) {
234             Log.d(TAG, String.format("ContiguousFIFOAggregator    first: %d", hash));
235         }
236         callback.onBecomeFirstExpected(key);
237     }
238 
contains(final T key)239     private boolean contains(final T key) {
240         return mTasks.get(key.hashCode()) != null;
241     }
242 
243     /**
244      * Get a pretty string representing the internal data.
245      * @return  a String for the internal data.
246      */
prettyPrint()247     private String prettyPrint() {
248         if (mExpected.isEmpty()) {
249             return "{}";
250         }
251 
252         StringBuilder buffer = new StringBuilder(mExpected.size() * 28);
253         buffer.append('{');
254         Iterator<T> it = mExpected.iterator();
255         while (it.hasNext()) {
256             final T key = it.next();
257             final int hash = key.hashCode();
258             buffer.append(hash);
259             buffer.append('=');
260             final Value value = mTasks.get(hash);
261             buffer.append(value);
262             if (it.hasNext()) {
263                 buffer.append(", ");
264             }
265         }
266         buffer.append('}');
267         if (mExpected.size() != mTasks.size()) {
268             buffer.append(" error");
269         }
270         return buffer.toString();
271     }
272 
273     /**
274      * Implement this interface if you want to be notified when the key becomes the first
275      * expected key.
276      * @param <T> The type of the key used for the aggregator.
277      */
278     public interface Callback<T> {
279 
280         /**
281          * The key you declared as expected has become the first expected key in this aggregator.
282          *
283          * We don't need a noLongerFirstExpected() method because this aggregator strictly adds
284          * additional to the end of the queue. For a first expected key to no longer be the first
285          * expected, it would either have to be forgotten with {@link #forget(Object)} or a task
286          * assigned and executed with {@link #execute(Object, Runnable)}.
287          *
288          * @param key The key that became first. We provide the key so the callback can either not
289          *            keep state, or it can keep state which may have changed so the callback can do
290          *            a comparison.
291          */
onBecomeFirstExpected(final T key)292         void onBecomeFirstExpected(final T key);
293     }
294 
295     /**
296      * Holds the callback and task for when a key later becomes the first expected key.
297      */
298     private class Value {
299 
300         final Callback<T> callback;
301         Runnable task;
302 
Value(final Callback<T> callback, final Runnable task)303         Value(final Callback<T> callback, final Runnable task) {
304             this.callback = callback;
305             this.task = task;
306         }
307 
308         @Override
toString()309         public String toString() {
310             return String.valueOf(task);
311         }
312     }
313 }
314