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