1 // Copyright 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 package org.chromium.base; 6 7 import java.util.ArrayList; 8 import java.util.Iterator; 9 import java.util.List; 10 import java.util.NoSuchElementException; 11 12 import javax.annotation.concurrent.NotThreadSafe; 13 14 /** 15 * A container for a list of observers. 16 * <p/> 17 * This container can be modified during iteration without invalidating the iterator. 18 * So, it safely handles the case of an observer removing itself or other observers from the list 19 * while observers are being notified. 20 * <p/> 21 * The implementation (and the interface) is heavily influenced by the C++ ObserverList. 22 * Notable differences: 23 * - The iterator implements NOTIFY_EXISTING_ONLY. 24 * - The FOR_EACH_OBSERVER closure is left to the clients to implement in terms of iterator(). 25 * <p/> 26 * This class is not threadsafe. Observers MUST be added, removed and will be notified on the same 27 * thread this is created. 28 * 29 * @param <E> The type of observers that this list should hold. 30 */ 31 @NotThreadSafe 32 public class ObserverList<E> implements Iterable<E> { 33 /** 34 * Extended iterator interface that provides rewind functionality. 35 */ 36 public interface RewindableIterator<E> extends Iterator<E> { 37 /** 38 * Rewind the iterator back to the beginning. 39 * 40 * If we need to iterate multiple times, we can avoid iterator object reallocation by using 41 * this method. 42 */ 43 public void rewind(); 44 } 45 46 public final List<E> mObservers = new ArrayList<E>(); 47 private int mIterationDepth = 0; 48 private int mCount = 0; 49 50 public ObserverList() {} 51 52 /** 53 * Add an observer to the list. 54 * <p/> 55 * An observer should not be added to the same list more than once. If an iteration is already 56 * in progress, this observer will be not be visible during that iteration. 57 * 58 * @return true if the observer list changed as a result of the call. 59 */ 60 public boolean addObserver(E obs) { 61 // Avoid adding null elements to the list as they may be removed on a compaction. 62 if (obs == null || mObservers.contains(obs)) { 63 return false; 64 } 65 66 // Structurally modifying the underlying list here. This means we 67 // cannot use the underlying list's iterator to iterate over the list. 68 boolean result = mObservers.add(obs); 69 assert result; 70 71 ++mCount; 72 return true; 73 } 74 75 /** 76 * Remove an observer from the list if it is in the list. 77 * 78 * @return true if an element was removed as a result of this call. 79 */ 80 public boolean removeObserver(E obs) { 81 if (obs == null) { 82 return false; 83 } 84 85 int index = mObservers.indexOf(obs); 86 if (index == -1) { 87 return false; 88 } 89 90 if (mIterationDepth == 0) { 91 // No one is iterating over the list. 92 mObservers.remove(index); 93 } else { 94 mObservers.set(index, null); 95 } 96 --mCount; 97 assert mCount >= 0; 98 99 return true; 100 } 101 102 public boolean hasObserver(E obs) { 103 return mObservers.contains(obs); 104 } 105 106 public void clear() { 107 mCount = 0; 108 109 if (mIterationDepth == 0) { 110 mObservers.clear(); 111 return; 112 } 113 114 int size = mObservers.size(); 115 for (int i = 0; i < size; i++) { 116 mObservers.set(i, null); 117 } 118 } 119 120 @Override 121 public Iterator<E> iterator() { 122 return new ObserverListIterator(); 123 } 124 125 /** 126 * It's the same as {@link ObserverList#iterator()} but the return type is 127 * {@link RewindableIterator}. Use this iterator type if you need to use 128 * {@link RewindableIterator#rewind()}. 129 */ 130 public RewindableIterator<E> rewindableIterator() { 131 return new ObserverListIterator(); 132 } 133 134 /** 135 * Returns the number of observers currently registered in the ObserverList. 136 * This is equivalent to the number of non-empty spaces in |mObservers|. 137 */ 138 public int size() { 139 return mCount; 140 } 141 142 /** 143 * Returns true if the ObserverList contains no observers. 144 */ 145 public boolean isEmpty() { 146 return mCount == 0; 147 } 148 149 /** 150 * Compact the underlying list be removing null elements. 151 * <p/> 152 * Should only be called when mIterationDepth is zero. 153 */ 154 private void compact() { 155 assert mIterationDepth == 0; 156 for (int i = mObservers.size() - 1; i >= 0; i--) { 157 if (mObservers.get(i) == null) { 158 mObservers.remove(i); 159 } 160 } 161 } 162 163 private void incrementIterationDepth() { 164 mIterationDepth++; 165 } 166 167 private void decrementIterationDepthAndCompactIfNeeded() { 168 mIterationDepth--; 169 assert mIterationDepth >= 0; 170 if (mIterationDepth == 0) compact(); 171 } 172 173 /** 174 * Returns the size of the underlying storage of the ObserverList. 175 * It will take into account the empty spaces inside |mObservers|. 176 */ 177 private int capacity() { 178 return mObservers.size(); 179 } 180 181 private E getObserverAt(int index) { 182 return mObservers.get(index); 183 } 184 185 private class ObserverListIterator implements RewindableIterator<E> { 186 private int mListEndMarker; 187 private int mIndex = 0; 188 private boolean mIsExhausted = false; 189 190 private ObserverListIterator() { 191 ObserverList.this.incrementIterationDepth(); 192 mListEndMarker = ObserverList.this.capacity(); 193 } 194 195 @Override 196 public void rewind() { 197 compactListIfNeeded(); 198 ObserverList.this.incrementIterationDepth(); 199 mListEndMarker = ObserverList.this.capacity(); 200 mIsExhausted = false; 201 mIndex = 0; 202 } 203 204 @Override 205 public boolean hasNext() { 206 int lookupIndex = mIndex; 207 while (lookupIndex < mListEndMarker && 208 ObserverList.this.getObserverAt(lookupIndex) == null) { 209 lookupIndex++; 210 } 211 if (lookupIndex < mListEndMarker) return true; 212 213 // We have reached the end of the list, allow for compaction. 214 compactListIfNeeded(); 215 return false; 216 } 217 218 @Override 219 public E next() { 220 // Advance if the current element is null. 221 while (mIndex < mListEndMarker && ObserverList.this.getObserverAt(mIndex) == null) { 222 mIndex++; 223 } 224 if (mIndex < mListEndMarker) return ObserverList.this.getObserverAt(mIndex++); 225 226 // We have reached the end of the list, allow for compaction. 227 compactListIfNeeded(); 228 throw new NoSuchElementException(); 229 } 230 231 @Override 232 public void remove() { 233 throw new UnsupportedOperationException(); 234 } 235 236 private void compactListIfNeeded() { 237 if (!mIsExhausted) { 238 mIsExhausted = true; 239 ObserverList.this.decrementIterationDepthAndCompactIfNeeded(); 240 } 241 } 242 } 243 } 244
