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.21 by jsr166, Sat Dec 31 19:26:24 2011 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 46 | Line 63 | public class ReadMostlyVector<E> impleme
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;
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	>	// Version of indexOf that returns -1 if either not present or invalid
164	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
165	>	long seq) {
166		for (int i = index; i < fence; ++i) {
167	<	Object x = items[i];
168	<	if (o == null? x == null : (x != null && o.equals(x)))
167	>	Object e = items[i];
168	>	if (lock.getSequence() != seq)
169	>	break;
170	>	if ((x == null) ? e == null : x.equals(e))
171		return i;
172		}
173		return -1;
174		}
175
176	<	static int internalLastIndexOf(Object o, Object[] items,
177	<	int index, int origin) {
176	>	final int rawIndexOf(Object x, int index, int fence) {
177	>	Object[] items = array;
178	>	for (int i = index; i < fence; ++i) {
179	>	Object e = items[i];
180	>	if ((x == null) ? e == null : x.equals(e))
181	>	return i;
182	>	}
183	>	return -1;
184	>	}
185	>
186	>	final int validatedLastIndexOf(Object x, Object[] items,
187	>	int index, int origin, long seq) {
188	>	for (int i = index; i >= origin; --i) {
189	>	Object e = items[i];
190	>	if (lock.getSequence() != seq)
191	>	break;
192	>	if ((x == null) ? e == null : x.equals(e))
193	>	return i;
194	>	}
195	>	return -1;
196	>	}
197	>
198	>	final int rawLastIndexOf(Object x, int index, int origin) {
199	>	Object[] items = array;
200		for (int i = index; i >= origin; --i) {
201	<	Object x = items[i];
202	<	if (o == null? x == null : (x != null && o.equals(x)))
201	>	Object e = items[i];
202	>	if ((x == null) ? e == null : x.equals(e))
203		return i;
204		}
205		return -1;
206		}
207
208	<	final void internalAdd(E e) {
209	<	int c = count;
210	<	if (c >= array.length)
211	<	grow(c + 1);
212	<	array[c] = e;
213	<	count = c + 1;
208	>	final void rawAdd(E e) {
209	>	int n = count;
210	>	Object[] items = array;
211	>	if (n >= items.length)
212	>	items = grow(n + 1);
213	>	items[n] = e;
214	>	count = n + 1;
215		}
216
217	<	final void internalAddAt(int index, E e) {
218	<	int c = count;
219	<	if (index > c)
217	>	final void rawAddAt(int index, E e) {
218	>	int n = count;
219	>	Object[] items = array;
220	>	if (index > n)
221		throw new ArrayIndexOutOfBoundsException(index);
222	<	if (c >= array.length)
223	<	grow(c + 1);
224	<	System.arraycopy(array, index, array, index + 1, c - index);
225	<	array[index] = e;
226	<	count = c + 1;
222	>	if (n >= items.length)
223	>	items = grow(n + 1);
224	>	if (index < n)
225	>	System.arraycopy(items, index, items, index + 1, n - index);
226	>	items[index] = e;
227	>	count = n + 1;
228		}
229
230	<	final boolean internalAddAllAt(int index, Object[] elements) {
231	<	int c = count;
232	<	if (index < 0 || index > c)
230	>	final boolean rawAddAllAt(int index, Object[] elements) {
231	>	int n = count;
232	>	Object[] items = array;
233	>	if (index < 0 || index > n)
234		throw new ArrayIndexOutOfBoundsException(index);
235		int len = elements.length;
236		if (len == 0)
237		return false;
238	<	int newCount = c + len;
239	<	if (newCount >= array.length)
240	<	grow(newCount);
241	<	int mv = count - index;
238	>	int newCount = n + len;
239	>	if (newCount >= items.length)
240	>	items = grow(newCount);
241	>	int mv = n - index;
242		if (mv > 0)
243	<	System.arraycopy(array, index, array, index + len, mv);
244	<	System.arraycopy(elements, 0, array, index, len);
243	>	System.arraycopy(items, index, items, index + len, mv);
244	>	System.arraycopy(elements, 0, items, index, len);
245		count = newCount;
246		return true;
247		}
248
249	<	final boolean internalRemoveAt(int index) {
250	<	int c = count - 1;
251	<	if (index < 0 || index > c)
249	>	final boolean rawRemoveAt(int index) {
250	>	int n = count - 1;
251	>	Object[] items = array;
252	>	if (index < 0 || index > n)
253		return false;
254	<	int mv = c - index;
254	>	int mv = n - index;
255		if (mv > 0)
256	<	System.arraycopy(array, index + 1, array, index, mv);
257	<	array[c] = null;
258	<	count = c;
256	>	System.arraycopy(items, index + 1, items, index, mv);
257	>	items[n] = null;
258	>	count = n;
259		return true;
260		}
261
262		/**
263		* Internal version of removeAll for lists and sublists. In this
264	<	* and other similar methods below, the span argument is, if
265	<	* non-negative, the purported size of a list/sublist, or is left
266	<	* negative if the size should be determined via count field under
267	<	* lock.
264	>	* and other similar methods below, the bound argument is, if
265	>	* non-negative, the purported upper bound of a list/sublist, or
266	>	* is left negative if the bound should be determined via count
267	>	* field under lock.
268		*/
269	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
270	<	SequenceLock lock = this.lock;
269	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
270	>	final SequenceLock lock = this.lock;
271		boolean removed = false;
272		lock.lock();
273		try {
274	<	int fence = count;
275	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
274	>	int n = count;
275	>	int fence = bound < 0 || bound > n ? n : bound;
276		if (origin >= 0 && origin < fence) {
277		for (Object x : c) {
278	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
278	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
279		removed = true;
280		}
281		}
#	Line 240 | Line 285 | public class ReadMostlyVector<E> impleme
285		return removed;
286		}
287
288	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
289	<	SequenceLock lock = this.lock;
288	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
289	>	final SequenceLock lock = this.lock;
290		boolean removed = false;
291		if (c != this) {
292		lock.lock();
293		try {
294	+	Object[] items = array;
295		int i = origin;
296	<	int fence = count;
297	<	if (span >= 0 && origin + span < fence)
298	<	fence = origin + span;
299	<	while (i < fence) {
254	<	if (c.contains(array[i]))
296	>	int n = count;
297	>	int fence = bound < 0 || bound > n ? n : bound;
298	>	while (i >= 0 && i < fence) {
299	>	if (c.contains(items[i]))
300		++i;
301		else {
302		--fence;
303	<	int mv = --count - i;
303	>	int mv = --n - i;
304		if (mv > 0)
305	<	System.arraycopy(array, i + 1, array, i, mv);
261	<	removed = true;
305	>	System.arraycopy(items, i + 1, items, i, mv);
306		}
307		}
308	+	if (count != n) {
309	+	count = n;
310	+	removed = true;
311	+	}
312		} finally {
313		lock.unlock();
314		}
#	Line 268 | Line 316 | public class ReadMostlyVector<E> impleme
316		return removed;
317		}
318
319	<	final void internalClear(int origin, int span) {
320	<	int c = count;
321	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
319	>	final void internalClear(int origin, int bound) {
320	>	int n = count;
321	>	int fence = bound < 0 || bound > n ? n : bound;
322		if (origin >= 0 && origin < fence) {
323	+	Object[] items = array;
324		int removed = fence - origin;
325	<	int newCount = c - removed;
326	<	int mv = c - (origin + removed);
325	>	int newCount = n - removed;
326	>	int mv = n - (origin + removed);
327		if (mv > 0)
328	<	System.arraycopy(array, origin + removed, array, origin, mv);
329	<	for (int i = c; i < newCount; ++i)
330	<	array[i] = null;
328	>	System.arraycopy(items, origin + removed, items, origin, mv);
329	>	for (int i = n; i < newCount; ++i)
330	>	items[i] = null;
331		count = newCount;
332		}
333		}
334
335	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
336	<	SequenceLock lock = this.lock;
335	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
336	>	final SequenceLock lock = this.lock;
337		boolean contained;
338		boolean locked = false;
339		try {
340		for (;;) {
341		long seq = lock.awaitAvailability();
342	+	int n = count;
343		Object[] items = array;
344		int len = items.length;
345	<	int c = count;
298	<	if (c > len)
345	>	if (n > len)
346		continue;
347	<	int fence = c;
348	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
347	>	int fence = bound < 0 || bound > n ? n : bound;
348	>	if (origin < 0)
349		contained = false;
350		else {
351		contained = true;
352	<	for (Object e : coll) {
353	<	if (internalIndexOf(e, items, origin, fence) < 0) {
352	>	for (Object e : c) {
353	>	int idx = (locked ?
354	>	rawIndexOf(e, origin, fence) :
355	>	validatedIndexOf(e, items, origin,
356	>	fence, seq));
357	>	if (idx < 0) {
358		contained = false;
359		break;
360		}
#	Line 323 | Line 372 | public class ReadMostlyVector<E> impleme
372		return contained;
373		}
374
375	<	final boolean internalEquals(List<?> list, int origin, int span) {
376	<	SequenceLock lock = this.lock;
328	<	boolean equal;
375	>	final boolean internalEquals(List<?> list, int origin, int bound) {
376	>	final SequenceLock lock = this.lock;
377		boolean locked = false;
378	+	boolean equal;
379		try {
380		for (;;) {
332	–	equal = true;
381		long seq = lock.awaitAvailability();
382		Object[] items = array;
383	<	int len = items.length;
384	<	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)
383	>	int n = count;
384	>	if (n > items.length || origin < 0)
385		equal = false;
386		else {
387	+	equal = true;
388	+	int fence = bound < 0 || bound > n ? n : bound;
389		Iterator<?> it = list.iterator();
390		for (int i = origin; i < fence; ++i) {
391	<	if (!it.hasNext()) {
392	<	equal = false;
393	<	break;
394	<	}
395	<	Object x = it.next();
396	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
391	>	Object x = items[i];
392	>	Object y;
393	>	if ((!locked && lock.getSequence() != seq) ||
394	>	!it.hasNext() ||
395	>	(y = it.next()) == null ?
396	>	x != null : !y.equals(x)) {
397		equal = false;
398		break;
399		}
#	Line 370 | Line 413 | public class ReadMostlyVector<E> impleme
413		return equal;
414		}
415
416	<	final int internalHashCode(int origin, int span) {
417	<	SequenceLock lock = this.lock;
416	>	final int internalHashCode(int origin, int bound) {
417	>	final SequenceLock lock = this.lock;
418		int hash;
419		boolean locked = false;
420		try {
#	Line 379 | Line 422 | public class ReadMostlyVector<E> impleme
422		hash = 1;
423		long seq = lock.awaitAvailability();
424		Object[] items = array;
425	+	int n = count;
426		int len = items.length;
427	<	int c = count;
384	<	if (c > len)
427	>	if (n > len)
428		continue;
429	<	int fence = c;
430	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
429	>	int fence = bound < 0 || bound > n ? n : bound;
430	>	if (origin >= 0) {
431		for (int i = origin; i < fence; ++i) {
432		Object e = items[i];
433		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 445 | public class ReadMostlyVector<E> impleme
445		return hash;
446		}
447
448	<	final String internalToString(int origin, int span) {
449	<	SequenceLock lock = this.lock;
448	>	final String internalToString(int origin, int bound) {
449	>	final SequenceLock lock = this.lock;
450		String ret;
451		boolean locked = false;
452		try {
453	<	for (;;) {
453	>	outer:for (;;) {
454		long seq = lock.awaitAvailability();
455		Object[] items = array;
456	+	int n = count;
457		int len = items.length;
458	<	int c = count;
417	<	if (c > len)
458	>	if (n > len)
459		continue;
460	<	int fence = c;
461	<	if (span >= 0 && origin + span < fence)
462	<	fence = origin + span;
463	<	if (origin >= 0 && fence <= c) {
464	<	if (origin == fence)
465	<	ret = "[]";
466	<	else {
467	<	StringBuilder sb = new StringBuilder();
468	<	sb.append('[');
469	<	for (int i = origin;;) {
470	<	Object e = items[i];
471	<	sb.append(e == this ? "(this Collection)" : e);
472	<	if (++i < fence)
473	<	sb.append(',').append(' ');
474	<	else {
475	<	ret = sb.append(']').toString();
476	<	break;
477	<	}
460	>	int fence = bound < 0 || bound > n ? n : bound;
461	>	if (origin < 0 || origin == fence)
462	>	ret = "[]";
463	>	else {
464	>	StringBuilder sb = new StringBuilder();
465	>	sb.append('[');
466	>	for (int i = origin;;) {
467	>	Object e = items[i];
468	>	if (e == this)
469	>	sb.append("(this Collection)");
470	>	else if (!locked && lock.getSequence() != seq)
471	>	continue outer;
472	>	else
473	>	sb.append(e.toString());
474	>	if (++i < fence)
475	>	sb.append(',').append(' ');
476	>	else {
477	>	ret = sb.append(']').toString();
478	>	break;
479		}
480		}
439	–	if (lock.getSequence() == seq)
440	–	break;
481		}
482	+	if (lock.getSequence() == seq)
483	+	break;
484		lock.lock();
485		locked = true;
486		}
#	Line 449 | Line 491 | public class ReadMostlyVector<E> impleme
491		return ret;
492		}
493
494	<	final Object[] internalToArray(int origin, int span) {
494	>	final Object[] internalToArray(int origin, int bound) {
495		Object[] result;
496	<	SequenceLock lock = this.lock;
496	>	final SequenceLock lock = this.lock;
497		boolean locked = false;
498		try {
499		for (;;) {
500		result = null;
501		long seq = lock.awaitAvailability();
502		Object[] items = array;
503	+	int n = count;
504		int len = items.length;
505	<	int c = count;
506	<	int fence = c;
507	<	if (span >= 0 && origin + span < fence)
508	<	fence = origin + span;
466	<	if (c <= len && fence <= len) {
505	>	if (n > len)
506	>	continue;
507	>	int fence = bound < 0 || bound > n ? n : bound;
508	>	if (origin >= 0)
509		result = Arrays.copyOfRange(items, origin, fence,
510		Object[].class);
511	<	if (lock.getSequence() == seq)
512	<	break;
471	<	}
511	>	if (lock.getSequence() == seq)
512	>	break;
513		lock.lock();
514		locked = true;
515		}
#	Line 479 | Line 520 | public class ReadMostlyVector<E> impleme
520		return result;
521		}
522
523	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
523	>	@SuppressWarnings("unchecked")
524	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
525	>	int alen = a.length;
526		T[] result;
527	<	SequenceLock lock = this.lock;
527	>	final SequenceLock lock = this.lock;
528		boolean locked = false;
529		try {
530		for (;;) {
531		long seq = lock.awaitAvailability();
532		Object[] items = array;
533	+	int n = count;
534		int len = items.length;
535	<	int c = count;
536	<	int fence = c;
537	<	if (span >= 0 && origin + span < fence)
538	<	fence = origin + span;
539	<	if (c <= len && fence <= len) {
540	<	if (a.length < count)
541	<	result = (T[]) Arrays.copyOfRange(array, origin,
542	<	fence, a.getClass());
543	<	else {
544	<	int n = fence - origin;
545	<	System.arraycopy(array, 0, a, origin, fence - origin);
546	<	if (a.length > n)
503	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
535	>	if (n > len)
536	>	continue;
537	>	int fence = bound < 0 || bound > n ? n : bound;
538	>	int rlen = fence - origin;
539	>	if (rlen < 0)
540	>	rlen = 0;
541	>	if (origin < 0 || alen >= rlen) {
542	>	if (rlen > 0)
543	>	System.arraycopy(items, 0, a, origin, rlen);
544	>	if (alen > rlen)
545	>	a[rlen] = null;
546	>	result = a;
547		}
548	+	else
549	+	result = (T[]) Arrays.copyOfRange(items, origin,
550	+	fence, a.getClass());
551	+	if (lock.getSequence() == seq)
552	+	break;
553		lock.lock();
554		locked = true;
555		}
#	Line 519 | Line 563 | public class ReadMostlyVector<E> impleme
563		// public List methods
564
565		public boolean add(E e) {
566	<	SequenceLock lock = this.lock;
566	>	final SequenceLock lock = this.lock;
567		lock.lock();
568		try {
569	<	internalAdd(e);
569	>	rawAdd(e);
570		} finally {
571		lock.unlock();
572		}
#	Line 530 | Line 574 | public class ReadMostlyVector<E> impleme
574		}
575
576		public void add(int index, E element) {
577	<	SequenceLock lock = this.lock;
577	>	final SequenceLock lock = this.lock;
578		lock.lock();
579		try {
580	<	internalAddAt(index, element);
580	>	rawAddAt(index, element);
581		} finally {
582		lock.unlock();
583		}
#	Line 544 | Line 588 | public class ReadMostlyVector<E> impleme
588		int len = elements.length;
589		if (len == 0)
590		return false;
591	<	SequenceLock lock = this.lock;
591	>	final SequenceLock lock = this.lock;
592		lock.lock();
593		try {
594	<	int newCount = count + len;
595	<	if (newCount >= array.length)
596	<	grow(newCount);
597	<	System.arraycopy(elements, 0, array, count, len);
594	>	Object[] items = array;
595	>	int n = count;
596	>	int newCount = n + len;
597	>	if (newCount >= items.length)
598	>	items = grow(newCount);
599	>	System.arraycopy(elements, 0, items, n, len);
600		count = newCount;
601		} finally {
602		lock.unlock();
#	Line 559 | Line 605 | public class ReadMostlyVector<E> impleme
605		}
606
607		public boolean addAll(int index, Collection<? extends E> c) {
608	<	SequenceLock lock = this.lock;
608	>	final SequenceLock lock = this.lock;
609		boolean ret;
610		Object[] elements = c.toArray();
611		lock.lock();
612		try {
613	<	ret = internalAddAllAt(index, elements);
613	>	ret = rawAddAllAt(index, elements);
614		} finally {
615		lock.unlock();
616		}
#	Line 572 | Line 618 | public class ReadMostlyVector<E> impleme
618		}
619
620		public void clear() {
621	<	SequenceLock lock = this.lock;
621	>	final SequenceLock lock = this.lock;
622		lock.lock();
623		try {
624	<	for (int i = 0; i < count; i++)
625	<	array[i] = null;
624	>	int n = count;
625	>	Object[] items = array;
626	>	for (int i = 0; i < n; i++)
627	>	items[i] = null;
628		count = 0;
629		} finally {
630		lock.unlock();
#	Line 596 | Line 644 | public class ReadMostlyVector<E> impleme
644		return true;
645		if (!(o instanceof List))
646		return false;
647	<	return internalEquals((List<?>)(o), 0, -1);
647	>	return internalEquals((List<?>)o, 0, -1);
648		}
649
650		public E get(int index) {
651	<	SequenceLock lock = this.lock;
651	>	final SequenceLock lock = this.lock;
652		for (;;) {
653		long seq = lock.awaitAvailability();
654	+	int n = count;
655		Object[] items = array;
656	<	int len = items.length;
657	<	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	<	}
656	>	@SuppressWarnings("unchecked")
657	>	E e = (index < items.length) ? (E) items[index] : null;
658		if (lock.getSequence() == seq) {
659	<	if (ex)
659	>	if (index >= n)
660		throw new ArrayIndexOutOfBoundsException(index);
661	<	else
624	<	return e;
661	>	return e;
662		}
663		}
664		}
#	Line 631 | Line 668 | public class ReadMostlyVector<E> impleme
668		}
669
670		public int indexOf(Object o) {
671	<	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	<	}
671	>	return indexOf(o, 0);
672		}
673
674		public boolean isEmpty() {
652	–	long ignore = lock.getSequence();
675		return count == 0;
676		}
677
678		public Iterator<E> iterator() {
679	<	return new Itr(this, 0);
679	>	return new Itr<E>(this, 0);
680		}
681
682		public int lastIndexOf(Object o) {
683	<	SequenceLock lock = this.lock;
684	<	long seq = lock.awaitAvailability();
685	<	Object[] items = array;
686	<	int c = count;
687	<	if (c <= items.length) {
688	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
689	<	if (lock.getSequence() == seq)
690	<	return idx;
691	<	}
692	<	lock.lock();
693	<	try {
694	<	return internalLastIndexOf(o, array, count-1, 0);
695	<	} finally {
696	<	lock.unlock();
683	>	final SequenceLock lock = this.lock;
684	>	for (;;) {
685	>	long seq = lock.awaitAvailability();
686	>	Object[] items = array;
687	>	int n = count;
688	>	if (n <= items.length) {
689	>	for (int i = n - 1; i >= 0; --i) {
690	>	Object e = items[i];
691	>	if (lock.getSequence() != seq) {
692	>	lock.lock();
693	>	try {
694	>	return rawLastIndexOf(o, count, 0);
695	>	} finally {
696	>	lock.unlock();
697	>	}
698	>	}
699	>	else if ((o == null) ? e == null : o.equals(e))
700	>	return i;
701	>	}
702	>	return -1;
703	>	}
704		}
705		}
706
707		public ListIterator<E> listIterator() {
708	<	return new Itr(this, 0);
708	>	return new Itr<E>(this, 0);
709		}
710
711		public ListIterator<E> listIterator(int index) {
712	<	return new Itr(this, index);
712	>	return new Itr<E>(this, index);
713		}
714
715		public E remove(int index) {
716	<	SequenceLock lock = this.lock;
688	<	E oldValue;
716	>	final SequenceLock lock = this.lock;
717		lock.lock();
718		try {
719		if (index < 0 || index >= count)
720		throw new ArrayIndexOutOfBoundsException(index);
721	<	oldValue = (E)array[index];
722	<	internalRemoveAt(index);
721	>	@SuppressWarnings("unchecked")
722	>	E oldValue = (E) array[index];
723	>	rawRemoveAt(index);
724	>	return oldValue;
725		} finally {
726		lock.unlock();
727		}
698	–	return oldValue;
728		}
729
730		public boolean remove(Object o) {
731	<	SequenceLock lock = this.lock;
703	<	boolean removed;
731	>	final SequenceLock lock = this.lock;
732		lock.lock();
733		try {
734	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
734	>	return rawRemoveAt(rawIndexOf(o, 0, count));
735		} finally {
736		lock.unlock();
737		}
710	–	return removed;
738		}
739
740		public boolean removeAll(Collection<?> c) {
#	Line 719 | Line 746 | public class ReadMostlyVector<E> impleme
746		}
747
748		public E set(int index, E element) {
749	<	E oldValue;
723	<	SequenceLock lock = this.lock;
749	>	final SequenceLock lock = this.lock;
750		lock.lock();
751		try {
752	+	Object[] items = array;
753		if (index < 0 || index >= count)
754		throw new ArrayIndexOutOfBoundsException(index);
755	<	oldValue = (E)array[index];
756	<	array[index] = element;
755	>	@SuppressWarnings("unchecked")
756	>	E oldValue = (E) items[index];
757	>	items[index] = element;
758	>	return oldValue;
759		} finally {
760		lock.unlock();
761		}
733	–	return oldValue;
762		}
763
764		public int size() {
737	–	long ignore = lock.getSequence();
765		return count;
766		}
767
#	Line 743 | Line 770 | public class ReadMostlyVector<E> impleme
770		int ssize = toIndex - fromIndex;
771		if (fromIndex < 0 || toIndex > c || ssize < 0)
772		throw new IndexOutOfBoundsException();
773	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
773	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
774		}
775
776		public Object[] toArray() {
#	Line 764 | Line 791 | public class ReadMostlyVector<E> impleme
791		* Append the element if not present.
792		*
793		* @param e element to be added to this list, if absent
794	<	* @return <tt>true</tt> if the element was added
794	>	* @return {@code true} if the element was added
795		*/
796		public boolean addIfAbsent(E e) {
797	<	boolean added;
771	<	SequenceLock lock = this.lock;
797	>	final SequenceLock lock = this.lock;
798		lock.lock();
799		try {
800	<	if (internalIndexOf(e, array, 0, count) < 0) {
801	<	internalAdd(e);
802	<	added = true;
800	>	if (rawIndexOf(e, 0, count) < 0) {
801	>	rawAdd(e);
802	>	return true;
803		}
804		else
805	<	added = false;
805	>	return false;
806		} finally {
807		lock.unlock();
808		}
783	–	return added;
809		}
810
811		/**
#	Line 802 | Line 827 | public class ReadMostlyVector<E> impleme
827		lock.lock();
828		try {
829		for (int i = 0; i < clen; ++i) {
830	<	Object e = cs[i];
831	<	if (internalIndexOf(e, array, 0, count) < 0) {
832	<	internalAdd((E)e);
830	>	@SuppressWarnings("unchecked")
831	>	E e = (E) cs[i];
832	>	if (rawIndexOf(e, 0, count) < 0) {
833	>	rawAdd(e);
834		++added;
835		}
836		}
#	Line 815 | Line 841 | public class ReadMostlyVector<E> impleme
841		return added;
842		}
843
844	+	/**
845	+	* Returns an iterator operating over a snapshot copy of the
846	+	* elements of this collection created upon construction of the
847	+	* iterator. The iterator does <em>NOT</em> support the
848	+	* {@code remove} method.
849	+	*
850	+	* @return an iterator over the elements in this list in proper sequence
851	+	*/
852	+	public Iterator<E> snapshotIterator() {
853	+	return new SnapshotIterator<E>(this);
854	+	}
855	+
856	+	static final class SnapshotIterator<E> implements Iterator<E> {
857	+	private final Object[] items;
858	+	private int cursor;
859	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
860	+	public boolean hasNext() { return cursor < items.length; }
861	+	@SuppressWarnings("unchecked")
862	+	public E next() {
863	+	if (cursor < items.length)
864	+	return (E) items[cursor++];
865	+	throw new NoSuchElementException();
866	+	}
867	+	public void remove() { throw new UnsupportedOperationException() ; }
868	+	}
869	+
870		// Vector-only methods
871
872		/** See {@link Vector#firstElement} */
873		public E firstElement() {
874	<	SequenceLock lock = this.lock;
874	>	final SequenceLock lock = this.lock;
875		for (;;) {
876		long seq = lock.awaitAvailability();
877		Object[] items = array;
878	<	int len = items.length;
879	<	int c = count;
880	<	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	<	}
878	>	int n = count;
879	>	@SuppressWarnings("unchecked")
880	>	E e = (items.length > 0) ? (E) items[0] : null;
881		if (lock.getSequence() == seq) {
882	<	if (ex)
882	>	if (n <= 0)
883		throw new NoSuchElementException();
884	<	else
843	<	return e;
884	>	return e;
885		}
886		}
887		}
888
889		/** See {@link Vector#lastElement} */
890		public E lastElement() {
891	<	SequenceLock lock = this.lock;
891	>	final SequenceLock lock = this.lock;
892		for (;;) {
893		long seq = lock.awaitAvailability();
894		Object[] items = array;
895	<	int len = items.length;
896	<	int c = count;
897	<	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	<	}
895	>	int n = count;
896	>	@SuppressWarnings("unchecked")
897	>	E e = (n > 0 && items.length >= n) ? (E) items[n - 1] : null;
898		if (lock.getSequence() == seq) {
899	<	if (ex)
899	>	if (n <= 0)
900		throw new NoSuchElementException();
901	<	else
871	<	return e;
901	>	return e;
902		}
903		}
904		}
905
906		/** See {@link Vector#indexOf(Object, int)} */
907		public int indexOf(Object o, int index) {
908	<	SequenceLock lock = this.lock;
908	>	final SequenceLock lock = this.lock;
909		int idx = 0;
910		boolean ex = false;
911		long seq = lock.awaitAvailability();
912		Object[] items = array;
913	<	int c = count;
913	>	int n = count;
914		boolean retry = false;
915	<	if (c > items.length)
915	>	if (n > items.length)
916		retry = true;
917		else if (index < 0)
918		ex = true;
919		else
920	<	idx = internalIndexOf(o, items, index, c);
920	>	idx = validatedIndexOf(o, items, index, n, seq);
921		if (retry || lock.getSequence() != seq) {
922		lock.lock();
923		try {
924		if (index < 0)
925		ex = true;
926		else
927	<	idx = internalIndexOf(o, array, 0, count);
927	>	idx = rawIndexOf(o, index, count);
928		} finally {
929		lock.unlock();
930		}
#	Line 906 | Line 936 | public class ReadMostlyVector<E> impleme
936
937		/** See {@link Vector#lastIndexOf(Object, int)} */
938		public int lastIndexOf(Object o, int index) {
939	<	SequenceLock lock = this.lock;
939	>	final SequenceLock lock = this.lock;
940		int idx = 0;
941		boolean ex = false;
942		long seq = lock.awaitAvailability();
943		Object[] items = array;
944	<	int c = count;
944	>	int n = count;
945		boolean retry = false;
946	<	if (c > items.length)
946	>	if (n > items.length)
947		retry = true;
948	<	else if (index >= c)
948	>	else if (index >= n)
949		ex = true;
950		else
951	<	idx = internalLastIndexOf(o, items, index, 0);
951	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
952		if (retry || lock.getSequence() != seq) {
953		lock.lock();
954		try {
955		if (index >= count)
956		ex = true;
957		else
958	<	idx = internalLastIndexOf(o, array, index, 0);
958	>	idx = rawLastIndexOf(o, index, 0);
959		} finally {
960		lock.unlock();
961		}
#	Line 939 | Line 969 | public class ReadMostlyVector<E> impleme
969		public void setSize(int newSize) {
970		if (newSize < 0)
971		throw new ArrayIndexOutOfBoundsException(newSize);
972	<	SequenceLock lock = this.lock;
972	>	final SequenceLock lock = this.lock;
973		lock.lock();
974		try {
975	<	int c = count;
976	<	if (newSize > c)
975	>	int n = count;
976	>	if (newSize > n)
977		grow(newSize);
978		else {
979	<	for (int i = newSize ; i < c ; i++)
980	<	array[i] = null;
979	>	Object[] items = array;
980	>	for (int i = newSize ; i < n ; i++)
981	>	items[i] = null;
982		}
983		count = newSize;
984		} finally {
#	Line 957 | Line 988 | public class ReadMostlyVector<E> impleme
988
989		/** See {@link Vector#copyInto} */
990		public void copyInto(Object[] anArray) {
991	<	SequenceLock lock = this.lock;
991	>	final SequenceLock lock = this.lock;
992		lock.lock();
993		try {
994		System.arraycopy(array, 0, anArray, 0, count);
#	Line 968 | Line 999 | public class ReadMostlyVector<E> impleme
999
1000		/** See {@link Vector#trimToSize} */
1001		public void trimToSize() {
1002	<	SequenceLock lock = this.lock;
1002	>	final SequenceLock lock = this.lock;
1003		lock.lock();
1004		try {
1005	<	if (count < array.length)
1006	<	array = Arrays.copyOf(array, count);
1005	>	Object[] items = array;
1006	>	int n = count;
1007	>	if (n < items.length)
1008	>	array = Arrays.copyOf(items, n);
1009		} finally {
1010		lock.unlock();
1011		}
#	Line 981 | Line 1014 | public class ReadMostlyVector<E> impleme
1014		/** See {@link Vector#ensureCapacity} */
1015		public void ensureCapacity(int minCapacity) {
1016		if (minCapacity > 0) {
1017	<	SequenceLock lock = this.lock;
1017	>	final SequenceLock lock = this.lock;
1018		lock.lock();
1019		try {
1020		if (minCapacity - array.length > 0)
#	Line 994 | Line 1027 | public class ReadMostlyVector<E> impleme
1027
1028		/** See {@link Vector#elements} */
1029		public Enumeration<E> elements() {
1030	<	return new Itr(this, 0);
1030	>	return new Itr<E>(this, 0);
1031		}
1032
1033		/** See {@link Vector#capacity} */
1034		public int capacity() {
1002	–	long ignore = lock.getSequence();
1035		return array.length;
1036		}
1037
#	Line 1040 | Line 1072 | public class ReadMostlyVector<E> impleme
1072
1073		// other methods
1074
1075	<	public Object clone() {
1076	<	SequenceLock lock = this.lock;
1075	>	public ReadMostlyVector<E> clone() {
1076	>	final SequenceLock lock = this.lock;
1077		Object[] a = null;
1046	–	int c;
1078		boolean retry = false;
1079		long seq = lock.awaitAvailability();
1080		Object[] items = array;
1081	<	c = count;
1082	<	if (c <= items.length)
1083	<	a = Arrays.copyOf(items, c);
1081	>	int n = count;
1082	>	if (n <= items.length)
1083	>	a = Arrays.copyOf(items, n);
1084		else
1085		retry = true;
1086		if (retry || lock.getSequence() != seq) {
1087		lock.lock();
1088		try {
1089	<	c = count;
1090	<	a = Arrays.copyOf(array, c);
1089	>	n = count;
1090	>	a = Arrays.copyOf(array, n);
1091		} finally {
1092		lock.unlock();
1093		}
1094		}
1095	<	return new ReadMostlyVector(a, c, capacityIncrement);
1095	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1096		}
1097
1098		private void writeObject(java.io.ObjectOutputStream s)
1099		throws java.io.IOException {
1100	<	SequenceLock lock = this.lock;
1100	>	final SequenceLock lock = this.lock;
1101		lock.lock();
1102		try {
1103		s.defaultWriteObject();
#	Line 1075 | Line 1106 | public class ReadMostlyVector<E> impleme
1106		}
1107		}
1108
1109	<	static final class Itr<E> implements ListIterator<E>, Enumeration<E>  {
1109	>	static final class Itr<E> implements ListIterator<E>, Enumeration<E> {
1110		final ReadMostlyVector<E> list;
1111		final SequenceLock lock;
1112		Object[] items;
1113	<	Object next, prev;
1113	>	E next, prev;
1114		long seq;
1115		int cursor;
1116		int fence;
1117		int lastRet;
1118	<	boolean haveNext, havePrev;
1118	>	boolean validNext, validPrev;
1119
1120		Itr(ReadMostlyVector<E> list, int index) {
1121		this.list = list;
#	Line 1097 | Line 1128 | public class ReadMostlyVector<E> impleme
1128		}
1129
1130		private void refresh() {
1131	+	validNext = validPrev = false;
1132		do {
1133		seq = lock.awaitAvailability();
1134		items = list.array;
1135	<	fence = list.count;
1136	<	} while (lock.getSequence() != seq);
1135	>	} while ((fence = list.count) > items.length ||
1136	>	lock.getSequence() != seq);
1137		}
1138
1139	+	@SuppressWarnings("unchecked")
1140		public boolean hasNext() {
1141	+	boolean valid;
1142		int i = cursor;
1143	<	while (i < fence && i >= 0) {
1143	>	for (;;) {
1144	>	if (i >= fence || i < 0 || i >= items.length) {
1145	>	valid = false;
1146	>	break;
1147	>	}
1148	>	next = (E) items[i];
1149		if (lock.getSequence() == seq) {
1150	<	next = items[i];
1151	<	return haveNext = true;
1150	>	valid = true;
1151	>	break;
1152		}
1153		refresh();
1154		}
1155	<	return false;
1155	>	return validNext = valid;
1156		}
1157
1158	+	@SuppressWarnings("unchecked")
1159		public boolean hasPrevious() {
1160	<	int i = cursor;
1161	<	while (i <= fence && i > 0) {
1160	>	boolean valid;
1161	>	int i = cursor - 1;
1162	>	for (;;) {
1163	>	if (i >= fence || i < 0 || i >= items.length) {
1164	>	valid = false;
1165	>	break;
1166	>	}
1167	>	prev = (E) items[i];
1168		if (lock.getSequence() == seq) {
1169	<	prev = items[i - 1];
1170	<	return havePrev = true;
1169	>	valid = true;
1170	>	break;
1171		}
1172		refresh();
1173		}
1174	<	return false;
1174	>	return validPrev = valid;
1175		}
1176
1177		public E next() {
1178	<	if (!haveNext && !hasNext())
1179	<	throw new NoSuchElementException();
1180	<	haveNext = false;
1181	<	lastRet = cursor++;
1182	<	return (E) next;
1178	>	if (validNext || hasNext()) {
1179	>	validNext = false;
1180	>	lastRet = cursor++;
1181	>	return next;
1182	>	}
1183	>	throw new NoSuchElementException();
1184		}
1185
1186		public E previous() {
1187	<	if (!havePrev && !hasPrevious())
1188	<	throw new NoSuchElementException();
1189	<	havePrev = false;
1190	<	lastRet = cursor--;
1191	<	return (E) prev;
1187	>	if (validPrev || hasPrevious()) {
1188	>	validPrev = false;
1189	>	lastRet = cursor--;
1190	>	return prev;
1191	>	}
1192	>	throw new NoSuchElementException();
1193		}
1194
1195		public void remove() {
#	Line 1196 | Line 1244 | public class ReadMostlyVector<E> impleme
1244		public int previousIndex() { return cursor - 1; }
1245		}
1246
1247	<	static final class ReadMostlyVectorSublist<E> implements List<E>, RandomAccess, java.io.Serializable {
1247	>	static final class ReadMostlyVectorSublist<E>
1248	>	implements List<E>, RandomAccess, java.io.Serializable {
1249	>	static final long serialVersionUID = 3041673470172026059L;
1250	>
1251		final ReadMostlyVector<E> list;
1252		final int offset;
1253		volatile int size;
1254
1255	<	ReadMostlyVectorSublist(ReadMostlyVector<E> list, int offset, int size) {
1255	>	ReadMostlyVectorSublist(ReadMostlyVector<E> list,
1256	>	int offset, int size) {
1257		this.list = list;
1258		this.offset = offset;
1259		this.size = size;
#	Line 1213 | Line 1265 | public class ReadMostlyVector<E> impleme
1265		}
1266
1267		public boolean add(E element) {
1268	<	SequenceLock lock = list.lock;
1268	>	final SequenceLock lock = list.lock;
1269		lock.lock();
1270		try {
1271		int c = size;
1272	<	list.internalAddAt(c + offset, element);
1272	>	list.rawAddAt(c + offset, element);
1273		size = c + 1;
1274		} finally {
1275		lock.unlock();
#	Line 1226 | Line 1278 | public class ReadMostlyVector<E> impleme
1278		}
1279
1280		public void add(int index, E element) {
1281	<	SequenceLock lock = list.lock;
1281	>	final SequenceLock lock = list.lock;
1282		lock.lock();
1283		try {
1284		if (index < 0 || index > size)
1285		throw new ArrayIndexOutOfBoundsException(index);
1286	<	list.internalAddAt(index + offset, element);
1286	>	list.rawAddAt(index + offset, element);
1287		++size;
1288		} finally {
1289		lock.unlock();
#	Line 1240 | Line 1292 | public class ReadMostlyVector<E> impleme
1292
1293		public boolean addAll(Collection<? extends E> c) {
1294		Object[] elements = c.toArray();
1295	<	int added;
1244	<	SequenceLock lock = list.lock;
1295	>	final SequenceLock lock = list.lock;
1296		lock.lock();
1297		try {
1298		int s = size;
1299		int pc = list.count;
1300	<	list.internalAddAllAt(offset + s, elements);
1301	<	added = list.count - pc;
1300	>	list.rawAddAllAt(offset + s, elements);
1301	>	int added = list.count - pc;
1302		size = s + added;
1303	+	return added != 0;
1304		} finally {
1305		lock.unlock();
1306		}
1255	–	return added != 0;
1307		}
1308
1309		public boolean addAll(int index, Collection<? extends E> c) {
1310		Object[] elements = c.toArray();
1311	<	int added;
1261	<	SequenceLock lock = list.lock;
1311	>	final SequenceLock lock = list.lock;
1312		lock.lock();
1313		try {
1314		int s = size;
1315		if (index < 0 || index > s)
1316		throw new ArrayIndexOutOfBoundsException(index);
1317		int pc = list.count;
1318	<	list.internalAddAllAt(index + offset, elements);
1319	<	added = list.count - pc;
1318	>	list.rawAddAllAt(index + offset, elements);
1319	>	int added = list.count - pc;
1320		size = s + added;
1321	+	return added != 0;
1322		} finally {
1323		lock.unlock();
1324		}
1274	–	return added != 0;
1325		}
1326
1327		public void clear() {
1328	<	SequenceLock lock = list.lock;
1328	>	final SequenceLock lock = list.lock;
1329		lock.lock();
1330		try {
1331	<	list.internalClear(offset, size);
1331	>	list.internalClear(offset, offset + size);
1332		size = 0;
1333		} finally {
1334		lock.unlock();
#	Line 1290 | Line 1340 | public class ReadMostlyVector<E> impleme
1340		}
1341
1342		public boolean containsAll(Collection<?> c) {
1343	<	return list.internalContainsAll(c, offset, size);
1343	>	return list.internalContainsAll(c, offset, offset + size);
1344		}
1345
1346		public boolean equals(Object o) {
#	Line 1298 | Line 1348 | public class ReadMostlyVector<E> impleme
1348		return true;
1349		if (!(o instanceof List))
1350		return false;
1351	<	return list.internalEquals((List<?>)(o), offset, size);
1351	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1352		}
1353
1354		public E get(int index) {
#	Line 1308 | Line 1358 | public class ReadMostlyVector<E> impleme
1358		}
1359
1360		public int hashCode() {
1361	<	return list.internalHashCode(offset, size);
1361	>	return list.internalHashCode(offset, offset + size);
1362		}
1363
1364		public int indexOf(Object o) {
1365	<	SequenceLock lock = list.lock;
1365	>	final SequenceLock lock = list.lock;
1366		long seq = lock.awaitAvailability();
1367		Object[] items = list.array;
1368		int c = list.count;
1369		if (c <= items.length) {
1370	<	int idx = internalIndexOf(o, items, offset, offset+size);
1370	>	int idx = list.validatedIndexOf(o, items, offset,
1371	>	offset + size, seq);
1372		if (lock.getSequence() == seq)
1373		return idx < 0 ? -1 : idx - offset;
1374		}
1375		lock.lock();
1376		try {
1377	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1377	>	int idx = list.rawIndexOf(o, offset, offset + size);
1378		return idx < 0 ? -1 : idx - offset;
1379		} finally {
1380		lock.unlock();
#	Line 1335 | Line 1386 | public class ReadMostlyVector<E> impleme
1386		}
1387
1388		public Iterator<E> iterator() {
1389	<	return new SubItr(this, offset);
1389	>	return new SubItr<E>(this, offset);
1390		}
1391
1392		public int lastIndexOf(Object o) {
1393	<	SequenceLock lock = list.lock;
1393	>	final SequenceLock lock = list.lock;
1394		long seq = lock.awaitAvailability();
1395		Object[] items = list.array;
1396		int c = list.count;
1397		if (c <= items.length) {
1398	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1398	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1399	>	offset, seq);
1400		if (lock.getSequence() == seq)
1401		return idx < 0 ? -1 : idx - offset;
1402		}
1403		lock.lock();
1404		try {
1405	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1405	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1406		return idx < 0 ? -1 : idx - offset;
1407		} finally {
1408		lock.unlock();
#	Line 1359 | Line 1410 | public class ReadMostlyVector<E> impleme
1410		}
1411
1412		public ListIterator<E> listIterator() {
1413	<	return new SubItr(this, offset);
1413	>	return new SubItr<E>(this, offset);
1414		}
1415
1416		public ListIterator<E> listIterator(int index) {
1417	<	return new SubItr(this, index + offset);
1417	>	return new SubItr<E>(this, index + offset);
1418		}
1419
1420		public E remove(int index) {
1421	<	E result;
1371	<	SequenceLock lock = list.lock;
1421	>	final SequenceLock lock = list.lock;
1422		lock.lock();
1423		try {
1424	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1424	>	Object[] items = list.array;
1425		int i = index + offset;
1426	<	result = (E)list.array[i];
1427	<	list.internalRemoveAt(i);
1426	>	if (index < 0 || index >= size || i >= items.length)
1427	>	throw new ArrayIndexOutOfBoundsException(index);
1428	>	@SuppressWarnings("unchecked")
1429	>	E result = (E) items[i];
1430	>	list.rawRemoveAt(i);
1431		size--;
1432	+	return result;
1433		} finally {
1434		lock.unlock();
1435		}
1383	–	return result;
1436		}
1437
1438		public boolean remove(Object o) {
1439	<	boolean removed = false;
1388	<	SequenceLock lock = list.lock;
1439	>	final SequenceLock lock = list.lock;
1440		lock.lock();
1441		try {
1442	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1443	<	offset+size))) {
1393	<	removed = true;
1442	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1443	>	offset + size))) {
1444		--size;
1445	+	return true;
1446		}
1447	+	else
1448	+	return false;
1449		} finally {
1450		lock.unlock();
1451		}
1399	–	return removed;
1452		}
1453
1454		public boolean removeAll(Collection<?> c) {
1455	<	return list.internalRemoveAll(c, offset, size);
1455	>	return list.internalRemoveAll(c, offset, offset + size);
1456		}
1457
1458		public boolean retainAll(Collection<?> c) {
1459	<	return list.internalRetainAll(c, offset, size);
1459	>	return list.internalRetainAll(c, offset, offset + size);
1460		}
1461
1462		public E set(int index, E element) {
#	Line 1422 | Line 1474 | public class ReadMostlyVector<E> impleme
1474		int ssize = toIndex - fromIndex;
1475		if (fromIndex < 0 || toIndex > c || ssize < 0)
1476		throw new IndexOutOfBoundsException();
1477	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1477	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1478		}
1479
1480		public Object[] toArray() {
1481	<	return list.internalToArray(offset, size);
1481	>	return list.internalToArray(offset, offset + size);
1482		}
1483
1484		public <T> T[] toArray(T[] a) {
1485	<	return list.internalToArray(a, offset, size);
1485	>	return list.internalToArray(a, offset, offset + size);
1486		}
1487
1488		public String toString() {
1489	<	return list.internalToString(offset, size);
1489	>	return list.internalToString(offset, offset + size);
1490		}
1491
1492		}
#	Line 1444 | Line 1496 | public class ReadMostlyVector<E> impleme
1496		final ReadMostlyVector<E> list;
1497		final SequenceLock lock;
1498		Object[] items;
1499	<	Object next, prev;
1499	>	E next, prev;
1500		long seq;
1501		int cursor;
1502		int fence;
1503		int lastRet;
1504	<	boolean haveNext, havePrev;
1504	>	boolean validNext, validPrev;
1505
1506		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1507		this.sublist = sublist;
#	Line 1463 | Line 1515 | public class ReadMostlyVector<E> impleme
1515		}
1516
1517		private void refresh() {
1518	+	validNext = validPrev = false;
1519		do {
1520	+	int n;
1521		seq = lock.awaitAvailability();
1522		items = list.array;
1523	<	int c = list.count;
1523	>	if ((n = list.count) > items.length)
1524	>	continue;
1525		int b = sublist.offset + sublist.size;
1526	<	fence = b < c ? b : c;
1526	>	fence = b < n ? b : n;
1527		} while (lock.getSequence() != seq);
1528		}
1529
1530	+	@SuppressWarnings("unchecked")
1531		public boolean hasNext() {
1532	+	boolean valid;
1533		int i = cursor;
1534	<	while (i < fence && i >= 0) {
1534	>	for (;;) {
1535	>	if (i >= fence || i < 0 || i >= items.length) {
1536	>	valid = false;
1537	>	break;
1538	>	}
1539	>	next = (E) items[i];
1540		if (lock.getSequence() == seq) {
1541	<	next = items[i];
1542	<	return haveNext = true;
1541	>	valid = true;
1542	>	break;
1543		}
1544		refresh();
1545		}
1546	<	return false;
1546	>	return validNext = valid;
1547		}
1548
1549	+	@SuppressWarnings("unchecked")
1550		public boolean hasPrevious() {
1551	<	int i = cursor;
1552	<	while (i <= fence && i > 0) {
1551	>	boolean valid;
1552	>	int i = cursor - 1;
1553	>	for (;;) {
1554	>	if (i >= fence || i < 0 || i >= items.length) {
1555	>	valid = false;
1556	>	break;
1557	>	}
1558	>	prev = (E) items[i];
1559		if (lock.getSequence() == seq) {
1560	<	prev = items[i - 1];
1561	<	return havePrev = true;
1560	>	valid = true;
1561	>	break;
1562		}
1563		refresh();
1564		}
1565	<	return false;
1565	>	return validPrev = valid;
1566		}
1567
1568		public E next() {
1569	<	if (!haveNext && !hasNext())
1570	<	throw new NoSuchElementException();
1571	<	haveNext = false;
1572	<	lastRet = cursor++;
1573	<	return (E) next;
1569	>	if (validNext || hasNext()) {
1570	>	validNext = false;
1571	>	lastRet = cursor++;
1572	>	return next;
1573	>	}
1574	>	throw new NoSuchElementException();
1575		}
1576
1577		public E previous() {
1578	<	if (!havePrev && !hasPrevious())
1579	<	throw new NoSuchElementException();
1580	<	havePrev = false;
1581	<	lastRet = cursor--;
1582	<	return (E) prev;
1578	>	if (validPrev || hasPrevious()) {
1579	>	validPrev = false;
1580	>	lastRet = cursor--;
1581	>	return prev;
1582	>	}
1583	>	throw new NoSuchElementException();
1584		}
1585
1586		public int nextIndex() {

Diff Legend

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