1 /*
2  * Copyright (C) 2015 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 package com.android.internal.util;
17 
18 import java.util.ArrayList;
19 import java.util.List;
20 
21 /**
22  * Tracks callbacks for the event. This class supports reentrant modification
23  * of the callbacks during notification without adversely disrupting notifications.
24  * A common pattern for callbacks is to receive a notification and then remove
25  * themselves. This class handles this behavior with constant memory under
26  * most circumstances.
27  *
28  * <p>A subclass of {@link CallbackRegistry.NotifierCallback} must be passed to
29  * the constructor to define how notifications should be called. That implementation
30  * does the actual notification on the listener.</p>
31  *
32  * <p>This class supports only callbacks with at most two parameters.
33  * Typically, these are the notification originator and a parameter, but these may
34  * be used as required. If more than two parameters are required or primitive types
35  * must be used, <code>A</code> should be some kind of containing structure that
36  * the subclass may reuse between notifications.</p>
37  *
38  * @param <C> The callback type.
39  * @param <T> The notification sender type. Typically this is the containing class.
40  * @param <A> Opaque argument used to pass additional data beyond an int.
41  */
42 @android.ravenwood.annotation.RavenwoodKeepWholeClass
43 public class CallbackRegistry<C, T, A> implements Cloneable {
44     private static final String TAG = "CallbackRegistry";
45 
46     /** An ordered collection of listeners waiting to be notified. */
47     private List<C> mCallbacks = new ArrayList<C>();
48 
49     /**
50      * A bit flag for the first 64 listeners that are removed during notification.
51      * The lowest significant bit corresponds to the 0th index into mCallbacks.
52      * For a small number of callbacks, no additional array of objects needs to
53      * be allocated.
54      */
55     private long mFirst64Removed = 0x0;
56 
57     /**
58      * Bit flags for the remaining callbacks that are removed during notification.
59      * When there are more than 64 callbacks and one is marked for removal, a dynamic
60      * array of bits are allocated for the callbacks.
61      */
62     private long[] mRemainderRemoved;
63 
64     /**
65      * The reentrancy level of the notification. When we notify a callback, it may cause
66      * further notifications. The reentrancy level must be tracked to let us clean up
67      * the callback state when all notifications have been processed.
68      */
69     private int mNotificationLevel;
70 
71     /** The notification mechanism for notifying an event. */
72     private final NotifierCallback<C, T, A> mNotifier;
73 
74     /**
75      * Creates an EventRegistry that notifies the event with notifier.
76      * @param notifier The class to use to notify events.
77      */
CallbackRegistry(NotifierCallback<C, T, A> notifier)78     public CallbackRegistry(NotifierCallback<C, T, A> notifier) {
79         mNotifier = notifier;
80     }
81 
82     /**
83      * Notify all callbacks.
84      *
85      * @param sender The originator. This is an opaque parameter passed to
86      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
87      * @param arg An opaque parameter passed to
88      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
89      * @param arg2 An opaque parameter passed to
90      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
91      */
notifyCallbacks(T sender, int arg, A arg2)92     public synchronized void notifyCallbacks(T sender, int arg, A arg2) {
93         mNotificationLevel++;
94         notifyRecurseLocked(sender, arg, arg2);
95         mNotificationLevel--;
96         if (mNotificationLevel == 0) {
97             if (mRemainderRemoved != null) {
98                 for (int i = mRemainderRemoved.length - 1; i >= 0; i--) {
99                     final long removedBits = mRemainderRemoved[i];
100                     if (removedBits != 0) {
101                         removeRemovedCallbacks((i + 1) * Long.SIZE, removedBits);
102                         mRemainderRemoved[i] = 0;
103                     }
104                 }
105             }
106             if (mFirst64Removed != 0) {
107                 removeRemovedCallbacks(0, mFirst64Removed);
108                 mFirst64Removed = 0;
109             }
110         }
111     }
112 
113     /**
114      * Notify up to the first Long.SIZE callbacks that don't have a bit set in <code>removed</code>.
115      *
116      * @param sender The originator. This is an opaque parameter passed to
117      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
118      * @param arg An opaque parameter passed to
119      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
120      * @param arg2 An opaque parameter passed to
121      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
122      */
notifyFirst64Locked(T sender, int arg, A arg2)123     private void notifyFirst64Locked(T sender, int arg, A arg2) {
124         final int maxNotified = Math.min(Long.SIZE, mCallbacks.size());
125         notifyCallbacksLocked(sender, arg, arg2, 0, maxNotified, mFirst64Removed);
126     }
127 
128     /**
129      * Notify all callbacks using a recursive algorithm to avoid allocating on the heap.
130      * This part captures the callbacks beyond Long.SIZE that have no bits allocated for
131      * removal before it recurses into {@link #notifyRemainderLocked(Object, int, A, int)}.
132      * <p>
133      * Recursion is used to avoid allocating temporary state on the heap. Each stack has one
134      * long (64 callbacks) worth of information of which has been removed.
135      *
136      * @param sender The originator. This is an opaque parameter passed to
137      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
138      * @param arg An opaque parameter passed to
139      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
140      * @param arg2 An opaque parameter passed to
141      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
142      */
notifyRecurseLocked(T sender, int arg, A arg2)143     private void notifyRecurseLocked(T sender, int arg, A arg2) {
144         final int callbackCount = mCallbacks.size();
145         final int remainderIndex = mRemainderRemoved == null ? -1 : mRemainderRemoved.length - 1;
146 
147         // Now we've got all callbacks that have no mRemainderRemoved value, so notify the
148         // others.
149         notifyRemainderLocked(sender, arg, arg2, remainderIndex);
150 
151         // notifyRemainderLocked notifies all at maxIndex, so we'd normally start at maxIndex + 1
152         // However, we must also keep track of those in mFirst64Removed, so we add 2 instead:
153         final int startCallbackIndex = (remainderIndex + 2) * Long.SIZE;
154 
155         // The remaining have no bit set
156         notifyCallbacksLocked(sender, arg, arg2, startCallbackIndex, callbackCount, 0);
157     }
158 
159     /**
160      * Notify callbacks that have mRemainderRemoved bits set for remainderIndex. If
161      * remainderIndex is -1, the first 64 will be notified instead.
162      *
163      * @param sender The originator. This is an opaque parameter passed to
164      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
165      * @param arg An opaque parameter passed to
166      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
167      * @param arg2 An opaque parameter passed to
168      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
169      * @param remainderIndex The index into mRemainderRemoved that should be notified.
170      */
notifyRemainderLocked(T sender, int arg, A arg2, int remainderIndex)171     private void notifyRemainderLocked(T sender, int arg, A arg2, int remainderIndex) {
172         if (remainderIndex < 0) {
173             notifyFirst64Locked(sender, arg, arg2);
174         } else {
175             final long bits = mRemainderRemoved[remainderIndex];
176             final int startIndex = (remainderIndex + 1) * Long.SIZE;
177             final int endIndex = Math.min(mCallbacks.size(), startIndex + Long.SIZE);
178             notifyRemainderLocked(sender, arg, arg2, remainderIndex - 1);
179             notifyCallbacksLocked(sender, arg, arg2, startIndex, endIndex, bits);
180         }
181     }
182 
183     /**
184      * Notify callbacks from startIndex to endIndex, using bits as the bit status
185      * for whether they have been removed or not. bits should be from mRemainderRemoved or
186      * mFirst64Removed. bits set to 0 indicates that all callbacks from startIndex to
187      * endIndex should be notified.
188      *
189      * @param sender The originator. This is an opaque parameter passed to
190      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
191      * @param arg An opaque parameter passed to
192      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
193      * @param arg2 An opaque parameter passed to
194      *      {@link CallbackRegistry.NotifierCallback#onNotifyCallback(Object, Object, int, A)}
195      * @param startIndex The index into the mCallbacks to start notifying.
196      * @param endIndex One past the last index into mCallbacks to notify.
197      * @param bits A bit field indicating which callbacks have been removed and shouldn't
198      *             be notified.
199      */
notifyCallbacksLocked(T sender, int arg, A arg2, final int startIndex, final int endIndex, final long bits)200     private void notifyCallbacksLocked(T sender, int arg, A arg2, final int startIndex,
201             final int endIndex, final long bits) {
202         long bitMask = 1;
203         for (int i = startIndex; i < endIndex; i++) {
204             if ((bits & bitMask) == 0) {
205                 mNotifier.onNotifyCallback(mCallbacks.get(i), sender, arg, arg2);
206             }
207             bitMask <<= 1;
208         }
209     }
210 
211     /**
212      * Add a callback to be notified. If the callback is already in the list, another won't
213      * be added. This does not affect current notifications.
214      * @param callback The callback to add.
215      */
add(C callback)216     public synchronized void add(C callback) {
217         int index = mCallbacks.lastIndexOf(callback);
218         if (index < 0 || isRemovedLocked(index)) {
219             mCallbacks.add(callback);
220         }
221     }
222 
223     /**
224      * Returns true if the callback at index has been marked for removal.
225      *
226      * @param index The index into mCallbacks to check.
227      * @return true if the callback at index has been marked for removal.
228      */
isRemovedLocked(int index)229     private boolean isRemovedLocked(int index) {
230         if (index < Long.SIZE) {
231             // It is in the first 64 callbacks, just check the bit.
232             final long bitMask = 1L << index;
233             return (mFirst64Removed & bitMask) != 0;
234         } else if (mRemainderRemoved == null) {
235             // It is after the first 64 callbacks, but nothing else was marked for removal.
236             return false;
237         } else {
238             final int maskIndex = (index / Long.SIZE) - 1;
239             if (maskIndex >= mRemainderRemoved.length) {
240                 // There are some items in mRemainderRemoved, but nothing at the given index.
241                 return false;
242             } else {
243                 // There is something marked for removal, so we have to check the bit.
244                 final long bits = mRemainderRemoved[maskIndex];
245                 final long bitMask = 1L << (index % Long.SIZE);
246                 return (bits & bitMask) != 0;
247             }
248         }
249     }
250 
251     /**
252      * Removes callbacks from startIndex to startIndex + Long.SIZE, based
253      * on the bits set in removed.
254      * @param startIndex The index into the mCallbacks to start removing callbacks.
255      * @param removed The bits indicating removal, where each bit is set for one callback
256      *                to be removed.
257      */
removeRemovedCallbacks(int startIndex, long removed)258     private void removeRemovedCallbacks(int startIndex, long removed) {
259         // The naive approach should be fine. There may be a better bit-twiddling approach.
260         final int endIndex = startIndex + Long.SIZE;
261 
262         long bitMask = 1L << (Long.SIZE - 1);
263         for (int i = endIndex - 1; i >= startIndex; i--) {
264             if ((removed & bitMask) != 0) {
265                 mCallbacks.remove(i);
266             }
267             bitMask >>>= 1;
268         }
269     }
270 
271     /**
272      * Remove a callback. This callback won't be notified after this call completes.
273      * @param callback The callback to remove.
274      */
remove(C callback)275     public synchronized void remove(C callback) {
276         if (mNotificationLevel == 0) {
277             mCallbacks.remove(callback);
278         } else {
279             int index = mCallbacks.lastIndexOf(callback);
280             if (index >= 0) {
281                 setRemovalBitLocked(index);
282             }
283         }
284     }
285 
setRemovalBitLocked(int index)286     private void setRemovalBitLocked(int index) {
287         if (index < Long.SIZE) {
288             // It is in the first 64 callbacks, just check the bit.
289             final long bitMask = 1L << index;
290             mFirst64Removed |= bitMask;
291         } else {
292             final int remainderIndex = (index / Long.SIZE) - 1;
293             if (mRemainderRemoved == null) {
294                 mRemainderRemoved = new long[mCallbacks.size() / Long.SIZE];
295             } else if (mRemainderRemoved.length < remainderIndex) {
296                 // need to make it bigger
297                 long[] newRemainders = new long[mCallbacks.size() / Long.SIZE];
298                 System.arraycopy(mRemainderRemoved, 0, newRemainders, 0, mRemainderRemoved.length);
299                 mRemainderRemoved = newRemainders;
300             }
301             final long bitMask = 1L << (index % Long.SIZE);
302             mRemainderRemoved[remainderIndex] |= bitMask;
303         }
304     }
305 
306     /**
307      * Makes a copy of the registered callbacks and returns it.
308      *
309      * @return a copy of the registered callbacks.
310      */
copyListeners()311     public synchronized ArrayList<C> copyListeners() {
312         ArrayList<C> callbacks = new ArrayList<C>(mCallbacks.size());
313         int numListeners = mCallbacks.size();
314         for (int i = 0; i < numListeners; i++) {
315             if (!isRemovedLocked(i)) {
316                 callbacks.add(mCallbacks.get(i));
317             }
318         }
319         return callbacks;
320     }
321 
322     /**
323      * Returns true if there are no registered callbacks or false otherwise.
324      *
325      * @return true if there are no registered callbacks or false otherwise.
326      */
isEmpty()327     public synchronized boolean isEmpty() {
328         if (mCallbacks.isEmpty()) {
329             return true;
330         } else if (mNotificationLevel == 0) {
331             return false;
332         } else {
333             int numListeners = mCallbacks.size();
334             for (int i = 0; i < numListeners; i++) {
335                 if (!isRemovedLocked(i)) {
336                     return false;
337                 }
338             }
339             return true;
340         }
341     }
342 
343     /**
344      * Removes all callbacks from the list.
345      */
clear()346     public synchronized void clear() {
347         if (mNotificationLevel == 0) {
348             mCallbacks.clear();
349         } else if (!mCallbacks.isEmpty()) {
350             for (int i = mCallbacks.size() - 1; i >= 0; i--) {
351                 setRemovalBitLocked(i);
352             }
353         }
354     }
355 
clone()356     public synchronized CallbackRegistry<C, T, A> clone() {
357         CallbackRegistry<C, T, A> clone = null;
358         try {
359             clone = (CallbackRegistry<C, T, A>) super.clone();
360             clone.mFirst64Removed = 0;
361             clone.mRemainderRemoved = null;
362             clone.mNotificationLevel = 0;
363             clone.mCallbacks = new ArrayList<C>();
364             final int numListeners = mCallbacks.size();
365             for (int i = 0; i < numListeners; i++) {
366                 if (!isRemovedLocked(i)) {
367                     clone.mCallbacks.add(mCallbacks.get(i));
368                 }
369             }
370         } catch (CloneNotSupportedException e) {
371             e.printStackTrace();
372         }
373         return clone;
374     }
375 
376     /**
377      * Class used to notify events from CallbackRegistry.
378      *
379      * @param <C> The callback type.
380      * @param <T> The notification sender type. Typically this is the containing class.
381      * @param <A> An opaque argument to pass to the notifier
382      */
383     public abstract static class NotifierCallback<C, T, A> {
384         /**
385          * Used to notify the callback.
386          *
387          * @param callback The callback to notify.
388          * @param sender The opaque sender object.
389          * @param arg The opaque notification parameter.
390          * @param arg2 An opaque argument passed in
391          *        {@link CallbackRegistry#notifyCallbacks}
392          * @see CallbackRegistry#CallbackRegistry(CallbackRegistry.NotifierCallback)
393          */
onNotifyCallback(C callback, T sender, int arg, A arg2)394         public abstract void onNotifyCallback(C callback, T sender, int arg, A arg2);
395     }
396 }
397