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<Integer> 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 < 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 }
228