ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/extra/ReadMostlyVector.java

Comparing jsr166/src/jsr166e/extra/ReadMostlyVector.java (file contents):
Revision 1.1 by dl, Fri Jul 15 23:56:18 2011 UTC vs.
Revision 1.24 by jsr166, Mon Jan 2 23:13:10 2012 UTC

#	Line 9 | Line 9 | import jsr166e.*;
9		import java.util.*;
10
11		/**
12	<	* A class with the same API and array-based characteristics as {@link
13	<	* java.util.Vector} but with reduced contention and improved
12	>	* A class with the same methods and array-based characteristics as
13	>	* {@link java.util.Vector} but with reduced contention and improved
14		* throughput when invocations of read-only methods by multiple
15	<	* threads are most common.  Instances of this class may have
16	<	* relatively poorer performance in other contexts.
15	>	* threads are most common.
16		*
17		* <p> The iterators returned by this class's {@link #iterator()
18		* iterator} and {@link #listIterator(int) listIterator} methods are
19		* best-effort in the presence of concurrent modifications, and do
20		* <em>NOT</em> throw {@link ConcurrentModificationException}.  An
21		* iterator's {@code next()} method returns consecutive elements as
22	<	* they appear in the underlying array upon each access.
22	>	* they appear in the underlying array upon each access. Alternatively,
23	>	* method {@link #snapshotIterator} may be used for deterministic
24	>	* traversals, at the expense of making a copy, and unavailability of
25	>	* method {@code Iterator.remove}.
26		*
27		* <p>Otherwise, this class supports all methods, under the same
28		* documented specifications, as {@code Vector}.  Consult {@link
#	Line 30 | Line 32 | import java.util.*;
32		*
33		* @author Doug Lea
34		*/
35	<	public class ReadMostlyVector<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
35	>	public class ReadMostlyVector<E>
36	>	implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
37		private static final long serialVersionUID = 8673264195747942595L;
38
39		/*
40		* This class exists mainly as a vehicle to exercise various
41	<	* constructions using SequenceLocks, which are not yet explained
42	<	* well here.
41	>	* constructions using SequenceLocks. Read-only methods
42	>	* take one of a few forms:
43	>	*
44	>	* Short methods,including get(index), continually retry obtaining
45	>	* a snapshot of array, count, and element, using sequence number
46	>	* to validate.
47	>	*
48	>	* Methods that are potentially O(n) (or worse) try once in
49	>	* read-only mode, and then lock. When in read-only mode, they
50	>	* validate only at the end of an array scan unless the element is
51	>	* actually used (for example, as an argument of method equals).
52	>	*
53	>	* We rely on some invariants that are always true, even for field
54	>	* reads in read-only mode that have not yet been validated:
55	>	* - array != null
56	>	* - count >= 0
57		*/
58
59		/**
#	Line 45 | Line 62 | public class ReadMostlyVector<E> impleme
62		*/
63		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
64
65	<	// fields are non-private to simpify nested class access
66	<	Object[] array;
65	>	// fields are non-private to simplify nested class access
66	>	volatile Object[] array;
67		final SequenceLock lock;
68	<	int count;
68	>	volatile int count;
69		final int capacityIncrement;
70
71		/**
#	Line 118 | Line 135 | public class ReadMostlyVector<E> impleme
135		}
136
137		// For explanation, see CopyOnWriteArrayList
138	<	final void grow(int minCapacity) {
138	>	final Object[] grow(int minCapacity) {
139		int oldCapacity = array.length;
140		int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
141		capacityIncrement : oldCapacity);
#	Line 126 | Line 143 | public class ReadMostlyVector<E> impleme
143		newCapacity = minCapacity;
144		if (newCapacity - MAX_ARRAY_SIZE > 0)
145		newCapacity = hugeCapacity(minCapacity);
146	<	array = Arrays.copyOf(array, newCapacity);
146	>	return array = Arrays.copyOf(array, newCapacity);
147		}
148
149		static int hugeCapacity(int minCapacity) {
#	Line 143 | Line 160 | public class ReadMostlyVector<E> impleme
160		* as well as sublist and iterator classes.
161		*/
162
163	<	static int internalIndexOf(Object o, Object[] items,
164	<	int index, int fence) {
163	>	/**
164	>	* Version of indexOf that returns -1 if either not present or invalid.
165	>	*
166	>	* @throws ArrayIndexOutOfBoundsException if index is negative
167	>	*/
168	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
169	>	long seq) {
170		for (int i = index; i < fence; ++i) {
171	<	Object x = items[i];
172	<	if (o == null? x == null : (x != null && o.equals(x)))
171	>	Object e = items[i];
172	>	if (lock.getSequence() != seq)
173	>	break;
174	>	if ((x == null) ? e == null : x.equals(e))
175	>	return i;
176	>	}
177	>	return -1;
178	>	}
179	>
180	>	/**
181	>	* @throws ArrayIndexOutOfBoundsException if index is negative
182	>	*/
183	>	final int rawIndexOf(Object x, int index, int fence) {
184	>	Object[] items = array;
185	>	for (int i = index; i < fence; ++i) {
186	>	Object e = items[i];
187	>	if ((x == null) ? e == null : x.equals(e))
188	>	return i;
189	>	}
190	>	return -1;
191	>	}
192	>
193	>	final int validatedLastIndexOf(Object x, Object[] items,
194	>	int index, int origin, long seq) {
195	>	for (int i = index; i >= origin; --i) {
196	>	Object e = items[i];
197	>	if (lock.getSequence() != seq)
198	>	break;
199	>	if ((x == null) ? e == null : x.equals(e))
200		return i;
201		}
202		return -1;
203		}
204
205	<	static int internalLastIndexOf(Object o, Object[] items,
206	<	int index, int origin) {
205	>	final int rawLastIndexOf(Object x, int index, int origin) {
206	>	Object[] items = array;
207		for (int i = index; i >= origin; --i) {
208	<	Object x = items[i];
209	<	if (o == null? x == null : (x != null && o.equals(x)))
208	>	Object e = items[i];
209	>	if ((x == null) ? e == null : x.equals(e))
210		return i;
211		}
212		return -1;
213		}
214
215	<	final void internalAdd(E e) {
216	<	int c = count;
217	<	if (c >= array.length)
218	<	grow(c + 1);
219	<	array[c] = e;
220	<	count = c + 1;
215	>	final void rawAdd(E e) {
216	>	int n = count;
217	>	Object[] items = array;
218	>	if (n >= items.length)
219	>	items = grow(n + 1);
220	>	items[n] = e;
221	>	count = n + 1;
222		}
223
224	<	final void internalAddAt(int index, E e) {
225	<	int c = count;
226	<	if (index > c)
224	>	final void rawAddAt(int index, E e) {
225	>	int n = count;
226	>	Object[] items = array;
227	>	if (index > n)
228		throw new ArrayIndexOutOfBoundsException(index);
229	<	if (c >= array.length)
230	<	grow(c + 1);
231	<	System.arraycopy(array, index, array, index + 1, c - index);
232	<	array[index] = e;
233	<	count = c + 1;
229	>	if (n >= items.length)
230	>	items = grow(n + 1);
231	>	if (index < n)
232	>	System.arraycopy(items, index, items, index + 1, n - index);
233	>	items[index] = e;
234	>	count = n + 1;
235		}
236
237	<	final boolean internalAddAllAt(int index, Object[] elements) {
238	<	int c = count;
239	<	if (index < 0 || index > c)
237	>	final boolean rawAddAllAt(int index, Object[] elements) {
238	>	int n = count;
239	>	Object[] items = array;
240	>	if (index < 0 || index > n)
241		throw new ArrayIndexOutOfBoundsException(index);
242		int len = elements.length;
243		if (len == 0)
244		return false;
245	<	int newCount = c + len;
246	<	if (newCount >= array.length)
247	<	grow(newCount);
248	<	int mv = count - index;
245	>	int newCount = n + len;
246	>	if (newCount >= items.length)
247	>	items = grow(newCount);
248	>	int mv = n - index;
249		if (mv > 0)
250	<	System.arraycopy(array, index, array, index + len, mv);
251	<	System.arraycopy(elements, 0, array, index, len);
250	>	System.arraycopy(items, index, items, index + len, mv);
251	>	System.arraycopy(elements, 0, items, index, len);
252		count = newCount;
253		return true;
254		}
255
256	<	final boolean internalRemoveAt(int index) {
257	<	int c = count - 1;
258	<	if (index < 0 || index > c)
256	>	final boolean rawRemoveAt(int index) {
257	>	int n = count - 1;
258	>	Object[] items = array;
259	>	if (index < 0 || index > n)
260		return false;
261	<	int mv = c - index;
261	>	int mv = n - index;
262		if (mv > 0)
263	<	System.arraycopy(array, index + 1, array, index, mv);
264	<	array[c] = null;
265	<	count = c;
263	>	System.arraycopy(items, index + 1, items, index, mv);
264	>	items[n] = null;
265	>	count = n;
266		return true;
267		}
268
269		/**
270		* Internal version of removeAll for lists and sublists. In this
271	<	* and other similar methods below, the span argument is, if
272	<	* non-negative, the purported size of a list/sublist, or is left
273	<	* negative if the size should be determined via count field under
274	<	* lock.
271	>	* and other similar methods below, the bound argument is, if
272	>	* non-negative, the purported upper bound of a list/sublist, or
273	>	* is left negative if the bound should be determined via count
274	>	* field under lock.
275		*/
276	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
277	<	SequenceLock lock = this.lock;
276	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
277	>	final SequenceLock lock = this.lock;
278		boolean removed = false;
279		lock.lock();
280		try {
281	<	int fence = count;
282	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
281	>	int n = count;
282	>	int fence = bound < 0 || bound > n ? n : bound;
283		if (origin >= 0 && origin < fence) {
284		for (Object x : c) {
285	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
285	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
286		removed = true;
287		}
288		}
#	Line 240 | Line 292 | public class ReadMostlyVector<E> impleme
292		return removed;
293		}
294
295	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
296	<	SequenceLock lock = this.lock;
295	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
296	>	final SequenceLock lock = this.lock;
297		boolean removed = false;
298		if (c != this) {
299		lock.lock();
300		try {
301	+	Object[] items = array;
302		int i = origin;
303	<	int fence = count;
304	<	if (span >= 0 && origin + span < fence)
305	<	fence = origin + span;
306	<	while (i < fence) {
254	<	if (c.contains(array[i]))
303	>	int n = count;
304	>	int fence = bound < 0 || bound > n ? n : bound;
305	>	while (i >= 0 && i < fence) {
306	>	if (c.contains(items[i]))
307		++i;
308		else {
309		--fence;
310	<	int mv = --count - i;
310	>	int mv = --n - i;
311		if (mv > 0)
312	<	System.arraycopy(array, i + 1, array, i, mv);
261	<	removed = true;
312	>	System.arraycopy(items, i + 1, items, i, mv);
313		}
314		}
315	+	if (count != n) {
316	+	count = n;
317	+	removed = true;
318	+	}
319		} finally {
320		lock.unlock();
321		}
#	Line 268 | Line 323 | public class ReadMostlyVector<E> impleme
323		return removed;
324		}
325
326	<	final void internalClear(int origin, int span) {
327	<	int c = count;
328	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
326	>	final void internalClear(int origin, int bound) {
327	>	int n = count;
328	>	int fence = bound < 0 || bound > n ? n : bound;
329		if (origin >= 0 && origin < fence) {
330	+	Object[] items = array;
331		int removed = fence - origin;
332	<	int newCount = c - removed;
333	<	int mv = c - (origin + removed);
332	>	int newCount = n - removed;
333	>	int mv = n - (origin + removed);
334		if (mv > 0)
335	<	System.arraycopy(array, origin + removed, array, origin, mv);
336	<	for (int i = c; i < newCount; ++i)
337	<	array[i] = null;
335	>	System.arraycopy(items, origin + removed, items, origin, mv);
336	>	for (int i = n; i < newCount; ++i)
337	>	items[i] = null;
338		count = newCount;
339		}
340		}
341
342	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
343	<	SequenceLock lock = this.lock;
342	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
343	>	final SequenceLock lock = this.lock;
344		boolean contained;
345		boolean locked = false;
346		try {
347		for (;;) {
348		long seq = lock.awaitAvailability();
349	+	int n = count;
350		Object[] items = array;
351		int len = items.length;
352	<	int c = count;
298	<	if (c > len)
352	>	if (n > len)
353		continue;
354	<	int fence = c;
355	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
354	>	int fence = bound < 0 || bound > n ? n : bound;
355	>	if (origin < 0)
356		contained = false;
357		else {
358		contained = true;
359	<	for (Object e : coll) {
360	<	if (internalIndexOf(e, items, origin, fence) < 0) {
359	>	for (Object e : c) {
360	>	int idx = (locked ?
361	>	rawIndexOf(e, origin, fence) :
362	>	validatedIndexOf(e, items, origin,
363	>	fence, seq));
364	>	if (idx < 0) {
365		contained = false;
366		break;
367		}
#	Line 323 | Line 379 | public class ReadMostlyVector<E> impleme
379		return contained;
380		}
381
382	<	final boolean internalEquals(List<?> list, int origin, int span) {
383	<	SequenceLock lock = this.lock;
328	<	boolean equal;
382	>	final boolean internalEquals(List<?> list, int origin, int bound) {
383	>	final SequenceLock lock = this.lock;
384		boolean locked = false;
385	+	boolean equal;
386		try {
387		for (;;) {
332	–	equal = true;
388		long seq = lock.awaitAvailability();
389		Object[] items = array;
390	<	int len = items.length;
391	<	int c = count;
337	<	if (c > len)
338	<	continue;
339	<	int fence = c;
340	<	if (span >= 0 && origin + span < fence)
341	<	fence = origin + span;
342	<	if (origin < 0 || fence > c)
390	>	int n = count;
391	>	if (n > items.length || origin < 0)
392		equal = false;
393		else {
394	+	equal = true;
395	+	int fence = bound < 0 || bound > n ? n : bound;
396		Iterator<?> it = list.iterator();
397		for (int i = origin; i < fence; ++i) {
398	<	if (!it.hasNext()) {
399	<	equal = false;
400	<	break;
401	<	}
402	<	Object x = it.next();
403	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
398	>	Object x = items[i];
399	>	Object y;
400	>	if ((!locked && lock.getSequence() != seq) ||
401	>	!it.hasNext() ||
402	>	(y = it.next()) == null ?
403	>	x != null : !y.equals(x)) {
404		equal = false;
405		break;
406		}
#	Line 370 | Line 420 | public class ReadMostlyVector<E> impleme
420		return equal;
421		}
422
423	<	final int internalHashCode(int origin, int span) {
424	<	SequenceLock lock = this.lock;
423	>	final int internalHashCode(int origin, int bound) {
424	>	final SequenceLock lock = this.lock;
425		int hash;
426		boolean locked = false;
427		try {
#	Line 379 | Line 429 | public class ReadMostlyVector<E> impleme
429		hash = 1;
430		long seq = lock.awaitAvailability();
431		Object[] items = array;
432	+	int n = count;
433		int len = items.length;
434	<	int c = count;
384	<	if (c > len)
434	>	if (n > len)
435		continue;
436	<	int fence = c;
437	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
436	>	int fence = bound < 0 || bound > n ? n : bound;
437	>	if (origin >= 0) {
438		for (int i = origin; i < fence; ++i) {
439		Object e = items[i];
440		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 452 | public class ReadMostlyVector<E> impleme
452		return hash;
453		}
454
455	<	final String internalToString(int origin, int span) {
456	<	SequenceLock lock = this.lock;
455	>	final String internalToString(int origin, int bound) {
456	>	final SequenceLock lock = this.lock;
457		String ret;
458		boolean locked = false;
459		try {
460	<	for (;;) {
460	>	outer:for (;;) {
461		long seq = lock.awaitAvailability();
462		Object[] items = array;
463	+	int n = count;
464		int len = items.length;
465	<	int c = count;
417	<	if (c > len)
465	>	if (n > len)
466		continue;
467	<	int fence = c;
468	<	if (span >= 0 && origin + span < fence)
469	<	fence = origin + span;
470	<	if (origin >= 0 && fence <= c) {
471	<	if (origin == fence)
472	<	ret = "[]";
473	<	else {
474	<	StringBuilder sb = new StringBuilder();
475	<	sb.append('[');
476	<	for (int i = origin;;) {
477	<	Object e = items[i];
478	<	sb.append(e == this ? "(this Collection)" : e);
479	<	if (++i < fence)
480	<	sb.append(',').append(' ');
481	<	else {
482	<	ret = sb.append(']').toString();
483	<	break;
484	<	}
467	>	int fence = bound < 0 || bound > n ? n : bound;
468	>	if (origin < 0 || origin == fence)
469	>	ret = "[]";
470	>	else {
471	>	StringBuilder sb = new StringBuilder();
472	>	sb.append('[');
473	>	for (int i = origin;;) {
474	>	Object e = items[i];
475	>	if (e == this)
476	>	sb.append("(this Collection)");
477	>	else if (!locked && lock.getSequence() != seq)
478	>	continue outer;
479	>	else
480	>	sb.append(e.toString());
481	>	if (++i < fence)
482	>	sb.append(',').append(' ');
483	>	else {
484	>	ret = sb.append(']').toString();
485	>	break;
486		}
487		}
439	–	if (lock.getSequence() == seq)
440	–	break;
488		}
489	+	if (lock.getSequence() == seq)
490	+	break;
491		lock.lock();
492		locked = true;
493		}
#	Line 449 | Line 498 | public class ReadMostlyVector<E> impleme
498		return ret;
499		}
500
501	<	final Object[] internalToArray(int origin, int span) {
501	>	final Object[] internalToArray(int origin, int bound) {
502		Object[] result;
503	<	SequenceLock lock = this.lock;
503	>	final SequenceLock lock = this.lock;
504		boolean locked = false;
505		try {
506		for (;;) {
507		result = null;
508		long seq = lock.awaitAvailability();
509		Object[] items = array;
510	+	int n = count;
511		int len = items.length;
512	<	int c = count;
513	<	int fence = c;
514	<	if (span >= 0 && origin + span < fence)
515	<	fence = origin + span;
466	<	if (c <= len && fence <= len) {
512	>	if (n > len)
513	>	continue;
514	>	int fence = bound < 0 || bound > n ? n : bound;
515	>	if (origin >= 0)
516		result = Arrays.copyOfRange(items, origin, fence,
517		Object[].class);
518	<	if (lock.getSequence() == seq)
519	<	break;
471	<	}
518	>	if (lock.getSequence() == seq)
519	>	break;
520		lock.lock();
521		locked = true;
522		}
#	Line 479 | Line 527 | public class ReadMostlyVector<E> impleme
527		return result;
528		}
529
530	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
530	>	@SuppressWarnings("unchecked")
531	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
532	>	int alen = a.length;
533		T[] result;
534	<	SequenceLock lock = this.lock;
534	>	final SequenceLock lock = this.lock;
535		boolean locked = false;
536		try {
537		for (;;) {
538		long seq = lock.awaitAvailability();
539		Object[] items = array;
540	+	int n = count;
541		int len = items.length;
542	<	int c = count;
543	<	int fence = c;
544	<	if (span >= 0 && origin + span < fence)
545	<	fence = origin + span;
546	<	if (c <= len && fence <= len) {
547	<	if (a.length < count)
548	<	result = (T[]) Arrays.copyOfRange(array, origin,
549	<	fence, a.getClass());
550	<	else {
551	<	int n = fence - origin;
552	<	System.arraycopy(array, 0, a, origin, fence - origin);
553	<	if (a.length > n)
503	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
542	>	if (n > len)
543	>	continue;
544	>	int fence = bound < 0 || bound > n ? n : bound;
545	>	int rlen = fence - origin;
546	>	if (rlen < 0)
547	>	rlen = 0;
548	>	if (origin < 0 || alen >= rlen) {
549	>	if (rlen > 0)
550	>	System.arraycopy(items, 0, a, origin, rlen);
551	>	if (alen > rlen)
552	>	a[rlen] = null;
553	>	result = a;
554		}
555	+	else
556	+	result = (T[]) Arrays.copyOfRange(items, origin,
557	+	fence, a.getClass());
558	+	if (lock.getSequence() == seq)
559	+	break;
560		lock.lock();
561		locked = true;
562		}
#	Line 519 | Line 570 | public class ReadMostlyVector<E> impleme
570		// public List methods
571
572		public boolean add(E e) {
573	<	SequenceLock lock = this.lock;
573	>	final SequenceLock lock = this.lock;
574		lock.lock();
575		try {
576	<	internalAdd(e);
576	>	rawAdd(e);
577		} finally {
578		lock.unlock();
579		}
#	Line 530 | Line 581 | public class ReadMostlyVector<E> impleme
581		}
582
583		public void add(int index, E element) {
584	<	SequenceLock lock = this.lock;
584	>	final SequenceLock lock = this.lock;
585		lock.lock();
586		try {
587	<	internalAddAt(index, element);
587	>	rawAddAt(index, element);
588		} finally {
589		lock.unlock();
590		}
#	Line 544 | Line 595 | public class ReadMostlyVector<E> impleme
595		int len = elements.length;
596		if (len == 0)
597		return false;
598	<	SequenceLock lock = this.lock;
598	>	final SequenceLock lock = this.lock;
599		lock.lock();
600		try {
601	<	int newCount = count + len;
602	<	if (newCount >= array.length)
603	<	grow(newCount);
604	<	System.arraycopy(elements, 0, array, count, len);
601	>	Object[] items = array;
602	>	int n = count;
603	>	int newCount = n + len;
604	>	if (newCount >= items.length)
605	>	items = grow(newCount);
606	>	System.arraycopy(elements, 0, items, n, len);
607		count = newCount;
608		} finally {
609		lock.unlock();
#	Line 559 | Line 612 | public class ReadMostlyVector<E> impleme
612		}
613
614		public boolean addAll(int index, Collection<? extends E> c) {
615	<	SequenceLock lock = this.lock;
615	>	final SequenceLock lock = this.lock;
616		boolean ret;
617		Object[] elements = c.toArray();
618		lock.lock();
619		try {
620	<	ret = internalAddAllAt(index, elements);
620	>	ret = rawAddAllAt(index, elements);
621		} finally {
622		lock.unlock();
623		}
#	Line 572 | Line 625 | public class ReadMostlyVector<E> impleme
625		}
626
627		public void clear() {
628	<	SequenceLock lock = this.lock;
628	>	final SequenceLock lock = this.lock;
629		lock.lock();
630		try {
631	<	for (int i = 0; i < count; i++)
632	<	array[i] = null;
631	>	int n = count;
632	>	Object[] items = array;
633	>	for (int i = 0; i < n; i++)
634	>	items[i] = null;
635		count = 0;
636		} finally {
637		lock.unlock();
#	Line 596 | Line 651 | public class ReadMostlyVector<E> impleme
651		return true;
652		if (!(o instanceof List))
653		return false;
654	<	return internalEquals((List<?>)(o), 0, -1);
654	>	return internalEquals((List<?>)o, 0, -1);
655		}
656
657		public E get(int index) {
658	<	SequenceLock lock = this.lock;
658	>	final SequenceLock lock = this.lock;
659		for (;;) {
660		long seq = lock.awaitAvailability();
661	+	int n = count;
662		Object[] items = array;
663	<	int len = items.length;
664	<	int c = count;
609	<	if (c > len)
610	<	continue;
611	<	E e; boolean ex;
612	<	if (index < 0 || index >= c) {
613	<	e = null;
614	<	ex = true;
615	<	}
616	<	else {
617	<	e = (E)items[index];
618	<	ex = false;
619	<	}
663	>	@SuppressWarnings("unchecked")
664	>	E e = (index < items.length) ? (E) items[index] : null;
665		if (lock.getSequence() == seq) {
666	<	if (ex)
666	>	if (index >= n)
667		throw new ArrayIndexOutOfBoundsException(index);
668	<	else
624	<	return e;
668	>	return e;
669		}
670		}
671		}
#	Line 631 | Line 675 | public class ReadMostlyVector<E> impleme
675		}
676
677		public int indexOf(Object o) {
678	<	SequenceLock lock = this.lock;
635	<	long seq = lock.awaitAvailability();
636	<	Object[] items = array;
637	<	int c = count;
638	<	if (c <= items.length) {
639	<	int idx = internalIndexOf(o, items, 0, c);
640	<	if (lock.getSequence() == seq)
641	<	return idx;
642	<	}
643	<	lock.lock();
644	<	try {
645	<	return internalIndexOf(o, array, 0, count);
646	<	} finally {
647	<	lock.unlock();
648	<	}
678	>	return indexOf(o, 0);
679		}
680
681		public boolean isEmpty() {
652	–	long ignore = lock.getSequence();
682		return count == 0;
683		}
684
685		public Iterator<E> iterator() {
686	<	return new Itr(this, 0);
686	>	return new Itr<E>(this, 0);
687		}
688
689		public int lastIndexOf(Object o) {
690	<	SequenceLock lock = this.lock;
691	<	long seq = lock.awaitAvailability();
692	<	Object[] items = array;
693	<	int c = count;
694	<	if (c <= items.length) {
695	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
696	<	if (lock.getSequence() == seq)
697	<	return idx;
698	<	}
699	<	lock.lock();
700	<	try {
701	<	return internalLastIndexOf(o, array, count-1, 0);
702	<	} finally {
703	<	lock.unlock();
690	>	final SequenceLock lock = this.lock;
691	>	for (;;) {
692	>	long seq = lock.awaitAvailability();
693	>	Object[] items = array;
694	>	int n = count;
695	>	if (n <= items.length) {
696	>	for (int i = n - 1; i >= 0; --i) {
697	>	Object e = items[i];
698	>	if (lock.getSequence() != seq) {
699	>	lock.lock();
700	>	try {
701	>	return rawLastIndexOf(o, count - 1, 0);
702	>	} finally {
703	>	lock.unlock();
704	>	}
705	>	}
706	>	else if ((o == null) ? e == null : o.equals(e))
707	>	return i;
708	>	}
709	>	return -1;
710	>	}
711		}
712		}
713
714		public ListIterator<E> listIterator() {
715	<	return new Itr(this, 0);
715	>	return new Itr<E>(this, 0);
716		}
717
718		public ListIterator<E> listIterator(int index) {
719	<	return new Itr(this, index);
719	>	return new Itr<E>(this, index);
720		}
721
722		public E remove(int index) {
723	<	SequenceLock lock = this.lock;
688	<	E oldValue;
723	>	final SequenceLock lock = this.lock;
724		lock.lock();
725		try {
726		if (index < 0 || index >= count)
727		throw new ArrayIndexOutOfBoundsException(index);
728	<	oldValue = (E)array[index];
729	<	internalRemoveAt(index);
728	>	@SuppressWarnings("unchecked")
729	>	E oldValue = (E) array[index];
730	>	rawRemoveAt(index);
731	>	return oldValue;
732		} finally {
733		lock.unlock();
734		}
698	–	return oldValue;
735		}
736
737		public boolean remove(Object o) {
738	<	SequenceLock lock = this.lock;
703	<	boolean removed;
738	>	final SequenceLock lock = this.lock;
739		lock.lock();
740		try {
741	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
741	>	return rawRemoveAt(rawIndexOf(o, 0, count));
742		} finally {
743		lock.unlock();
744		}
710	–	return removed;
745		}
746
747		public boolean removeAll(Collection<?> c) {
#	Line 719 | Line 753 | public class ReadMostlyVector<E> impleme
753		}
754
755		public E set(int index, E element) {
756	<	E oldValue;
723	<	SequenceLock lock = this.lock;
756	>	final SequenceLock lock = this.lock;
757		lock.lock();
758		try {
759	+	Object[] items = array;
760		if (index < 0 || index >= count)
761		throw new ArrayIndexOutOfBoundsException(index);
762	<	oldValue = (E)array[index];
763	<	array[index] = element;
762	>	@SuppressWarnings("unchecked")
763	>	E oldValue = (E) items[index];
764	>	items[index] = element;
765	>	return oldValue;
766		} finally {
767		lock.unlock();
768		}
733	–	return oldValue;
769		}
770
771		public int size() {
737	–	long ignore = lock.getSequence();
772		return count;
773		}
774
#	Line 743 | Line 777 | public class ReadMostlyVector<E> impleme
777		int ssize = toIndex - fromIndex;
778		if (fromIndex < 0 || toIndex > c || ssize < 0)
779		throw new IndexOutOfBoundsException();
780	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
780	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
781		}
782
783		public Object[] toArray() {
#	Line 764 | Line 798 | public class ReadMostlyVector<E> impleme
798		* Append the element if not present.
799		*
800		* @param e element to be added to this list, if absent
801	<	* @return <tt>true</tt> if the element was added
801	>	* @return {@code true} if the element was added
802		*/
803		public boolean addIfAbsent(E e) {
804	<	boolean added;
771	<	SequenceLock lock = this.lock;
804	>	final SequenceLock lock = this.lock;
805		lock.lock();
806		try {
807	<	if (internalIndexOf(e, array, 0, count) < 0) {
808	<	internalAdd(e);
809	<	added = true;
807	>	if (rawIndexOf(e, 0, count) < 0) {
808	>	rawAdd(e);
809	>	return true;
810		}
811		else
812	<	added = false;
812	>	return false;
813		} finally {
814		lock.unlock();
815		}
783	–	return added;
816		}
817
818		/**
#	Line 802 | Line 834 | public class ReadMostlyVector<E> impleme
834		lock.lock();
835		try {
836		for (int i = 0; i < clen; ++i) {
837	<	Object e = cs[i];
838	<	if (internalIndexOf(e, array, 0, count) < 0) {
839	<	internalAdd((E)e);
837	>	@SuppressWarnings("unchecked")
838	>	E e = (E) cs[i];
839	>	if (rawIndexOf(e, 0, count) < 0) {
840	>	rawAdd(e);
841		++added;
842		}
843		}
#	Line 815 | Line 848 | public class ReadMostlyVector<E> impleme
848		return added;
849		}
850
851	+	/**
852	+	* Returns an iterator operating over a snapshot copy of the
853	+	* elements of this collection created upon construction of the
854	+	* iterator. The iterator does <em>NOT</em> support the
855	+	* {@code remove} method.
856	+	*
857	+	* @return an iterator over the elements in this list in proper sequence
858	+	*/
859	+	public Iterator<E> snapshotIterator() {
860	+	return new SnapshotIterator<E>(this);
861	+	}
862	+
863	+	static final class SnapshotIterator<E> implements Iterator<E> {
864	+	private final Object[] items;
865	+	private int cursor;
866	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
867	+	public boolean hasNext() { return cursor < items.length; }
868	+	@SuppressWarnings("unchecked")
869	+	public E next() {
870	+	if (cursor < items.length)
871	+	return (E) items[cursor++];
872	+	throw new NoSuchElementException();
873	+	}
874	+	public void remove() { throw new UnsupportedOperationException() ; }
875	+	}
876	+
877		// Vector-only methods
878
879		/** See {@link Vector#firstElement} */
880		public E firstElement() {
881	<	SequenceLock lock = this.lock;
881	>	final SequenceLock lock = this.lock;
882		for (;;) {
883		long seq = lock.awaitAvailability();
884		Object[] items = array;
885	<	int len = items.length;
886	<	int c = count;
887	<	if (c > len || c < 0)
829	<	continue;
830	<	E e; boolean ex;
831	<	if (c == 0) {
832	<	e = null;
833	<	ex = true;
834	<	}
835	<	else {
836	<	e = (E)items[0];
837	<	ex = false;
838	<	}
885	>	int n = count;
886	>	@SuppressWarnings("unchecked")
887	>	E e = (items.length > 0) ? (E) items[0] : null;
888		if (lock.getSequence() == seq) {
889	<	if (ex)
889	>	if (n <= 0)
890		throw new NoSuchElementException();
891	<	else
843	<	return e;
891	>	return e;
892		}
893		}
894		}
895
896		/** See {@link Vector#lastElement} */
897		public E lastElement() {
898	<	SequenceLock lock = this.lock;
898	>	final SequenceLock lock = this.lock;
899		for (;;) {
900		long seq = lock.awaitAvailability();
901		Object[] items = array;
902	<	int len = items.length;
903	<	int c = count;
904	<	if (c > len || c < 0)
857	<	continue;
858	<	E e; boolean ex;
859	<	if (c == 0) {
860	<	e = null;
861	<	ex = true;
862	<	}
863	<	else {
864	<	e = (E)items[c - 1];
865	<	ex = false;
866	<	}
902	>	int n = count;
903	>	@SuppressWarnings("unchecked")
904	>	E e = (n > 0 && items.length >= n) ? (E) items[n - 1] : null;
905		if (lock.getSequence() == seq) {
906	<	if (ex)
906	>	if (n <= 0)
907		throw new NoSuchElementException();
908	<	else
871	<	return e;
908	>	return e;
909		}
910		}
911		}
912
913		/** See {@link Vector#indexOf(Object, int)} */
914		public int indexOf(Object o, int index) {
915	<	SequenceLock lock = this.lock;
879	<	int idx = 0;
880	<	boolean ex = false;
915	>	final SequenceLock lock = this.lock;
916		long seq = lock.awaitAvailability();
917		Object[] items = array;
918	<	int c = count;
919	<	boolean retry = false;
920	<	if (c > items.length)
921	<	retry = true;
922	<	else if (index < 0)
888	<	ex = true;
889	<	else
890	<	idx = internalIndexOf(o, items, index, c);
891	<	if (retry || lock.getSequence() != seq) {
918	>	int n = count;
919	>	int idx = -1;
920	>	if (n <= items.length)
921	>	idx = validatedIndexOf(o, items, index, n, seq);
922	>	if (lock.getSequence() != seq) {
923		lock.lock();
924		try {
925	<	if (index < 0)
895	<	ex = true;
896	<	else
897	<	idx = internalIndexOf(o, array, 0, count);
925	>	idx = rawIndexOf(o, index, count);
926		} finally {
927		lock.unlock();
928		}
929		}
930	<	if (ex)
903	<	throw new ArrayIndexOutOfBoundsException(index);
930	>	// Above code will throw AIOOBE when index < 0
931		return idx;
932		}
933
934		/** See {@link Vector#lastIndexOf(Object, int)} */
935		public int lastIndexOf(Object o, int index) {
936	<	SequenceLock lock = this.lock;
910	<	int idx = 0;
911	<	boolean ex = false;
936	>	final SequenceLock lock = this.lock;
937		long seq = lock.awaitAvailability();
938		Object[] items = array;
939	<	int c = count;
940	<	boolean retry = false;
941	<	if (c > items.length)
942	<	retry = true;
943	<	else if (index >= c)
919	<	ex = true;
920	<	else
921	<	idx = internalLastIndexOf(o, items, index, 0);
922	<	if (retry || lock.getSequence() != seq) {
939	>	int n = count;
940	>	int idx = -1;
941	>	if (index < Math.min(n, items.length))
942	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
943	>	if (lock.getSequence() != seq) {
944		lock.lock();
945		try {
946	<	if (index >= count)
947	<	ex = true;
948	<	else
928	<	idx = internalLastIndexOf(o, array, index, 0);
946	>	n = count;
947	>	if (index < n)
948	>	idx = rawLastIndexOf(o, index, 0);
949		} finally {
950		lock.unlock();
951		}
952		}
953	<	if (ex)
954	<	throw new ArrayIndexOutOfBoundsException(index);
953	>	if (index >= n)
954	>	throw new IndexOutOfBoundsException(index + " >= " + n);
955		return idx;
956		}
957
#	Line 939 | Line 959 | public class ReadMostlyVector<E> impleme
959		public void setSize(int newSize) {
960		if (newSize < 0)
961		throw new ArrayIndexOutOfBoundsException(newSize);
962	<	SequenceLock lock = this.lock;
962	>	final SequenceLock lock = this.lock;
963		lock.lock();
964		try {
965	<	int c = count;
966	<	if (newSize > c)
965	>	int n = count;
966	>	if (newSize > n)
967		grow(newSize);
968		else {
969	<	for (int i = newSize ; i < c ; i++)
970	<	array[i] = null;
969	>	Object[] items = array;
970	>	for (int i = newSize ; i < n ; i++)
971	>	items[i] = null;
972		}
973		count = newSize;
974		} finally {
#	Line 957 | Line 978 | public class ReadMostlyVector<E> impleme
978
979		/** See {@link Vector#copyInto} */
980		public void copyInto(Object[] anArray) {
981	<	SequenceLock lock = this.lock;
981	>	final SequenceLock lock = this.lock;
982		lock.lock();
983		try {
984		System.arraycopy(array, 0, anArray, 0, count);
#	Line 968 | Line 989 | public class ReadMostlyVector<E> impleme
989
990		/** See {@link Vector#trimToSize} */
991		public void trimToSize() {
992	<	SequenceLock lock = this.lock;
992	>	final SequenceLock lock = this.lock;
993		lock.lock();
994		try {
995	<	if (count < array.length)
996	<	array = Arrays.copyOf(array, count);
995	>	Object[] items = array;
996	>	int n = count;
997	>	if (n < items.length)
998	>	array = Arrays.copyOf(items, n);
999		} finally {
1000		lock.unlock();
1001		}
#	Line 981 | Line 1004 | public class ReadMostlyVector<E> impleme
1004		/** See {@link Vector#ensureCapacity} */
1005		public void ensureCapacity(int minCapacity) {
1006		if (minCapacity > 0) {
1007	<	SequenceLock lock = this.lock;
1007	>	final SequenceLock lock = this.lock;
1008		lock.lock();
1009		try {
1010		if (minCapacity - array.length > 0)
#	Line 994 | Line 1017 | public class ReadMostlyVector<E> impleme
1017
1018		/** See {@link Vector#elements} */
1019		public Enumeration<E> elements() {
1020	<	return new Itr(this, 0);
1020	>	return new Itr<E>(this, 0);
1021		}
1022
1023		/** See {@link Vector#capacity} */
1024		public int capacity() {
1002	–	long ignore = lock.getSequence();
1025		return array.length;
1026		}
1027
#	Line 1040 | Line 1062 | public class ReadMostlyVector<E> impleme
1062
1063		// other methods
1064
1065	<	public Object clone() {
1066	<	SequenceLock lock = this.lock;
1065	>	public ReadMostlyVector<E> clone() {
1066	>	final SequenceLock lock = this.lock;
1067		Object[] a = null;
1046	–	int c;
1068		boolean retry = false;
1069		long seq = lock.awaitAvailability();
1070		Object[] items = array;
1071	<	c = count;
1072	<	if (c <= items.length)
1073	<	a = Arrays.copyOf(items, c);
1071	>	int n = count;
1072	>	if (n <= items.length)
1073	>	a = Arrays.copyOf(items, n);
1074		else
1075		retry = true;
1076		if (retry || lock.getSequence() != seq) {
1077		lock.lock();
1078		try {
1079	<	c = count;
1080	<	a = Arrays.copyOf(array, c);
1079	>	n = count;
1080	>	a = Arrays.copyOf(array, n);
1081		} finally {
1082		lock.unlock();
1083		}
1084		}
1085	<	return new ReadMostlyVector(a, c, capacityIncrement);
1085	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1086		}
1087
1088		private void writeObject(java.io.ObjectOutputStream s)
1089		throws java.io.IOException {
1090	<	SequenceLock lock = this.lock;
1090	>	final SequenceLock lock = this.lock;
1091		lock.lock();
1092		try {
1093		s.defaultWriteObject();
#	Line 1075 | Line 1096 | public class ReadMostlyVector<E> impleme
1096		}
1097		}
1098
1099	<	static final class Itr<E> implements ListIterator<E>, Enumeration<E>  {
1099	>	static final class Itr<E> implements ListIterator<E>, Enumeration<E> {
1100		final ReadMostlyVector<E> list;
1101		final SequenceLock lock;
1102		Object[] items;
1103	<	Object next, prev;
1103	>	E next, prev;
1104		long seq;
1105		int cursor;
1106		int fence;
1107		int lastRet;
1108	<	boolean haveNext, havePrev;
1108	>	boolean validNext, validPrev;
1109
1110		Itr(ReadMostlyVector<E> list, int index) {
1111		this.list = list;
#	Line 1097 | Line 1118 | public class ReadMostlyVector<E> impleme
1118		}
1119
1120		private void refresh() {
1121	+	validNext = validPrev = false;
1122		do {
1123		seq = lock.awaitAvailability();
1124		items = list.array;
1125	<	fence = list.count;
1126	<	} while (lock.getSequence() != seq);
1125	>	} while ((fence = list.count) > items.length ||
1126	>	lock.getSequence() != seq);
1127		}
1128
1129	+	@SuppressWarnings("unchecked")
1130		public boolean hasNext() {
1131	+	boolean valid;
1132		int i = cursor;
1133	<	while (i < fence && i >= 0) {
1133	>	for (;;) {
1134	>	if (i >= fence || i < 0 || i >= items.length) {
1135	>	valid = false;
1136	>	break;
1137	>	}
1138	>	next = (E) items[i];
1139		if (lock.getSequence() == seq) {
1140	<	next = items[i];
1141	<	return haveNext = true;
1140	>	valid = true;
1141	>	break;
1142		}
1143		refresh();
1144		}
1145	<	return false;
1145	>	return validNext = valid;
1146		}
1147
1148	+	@SuppressWarnings("unchecked")
1149		public boolean hasPrevious() {
1150	<	int i = cursor;
1151	<	while (i <= fence && i > 0) {
1150	>	boolean valid;
1151	>	int i = cursor - 1;
1152	>	for (;;) {
1153	>	if (i >= fence || i < 0 || i >= items.length) {
1154	>	valid = false;
1155	>	break;
1156	>	}
1157	>	prev = (E) items[i];
1158		if (lock.getSequence() == seq) {
1159	<	prev = items[i - 1];
1160	<	return havePrev = true;
1159	>	valid = true;
1160	>	break;
1161		}
1162		refresh();
1163		}
1164	<	return false;
1164	>	return validPrev = valid;
1165		}
1166
1167		public E next() {
1168	<	if (!haveNext && !hasNext())
1169	<	throw new NoSuchElementException();
1170	<	haveNext = false;
1171	<	lastRet = cursor++;
1172	<	return (E) next;
1168	>	if (validNext || hasNext()) {
1169	>	validNext = false;
1170	>	lastRet = cursor++;
1171	>	return next;
1172	>	}
1173	>	throw new NoSuchElementException();
1174		}
1175
1176		public E previous() {
1177	<	if (!havePrev && !hasPrevious())
1178	<	throw new NoSuchElementException();
1179	<	havePrev = false;
1180	<	lastRet = cursor--;
1181	<	return (E) prev;
1177	>	if (validPrev || hasPrevious()) {
1178	>	validPrev = false;
1179	>	lastRet = cursor--;
1180	>	return prev;
1181	>	}
1182	>	throw new NoSuchElementException();
1183		}
1184
1185		public void remove() {
#	Line 1196 | Line 1234 | public class ReadMostlyVector<E> impleme
1234		public int previousIndex() { return cursor - 1; }
1235		}
1236
1237	<	static final class ReadMostlyVectorSublist<E> implements List<E>, RandomAccess, java.io.Serializable {
1237	>	static final class ReadMostlyVectorSublist<E>
1238	>	implements List<E>, RandomAccess, java.io.Serializable {
1239	>	static final long serialVersionUID = 3041673470172026059L;
1240	>
1241		final ReadMostlyVector<E> list;
1242		final int offset;
1243		volatile int size;
1244
1245	<	ReadMostlyVectorSublist(ReadMostlyVector<E> list, int offset, int size) {
1245	>	ReadMostlyVectorSublist(ReadMostlyVector<E> list,
1246	>	int offset, int size) {
1247		this.list = list;
1248		this.offset = offset;
1249		this.size = size;
#	Line 1213 | Line 1255 | public class ReadMostlyVector<E> impleme
1255		}
1256
1257		public boolean add(E element) {
1258	<	SequenceLock lock = list.lock;
1258	>	final SequenceLock lock = list.lock;
1259		lock.lock();
1260		try {
1261		int c = size;
1262	<	list.internalAddAt(c + offset, element);
1262	>	list.rawAddAt(c + offset, element);
1263		size = c + 1;
1264		} finally {
1265		lock.unlock();
#	Line 1226 | Line 1268 | public class ReadMostlyVector<E> impleme
1268		}
1269
1270		public void add(int index, E element) {
1271	<	SequenceLock lock = list.lock;
1271	>	final SequenceLock lock = list.lock;
1272		lock.lock();
1273		try {
1274		if (index < 0 || index > size)
1275		throw new ArrayIndexOutOfBoundsException(index);
1276	<	list.internalAddAt(index + offset, element);
1276	>	list.rawAddAt(index + offset, element);
1277		++size;
1278		} finally {
1279		lock.unlock();
#	Line 1240 | Line 1282 | public class ReadMostlyVector<E> impleme
1282
1283		public boolean addAll(Collection<? extends E> c) {
1284		Object[] elements = c.toArray();
1285	<	int added;
1244	<	SequenceLock lock = list.lock;
1285	>	final SequenceLock lock = list.lock;
1286		lock.lock();
1287		try {
1288		int s = size;
1289		int pc = list.count;
1290	<	list.internalAddAllAt(offset + s, elements);
1291	<	added = list.count - pc;
1290	>	list.rawAddAllAt(offset + s, elements);
1291	>	int added = list.count - pc;
1292		size = s + added;
1293	+	return added != 0;
1294		} finally {
1295		lock.unlock();
1296		}
1255	–	return added != 0;
1297		}
1298
1299		public boolean addAll(int index, Collection<? extends E> c) {
1300		Object[] elements = c.toArray();
1301	<	int added;
1261	<	SequenceLock lock = list.lock;
1301	>	final SequenceLock lock = list.lock;
1302		lock.lock();
1303		try {
1304		int s = size;
1305		if (index < 0 || index > s)
1306		throw new ArrayIndexOutOfBoundsException(index);
1307		int pc = list.count;
1308	<	list.internalAddAllAt(index + offset, elements);
1309	<	added = list.count - pc;
1308	>	list.rawAddAllAt(index + offset, elements);
1309	>	int added = list.count - pc;
1310		size = s + added;
1311	+	return added != 0;
1312		} finally {
1313		lock.unlock();
1314		}
1274	–	return added != 0;
1315		}
1316
1317		public void clear() {
1318	<	SequenceLock lock = list.lock;
1318	>	final SequenceLock lock = list.lock;
1319		lock.lock();
1320		try {
1321	<	list.internalClear(offset, size);
1321	>	list.internalClear(offset, offset + size);
1322		size = 0;
1323		} finally {
1324		lock.unlock();
#	Line 1290 | Line 1330 | public class ReadMostlyVector<E> impleme
1330		}
1331
1332		public boolean containsAll(Collection<?> c) {
1333	<	return list.internalContainsAll(c, offset, size);
1333	>	return list.internalContainsAll(c, offset, offset + size);
1334		}
1335
1336		public boolean equals(Object o) {
#	Line 1298 | Line 1338 | public class ReadMostlyVector<E> impleme
1338		return true;
1339		if (!(o instanceof List))
1340		return false;
1341	<	return list.internalEquals((List<?>)(o), offset, size);
1341	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1342		}
1343
1344		public E get(int index) {
#	Line 1308 | Line 1348 | public class ReadMostlyVector<E> impleme
1348		}
1349
1350		public int hashCode() {
1351	<	return list.internalHashCode(offset, size);
1351	>	return list.internalHashCode(offset, offset + size);
1352		}
1353
1354		public int indexOf(Object o) {
1355	<	SequenceLock lock = list.lock;
1355	>	final SequenceLock lock = list.lock;
1356		long seq = lock.awaitAvailability();
1357		Object[] items = list.array;
1358		int c = list.count;
1359		if (c <= items.length) {
1360	<	int idx = internalIndexOf(o, items, offset, offset+size);
1360	>	int idx = list.validatedIndexOf(o, items, offset,
1361	>	offset + size, seq);
1362		if (lock.getSequence() == seq)
1363		return idx < 0 ? -1 : idx - offset;
1364		}
1365		lock.lock();
1366		try {
1367	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1367	>	int idx = list.rawIndexOf(o, offset, offset + size);
1368		return idx < 0 ? -1 : idx - offset;
1369		} finally {
1370		lock.unlock();
#	Line 1335 | Line 1376 | public class ReadMostlyVector<E> impleme
1376		}
1377
1378		public Iterator<E> iterator() {
1379	<	return new SubItr(this, offset);
1379	>	return new SubItr<E>(this, offset);
1380		}
1381
1382		public int lastIndexOf(Object o) {
1383	<	SequenceLock lock = list.lock;
1383	>	final SequenceLock lock = list.lock;
1384		long seq = lock.awaitAvailability();
1385		Object[] items = list.array;
1386		int c = list.count;
1387		if (c <= items.length) {
1388	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1388	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1389	>	offset, seq);
1390		if (lock.getSequence() == seq)
1391		return idx < 0 ? -1 : idx - offset;
1392		}
1393		lock.lock();
1394		try {
1395	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1395	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1396		return idx < 0 ? -1 : idx - offset;
1397		} finally {
1398		lock.unlock();
#	Line 1359 | Line 1400 | public class ReadMostlyVector<E> impleme
1400		}
1401
1402		public ListIterator<E> listIterator() {
1403	<	return new SubItr(this, offset);
1403	>	return new SubItr<E>(this, offset);
1404		}
1405
1406		public ListIterator<E> listIterator(int index) {
1407	<	return new SubItr(this, index + offset);
1407	>	return new SubItr<E>(this, index + offset);
1408		}
1409
1410		public E remove(int index) {
1411	<	E result;
1371	<	SequenceLock lock = list.lock;
1411	>	final SequenceLock lock = list.lock;
1412		lock.lock();
1413		try {
1414	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1414	>	Object[] items = list.array;
1415		int i = index + offset;
1416	<	result = (E)list.array[i];
1417	<	list.internalRemoveAt(i);
1416	>	if (index < 0 || index >= size || i >= items.length)
1417	>	throw new ArrayIndexOutOfBoundsException(index);
1418	>	@SuppressWarnings("unchecked")
1419	>	E result = (E) items[i];
1420	>	list.rawRemoveAt(i);
1421		size--;
1422	+	return result;
1423		} finally {
1424		lock.unlock();
1425		}
1383	–	return result;
1426		}
1427
1428		public boolean remove(Object o) {
1429	<	boolean removed = false;
1388	<	SequenceLock lock = list.lock;
1429	>	final SequenceLock lock = list.lock;
1430		lock.lock();
1431		try {
1432	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1433	<	offset+size))) {
1393	<	removed = true;
1432	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1433	>	offset + size))) {
1434		--size;
1435	+	return true;
1436		}
1437	+	else
1438	+	return false;
1439		} finally {
1440		lock.unlock();
1441		}
1399	–	return removed;
1442		}
1443
1444		public boolean removeAll(Collection<?> c) {
1445	<	return list.internalRemoveAll(c, offset, size);
1445	>	return list.internalRemoveAll(c, offset, offset + size);
1446		}
1447
1448		public boolean retainAll(Collection<?> c) {
1449	<	return list.internalRetainAll(c, offset, size);
1449	>	return list.internalRetainAll(c, offset, offset + size);
1450		}
1451
1452		public E set(int index, E element) {
#	Line 1422 | Line 1464 | public class ReadMostlyVector<E> impleme
1464		int ssize = toIndex - fromIndex;
1465		if (fromIndex < 0 || toIndex > c || ssize < 0)
1466		throw new IndexOutOfBoundsException();
1467	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1467	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1468		}
1469
1470		public Object[] toArray() {
1471	<	return list.internalToArray(offset, size);
1471	>	return list.internalToArray(offset, offset + size);
1472		}
1473
1474		public <T> T[] toArray(T[] a) {
1475	<	return list.internalToArray(a, offset, size);
1475	>	return list.internalToArray(a, offset, offset + size);
1476		}
1477
1478		public String toString() {
1479	<	return list.internalToString(offset, size);
1479	>	return list.internalToString(offset, offset + size);
1480		}
1481
1482		}
#	Line 1444 | Line 1486 | public class ReadMostlyVector<E> impleme
1486		final ReadMostlyVector<E> list;
1487		final SequenceLock lock;
1488		Object[] items;
1489	<	Object next, prev;
1489	>	E next, prev;
1490		long seq;
1491		int cursor;
1492		int fence;
1493		int lastRet;
1494	<	boolean haveNext, havePrev;
1494	>	boolean validNext, validPrev;
1495
1496		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1497		this.sublist = sublist;
#	Line 1463 | Line 1505 | public class ReadMostlyVector<E> impleme
1505		}
1506
1507		private void refresh() {
1508	+	validNext = validPrev = false;
1509		do {
1510	+	int n;
1511		seq = lock.awaitAvailability();
1512		items = list.array;
1513	<	int c = list.count;
1513	>	if ((n = list.count) > items.length)
1514	>	continue;
1515		int b = sublist.offset + sublist.size;
1516	<	fence = b < c ? b : c;
1516	>	fence = b < n ? b : n;
1517		} while (lock.getSequence() != seq);
1518		}
1519
1520	+	@SuppressWarnings("unchecked")
1521		public boolean hasNext() {
1522	+	boolean valid;
1523		int i = cursor;
1524	<	while (i < fence && i >= 0) {
1524	>	for (;;) {
1525	>	if (i >= fence || i < 0 || i >= items.length) {
1526	>	valid = false;
1527	>	break;
1528	>	}
1529	>	next = (E) items[i];
1530		if (lock.getSequence() == seq) {
1531	<	next = items[i];
1532	<	return haveNext = true;
1531	>	valid = true;
1532	>	break;
1533		}
1534		refresh();
1535		}
1536	<	return false;
1536	>	return validNext = valid;
1537		}
1538
1539	+	@SuppressWarnings("unchecked")
1540		public boolean hasPrevious() {
1541	<	int i = cursor;
1542	<	while (i <= fence && i > 0) {
1541	>	boolean valid;
1542	>	int i = cursor - 1;
1543	>	for (;;) {
1544	>	if (i >= fence || i < 0 || i >= items.length) {
1545	>	valid = false;
1546	>	break;
1547	>	}
1548	>	prev = (E) items[i];
1549		if (lock.getSequence() == seq) {
1550	<	prev = items[i - 1];
1551	<	return havePrev = true;
1550	>	valid = true;
1551	>	break;
1552		}
1553		refresh();
1554		}
1555	<	return false;
1555	>	return validPrev = valid;
1556		}
1557
1558		public E next() {
1559	<	if (!haveNext && !hasNext())
1560	<	throw new NoSuchElementException();
1561	<	haveNext = false;
1562	<	lastRet = cursor++;
1563	<	return (E) next;
1559	>	if (validNext || hasNext()) {
1560	>	validNext = false;
1561	>	lastRet = cursor++;
1562	>	return next;
1563	>	}
1564	>	throw new NoSuchElementException();
1565		}
1566
1567		public E previous() {
1568	<	if (!havePrev && !hasPrevious())
1569	<	throw new NoSuchElementException();
1570	<	havePrev = false;
1571	<	lastRet = cursor--;
1572	<	return (E) prev;
1568	>	if (validPrev || hasPrevious()) {
1569	>	validPrev = false;
1570	>	lastRet = cursor--;
1571	>	return prev;
1572	>	}
1573	>	throw new NoSuchElementException();
1574		}
1575
1576		public int nextIndex() {

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines