1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * Written by Doug Lea with assistance from members of JCP JSR-166
27 * Expert Group. Adapted and released, under explicit permission,
28 * from JDK ArrayList.java which carries the following copyright:
29 *
30 * Copyright 1997 by Sun Microsystems, Inc.,
31 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
32 * All rights reserved.
33 */
34
35 package java.util.concurrent;
36
37 import java.lang.invoke.VarHandle;
38 import java.lang.reflect.Field;
39 import java.util.Arrays;
40 import java.util.Collection;
41 import java.util.Comparator;
42 import java.util.ConcurrentModificationException;
43 import java.util.Iterator;
44 import java.util.List;
45 import java.util.ListIterator;
46 import java.util.NoSuchElementException;
47 import java.util.Objects;
48 import java.util.RandomAccess;
49 import java.util.Spliterator;
50 import java.util.Spliterators;
51 import java.util.function.Consumer;
52 import java.util.function.Predicate;
53 import java.util.function.UnaryOperator;
54 import jdk.internal.access.SharedSecrets;
55
56 /**
57 * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
58 * operations ({@code add}, {@code set}, and so on) are implemented by
59 * making a fresh copy of the underlying array.
60 *
61 * <p>This is ordinarily too costly, but may be <em>more</em> efficient
62 * than alternatives when traversal operations vastly outnumber
63 * mutations, and is useful when you cannot or don't want to
64 * synchronize traversals, yet need to preclude interference among
65 * concurrent threads. The "snapshot" style iterator method uses a
66 * reference to the state of the array at the point that the iterator
67 * was created. This array never changes during the lifetime of the
68 * iterator, so interference is impossible and the iterator is
69 * guaranteed not to throw {@code ConcurrentModificationException}.
70 * The iterator will not reflect additions, removals, or changes to
71 * the list since the iterator was created. Element-changing
72 * operations on iterators themselves ({@code remove}, {@code set}, and
73 * {@code add}) are not supported. These methods throw
74 * {@code UnsupportedOperationException}.
75 *
76 * <p>All elements are permitted, including {@code null}.
77 *
78 * <p>Memory consistency effects: As with other concurrent
79 * collections, actions in a thread prior to placing an object into a
80 * {@code CopyOnWriteArrayList}
81 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
82 * actions subsequent to the access or removal of that element from
83 * the {@code CopyOnWriteArrayList} in another thread.
84 *
85 * <p>This class is a member of the
86 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
87 * Java Collections Framework</a>.
88 *
89 * @since 1.5
90 * @author Doug Lea
91 * @param <E> the type of elements held in this list
92 */
93 public class CopyOnWriteArrayList<E>
94 implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
95 private static final long serialVersionUID = 8673264195747942595L;
96
97 /**
98 * The lock protecting all mutators. (We have a mild preference
99 * for builtin monitors over ReentrantLock when either will do.)
100 */
101 final transient Object lock = new Object();
102
103 /** The array, accessed only via getArray/setArray. */
104 private transient volatile Object[] array;
105
106 /**
107 * Gets the array. Non-private so as to also be accessible
108 * from CopyOnWriteArraySet class.
109 */
110 final Object[] getArray() {
111 return array;
112 }
113
114 /**
115 * Sets the array.
116 */
117 final void setArray(Object[] a) {
118 array = a;
119 }
120
121 /**
122 * Creates an empty list.
123 */
124 public CopyOnWriteArrayList() {
125 setArray(new Object[0]);
126 }
127
128 /**
129 * Creates a list containing the elements of the specified
130 * collection, in the order they are returned by the collection's
131 * iterator.
132 *
133 * @param c the collection of initially held elements
134 * @throws NullPointerException if the specified collection is null
135 */
136 public CopyOnWriteArrayList(Collection<? extends E> c) {
137 Object[] es;
138 if (c.getClass() == CopyOnWriteArrayList.class)
139 es = ((CopyOnWriteArrayList<?>)c).getArray();
140 else {
141 es = c.toArray();
142 // defend against c.toArray (incorrectly) not returning Object[]
143 // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
144 if (es.getClass() != Object[].class)
145 es = Arrays.copyOf(es, es.length, Object[].class);
146 }
147 setArray(es);
148 }
149
150 /**
151 * Creates a list holding a copy of the given array.
152 *
153 * @param toCopyIn the array (a copy of this array is used as the
154 * internal array)
155 * @throws NullPointerException if the specified array is null
156 */
157 public CopyOnWriteArrayList(E[] toCopyIn) {
158 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
159 }
160
161 /**
162 * Returns the number of elements in this list.
163 *
164 * @return the number of elements in this list
165 */
166 public int size() {
167 return getArray().length;
168 }
169
170 /**
171 * Returns {@code true} if this list contains no elements.
172 *
173 * @return {@code true} if this list contains no elements
174 */
175 public boolean isEmpty() {
176 return size() == 0;
177 }
178
179 /**
180 * static version of indexOf, to allow repeated calls without
181 * needing to re-acquire array each time.
182 * @param o element to search for
183 * @param es the array
184 * @param from first index to search
185 * @param to one past last index to search
186 * @return index of element, or -1 if absent
187 */
188 private static int indexOfRange(Object o, Object[] es, int from, int to) {
189 if (o == null) {
190 for (int i = from; i < to; i++)
191 if (es[i] == null)
192 return i;
193 } else {
194 for (int i = from; i < to; i++)
195 if (o.equals(es[i]))
196 return i;
197 }
198 return -1;
199 }
200
201 /**
202 * static version of lastIndexOf.
203 * @param o element to search for
204 * @param es the array
205 * @param from index of first element of range, last element to search
206 * @param to one past last element of range, first element to search
207 * @return index of element, or -1 if absent
208 */
209 private static int lastIndexOfRange(Object o, Object[] es, int from, int to) {
210 if (o == null) {
211 for (int i = to - 1; i >= from; i--)
212 if (es[i] == null)
213 return i;
214 } else {
215 for (int i = to - 1; i >= from; i--)
216 if (o.equals(es[i]))
217 return i;
218 }
219 return -1;
220 }
221
222 /**
223 * Returns {@code true} if this list contains the specified element.
224 * More formally, returns {@code true} if and only if this list contains
225 * at least one element {@code e} such that {@code Objects.equals(o, e)}.
226 *
227 * @param o element whose presence in this list is to be tested
228 * @return {@code true} if this list contains the specified element
229 */
230 public boolean contains(Object o) {
231 return indexOf(o) >= 0;
232 }
233
234 /**
235 * {@inheritDoc}
236 */
237 public int indexOf(Object o) {
238 Object[] es = getArray();
239 return indexOfRange(o, es, 0, es.length);
240 }
241
242 /**
243 * Returns the index of the first occurrence of the specified element in
244 * this list, searching forwards from {@code index}, or returns -1 if
245 * the element is not found.
246 * More formally, returns the lowest index {@code i} such that
247 * {@code i >= index && Objects.equals(get(i), e)},
248 * or -1 if there is no such index.
249 *
250 * @param e element to search for
251 * @param index index to start searching from
252 * @return the index of the first occurrence of the element in
253 * this list at position {@code index} or later in the list;
254 * {@code -1} if the element is not found.
255 * @throws IndexOutOfBoundsException if the specified index is negative
256 */
257 public int indexOf(E e, int index) {
258 Object[] es = getArray();
259 return indexOfRange(e, es, index, es.length);
260 }
261
262 /**
263 * {@inheritDoc}
264 */
265 public int lastIndexOf(Object o) {
266 Object[] es = getArray();
267 return lastIndexOfRange(o, es, 0, es.length);
268 }
269
270 /**
271 * Returns the index of the last occurrence of the specified element in
272 * this list, searching backwards from {@code index}, or returns -1 if
273 * the element is not found.
274 * More formally, returns the highest index {@code i} such that
275 * {@code i <= index && Objects.equals(get(i), e)},
276 * or -1 if there is no such index.
277 *
278 * @param e element to search for
279 * @param index index to start searching backwards from
280 * @return the index of the last occurrence of the element at position
281 * less than or equal to {@code index} in this list;
282 * -1 if the element is not found.
283 * @throws IndexOutOfBoundsException if the specified index is greater
284 * than or equal to the current size of this list
285 */
286 public int lastIndexOf(E e, int index) {
287 Object[] es = getArray();
288 return lastIndexOfRange(e, es, 0, index + 1);
289 }
290
291 /**
292 * Returns a shallow copy of this list. (The elements themselves
293 * are not copied.)
294 *
295 * @return a clone of this list
296 */
297 public Object clone() {
298 try {
299 @SuppressWarnings("unchecked")
300 CopyOnWriteArrayList<E> clone =
301 (CopyOnWriteArrayList<E>) super.clone();
302 clone.resetLock();
303 // Unlike in readObject, here we cannot visibility-piggyback on the
304 // volatile write in setArray().
305 VarHandle.releaseFence();
306 return clone;
307 } catch (CloneNotSupportedException e) {
308 // this shouldn't happen, since we are Cloneable
309 throw new InternalError();
310 }
311 }
312
313 /**
314 * Returns an array containing all of the elements in this list
315 * in proper sequence (from first to last element).
316 *
317 * <p>The returned array will be "safe" in that no references to it are
318 * maintained by this list. (In other words, this method must allocate
319 * a new array). The caller is thus free to modify the returned array.
320 *
321 * <p>This method acts as bridge between array-based and collection-based
322 * APIs.
323 *
324 * @return an array containing all the elements in this list
325 */
326 public Object[] toArray() {
327 return getArray().clone();
328 }
329
330 /**
331 * Returns an array containing all of the elements in this list in
332 * proper sequence (from first to last element); the runtime type of
333 * the returned array is that of the specified array. If the list fits
334 * in the specified array, it is returned therein. Otherwise, a new
335 * array is allocated with the runtime type of the specified array and
336 * the size of this list.
337 *
338 * <p>If this list fits in the specified array with room to spare
339 * (i.e., the array has more elements than this list), the element in
340 * the array immediately following the end of the list is set to
341 * {@code null}. (This is useful in determining the length of this
342 * list <i>only</i> if the caller knows that this list does not contain
343 * any null elements.)
344 *
345 * <p>Like the {@link #toArray()} method, this method acts as bridge between
346 * array-based and collection-based APIs. Further, this method allows
347 * precise control over the runtime type of the output array, and may,
348 * under certain circumstances, be used to save allocation costs.
349 *
350 * <p>Suppose {@code x} is a list known to contain only strings.
351 * The following code can be used to dump the list into a newly
352 * allocated array of {@code String}:
353 *
354 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
355 *
356 * Note that {@code toArray(new Object[0])} is identical in function to
357 * {@code toArray()}.
358 *
359 * @param a the array into which the elements of the list are to
360 * be stored, if it is big enough; otherwise, a new array of the
361 * same runtime type is allocated for this purpose.
362 * @return an array containing all the elements in this list
363 * @throws ArrayStoreException if the runtime type of the specified array
364 * is not a supertype of the runtime type of every element in
365 * this list
366 * @throws NullPointerException if the specified array is null
367 */
368 @SuppressWarnings("unchecked")
369 public <T> T[] toArray(T[] a) {
370 Object[] es = getArray();
371 int len = es.length;
372 if (a.length < len)
373 return (T[]) Arrays.copyOf(es, len, a.getClass());
374 else {
375 System.arraycopy(es, 0, a, 0, len);
376 if (a.length > len)
377 a[len] = null;
378 return a;
379 }
380 }
381
382 // Positional Access Operations
383
384 @SuppressWarnings("unchecked")
385 static <E> E elementAt(Object[] a, int index) {
386 return (E) a[index];
387 }
388
389 static String outOfBounds(int index, int size) {
390 return "Index: " + index + ", Size: " + size;
391 }
392
393 /**
394 * {@inheritDoc}
395 *
396 * @throws IndexOutOfBoundsException {@inheritDoc}
397 */
398 public E get(int index) {
399 return elementAt(getArray(), index);
400 }
401
402 /**
403 * Replaces the element at the specified position in this list with the
404 * specified element.
405 *
406 * @throws IndexOutOfBoundsException {@inheritDoc}
407 */
408 public E set(int index, E element) {
409 synchronized (lock) {
410 Object[] es = getArray();
411 E oldValue = elementAt(es, index);
412
413 if (oldValue != element) {
414 es = es.clone();
415 es[index] = element;
416 setArray(es);
417 }
418 return oldValue;
419 }
420 }
421
422 /**
423 * Appends the specified element to the end of this list.
424 *
425 * @param e element to be appended to this list
426 * @return {@code true} (as specified by {@link Collection#add})
427 */
428 public boolean add(E e) {
429 synchronized (lock) {
430 Object[] es = getArray();
431 int len = es.length;
432 es = Arrays.copyOf(es, len + 1);
433 es[len] = e;
434 setArray(es);
435 return true;
436 }
437 }
438
439 /**
440 * Inserts the specified element at the specified position in this
441 * list. Shifts the element currently at that position (if any) and
442 * any subsequent elements to the right (adds one to their indices).
443 *
444 * @throws IndexOutOfBoundsException {@inheritDoc}
445 */
446 public void add(int index, E element) {
447 synchronized (lock) {
448 Object[] es = getArray();
449 int len = es.length;
450 if (index > len || index < 0)
451 throw new IndexOutOfBoundsException(outOfBounds(index, len));
452 Object[] newElements;
453 int numMoved = len - index;
454 if (numMoved == 0)
455 newElements = Arrays.copyOf(es, len + 1);
456 else {
457 newElements = new Object[len + 1];
458 System.arraycopy(es, 0, newElements, 0, index);
459 System.arraycopy(es, index, newElements, index + 1,
460 numMoved);
461 }
462 newElements[index] = element;
463 setArray(newElements);
464 }
465 }
466
467 /**
468 * Removes the element at the specified position in this list.
469 * Shifts any subsequent elements to the left (subtracts one from their
470 * indices). Returns the element that was removed from the list.
471 *
472 * @throws IndexOutOfBoundsException {@inheritDoc}
473 */
474 public E remove(int index) {
475 synchronized (lock) {
476 Object[] es = getArray();
477 int len = es.length;
478 E oldValue = elementAt(es, index);
479 int numMoved = len - index - 1;
480 Object[] newElements;
481 if (numMoved == 0)
482 newElements = Arrays.copyOf(es, len - 1);
483 else {
484 newElements = new Object[len - 1];
485 System.arraycopy(es, 0, newElements, 0, index);
486 System.arraycopy(es, index + 1, newElements, index,
487 numMoved);
488 }
489 setArray(newElements);
490 return oldValue;
491 }
492 }
493
494 /**
495 * Removes the first occurrence of the specified element from this list,
496 * if it is present. If this list does not contain the element, it is
497 * unchanged. More formally, removes the element with the lowest index
498 * {@code i} such that {@code Objects.equals(o, get(i))}
499 * (if such an element exists). Returns {@code true} if this list
500 * contained the specified element (or equivalently, if this list
501 * changed as a result of the call).
502 *
503 * @param o element to be removed from this list, if present
504 * @return {@code true} if this list contained the specified element
505 */
506 public boolean remove(Object o) {
507 Object[] snapshot = getArray();
508 int index = indexOfRange(o, snapshot, 0, snapshot.length);
509 return index >= 0 && remove(o, snapshot, index);
510 }
511
512 /**
513 * A version of remove(Object) using the strong hint that given
514 * recent snapshot contains o at the given index.
515 */
516 private boolean remove(Object o, Object[] snapshot, int index) {
517 synchronized (lock) {
518 Object[] current = getArray();
519 int len = current.length;
520 if (snapshot != current) findIndex: {
521 int prefix = Math.min(index, len);
522 for (int i = 0; i < prefix; i++) {
523 if (current[i] != snapshot[i]
524 && Objects.equals(o, current[i])) {
525 index = i;
526 break findIndex;
527 }
528 }
529 if (index >= len)
530 return false;
531 if (current[index] == o)
532 break findIndex;
533 index = indexOfRange(o, current, index, len);
534 if (index < 0)
535 return false;
536 }
537 Object[] newElements = new Object[len - 1];
538 System.arraycopy(current, 0, newElements, 0, index);
539 System.arraycopy(current, index + 1,
540 newElements, index,
541 len - index - 1);
542 setArray(newElements);
543 return true;
544 }
545 }
546
547 /**
548 * Removes from this list all of the elements whose index is between
549 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
550 * Shifts any succeeding elements to the left (reduces their index).
551 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
552 * (If {@code toIndex==fromIndex}, this operation has no effect.)
553 *
554 * @param fromIndex index of first element to be removed
555 * @param toIndex index after last element to be removed
556 * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
557 * ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
558 */
559 void removeRange(int fromIndex, int toIndex) {
560 synchronized (lock) {
561 Object[] es = getArray();
562 int len = es.length;
563
564 if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
565 throw new IndexOutOfBoundsException();
566 int newlen = len - (toIndex - fromIndex);
567 int numMoved = len - toIndex;
568 if (numMoved == 0)
569 setArray(Arrays.copyOf(es, newlen));
570 else {
571 Object[] newElements = new Object[newlen];
572 System.arraycopy(es, 0, newElements, 0, fromIndex);
573 System.arraycopy(es, toIndex, newElements,
574 fromIndex, numMoved);
575 setArray(newElements);
576 }
577 }
578 }
579
580 /**
581 * Appends the element, if not present.
582 *
583 * @param e element to be added to this list, if absent
584 * @return {@code true} if the element was added
585 */
586 public boolean addIfAbsent(E e) {
587 Object[] snapshot = getArray();
588 return indexOfRange(e, snapshot, 0, snapshot.length) < 0
589 && addIfAbsent(e, snapshot);
590 }
591
592 /**
593 * A version of addIfAbsent using the strong hint that given
594 * recent snapshot does not contain e.
595 */
596 private boolean addIfAbsent(E e, Object[] snapshot) {
597 synchronized (lock) {
598 Object[] current = getArray();
599 int len = current.length;
600 if (snapshot != current) {
601 // Optimize for lost race to another addXXX operation
602 int common = Math.min(snapshot.length, len);
603 for (int i = 0; i < common; i++)
604 if (current[i] != snapshot[i]
605 && Objects.equals(e, current[i]))
606 return false;
607 if (indexOfRange(e, current, common, len) >= 0)
608 return false;
609 }
610 Object[] newElements = Arrays.copyOf(current, len + 1);
611 newElements[len] = e;
612 setArray(newElements);
613 return true;
614 }
615 }
616
617 /**
618 * Returns {@code true} if this list contains all of the elements of the
619 * specified collection.
620 *
621 * @param c collection to be checked for containment in this list
622 * @return {@code true} if this list contains all of the elements of the
623 * specified collection
624 * @throws NullPointerException if the specified collection is null
625 * @see #contains(Object)
626 */
627 public boolean containsAll(Collection<?> c) {
628 Object[] es = getArray();
629 int len = es.length;
630 for (Object e : c) {
631 if (indexOfRange(e, es, 0, len) < 0)
632 return false;
633 }
634 return true;
635 }
636
637 /**
638 * Removes from this list all of its elements that are contained in
639 * the specified collection. This is a particularly expensive operation
640 * in this class because of the need for an internal temporary array.
641 *
642 * @param c collection containing elements to be removed from this list
643 * @return {@code true} if this list changed as a result of the call
644 * @throws ClassCastException if the class of an element of this list
645 * is incompatible with the specified collection
646 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
647 * @throws NullPointerException if this list contains a null element and the
648 * specified collection does not permit null elements
649 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>),
650 * or if the specified collection is null
651 * @see #remove(Object)
652 */
653 public boolean removeAll(Collection<?> c) {
654 Objects.requireNonNull(c);
655 return bulkRemove(e -> c.contains(e));
656 }
657
658 /**
659 * Retains only the elements in this list that are contained in the
660 * specified collection. In other words, removes from this list all of
661 * its elements that are not contained in the specified collection.
662 *
663 * @param c collection containing elements to be retained in this list
664 * @return {@code true} if this list changed as a result of the call
665 * @throws ClassCastException if the class of an element of this list
666 * is incompatible with the specified collection
667 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
668 * @throws NullPointerException if this list contains a null element and the
669 * specified collection does not permit null elements
670 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>),
671 * or if the specified collection is null
672 * @see #remove(Object)
673 */
674 public boolean retainAll(Collection<?> c) {
675 Objects.requireNonNull(c);
676 return bulkRemove(e -> !c.contains(e));
677 }
678
679 /**
680 * Appends all of the elements in the specified collection that
681 * are not already contained in this list, to the end of
682 * this list, in the order that they are returned by the
683 * specified collection's iterator.
684 *
685 * @param c collection containing elements to be added to this list
686 * @return the number of elements added
687 * @throws NullPointerException if the specified collection is null
688 * @see #addIfAbsent(Object)
689 */
690 public int addAllAbsent(Collection<? extends E> c) {
691 Object[] cs = c.toArray();
692 if (cs.length == 0)
693 return 0;
694 synchronized (lock) {
695 Object[] es = getArray();
696 int len = es.length;
697 int added = 0;
698 // uniquify and compact elements in cs
699 for (int i = 0; i < cs.length; ++i) {
700 Object e = cs[i];
701 if (indexOfRange(e, es, 0, len) < 0 &&
702 indexOfRange(e, cs, 0, added) < 0)
703 cs[added++] = e;
704 }
705 if (added > 0) {
706 Object[] newElements = Arrays.copyOf(es, len + added);
707 System.arraycopy(cs, 0, newElements, len, added);
708 setArray(newElements);
709 }
710 return added;
711 }
712 }
713
714 /**
715 * Removes all of the elements from this list.
716 * The list will be empty after this call returns.
717 */
718 public void clear() {
719 synchronized (lock) {
720 setArray(new Object[0]);
721 }
722 }
723
724 /**
725 * Appends all of the elements in the specified collection to the end
726 * of this list, in the order that they are returned by the specified
727 * collection's iterator.
728 *
729 * @param c collection containing elements to be added to this list
730 * @return {@code true} if this list changed as a result of the call
731 * @throws NullPointerException if the specified collection is null
732 * @see #add(Object)
733 */
734 public boolean addAll(Collection<? extends E> c) {
735 Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
736 ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
737 if (cs.length == 0)
738 return false;
739 synchronized (lock) {
740 Object[] es = getArray();
741 int len = es.length;
742 Object[] newElements;
743 if (len == 0 && cs.getClass() == Object[].class)
744 newElements = cs;
745 else {
746 newElements = Arrays.copyOf(es, len + cs.length);
747 System.arraycopy(cs, 0, newElements, len, cs.length);
748 }
749 setArray(newElements);
750 return true;
751 }
752 }
753
754 /**
755 * Inserts all of the elements in the specified collection into this
756 * list, starting at the specified position. Shifts the element
757 * currently at that position (if any) and any subsequent elements to
758 * the right (increases their indices). The new elements will appear
759 * in this list in the order that they are returned by the
760 * specified collection's iterator.
761 *
762 * @param index index at which to insert the first element
763 * from the specified collection
764 * @param c collection containing elements to be added to this list
765 * @return {@code true} if this list changed as a result of the call
766 * @throws IndexOutOfBoundsException {@inheritDoc}
767 * @throws NullPointerException if the specified collection is null
768 * @see #add(int,Object)
769 */
770 public boolean addAll(int index, Collection<? extends E> c) {
771 Object[] cs = c.toArray();
772 synchronized (lock) {
773 Object[] es = getArray();
774 int len = es.length;
775 if (index > len || index < 0)
776 throw new IndexOutOfBoundsException(outOfBounds(index, len));
777 if (cs.length == 0)
778 return false;
779 int numMoved = len - index;
780 Object[] newElements;
781 if (numMoved == 0)
782 newElements = Arrays.copyOf(es, len + cs.length);
783 else {
784 newElements = new Object[len + cs.length];
785 System.arraycopy(es, 0, newElements, 0, index);
786 System.arraycopy(es, index,
787 newElements, index + cs.length,
788 numMoved);
789 }
790 System.arraycopy(cs, 0, newElements, index, cs.length);
791 setArray(newElements);
792 return true;
793 }
794 }
795
796 /**
797 * @throws NullPointerException {@inheritDoc}
798 */
799 public void forEach(Consumer<? super E> action) {
800 Objects.requireNonNull(action);
801 for (Object x : getArray()) {
802 @SuppressWarnings("unchecked") E e = (E) x;
803 action.accept(e);
804 }
805 }
806
807 /**
808 * @throws NullPointerException {@inheritDoc}
809 */
810 public boolean removeIf(Predicate<? super E> filter) {
811 Objects.requireNonNull(filter);
812 return bulkRemove(filter);
813 }
814
815 // A tiny bit set implementation
816
817 private static long[] nBits(int n) {
818 return new long[((n - 1) >> 6) + 1];
819 }
820 private static void setBit(long[] bits, int i) {
821 bits[i >> 6] |= 1L << i;
822 }
823 private static boolean isClear(long[] bits, int i) {
824 return (bits[i >> 6] & (1L << i)) == 0;
825 }
826
827 private boolean bulkRemove(Predicate<? super E> filter) {
828 synchronized (lock) {
829 return bulkRemove(filter, 0, getArray().length);
830 }
831 }
832
833 boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
834 // assert Thread.holdsLock(lock);
835 final Object[] es = getArray();
836 // Optimize for initial run of survivors
837 for (; i < end && !filter.test(elementAt(es, i)); i++)
838 ;
839 if (i < end) {
840 final int beg = i;
841 final long[] deathRow = nBits(end - beg);
842 int deleted = 1;
843 deathRow[0] = 1L; // set bit 0
844 for (i = beg + 1; i < end; i++)
845 if (filter.test(elementAt(es, i))) {
846 setBit(deathRow, i - beg);
847 deleted++;
848 }
849 // Did filter reentrantly modify the list?
850 if (es != getArray())
851 throw new ConcurrentModificationException();
852 final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
853 int w = beg;
854 for (i = beg; i < end; i++)
855 if (isClear(deathRow, i - beg))
856 newElts[w++] = es[i];
857 System.arraycopy(es, i, newElts, w, es.length - i);
858 setArray(newElts);
859 return true;
860 } else {
861 if (es != getArray())
862 throw new ConcurrentModificationException();
863 return false;
864 }
865 }
866
867 public void replaceAll(UnaryOperator<E> operator) {
868 synchronized (lock) {
869 replaceAllRange(operator, 0, getArray().length);
870 }
871 }
872
873 void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
874 // assert Thread.holdsLock(lock);
875 Objects.requireNonNull(operator);
876 final Object[] es = getArray().clone();
877 for (; i < end; i++)
878 es[i] = operator.apply(elementAt(es, i));
879 setArray(es);
880 }
881
882 public void sort(Comparator<? super E> c) {
883 synchronized (lock) {
884 sortRange(c, 0, getArray().length);
885 }
886 }
887
888 @SuppressWarnings("unchecked")
889 void sortRange(Comparator<? super E> c, int i, int end) {
890 // assert Thread.holdsLock(lock);
891 final Object[] es = getArray().clone();
892 Arrays.sort(es, i, end, (Comparator<Object>)c);
893 setArray(es);
894 }
895
896 /**
897 * Saves this list to a stream (that is, serializes it).
898 *
899 * @param s the stream
900 * @throws java.io.IOException if an I/O error occurs
901 * @serialData The length of the array backing the list is emitted
902 * (int), followed by all of its elements (each an Object)
903 * in the proper order.
904 */
905 private void writeObject(java.io.ObjectOutputStream s)
906 throws java.io.IOException {
907
908 s.defaultWriteObject();
909
910 Object[] es = getArray();
911 // Write out array length
912 s.writeInt(es.length);
913
914 // Write out all elements in the proper order.
915 for (Object element : es)
916 s.writeObject(element);
917 }
918
919 /**
920 * Reconstitutes this list from a stream (that is, deserializes it).
921 * @param s the stream
922 * @throws ClassNotFoundException if the class of a serialized object
923 * could not be found
924 * @throws java.io.IOException if an I/O error occurs
925 */
926 private void readObject(java.io.ObjectInputStream s)
927 throws java.io.IOException, ClassNotFoundException {
928
929 s.defaultReadObject();
930
931 // bind to new lock
932 resetLock();
933
934 // Read in array length and allocate array
935 int len = s.readInt();
936 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len);
937 Object[] es = new Object[len];
938
939 // Read in all elements in the proper order.
940 for (int i = 0; i < len; i++)
941 es[i] = s.readObject();
942 setArray(es);
943 }
944
945 /**
946 * Returns a string representation of this list. The string
947 * representation consists of the string representations of the list's
948 * elements in the order they are returned by its iterator, enclosed in
949 * square brackets ({@code "[]"}). Adjacent elements are separated by
950 * the characters {@code ", "} (comma and space). Elements are
951 * converted to strings as by {@link String#valueOf(Object)}.
952 *
953 * @return a string representation of this list
954 */
955 public String toString() {
956 return Arrays.toString(getArray());
957 }
958
959 /**
960 * Compares the specified object with this list for equality.
961 * Returns {@code true} if the specified object is the same object
962 * as this object, or if it is also a {@link List} and the sequence
963 * of elements returned by an {@linkplain List#iterator() iterator}
964 * over the specified list is the same as the sequence returned by
965 * an iterator over this list. The two sequences are considered to
966 * be the same if they have the same length and corresponding
967 * elements at the same position in the sequence are <em>equal</em>.
968 * Two elements {@code e1} and {@code e2} are considered
969 * <em>equal</em> if {@code Objects.equals(e1, e2)}.
970 *
971 * @param o the object to be compared for equality with this list
972 * @return {@code true} if the specified object is equal to this list
973 */
974 public boolean equals(Object o) {
975 if (o == this)
976 return true;
977 if (!(o instanceof List))
978 return false;
979
980 List<?> list = (List<?>)o;
981 Iterator<?> it = list.iterator();
982 for (Object element : getArray())
983 if (!it.hasNext() || !Objects.equals(element, it.next()))
984 return false;
985 return !it.hasNext();
986 }
987
988 private static int hashCodeOfRange(Object[] es, int from, int to) {
989 int hashCode = 1;
990 for (int i = from; i < to; i++) {
991 Object x = es[i];
992 hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
993 }
994 return hashCode;
995 }
996
997 /**
998 * Returns the hash code value for this list.
999 *
1000 * <p>This implementation uses the definition in {@link List#hashCode}.
1001 *
1002 * @return the hash code value for this list
1003 */
1004 public int hashCode() {
1005 Object[] es = getArray();
1006 return hashCodeOfRange(es, 0, es.length);
1007 }
1008
1009 /**
1010 * Returns an iterator over the elements in this list in proper sequence.
1011 *
1012 * <p>The returned iterator provides a snapshot of the state of the list
1013 * when the iterator was constructed. No synchronization is needed while
1014 * traversing the iterator. The iterator does <em>NOT</em> support the
1015 * {@code remove} method.
1016 *
1017 * @return an iterator over the elements in this list in proper sequence
1018 */
1019 public Iterator<E> iterator() {
1020 return new COWIterator<E>(getArray(), 0);
1021 }
1022
1023 /**
1024 * {@inheritDoc}
1025 *
1026 * <p>The returned iterator provides a snapshot of the state of the list
1027 * when the iterator was constructed. No synchronization is needed while
1028 * traversing the iterator. The iterator does <em>NOT</em> support the
1029 * {@code remove}, {@code set} or {@code add} methods.
1030 */
1031 public ListIterator<E> listIterator() {
1032 return new COWIterator<E>(getArray(), 0);
1033 }
1034
1035 /**
1036 * {@inheritDoc}
1037 *
1038 * <p>The returned iterator provides a snapshot of the state of the list
1039 * when the iterator was constructed. No synchronization is needed while
1040 * traversing the iterator. The iterator does <em>NOT</em> support the
1041 * {@code remove}, {@code set} or {@code add} methods.
1042 *
1043 * @throws IndexOutOfBoundsException {@inheritDoc}
1044 */
1045 public ListIterator<E> listIterator(int index) {
1046 Object[] es = getArray();
1047 int len = es.length;
1048 if (index < 0 || index > len)
1049 throw new IndexOutOfBoundsException(outOfBounds(index, len));
1050
1051 return new COWIterator<E>(es, index);
1052 }
1053
1054 /**
1055 * Returns a {@link Spliterator} over the elements in this list.
1056 *
1057 * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE},
1058 * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and
1059 * {@link Spliterator#SUBSIZED}.
1060 *
1061 * <p>The spliterator provides a snapshot of the state of the list
1062 * when the spliterator was constructed. No synchronization is needed while
1063 * operating on the spliterator.
1064 *
1065 * @return a {@code Spliterator} over the elements in this list
1066 * @since 1.8
1067 */
1068 public Spliterator<E> spliterator() {
1069 return Spliterators.spliterator
1070 (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
1071 }
1072
1073 static final class COWIterator<E> implements ListIterator<E> {
1074 /** Snapshot of the array */
1075 private final Object[] snapshot;
1076 /** Index of element to be returned by subsequent call to next. */
1077 private int cursor;
1078
1079 COWIterator(Object[] es, int initialCursor) {
1080 cursor = initialCursor;
1081 snapshot = es;
1082 }
1083
1084 public boolean hasNext() {
1085 return cursor < snapshot.length;
1086 }
1087
1088 public boolean hasPrevious() {
1089 return cursor > 0;
1090 }
1091
1092 @SuppressWarnings("unchecked")
1093 public E next() {
1094 if (! hasNext())
1095 throw new NoSuchElementException();
1096 return (E) snapshot[cursor++];
1097 }
1098
1099 @SuppressWarnings("unchecked")
1100 public E previous() {
1101 if (! hasPrevious())
1102 throw new NoSuchElementException();
1103 return (E) snapshot[--cursor];
1104 }
1105
1106 public int nextIndex() {
1107 return cursor;
1108 }
1109
1110 public int previousIndex() {
1111 return cursor - 1;
1112 }
1113
1114 /**
1115 * Not supported. Always throws UnsupportedOperationException.
1116 * @throws UnsupportedOperationException always; {@code remove}
1117 * is not supported by this iterator.
1118 */
1119 public void remove() {
1120 throw new UnsupportedOperationException();
1121 }
1122
1123 /**
1124 * Not supported. Always throws UnsupportedOperationException.
1125 * @throws UnsupportedOperationException always; {@code set}
1126 * is not supported by this iterator.
1127 */
1128 public void set(E e) {
1129 throw new UnsupportedOperationException();
1130 }
1131
1132 /**
1133 * Not supported. Always throws UnsupportedOperationException.
1134 * @throws UnsupportedOperationException always; {@code add}
1135 * is not supported by this iterator.
1136 */
1137 public void add(E e) {
1138 throw new UnsupportedOperationException();
1139 }
1140
1141 @Override
1142 public void forEachRemaining(Consumer<? super E> action) {
1143 Objects.requireNonNull(action);
1144 final int size = snapshot.length;
1145 int i = cursor;
1146 cursor = size;
1147 for (; i < size; i++)
1148 action.accept(elementAt(snapshot, i));
1149 }
1150 }
1151
1152 /**
1153 * Returns a view of the portion of this list between
1154 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
1155 * The returned list is backed by this list, so changes in the
1156 * returned list are reflected in this list.
1157 *
1158 * <p>The semantics of the list returned by this method become
1159 * undefined if the backing list (i.e., this list) is modified in
1160 * any way other than via the returned list.
1161 *
1162 * @param fromIndex low endpoint (inclusive) of the subList
1163 * @param toIndex high endpoint (exclusive) of the subList
1164 * @return a view of the specified range within this list
1165 * @throws IndexOutOfBoundsException {@inheritDoc}
1166 */
1167 public List<E> subList(int fromIndex, int toIndex) {
1168 synchronized (lock) {
1169 Object[] es = getArray();
1170 int len = es.length;
1171 int size = toIndex - fromIndex;
1172 if (fromIndex < 0 || toIndex > len || size < 0)
1173 throw new IndexOutOfBoundsException();
1174 return new COWSubList(es, fromIndex, size);
1175 }
1176 }
1177
1178 /**
1179 * Sublist for CopyOnWriteArrayList.
1180 */
1181 private class COWSubList implements List<E>, RandomAccess {
1182 private final int offset;
1183 private int size;
1184 private Object[] expectedArray;
1185
1186 COWSubList(Object[] es, int offset, int size) {
1187 // assert Thread.holdsLock(lock);
1188 expectedArray = es;
1189 this.offset = offset;
1190 this.size = size;
1191 }
1192
1193 private void checkForComodification() {
1194 // assert Thread.holdsLock(lock);
1195 if (getArray() != expectedArray)
1196 throw new ConcurrentModificationException();
1197 }
1198
1199 private Object[] getArrayChecked() {
1200 // assert Thread.holdsLock(lock);
1201 Object[] a = getArray();
1202 if (a != expectedArray)
1203 throw new ConcurrentModificationException();
1204 return a;
1205 }
1206
1207 private void rangeCheck(int index) {
1208 // assert Thread.holdsLock(lock);
1209 if (index < 0 || index >= size)
1210 throw new IndexOutOfBoundsException(outOfBounds(index, size));
1211 }
1212
1213 private void rangeCheckForAdd(int index) {
1214 // assert Thread.holdsLock(lock);
1215 if (index < 0 || index > size)
1216 throw new IndexOutOfBoundsException(outOfBounds(index, size));
1217 }
1218
1219 public Object[] toArray() {
1220 final Object[] es;
1221 final int offset;
1222 final int size;
1223 synchronized (lock) {
1224 es = getArrayChecked();
1225 offset = this.offset;
1226 size = this.size;
1227 }
1228 return Arrays.copyOfRange(es, offset, offset + size);
1229 }
1230
1231 @SuppressWarnings("unchecked")
1232 public <T> T[] toArray(T[] a) {
1233 final Object[] es;
1234 final int offset;
1235 final int size;
1236 synchronized (lock) {
1237 es = getArrayChecked();
1238 offset = this.offset;
1239 size = this.size;
1240 }
1241 if (a.length < size)
1242 return (T[]) Arrays.copyOfRange(
1243 es, offset, offset + size, a.getClass());
1244 else {
1245 System.arraycopy(es, offset, a, 0, size);
1246 if (a.length > size)
1247 a[size] = null;
1248 return a;
1249 }
1250 }
1251
1252 public int indexOf(Object o) {
1253 final Object[] es;
1254 final int offset;
1255 final int size;
1256 synchronized (lock) {
1257 es = getArrayChecked();
1258 offset = this.offset;
1259 size = this.size;
1260 }
1261 int i = indexOfRange(o, es, offset, offset + size);
1262 return (i == -1) ? -1 : i - offset;
1263 }
1264
1265 public int lastIndexOf(Object o) {
1266 final Object[] es;
1267 final int offset;
1268 final int size;
1269 synchronized (lock) {
1270 es = getArrayChecked();
1271 offset = this.offset;
1272 size = this.size;
1273 }
1274 int i = lastIndexOfRange(o, es, offset, offset + size);
1275 return (i == -1) ? -1 : i - offset;
1276 }
1277
1278 public boolean contains(Object o) {
1279 return indexOf(o) >= 0;
1280 }
1281
1282 public boolean containsAll(Collection<?> c) {
1283 final Object[] es;
1284 final int offset;
1285 final int size;
1286 synchronized (lock) {
1287 es = getArrayChecked();
1288 offset = this.offset;
1289 size = this.size;
1290 }
1291 for (Object o : c)
1292 if (indexOfRange(o, es, offset, offset + size) < 0)
1293 return false;
1294 return true;
1295 }
1296
1297 public boolean isEmpty() {
1298 return size() == 0;
1299 }
1300
1301 public String toString() {
1302 return Arrays.toString(toArray());
1303 }
1304
1305 public int hashCode() {
1306 final Object[] es;
1307 final int offset;
1308 final int size;
1309 synchronized (lock) {
1310 es = getArrayChecked();
1311 offset = this.offset;
1312 size = this.size;
1313 }
1314 return hashCodeOfRange(es, offset, offset + size);
1315 }
1316
1317 public boolean equals(Object o) {
1318 if (o == this)
1319 return true;
1320 if (!(o instanceof List))
1321 return false;
1322 Iterator<?> it = ((List<?>)o).iterator();
1323
1324 final Object[] es;
1325 final int offset;
1326 final int size;
1327 synchronized (lock) {
1328 es = getArrayChecked();
1329 offset = this.offset;
1330 size = this.size;
1331 }
1332
1333 for (int i = offset, end = offset + size; i < end; i++)
1334 if (!it.hasNext() || !Objects.equals(es[i], it.next()))
1335 return false;
1336 return !it.hasNext();
1337 }
1338
1339 public E set(int index, E element) {
1340 synchronized (lock) {
1341 rangeCheck(index);
1342 checkForComodification();
1343 E x = CopyOnWriteArrayList.this.set(offset + index, element);
1344 expectedArray = getArray();
1345 return x;
1346 }
1347 }
1348
1349 public E get(int index) {
1350 synchronized (lock) {
1351 rangeCheck(index);
1352 checkForComodification();
1353 return CopyOnWriteArrayList.this.get(offset + index);
1354 }
1355 }
1356
1357 public int size() {
1358 synchronized (lock) {
1359 checkForComodification();
1360 return size;
1361 }
1362 }
1363
1364 public boolean add(E element) {
1365 synchronized (lock) {
1366 checkForComodification();
1367 CopyOnWriteArrayList.this.add(offset + size, element);
1368 expectedArray = getArray();
1369 size++;
1370 }
1371 return true;
1372 }
1373
1374 public void add(int index, E element) {
1375 synchronized (lock) {
1376 checkForComodification();
1377 rangeCheckForAdd(index);
1378 CopyOnWriteArrayList.this.add(offset + index, element);
1379 expectedArray = getArray();
1380 size++;
1381 }
1382 }
1383
1384 public boolean addAll(Collection<? extends E> c) {
1385 synchronized (lock) {
1386 final Object[] oldArray = getArrayChecked();
1387 boolean modified =
1388 CopyOnWriteArrayList.this.addAll(offset + size, c);
1389 size += (expectedArray = getArray()).length - oldArray.length;
1390 return modified;
1391 }
1392 }
1393
1394 public boolean addAll(int index, Collection<? extends E> c) {
1395 synchronized (lock) {
1396 rangeCheckForAdd(index);
1397 final Object[] oldArray = getArrayChecked();
1398 boolean modified =
1399 CopyOnWriteArrayList.this.addAll(offset + index, c);
1400 size += (expectedArray = getArray()).length - oldArray.length;
1401 return modified;
1402 }
1403 }
1404
1405 public void clear() {
1406 synchronized (lock) {
1407 checkForComodification();
1408 removeRange(offset, offset + size);
1409 expectedArray = getArray();
1410 size = 0;
1411 }
1412 }
1413
1414 public E remove(int index) {
1415 synchronized (lock) {
1416 rangeCheck(index);
1417 checkForComodification();
1418 E result = CopyOnWriteArrayList.this.remove(offset + index);
1419 expectedArray = getArray();
1420 size--;
1421 return result;
1422 }
1423 }
1424
1425 public boolean remove(Object o) {
1426 synchronized (lock) {
1427 checkForComodification();
1428 int index = indexOf(o);
1429 if (index == -1)
1430 return false;
1431 remove(index);
1432 return true;
1433 }
1434 }
1435
1436 public Iterator<E> iterator() {
1437 return listIterator(0);
1438 }
1439
1440 public ListIterator<E> listIterator() {
1441 return listIterator(0);
1442 }
1443
1444 public ListIterator<E> listIterator(int index) {
1445 synchronized (lock) {
1446 checkForComodification();
1447 rangeCheckForAdd(index);
1448 return new COWSubListIterator<E>(
1449 CopyOnWriteArrayList.this, index, offset, size);
1450 }
1451 }
1452
1453 public List<E> subList(int fromIndex, int toIndex) {
1454 synchronized (lock) {
1455 checkForComodification();
1456 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
1457 throw new IndexOutOfBoundsException();
1458 return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex);
1459 }
1460 }
1461
1462 public void forEach(Consumer<? super E> action) {
1463 Objects.requireNonNull(action);
1464 int i, end; final Object[] es;
1465 synchronized (lock) {
1466 es = getArrayChecked();
1467 i = offset;
1468 end = i + size;
1469 }
1470 for (; i < end; i++)
1471 action.accept(elementAt(es, i));
1472 }
1473
1474 public void replaceAll(UnaryOperator<E> operator) {
1475 synchronized (lock) {
1476 checkForComodification();
1477 replaceAllRange(operator, offset, offset + size);
1478 expectedArray = getArray();
1479 }
1480 }
1481
1482 public void sort(Comparator<? super E> c) {
1483 synchronized (lock) {
1484 checkForComodification();
1485 sortRange(c, offset, offset + size);
1486 expectedArray = getArray();
1487 }
1488 }
1489
1490 public boolean removeAll(Collection<?> c) {
1491 Objects.requireNonNull(c);
1492 return bulkRemove(e -> c.contains(e));
1493 }
1494
1495 public boolean retainAll(Collection<?> c) {
1496 Objects.requireNonNull(c);
1497 return bulkRemove(e -> !c.contains(e));
1498 }
1499
1500 public boolean removeIf(Predicate<? super E> filter) {
1501 Objects.requireNonNull(filter);
1502 return bulkRemove(filter);
1503 }
1504
1505 private boolean bulkRemove(Predicate<? super E> filter) {
1506 synchronized (lock) {
1507 final Object[] oldArray = getArrayChecked();
1508 boolean modified = CopyOnWriteArrayList.this.bulkRemove(
1509 filter, offset, offset + size);
1510 size += (expectedArray = getArray()).length - oldArray.length;
1511 return modified;
1512 }
1513 }
1514
1515 public Spliterator<E> spliterator() {
1516 synchronized (lock) {
1517 return Spliterators.spliterator(
1518 getArrayChecked(), offset, offset + size,
1519 Spliterator.IMMUTABLE | Spliterator.ORDERED);
1520 }
1521 }
1522
1523 }
1524
1525 private static class COWSubListIterator<E> implements ListIterator<E> {
1526 private final ListIterator<E> it;
1527 private final int offset;
1528 private final int size;
1529
1530 COWSubListIterator(List<E> l, int index, int offset, int size) {
1531 this.offset = offset;
1532 this.size = size;
1533 it = l.listIterator(index + offset);
1534 }
1535
1536 public boolean hasNext() {
1537 return nextIndex() < size;
1538 }
1539
1540 public E next() {
1541 if (hasNext())
1542 return it.next();
1543 else
1544 throw new NoSuchElementException();
1545 }
1546
1547 public boolean hasPrevious() {
1548 return previousIndex() >= 0;
1549 }
1550
1551 public E previous() {
1552 if (hasPrevious())
1553 return it.previous();
1554 else
1555 throw new NoSuchElementException();
1556 }
1557
1558 public int nextIndex() {
1559 return it.nextIndex() - offset;
1560 }
1561
1562 public int previousIndex() {
1563 return it.previousIndex() - offset;
1564 }
1565
1566 public void remove() {
1567 throw new UnsupportedOperationException();
1568 }
1569
1570 public void set(E e) {
1571 throw new UnsupportedOperationException();
1572 }
1573
1574 public void add(E e) {
1575 throw new UnsupportedOperationException();
1576 }
1577
1578 @Override
1579 @SuppressWarnings("unchecked")
1580 public void forEachRemaining(Consumer<? super E> action) {
1581 Objects.requireNonNull(action);
1582 while (hasNext()) {
1583 action.accept(it.next());
1584 }
1585 }
1586 }
1587
1588 /** Initializes the lock; for use when deserializing or cloning. */
1589 private void resetLock() {
1590 Field lockField = java.security.AccessController.doPrivileged(
1591 (java.security.PrivilegedAction<Field>) () -> {
1592 try {
1593 Field f = CopyOnWriteArrayList.class
1594 .getDeclaredField("lock");
1595 f.setAccessible(true);
1596 return f;
1597 } catch (ReflectiveOperationException e) {
1598 throw new Error(e);
1599 }});
1600 try {
1601 lockField.set(this, new Object());
1602 } catch (IllegalAccessException e) {
1603 throw new Error(e);
1604 }
1605 }
1606 }