View Javadoc
1   package ch.qos.logback.core.util;
2   
3   import java.util.Collection;
4   import java.util.Iterator;
5   import java.util.List;
6   import java.util.ListIterator;
7   import java.util.concurrent.CopyOnWriteArrayList;
8   import java.util.concurrent.atomic.AtomicBoolean;
9   
10  /**
11   * A GC-free lock-free thread-safe implementation of the {@link List} interface for use cases where iterations over the list vastly out-number modifications on the list.
12   * 
13   * <p>Underneath, it wraps an instance of {@link CopyOnWriteArrayList} and exposes a copy of the array used by that instance.
14   * 
15   * <p>Typical use:</p>
16   * 
17   * <pre>
18   *   COWArrayList&lt;Integer&gt; list = new COWArrayList(new Integer[0]);
19   *   
20   *   // modify the list
21   *   list.add(1);
22   *   list.add(2);
23   *   
24   *   Integer[] intArray = list.asTypedArray();
25   *   int sum = 0;
26   *   // iteration over the array is thread-safe
27   *   for(int i = 0; i &lt; intArray.length; i++) {
28   *     sum != intArray[i];
29   *   }
30   * </pre>  
31   *   
32   *  <p>If the list is not modified, then repetitive calls to {@link #asTypedArray()}, {@link #toArray()} and 
33   *  {@link #toArray(Object[])} are guaranteed to be GC-free. Note that iterating over the list using 
34   *  {@link COWArrayList#iterator()} and {@link COWArrayList#listIterator()} are <b>not</b> GC-free.</p>
35   *   
36   * @author Ceki Gulcu
37   * @since 1.1.10
38   */
39  public class COWArrayList<E> implements List<E> {
40  
41      // Implementation note: markAsStale() should always be invoked *after* list-modifying actions.
42      // If not, readers might get a stale array until the next write. The potential problem is nicely
43      // explained by Rob Eden. See https://github.com/qos-ch/logback/commit/32a2047a1adfc#commitcomment-20791176
44      
45      AtomicBoolean fresh = new AtomicBoolean(false);
46      CopyOnWriteArrayList<E> underlyingList = new CopyOnWriteArrayList<E>();
47      E[] ourCopy;
48      final E[] modelArray;
49  
50      public COWArrayList(E[] modelArray) {
51          this.modelArray = modelArray;
52      }
53  
54      @Override
55      public int size() {
56          return underlyingList.size();
57      }
58  
59      @Override
60      public boolean isEmpty() {
61          return underlyingList.isEmpty();
62      }
63  
64      @Override
65      public boolean contains(Object o) {
66          return underlyingList.contains(o);
67      }
68  
69      @Override
70      public Iterator<E> iterator() {
71          return underlyingList.iterator();
72      }
73  
74      private void refreshCopyIfNecessary() {
75          if (!isFresh()) {
76              refreshCopy();
77          }
78      }
79  
80      private boolean isFresh() {
81          return fresh.get();
82      }
83  
84      private void refreshCopy() {
85          ourCopy = underlyingList.toArray(modelArray);
86          fresh.set(true);
87      }
88  
89      @Override
90      public Object[] toArray() {
91          refreshCopyIfNecessary();
92          return ourCopy;
93      }
94  
95      @SuppressWarnings("unchecked")
96      @Override
97      public <T> T[] toArray(T[] a) {
98          refreshCopyIfNecessary();
99          return (T[]) ourCopy;
100     }
101 
102     /**
103      * Return an array of type E[]. The returned array is intended to be iterated over. 
104      * If the list is modified, subsequent calls to this method will return different/modified 
105      * array instances.
106      * 
107      * @return
108      */
109     public E[] asTypedArray() {
110         refreshCopyIfNecessary();
111         return ourCopy;
112     }
113     
114     private void markAsStale() {
115         fresh.set(false);
116     }
117     
118     public void addIfAbsent(E e) {
119         underlyingList.addIfAbsent(e);
120         markAsStale();
121     }
122 
123     @Override
124     public boolean add(E e) {
125         boolean result = underlyingList.add(e);
126         markAsStale();
127         return result;
128     }
129 
130     @Override
131     public boolean remove(Object o) {
132         boolean result = underlyingList.remove(o);
133         markAsStale();
134         return result;
135     }
136 
137     @Override
138     public boolean containsAll(Collection<?> c) {
139         return underlyingList.containsAll(c);
140     }
141 
142     @Override
143     public boolean addAll(Collection<? extends E> c) {
144         boolean result = underlyingList.addAll(c);
145         markAsStale();
146         return result;
147     }
148 
149     @Override
150     public boolean addAll(int index, Collection<? extends E> col) {
151         boolean result = underlyingList.addAll(index, col);
152         markAsStale();
153         return result;
154     }
155 
156     @Override
157     public boolean removeAll(Collection<?> col) {
158         boolean result = underlyingList.removeAll(col);
159         markAsStale();
160         return result;
161     }
162 
163     @Override
164     public boolean retainAll(Collection<?> col) {
165         boolean result = underlyingList.retainAll(col);
166         markAsStale();
167         return result;
168     }
169 
170     @Override
171     public void clear() {
172         underlyingList.clear();
173         markAsStale();
174     }
175 
176     @Override
177     public E get(int index) {
178         refreshCopyIfNecessary();
179         return (E) ourCopy[index];
180     }
181 
182     @Override
183     public E set(int index, E element) {
184         E e = underlyingList.set(index, element);
185         markAsStale();
186         return e;
187     }
188 
189     @Override
190     public void add(int index, E element) {
191         underlyingList.add(index, element);
192         markAsStale();
193     }
194 
195     @Override
196     public E remove(int index) {
197         E e = (E) underlyingList.remove(index);
198         markAsStale();
199         return e;
200     }
201 
202     @Override
203     public int indexOf(Object o) {
204         return underlyingList.indexOf(o);
205     }
206 
207     @Override
208     public int lastIndexOf(Object o) {
209         return underlyingList.lastIndexOf(o);
210     }
211 
212     @Override
213     public ListIterator<E> listIterator() {
214         return underlyingList.listIterator();
215     }
216 
217     @Override
218     public ListIterator<E> listIterator(int index) {
219         return underlyingList.listIterator(index);
220     }
221 
222     @Override
223     public List<E> subList(int fromIndex, int toIndex) {
224         return underlyingList.subList(fromIndex, toIndex);
225     }
226 
227 }