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.lang.Iterable; 8 import java.util.ArrayList; 9 import java.util.Iterator; 10 import java.util.List; 11 import java.util.NoSuchElementException; 12 13 import javax.annotation.concurrent.NotThreadSafe; 14 15 /** 16 * A container for a list of observers. 17 * <p/> 18 * This container can be modified during iteration without invalidating the iterator. 19 * So, it safely handles the case of an observer removing itself or other observers from the list 20 * while observers are being notified. 21 * <p/> 22 * The implementation (and the interface) is heavily influenced by the C++ ObserverList. 23 * Notable differences: 24 * - The iterator implements NOTIFY_EXISTING_ONLY. 25 * - The FOR_EACH_OBSERVER closure is left to the clients to implement in terms of iterator(). 26 * <p/> 27 * This class is not threadsafe. Observers MUST be added, removed and will be notified on the same 28 * thread this is created. 29 */ 30 @NotThreadSafe 31 public class ObserverList<E> implements Iterable<E> { 32 public final List<E> mObservers = new ArrayList<E>(); 33 private int mIterationDepth = 0; 34 35 public ObserverList() {} 36 37 /** 38 * Add an observer to the list. 39 * <p/> 40 * An observer should not be added to the same list more than once. If an iteration is already 41 * in progress, this observer will be not be visible during that iteration. 42 */ 43 public void addObserver(E obs) { 44 // Avoid adding null elements to the list as they may be removed on a compaction. 45 if (obs == null || mObservers.contains(obs)) { 46 assert false; 47 return; 48 } 49 50 // Structurally modifying the underlying list here. This means we 51 // cannot use the underlying list's iterator to iterate over the list. 52 mObservers.add(obs); 53 } 54 55 /** 56 * Remove an observer from the list if it is in the list. 57 */ 58 public void removeObserver(E obs) { 59 int index = mObservers.indexOf(obs); 60 61 if (index == -1) 62 return; 63 64 if (mIterationDepth == 0) { 65 // No one is iterating over the list. 66 mObservers.remove(obs); 67 } else { 68 mObservers.set(index, null); 69 } 70 } 71 72 public boolean hasObserver(E obs) { 73 return mObservers.contains(obs); 74 } 75 76 public void clear() { 77 if (mIterationDepth == 0) { 78 mObservers.clear(); 79 return; 80 } 81 82 int size = mObservers.size(); 83 for (int i = 0; i < size; i++) 84 mObservers.set(i, null); 85 } 86 87 @Override 88 public Iterator<E> iterator() { 89 return new ObserverListIterator(); 90 } 91 92 /** 93 * Compact the underlying list be removing null elements. 94 * <p/> 95 * Should only be called when mIterationDepth is zero. 96 */ 97 private void compact() { 98 assert mIterationDepth == 0; 99 // Safe to use the underlying list's iterator, as we know that no-one else 100 // is iterating over the list. 101 Iterator<E> it = mObservers.iterator(); 102 while (it.hasNext()) { 103 E el = it.next(); 104 if (el == null) 105 it.remove(); 106 } 107 } 108 109 private void incrementIterationDepth() { 110 mIterationDepth++; 111 } 112 113 private void decrementIterationDepthAndCompactIfNeeded() { 114 mIterationDepth--; 115 assert mIterationDepth >= 0; 116 if (mIterationDepth == 0) 117 compact(); 118 } 119 120 private int getSize() { 121 return mObservers.size(); 122 } 123 124 private E getObserverAt(int index) { 125 return mObservers.get(index); 126 } 127 128 private class ObserverListIterator implements Iterator<E> { 129 private final int mListEndMarker; 130 private int mIndex = 0; 131 private boolean mIsExhausted = false; 132 133 private ObserverListIterator() { 134 ObserverList.this.incrementIterationDepth(); 135 mListEndMarker = ObserverList.this.getSize(); 136 } 137 138 @Override 139 public boolean hasNext() { 140 int lookupIndex = mIndex; 141 while (lookupIndex < mListEndMarker && 142 ObserverList.this.getObserverAt(lookupIndex) == null) 143 lookupIndex++; 144 if (lookupIndex < mListEndMarker) 145 return true; 146 147 // We have reached the end of the list, allow for compaction. 148 compactListIfNeeded(); 149 return false; 150 } 151 152 @Override 153 public E next() { 154 // Advance if the current element is null. 155 while (mIndex < mListEndMarker && ObserverList.this.getObserverAt(mIndex) == null) 156 mIndex++; 157 if (mIndex < mListEndMarker) 158 return ObserverList.this.getObserverAt(mIndex++); 159 160 // We have reached the end of the list, allow for compaction. 161 compactListIfNeeded(); 162 throw new NoSuchElementException(); 163 } 164 165 @Override 166 public void remove() { 167 throw new UnsupportedOperationException(); 168 } 169 170 private void compactListIfNeeded() { 171 if (!mIsExhausted) { 172 mIsExhausted = true; 173 ObserverList.this.decrementIterationDepthAndCompactIfNeeded(); 174 } 175 } 176 } 177 } 178