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.14 by jsr166, Sun Dec 4 01:25:16 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
54		/**
#	Line 46 | Line 58 | public class ReadMostlyVector<E> impleme
58		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
59
60		// fields are non-private to simpify nested class access
61	<	Object[] array;
61	>	volatile Object[] array;
62		final SequenceLock lock;
63	<	int count;
63	>	volatile int count;
64		final int capacityIncrement;
65
66		/**
#	Line 118 | Line 130 | public class ReadMostlyVector<E> impleme
130		}
131
132		// For explanation, see CopyOnWriteArrayList
133	<	final void grow(int minCapacity) {
133	>	final Object[] grow(int minCapacity) {
134		int oldCapacity = array.length;
135		int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
136		capacityIncrement : oldCapacity);
#	Line 126 | Line 138 | public class ReadMostlyVector<E> impleme
138		newCapacity = minCapacity;
139		if (newCapacity - MAX_ARRAY_SIZE > 0)
140		newCapacity = hugeCapacity(minCapacity);
141	<	array = Arrays.copyOf(array, newCapacity);
141	>	return array = Arrays.copyOf(array, newCapacity);
142		}
143
144		static int hugeCapacity(int minCapacity) {
#	Line 143 | Line 155 | public class ReadMostlyVector<E> impleme
155		* as well as sublist and iterator classes.
156		*/
157
158	<	static int internalIndexOf(Object o, Object[] items,
159	<	int index, int fence) {
158	>	// Version of indexOf that returns -1 if either not present or invalid
159	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
160	>	long seq) {
161	>	for (int i = index; i < fence; ++i) {
162	>	Object e = items[i];
163	>	if (lock.getSequence() != seq)
164	>	break;
165	>	if ((x == null) ? e == null : x.equals(e))
166	>	return i;
167	>	}
168	>	return -1;
169	>	}
170	>
171	>	final int rawIndexOf(Object x, int index, int fence) {
172	>	Object[] items = array;
173		for (int i = index; i < fence; ++i) {
174	<	Object x = items[i];
175	<	if (o == null? x == null : (x != null && o.equals(x)))
174	>	Object e = items[i];
175	>	if ((x == null) ? e == null : x.equals(e))
176		return i;
177		}
178		return -1;
179		}
180
181	<	static int internalLastIndexOf(Object o, Object[] items,
182	<	int index, int origin) {
181	>	final int validatedLastIndexOf(Object x, Object[] items,
182	>	int index, int origin, long seq) {
183		for (int i = index; i >= origin; --i) {
184	<	Object x = items[i];
185	<	if (o == null? x == null : (x != null && o.equals(x)))
184	>	Object e = items[i];
185	>	if (lock.getSequence() != seq)
186	>	break;
187	>	if ((x == null) ? e == null : x.equals(e))
188		return i;
189		}
190		return -1;
191		}
192
193	<	final void internalAdd(E e) {
194	<	int c = count;
195	<	if (c >= array.length)
196	<	grow(c + 1);
197	<	array[c] = e;
198	<	count = c + 1;
193	>	final int rawLastIndexOf(Object x, int index, int origin) {
194	>	Object[] items = array;
195	>	for (int i = index; i >= origin; --i) {
196	>	Object e = items[i];
197	>	if ((x == null) ? e == null : x.equals(e))
198	>	return i;
199	>	}
200	>	return -1;
201		}
202
203	<	final void internalAddAt(int index, E e) {
204	<	int c = count;
205	<	if (index > c)
203	>	final void rawAdd(E e) {
204	>	int n = count;
205	>	Object[] items = array;
206	>	if (n >= items.length)
207	>	items = grow(n + 1);
208	>	items[n] = e;
209	>	count = n + 1;
210	>	}
211	>
212	>	final void rawAddAt(int index, E e) {
213	>	int n = count;
214	>	Object[] items = array;
215	>	if (index > n)
216		throw new ArrayIndexOutOfBoundsException(index);
217	<	if (c >= array.length)
218	<	grow(c + 1);
219	<	System.arraycopy(array, index, array, index + 1, c - index);
220	<	array[index] = e;
221	<	count = c + 1;
217	>	if (n >= items.length)
218	>	items = grow(n + 1);
219	>	if (index < n)
220	>	System.arraycopy(items, index, items, index + 1, n - index);
221	>	items[index] = e;
222	>	count = n + 1;
223		}
224
225	<	final boolean internalAddAllAt(int index, Object[] elements) {
226	<	int c = count;
227	<	if (index < 0 || index > c)
225	>	final boolean rawAddAllAt(int index, Object[] elements) {
226	>	int n = count;
227	>	Object[] items = array;
228	>	if (index < 0 || index > n)
229		throw new ArrayIndexOutOfBoundsException(index);
230		int len = elements.length;
231		if (len == 0)
232		return false;
233	<	int newCount = c + len;
234	<	if (newCount >= array.length)
235	<	grow(newCount);
236	<	int mv = count - index;
233	>	int newCount = n + len;
234	>	if (newCount >= items.length)
235	>	items = grow(newCount);
236	>	int mv = n - index;
237		if (mv > 0)
238	<	System.arraycopy(array, index, array, index + len, mv);
239	<	System.arraycopy(elements, 0, array, index, len);
238	>	System.arraycopy(items, index, items, index + len, mv);
239	>	System.arraycopy(elements, 0, items, index, len);
240		count = newCount;
241		return true;
242		}
243
244	<	final boolean internalRemoveAt(int index) {
245	<	int c = count - 1;
246	<	if (index < 0 || index > c)
244	>	final boolean rawRemoveAt(int index) {
245	>	int n = count - 1;
246	>	Object[] items = array;
247	>	if (index < 0 || index > n)
248		return false;
249	<	int mv = c - index;
249	>	int mv = n - index;
250		if (mv > 0)
251	<	System.arraycopy(array, index + 1, array, index, mv);
252	<	array[c] = null;
253	<	count = c;
251	>	System.arraycopy(items, index + 1, items, index, mv);
252	>	items[n] = null;
253	>	count = n;
254		return true;
255		}
256
257		/**
258		* Internal version of removeAll for lists and sublists. In this
259	<	* and other similar methods below, the span argument is, if
260	<	* non-negative, the purported size of a list/sublist, or is left
261	<	* negative if the size should be determined via count field under
262	<	* lock.
259	>	* and other similar methods below, the bound argument is, if
260	>	* non-negative, the purported upper bound of a list/sublist, or
261	>	* is left negative if the bound should be determined via count
262	>	* field under lock.
263		*/
264	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
265	<	SequenceLock lock = this.lock;
264	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
265	>	final SequenceLock lock = this.lock;
266		boolean removed = false;
267		lock.lock();
268		try {
269	<	int fence = count;
270	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
269	>	int n = count;
270	>	int fence = bound < 0 || bound > n ? n : bound;
271		if (origin >= 0 && origin < fence) {
272		for (Object x : c) {
273	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
273	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
274		removed = true;
275		}
276		}
#	Line 240 | Line 280 | public class ReadMostlyVector<E> impleme
280		return removed;
281		}
282
283	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
284	<	SequenceLock lock = this.lock;
283	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
284	>	final SequenceLock lock = this.lock;
285		boolean removed = false;
286		if (c != this) {
287		lock.lock();
288		try {
289	+	Object[] items = array;
290		int i = origin;
291	<	int fence = count;
292	<	if (span >= 0 && origin + span < fence)
293	<	fence = origin + span;
294	<	while (i < fence) {
254	<	if (c.contains(array[i]))
291	>	int n = count;
292	>	int fence = bound < 0 || bound > n ? n : bound;
293	>	while (i >= 0 && i < fence) {
294	>	if (c.contains(items[i]))
295		++i;
296		else {
297		--fence;
298	<	int mv = --count - i;
298	>	int mv = --n - i;
299		if (mv > 0)
300	<	System.arraycopy(array, i + 1, array, i, mv);
261	<	removed = true;
300	>	System.arraycopy(items, i + 1, items, i, mv);
301		}
302		}
303	+	if (count != n) {
304	+	count = n;
305	+	removed = true;
306	+	}
307		} finally {
308		lock.unlock();
309		}
#	Line 268 | Line 311 | public class ReadMostlyVector<E> impleme
311		return removed;
312		}
313
314	<	final void internalClear(int origin, int span) {
315	<	int c = count;
316	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
314	>	final void internalClear(int origin, int bound) {
315	>	int n = count;
316	>	int fence = bound < 0 || bound > n ? n : bound;
317		if (origin >= 0 && origin < fence) {
318	+	Object[] items = array;
319		int removed = fence - origin;
320	<	int newCount = c - removed;
321	<	int mv = c - (origin + removed);
320	>	int newCount = n - removed;
321	>	int mv = n - (origin + removed);
322		if (mv > 0)
323	<	System.arraycopy(array, origin + removed, array, origin, mv);
324	<	for (int i = c; i < newCount; ++i)
325	<	array[i] = null;
323	>	System.arraycopy(items, origin + removed, items, origin, mv);
324	>	for (int i = n; i < newCount; ++i)
325	>	items[i] = null;
326		count = newCount;
327		}
328		}
329
330	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
331	<	SequenceLock lock = this.lock;
330	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
331	>	final SequenceLock lock = this.lock;
332		boolean contained;
333		boolean locked = false;
334		try {
335		for (;;) {
336		long seq = lock.awaitAvailability();
337	+	int n = count;
338		Object[] items = array;
339		int len = items.length;
340	<	int c = count;
298	<	if (c > len)
340	>	if (n > len)
341		continue;
342	<	int fence = c;
343	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
342	>	int fence = bound < 0 || bound > n ? n : bound;
343	>	if (origin < 0)
344		contained = false;
345		else {
346		contained = true;
347	<	for (Object e : coll) {
348	<	if (internalIndexOf(e, items, origin, fence) < 0) {
347	>	for (Object e : c) {
348	>	int idx = (locked ?
349	>	rawIndexOf(e, origin, fence) :
350	>	validatedIndexOf(e, items, origin,
351	>	fence, seq));
352	>	if (idx < 0) {
353		contained = false;
354		break;
355		}
#	Line 323 | Line 367 | public class ReadMostlyVector<E> impleme
367		return contained;
368		}
369
370	<	final boolean internalEquals(List<?> list, int origin, int span) {
371	<	SequenceLock lock = this.lock;
328	<	boolean equal;
370	>	final boolean internalEquals(List<?> list, int origin, int bound) {
371	>	final SequenceLock lock = this.lock;
372		boolean locked = false;
373	+	boolean equal;
374		try {
375		for (;;) {
332	–	equal = true;
376		long seq = lock.awaitAvailability();
377		Object[] items = array;
378	<	int len = items.length;
379	<	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)
378	>	int n = count;
379	>	if (n > items.length || origin < 0)
380		equal = false;
381		else {
382	+	equal = true;
383	+	int fence = bound < 0 || bound > n ? n : bound;
384		Iterator<?> it = list.iterator();
385		for (int i = origin; i < fence; ++i) {
386	<	if (!it.hasNext()) {
387	<	equal = false;
388	<	break;
389	<	}
390	<	Object x = it.next();
391	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
386	>	Object x = items[i];
387	>	Object y;
388	>	if ((!locked && lock.getSequence() != seq) ||
389	>	!it.hasNext() ||
390	>	(y = it.next()) == null ?
391	>	x != null : !y.equals(x)) {
392		equal = false;
393		break;
394		}
#	Line 370 | Line 408 | public class ReadMostlyVector<E> impleme
408		return equal;
409		}
410
411	<	final int internalHashCode(int origin, int span) {
412	<	SequenceLock lock = this.lock;
411	>	final int internalHashCode(int origin, int bound) {
412	>	final SequenceLock lock = this.lock;
413		int hash;
414		boolean locked = false;
415		try {
#	Line 379 | Line 417 | public class ReadMostlyVector<E> impleme
417		hash = 1;
418		long seq = lock.awaitAvailability();
419		Object[] items = array;
420	+	int n = count;
421		int len = items.length;
422	<	int c = count;
384	<	if (c > len)
422	>	if (n > len)
423		continue;
424	<	int fence = c;
425	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
424	>	int fence = bound < 0 || bound > n ? n : bound;
425	>	if (origin >= 0) {
426		for (int i = origin; i < fence; ++i) {
427		Object e = items[i];
428		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 440 | public class ReadMostlyVector<E> impleme
440		return hash;
441		}
442
443	<	final String internalToString(int origin, int span) {
444	<	SequenceLock lock = this.lock;
443	>	final String internalToString(int origin, int bound) {
444	>	final SequenceLock lock = this.lock;
445		String ret;
446		boolean locked = false;
447		try {
448	<	for (;;) {
448	>	outer:for (;;) {
449		long seq = lock.awaitAvailability();
450		Object[] items = array;
451	+	int n = count;
452		int len = items.length;
453	<	int c = count;
417	<	if (c > len)
453	>	if (n > len)
454		continue;
455	<	int fence = c;
456	<	if (span >= 0 && origin + span < fence)
457	<	fence = origin + span;
458	<	if (origin >= 0 && fence <= c) {
459	<	if (origin == fence)
460	<	ret = "[]";
461	<	else {
462	<	StringBuilder sb = new StringBuilder();
463	<	sb.append('[');
464	<	for (int i = origin;;) {
465	<	Object e = items[i];
466	<	sb.append(e == this ? "(this Collection)" : e);
467	<	if (++i < fence)
468	<	sb.append(',').append(' ');
469	<	else {
470	<	ret = sb.append(']').toString();
471	<	break;
472	<	}
455	>	int fence = bound < 0 || bound > n ? n : bound;
456	>	if (origin < 0 || origin == fence)
457	>	ret = "[]";
458	>	else {
459	>	StringBuilder sb = new StringBuilder();
460	>	sb.append('[');
461	>	for (int i = origin;;) {
462	>	Object e = items[i];
463	>	if (e == this)
464	>	sb.append("(this Collection)");
465	>	else if (!locked && lock.getSequence() != seq)
466	>	continue outer;
467	>	else
468	>	sb.append(e.toString());
469	>	if (++i < fence)
470	>	sb.append(',').append(' ');
471	>	else {
472	>	ret = sb.append(']').toString();
473	>	break;
474		}
475		}
439	–	if (lock.getSequence() == seq)
440	–	break;
476		}
477	+	if (lock.getSequence() == seq)
478	+	break;
479		lock.lock();
480		locked = true;
481		}
#	Line 449 | Line 486 | public class ReadMostlyVector<E> impleme
486		return ret;
487		}
488
489	<	final Object[] internalToArray(int origin, int span) {
489	>	final Object[] internalToArray(int origin, int bound) {
490		Object[] result;
491	<	SequenceLock lock = this.lock;
491	>	final SequenceLock lock = this.lock;
492		boolean locked = false;
493		try {
494		for (;;) {
495		result = null;
496		long seq = lock.awaitAvailability();
497		Object[] items = array;
498	+	int n = count;
499		int len = items.length;
500	<	int c = count;
501	<	int fence = c;
502	<	if (span >= 0 && origin + span < fence)
503	<	fence = origin + span;
466	<	if (c <= len && fence <= len) {
500	>	if (n > len)
501	>	continue;
502	>	int fence = bound < 0 || bound > n ? n : bound;
503	>	if (origin >= 0)
504		result = Arrays.copyOfRange(items, origin, fence,
505		Object[].class);
506	<	if (lock.getSequence() == seq)
507	<	break;
471	<	}
506	>	if (lock.getSequence() == seq)
507	>	break;
508		lock.lock();
509		locked = true;
510		}
#	Line 479 | Line 515 | public class ReadMostlyVector<E> impleme
515		return result;
516		}
517
518	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
518	>	@SuppressWarnings("unchecked")
519	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
520	>	int alen = a.length;
521		T[] result;
522	<	SequenceLock lock = this.lock;
522	>	final SequenceLock lock = this.lock;
523		boolean locked = false;
524		try {
525		for (;;) {
526		long seq = lock.awaitAvailability();
527		Object[] items = array;
528	+	int n = count;
529		int len = items.length;
530	<	int c = count;
531	<	int fence = c;
532	<	if (span >= 0 && origin + span < fence)
533	<	fence = origin + span;
534	<	if (c <= len && fence <= len) {
535	<	if (a.length < count)
536	<	result = (T[]) Arrays.copyOfRange(array, origin,
537	<	fence, a.getClass());
538	<	else {
539	<	int n = fence - origin;
540	<	System.arraycopy(array, 0, a, origin, fence - origin);
541	<	if (a.length > n)
503	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
530	>	if (n > len)
531	>	continue;
532	>	int fence = bound < 0 || bound > n ? n : bound;
533	>	int rlen = fence - origin;
534	>	if (rlen < 0)
535	>	rlen = 0;
536	>	if (origin < 0 || alen >= rlen) {
537	>	if (rlen > 0)
538	>	System.arraycopy(items, 0, a, origin, rlen);
539	>	if (alen > rlen)
540	>	a[rlen] = null;
541	>	result = a;
542		}
543	+	else
544	+	result = (T[]) Arrays.copyOfRange(items, origin,
545	+	fence, a.getClass());
546	+	if (lock.getSequence() == seq)
547	+	break;
548		lock.lock();
549		locked = true;
550		}
#	Line 519 | Line 558 | public class ReadMostlyVector<E> impleme
558		// public List methods
559
560		public boolean add(E e) {
561	<	SequenceLock lock = this.lock;
561	>	final SequenceLock lock = this.lock;
562		lock.lock();
563		try {
564	<	internalAdd(e);
564	>	rawAdd(e);
565		} finally {
566		lock.unlock();
567		}
#	Line 530 | Line 569 | public class ReadMostlyVector<E> impleme
569		}
570
571		public void add(int index, E element) {
572	<	SequenceLock lock = this.lock;
572	>	final SequenceLock lock = this.lock;
573		lock.lock();
574		try {
575	<	internalAddAt(index, element);
575	>	rawAddAt(index, element);
576		} finally {
577		lock.unlock();
578		}
#	Line 544 | Line 583 | public class ReadMostlyVector<E> impleme
583		int len = elements.length;
584		if (len == 0)
585		return false;
586	<	SequenceLock lock = this.lock;
586	>	final SequenceLock lock = this.lock;
587		lock.lock();
588		try {
589	<	int newCount = count + len;
590	<	if (newCount >= array.length)
591	<	grow(newCount);
592	<	System.arraycopy(elements, 0, array, count, len);
589	>	Object[] items = array;
590	>	int n = count;
591	>	int newCount = n + len;
592	>	if (newCount >= items.length)
593	>	items = grow(newCount);
594	>	System.arraycopy(elements, 0, items, n, len);
595		count = newCount;
596		} finally {
597		lock.unlock();
#	Line 559 | Line 600 | public class ReadMostlyVector<E> impleme
600		}
601
602		public boolean addAll(int index, Collection<? extends E> c) {
603	<	SequenceLock lock = this.lock;
603	>	final SequenceLock lock = this.lock;
604		boolean ret;
605		Object[] elements = c.toArray();
606		lock.lock();
607		try {
608	<	ret = internalAddAllAt(index, elements);
608	>	ret = rawAddAllAt(index, elements);
609		} finally {
610		lock.unlock();
611		}
#	Line 572 | Line 613 | public class ReadMostlyVector<E> impleme
613		}
614
615		public void clear() {
616	<	SequenceLock lock = this.lock;
616	>	final SequenceLock lock = this.lock;
617		lock.lock();
618		try {
619	<	for (int i = 0; i < count; i++)
620	<	array[i] = null;
619	>	int n = count;
620	>	Object[] items = array;
621	>	for (int i = 0; i < n; i++)
622	>	items[i] = null;
623		count = 0;
624		} finally {
625		lock.unlock();
#	Line 596 | Line 639 | public class ReadMostlyVector<E> impleme
639		return true;
640		if (!(o instanceof List))
641		return false;
642	<	return internalEquals((List<?>)(o), 0, -1);
642	>	return internalEquals((List<?>)o, 0, -1);
643		}
644
645		public E get(int index) {
646	<	SequenceLock lock = this.lock;
646	>	final SequenceLock lock = this.lock;
647		for (;;) {
648		long seq = lock.awaitAvailability();
649	+	int n = count;
650		Object[] items = array;
651	<	int len = items.length;
608	<	int c = count;
609	<	if (c > len)
651	>	if (n > items.length)
652		continue;
653	<	E e; boolean ex;
654	<	if (index < 0 || index >= c) {
655	<	e = null;
614	<	ex = true;
615	<	}
616	<	else {
617	<	e = (E)items[index];
618	<	ex = false;
619	<	}
653	>	boolean outOfBounds = (index < 0 || index >= n);
654	>	@SuppressWarnings("unchecked")
655	>	E e = outOfBounds ? null : (E) items[index];
656		if (lock.getSequence() == seq) {
657	<	if (ex)
657	>	if (outOfBounds)
658		throw new ArrayIndexOutOfBoundsException(index);
659		else
660		return e;
#	Line 631 | Line 667 | public class ReadMostlyVector<E> impleme
667		}
668
669		public int indexOf(Object o) {
670	<	SequenceLock lock = this.lock;
671	<	long seq = lock.awaitAvailability();
672	<	Object[] items = array;
673	<	int c = count;
674	<	if (c <= items.length) {
675	<	int idx = internalIndexOf(o, items, 0, c);
676	<	if (lock.getSequence() == seq)
677	<	return idx;
678	<	}
679	<	lock.lock();
680	<	try {
681	<	return internalIndexOf(o, array, 0, count);
682	<	} finally {
683	<	lock.unlock();
670	>	final SequenceLock lock = this.lock;
671	>	for (;;) {
672	>	long seq = lock.awaitAvailability();
673	>	Object[] items = array;
674	>	int n = count;
675	>	if (n <= items.length) {
676	>	for (int i = 0; i < n; ++i) {
677	>	Object e = items[i];
678	>	if (lock.getSequence() != seq) {
679	>	lock.lock();
680	>	try {
681	>	return rawIndexOf(o, 0, count);
682	>	} finally {
683	>	lock.unlock();
684	>	}
685	>	}
686	>	else if ((o == null) ? e == null : o.equals(e))
687	>	return i;
688	>	}
689	>	return -1;
690	>	}
691		}
692		}
693
694		public boolean isEmpty() {
652	–	long ignore = lock.getSequence();
695		return count == 0;
696		}
697
698		public Iterator<E> iterator() {
699	<	return new Itr(this, 0);
699	>	return new Itr<E>(this, 0);
700		}
701
702		public int lastIndexOf(Object o) {
703	<	SequenceLock lock = this.lock;
704	<	long seq = lock.awaitAvailability();
705	<	Object[] items = array;
706	<	int c = count;
707	<	if (c <= items.length) {
708	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
709	<	if (lock.getSequence() == seq)
710	<	return idx;
711	<	}
712	<	lock.lock();
713	<	try {
714	<	return internalLastIndexOf(o, array, count-1, 0);
715	<	} finally {
716	<	lock.unlock();
703	>	final SequenceLock lock = this.lock;
704	>	for (;;) {
705	>	long seq = lock.awaitAvailability();
706	>	Object[] items = array;
707	>	int n = count;
708	>	if (n <= items.length) {
709	>	for (int i = n - 1; i >= 0; --i) {
710	>	Object e = items[i];
711	>	if (lock.getSequence() != seq) {
712	>	lock.lock();
713	>	try {
714	>	return rawLastIndexOf(o, 0, count);
715	>	} finally {
716	>	lock.unlock();
717	>	}
718	>	}
719	>	else if ((o == null) ? e == null : o.equals(e))
720	>	return i;
721	>	}
722	>	return -1;
723	>	}
724		}
725		}
726
727		public ListIterator<E> listIterator() {
728	<	return new Itr(this, 0);
728	>	return new Itr<E>(this, 0);
729		}
730
731		public ListIterator<E> listIterator(int index) {
732	<	return new Itr(this, index);
732	>	return new Itr<E>(this, index);
733		}
734
735		public E remove(int index) {
736	<	SequenceLock lock = this.lock;
688	<	E oldValue;
736	>	final SequenceLock lock = this.lock;
737		lock.lock();
738		try {
739		if (index < 0 || index >= count)
740		throw new ArrayIndexOutOfBoundsException(index);
741	<	oldValue = (E)array[index];
742	<	internalRemoveAt(index);
741	>	@SuppressWarnings("unchecked")
742	>	E oldValue = (E) array[index];
743	>	rawRemoveAt(index);
744	>	return oldValue;
745		} finally {
746		lock.unlock();
747		}
698	–	return oldValue;
748		}
749
750		public boolean remove(Object o) {
751	<	SequenceLock lock = this.lock;
703	<	boolean removed;
751	>	final SequenceLock lock = this.lock;
752		lock.lock();
753		try {
754	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
754	>	return rawRemoveAt(rawIndexOf(o, 0, count));
755		} finally {
756		lock.unlock();
757		}
710	–	return removed;
758		}
759
760		public boolean removeAll(Collection<?> c) {
#	Line 719 | Line 766 | public class ReadMostlyVector<E> impleme
766		}
767
768		public E set(int index, E element) {
769	<	E oldValue;
723	<	SequenceLock lock = this.lock;
769	>	final SequenceLock lock = this.lock;
770		lock.lock();
771		try {
772	+	Object[] items = array;
773		if (index < 0 || index >= count)
774		throw new ArrayIndexOutOfBoundsException(index);
775	<	oldValue = (E)array[index];
776	<	array[index] = element;
775	>	@SuppressWarnings("unchecked")
776	>	E oldValue = (E) items[index];
777	>	items[index] = element;
778	>	return oldValue;
779		} finally {
780		lock.unlock();
781		}
733	–	return oldValue;
782		}
783
784		public int size() {
737	–	long ignore = lock.getSequence();
785		return count;
786		}
787
#	Line 743 | Line 790 | public class ReadMostlyVector<E> impleme
790		int ssize = toIndex - fromIndex;
791		if (fromIndex < 0 || toIndex > c || ssize < 0)
792		throw new IndexOutOfBoundsException();
793	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
793	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
794		}
795
796		public Object[] toArray() {
#	Line 764 | Line 811 | public class ReadMostlyVector<E> impleme
811		* Append the element if not present.
812		*
813		* @param e element to be added to this list, if absent
814	<	* @return <tt>true</tt> if the element was added
814	>	* @return {@code true} if the element was added
815		*/
816		public boolean addIfAbsent(E e) {
817	<	boolean added;
771	<	SequenceLock lock = this.lock;
817	>	final SequenceLock lock = this.lock;
818		lock.lock();
819		try {
820	<	if (internalIndexOf(e, array, 0, count) < 0) {
821	<	internalAdd(e);
822	<	added = true;
820	>	if (rawIndexOf(e, 0, count) < 0) {
821	>	rawAdd(e);
822	>	return true;
823		}
824		else
825	<	added = false;
825	>	return false;
826		} finally {
827		lock.unlock();
828		}
783	–	return added;
829		}
830
831		/**
#	Line 802 | Line 847 | public class ReadMostlyVector<E> impleme
847		lock.lock();
848		try {
849		for (int i = 0; i < clen; ++i) {
850	<	Object e = cs[i];
851	<	if (internalIndexOf(e, array, 0, count) < 0) {
852	<	internalAdd((E)e);
850	>	@SuppressWarnings("unchecked")
851	>	E e = (E) cs[i];
852	>	if (rawIndexOf(e, 0, count) < 0) {
853	>	rawAdd(e);
854		++added;
855		}
856		}
#	Line 815 | Line 861 | public class ReadMostlyVector<E> impleme
861		return added;
862		}
863
864	+	/**
865	+	* Returns an iterator operating over a snapshot copy of the
866	+	* elements of this collection created upon construction of the
867	+	* iterator. The iterator does <em>NOT</em> support the
868	+	* {@code remove} method.
869	+	*
870	+	* @return an iterator over the elements in this list in proper sequence
871	+	*/
872	+	public Iterator<E> snapshotIterator() {
873	+	return new SnapshotIterator<E>(this);
874	+	}
875	+
876	+	static final class SnapshotIterator<E> implements Iterator<E> {
877	+	private final Object[] items;
878	+	private int cursor;
879	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
880	+	public boolean hasNext() { return cursor < items.length; }
881	+	@SuppressWarnings("unchecked")
882	+	public E next() {
883	+	if (cursor < items.length)
884	+	return (E) items[cursor++];
885	+	throw new NoSuchElementException();
886	+	}
887	+	public void remove() { throw new UnsupportedOperationException() ; }
888	+	}
889	+
890		// Vector-only methods
891
892		/** See {@link Vector#firstElement} */
893		public E firstElement() {
894	<	SequenceLock lock = this.lock;
894	>	final SequenceLock lock = this.lock;
895		for (;;) {
896		long seq = lock.awaitAvailability();
897		Object[] items = array;
898		int len = items.length;
899	<	int c = count;
900	<	if (c > len || c < 0)
899	>	int n = count;
900	>	if (n > len)
901		continue;
902	<	E e; boolean ex;
903	<	if (c == 0) {
904	<	e = null;
833	<	ex = true;
834	<	}
835	<	else {
836	<	e = (E)items[0];
837	<	ex = false;
838	<	}
902	>	boolean empty = (n == 0);
903	>	@SuppressWarnings("unchecked")
904	>	E e = empty ? null : (E) items[0];
905		if (lock.getSequence() == seq) {
906	<	if (ex)
906	>	if (empty)
907		throw new NoSuchElementException();
908		else
909		return e;
#	Line 847 | Line 913 | public class ReadMostlyVector<E> impleme
913
914		/** See {@link Vector#lastElement} */
915		public E lastElement() {
916	<	SequenceLock lock = this.lock;
916	>	final SequenceLock lock = this.lock;
917		for (;;) {
918		long seq = lock.awaitAvailability();
919		Object[] items = array;
920		int len = items.length;
921	<	int c = count;
922	<	if (c > len || c < 0)
921	>	int n = count;
922	>	if (n > len)
923		continue;
924	<	E e; boolean ex;
925	<	if (c == 0) {
926	<	e = null;
861	<	ex = true;
862	<	}
863	<	else {
864	<	e = (E)items[c - 1];
865	<	ex = false;
866	<	}
924	>	boolean empty = (n == 0);
925	>	@SuppressWarnings("unchecked")
926	>	E e = empty ? null : (E) items[n - 1];
927		if (lock.getSequence() == seq) {
928	<	if (ex)
928	>	if (empty)
929		throw new NoSuchElementException();
930		else
931		return e;
#	Line 875 | Line 935 | public class ReadMostlyVector<E> impleme
935
936		/** See {@link Vector#indexOf(Object, int)} */
937		public int indexOf(Object o, int index) {
938	<	SequenceLock lock = this.lock;
938	>	final SequenceLock lock = this.lock;
939		int idx = 0;
940		boolean ex = false;
941		long seq = lock.awaitAvailability();
942		Object[] items = array;
943	<	int c = count;
943	>	int n = count;
944		boolean retry = false;
945	<	if (c > items.length)
945	>	if (n > items.length)
946		retry = true;
947		else if (index < 0)
948		ex = true;
949		else
950	<	idx = internalIndexOf(o, items, index, c);
950	>	idx = validatedIndexOf(o, items, index, n, seq);
951		if (retry || lock.getSequence() != seq) {
952		lock.lock();
953		try {
954		if (index < 0)
955		ex = true;
956		else
957	<	idx = internalIndexOf(o, array, 0, count);
957	>	idx = rawIndexOf(o, 0, count);
958		} finally {
959		lock.unlock();
960		}
#	Line 906 | Line 966 | public class ReadMostlyVector<E> impleme
966
967		/** See {@link Vector#lastIndexOf(Object, int)} */
968		public int lastIndexOf(Object o, int index) {
969	<	SequenceLock lock = this.lock;
969	>	final SequenceLock lock = this.lock;
970		int idx = 0;
971		boolean ex = false;
972		long seq = lock.awaitAvailability();
973		Object[] items = array;
974	<	int c = count;
974	>	int n = count;
975		boolean retry = false;
976	<	if (c > items.length)
976	>	if (n > items.length)
977		retry = true;
978	<	else if (index >= c)
978	>	else if (index >= n)
979		ex = true;
980		else
981	<	idx = internalLastIndexOf(o, items, index, 0);
981	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
982		if (retry || lock.getSequence() != seq) {
983		lock.lock();
984		try {
985		if (index >= count)
986		ex = true;
987		else
988	<	idx = internalLastIndexOf(o, array, index, 0);
988	>	idx = rawLastIndexOf(o, index, 0);
989		} finally {
990		lock.unlock();
991		}
#	Line 939 | Line 999 | public class ReadMostlyVector<E> impleme
999		public void setSize(int newSize) {
1000		if (newSize < 0)
1001		throw new ArrayIndexOutOfBoundsException(newSize);
1002	<	SequenceLock lock = this.lock;
1002	>	final SequenceLock lock = this.lock;
1003		lock.lock();
1004		try {
1005	<	int c = count;
1006	<	if (newSize > c)
1005	>	int n = count;
1006	>	if (newSize > n)
1007		grow(newSize);
1008		else {
1009	<	for (int i = newSize ; i < c ; i++)
1010	<	array[i] = null;
1009	>	Object[] items = array;
1010	>	for (int i = newSize ; i < n ; i++)
1011	>	items[i] = null;
1012		}
1013		count = newSize;
1014		} finally {
#	Line 957 | Line 1018 | public class ReadMostlyVector<E> impleme
1018
1019		/** See {@link Vector#copyInto} */
1020		public void copyInto(Object[] anArray) {
1021	<	SequenceLock lock = this.lock;
1021	>	final SequenceLock lock = this.lock;
1022		lock.lock();
1023		try {
1024		System.arraycopy(array, 0, anArray, 0, count);
#	Line 968 | Line 1029 | public class ReadMostlyVector<E> impleme
1029
1030		/** See {@link Vector#trimToSize} */
1031		public void trimToSize() {
1032	<	SequenceLock lock = this.lock;
1032	>	final SequenceLock lock = this.lock;
1033		lock.lock();
1034		try {
1035	<	if (count < array.length)
1036	<	array = Arrays.copyOf(array, count);
1035	>	Object[] items = array;
1036	>	int n = count;
1037	>	if (n < items.length)
1038	>	array = Arrays.copyOf(items, n);
1039		} finally {
1040		lock.unlock();
1041		}
#	Line 981 | Line 1044 | public class ReadMostlyVector<E> impleme
1044		/** See {@link Vector#ensureCapacity} */
1045		public void ensureCapacity(int minCapacity) {
1046		if (minCapacity > 0) {
1047	<	SequenceLock lock = this.lock;
1047	>	final SequenceLock lock = this.lock;
1048		lock.lock();
1049		try {
1050		if (minCapacity - array.length > 0)
#	Line 994 | Line 1057 | public class ReadMostlyVector<E> impleme
1057
1058		/** See {@link Vector#elements} */
1059		public Enumeration<E> elements() {
1060	<	return new Itr(this, 0);
1060	>	return new Itr<E>(this, 0);
1061		}
1062
1063		/** See {@link Vector#capacity} */
1064		public int capacity() {
1002	–	long ignore = lock.getSequence();
1065		return array.length;
1066		}
1067
#	Line 1040 | Line 1102 | public class ReadMostlyVector<E> impleme
1102
1103		// other methods
1104
1105	<	public Object clone() {
1106	<	SequenceLock lock = this.lock;
1105	>	public ReadMostlyVector<E> clone() {
1106	>	final SequenceLock lock = this.lock;
1107		Object[] a = null;
1046	–	int c;
1108		boolean retry = false;
1109		long seq = lock.awaitAvailability();
1110		Object[] items = array;
1111	<	c = count;
1112	<	if (c <= items.length)
1113	<	a = Arrays.copyOf(items, c);
1111	>	int n = count;
1112	>	if (n <= items.length)
1113	>	a = Arrays.copyOf(items, n);
1114		else
1115		retry = true;
1116		if (retry || lock.getSequence() != seq) {
1117		lock.lock();
1118		try {
1119	<	c = count;
1120	<	a = Arrays.copyOf(array, c);
1119	>	n = count;
1120	>	a = Arrays.copyOf(array, n);
1121		} finally {
1122		lock.unlock();
1123		}
1124		}
1125	<	return new ReadMostlyVector(a, c, capacityIncrement);
1125	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1126		}
1127
1128		private void writeObject(java.io.ObjectOutputStream s)
1129		throws java.io.IOException {
1130	<	SequenceLock lock = this.lock;
1130	>	final SequenceLock lock = this.lock;
1131		lock.lock();
1132		try {
1133		s.defaultWriteObject();
#	Line 1079 | Line 1140 | public class ReadMostlyVector<E> impleme
1140		final ReadMostlyVector<E> list;
1141		final SequenceLock lock;
1142		Object[] items;
1143	<	Object next, prev;
1143	>	E next, prev;
1144		long seq;
1145		int cursor;
1146		int fence;
1147		int lastRet;
1148	<	boolean haveNext, havePrev;
1148	>	boolean validNext, validPrev;
1149
1150		Itr(ReadMostlyVector<E> list, int index) {
1151		this.list = list;
#	Line 1097 | Line 1158 | public class ReadMostlyVector<E> impleme
1158		}
1159
1160		private void refresh() {
1161	+	validNext = validPrev = false;
1162		do {
1163		seq = lock.awaitAvailability();
1164		items = list.array;
1165	<	fence = list.count;
1166	<	} while (lock.getSequence() != seq);
1165	>	} while ((fence = list.count) > items.length ||
1166	>	lock.getSequence() != seq);
1167		}
1168
1169	+	@SuppressWarnings("unchecked")
1170		public boolean hasNext() {
1171	+	boolean valid;
1172		int i = cursor;
1173	<	while (i < fence && i >= 0) {
1173	>	for (;;) {
1174	>	if (i >= fence || i < 0 || i >= items.length) {
1175	>	valid = false;
1176	>	break;
1177	>	}
1178	>	next = (E) items[i];
1179		if (lock.getSequence() == seq) {
1180	<	next = items[i];
1181	<	return haveNext = true;
1180	>	valid = true;
1181	>	break;
1182		}
1183		refresh();
1184		}
1185	<	return false;
1185	>	return validNext = valid;
1186		}
1187
1188	+	@SuppressWarnings("unchecked")
1189		public boolean hasPrevious() {
1190	<	int i = cursor;
1191	<	while (i <= fence && i > 0) {
1190	>	boolean valid;
1191	>	int i = cursor - 1;
1192	>	for (;;) {
1193	>	if (i >= fence || i < 0 || i >= items.length) {
1194	>	valid = false;
1195	>	break;
1196	>	}
1197	>	prev = (E) items[i];
1198		if (lock.getSequence() == seq) {
1199	<	prev = items[i - 1];
1200	<	return havePrev = true;
1199	>	valid = true;
1200	>	break;
1201		}
1202		refresh();
1203		}
1204	<	return false;
1204	>	return validPrev = valid;
1205		}
1206
1207		public E next() {
1208	<	if (!haveNext && !hasNext())
1209	<	throw new NoSuchElementException();
1210	<	haveNext = false;
1211	<	lastRet = cursor++;
1212	<	return (E) next;
1208	>	if (validNext || hasNext()) {
1209	>	validNext = false;
1210	>	lastRet = cursor++;
1211	>	return next;
1212	>	}
1213	>	throw new NoSuchElementException();
1214		}
1215
1216		public E previous() {
1217	<	if (!havePrev && !hasPrevious())
1218	<	throw new NoSuchElementException();
1219	<	havePrev = false;
1220	<	lastRet = cursor--;
1221	<	return (E) prev;
1217	>	if (validPrev || hasPrevious()) {
1218	>	validPrev = false;
1219	>	lastRet = cursor--;
1220	>	return prev;
1221	>	}
1222	>	throw new NoSuchElementException();
1223		}
1224
1225		public void remove() {
#	Line 1196 | Line 1274 | public class ReadMostlyVector<E> impleme
1274		public int previousIndex() { return cursor - 1; }
1275		}
1276
1277	<	static final class ReadMostlyVectorSublist<E> implements List<E>, RandomAccess, java.io.Serializable {
1277	>	static final class ReadMostlyVectorSublist<E>
1278	>	implements List<E>, RandomAccess, java.io.Serializable {
1279	>	static final long serialVersionUID = 3041673470172026059L;
1280	>
1281		final ReadMostlyVector<E> list;
1282		final int offset;
1283		volatile int size;
1284
1285	<	ReadMostlyVectorSublist(ReadMostlyVector<E> list, int offset, int size) {
1285	>	ReadMostlyVectorSublist(ReadMostlyVector<E> list,
1286	>	int offset, int size) {
1287		this.list = list;
1288		this.offset = offset;
1289		this.size = size;
#	Line 1213 | Line 1295 | public class ReadMostlyVector<E> impleme
1295		}
1296
1297		public boolean add(E element) {
1298	<	SequenceLock lock = list.lock;
1298	>	final SequenceLock lock = list.lock;
1299		lock.lock();
1300		try {
1301		int c = size;
1302	<	list.internalAddAt(c + offset, element);
1302	>	list.rawAddAt(c + offset, element);
1303		size = c + 1;
1304		} finally {
1305		lock.unlock();
#	Line 1226 | Line 1308 | public class ReadMostlyVector<E> impleme
1308		}
1309
1310		public void add(int index, E element) {
1311	<	SequenceLock lock = list.lock;
1311	>	final SequenceLock lock = list.lock;
1312		lock.lock();
1313		try {
1314		if (index < 0 || index > size)
1315		throw new ArrayIndexOutOfBoundsException(index);
1316	<	list.internalAddAt(index + offset, element);
1316	>	list.rawAddAt(index + offset, element);
1317		++size;
1318		} finally {
1319		lock.unlock();
#	Line 1240 | Line 1322 | public class ReadMostlyVector<E> impleme
1322
1323		public boolean addAll(Collection<? extends E> c) {
1324		Object[] elements = c.toArray();
1325	<	int added;
1244	<	SequenceLock lock = list.lock;
1325	>	final SequenceLock lock = list.lock;
1326		lock.lock();
1327		try {
1328		int s = size;
1329		int pc = list.count;
1330	<	list.internalAddAllAt(offset + s, elements);
1331	<	added = list.count - pc;
1330	>	list.rawAddAllAt(offset + s, elements);
1331	>	int added = list.count - pc;
1332		size = s + added;
1333	+	return added != 0;
1334		} finally {
1335		lock.unlock();
1336		}
1255	–	return added != 0;
1337		}
1338
1339		public boolean addAll(int index, Collection<? extends E> c) {
1340		Object[] elements = c.toArray();
1341	<	int added;
1261	<	SequenceLock lock = list.lock;
1341	>	final SequenceLock lock = list.lock;
1342		lock.lock();
1343		try {
1344		int s = size;
1345		if (index < 0 || index > s)
1346		throw new ArrayIndexOutOfBoundsException(index);
1347		int pc = list.count;
1348	<	list.internalAddAllAt(index + offset, elements);
1349	<	added = list.count - pc;
1348	>	list.rawAddAllAt(index + offset, elements);
1349	>	int added = list.count - pc;
1350		size = s + added;
1351	+	return added != 0;
1352		} finally {
1353		lock.unlock();
1354		}
1274	–	return added != 0;
1355		}
1356
1357		public void clear() {
1358	<	SequenceLock lock = list.lock;
1358	>	final SequenceLock lock = list.lock;
1359		lock.lock();
1360		try {
1361	<	list.internalClear(offset, size);
1361	>	list.internalClear(offset, offset + size);
1362		size = 0;
1363		} finally {
1364		lock.unlock();
#	Line 1290 | Line 1370 | public class ReadMostlyVector<E> impleme
1370		}
1371
1372		public boolean containsAll(Collection<?> c) {
1373	<	return list.internalContainsAll(c, offset, size);
1373	>	return list.internalContainsAll(c, offset, offset + size);
1374		}
1375
1376		public boolean equals(Object o) {
#	Line 1298 | Line 1378 | public class ReadMostlyVector<E> impleme
1378		return true;
1379		if (!(o instanceof List))
1380		return false;
1381	<	return list.internalEquals((List<?>)(o), offset, size);
1381	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1382		}
1383
1384		public E get(int index) {
#	Line 1308 | Line 1388 | public class ReadMostlyVector<E> impleme
1388		}
1389
1390		public int hashCode() {
1391	<	return list.internalHashCode(offset, size);
1391	>	return list.internalHashCode(offset, offset + size);
1392		}
1393
1394		public int indexOf(Object o) {
1395	<	SequenceLock lock = list.lock;
1395	>	final SequenceLock lock = list.lock;
1396		long seq = lock.awaitAvailability();
1397		Object[] items = list.array;
1398		int c = list.count;
1399		if (c <= items.length) {
1400	<	int idx = internalIndexOf(o, items, offset, offset+size);
1400	>	int idx = list.validatedIndexOf(o, items, offset,
1401	>	offset + size, seq);
1402		if (lock.getSequence() == seq)
1403		return idx < 0 ? -1 : idx - offset;
1404		}
1405		lock.lock();
1406		try {
1407	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1407	>	int idx = list.rawIndexOf(o, offset, offset + size);
1408		return idx < 0 ? -1 : idx - offset;
1409		} finally {
1410		lock.unlock();
#	Line 1335 | Line 1416 | public class ReadMostlyVector<E> impleme
1416		}
1417
1418		public Iterator<E> iterator() {
1419	<	return new SubItr(this, offset);
1419	>	return new SubItr<E>(this, offset);
1420		}
1421
1422		public int lastIndexOf(Object o) {
1423	<	SequenceLock lock = list.lock;
1423	>	final SequenceLock lock = list.lock;
1424		long seq = lock.awaitAvailability();
1425		Object[] items = list.array;
1426		int c = list.count;
1427		if (c <= items.length) {
1428	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1428	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1429	>	offset, seq);
1430		if (lock.getSequence() == seq)
1431		return idx < 0 ? -1 : idx - offset;
1432		}
1433		lock.lock();
1434		try {
1435	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1435	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1436		return idx < 0 ? -1 : idx - offset;
1437		} finally {
1438		lock.unlock();
#	Line 1359 | Line 1440 | public class ReadMostlyVector<E> impleme
1440		}
1441
1442		public ListIterator<E> listIterator() {
1443	<	return new SubItr(this, offset);
1443	>	return new SubItr<E>(this, offset);
1444		}
1445
1446		public ListIterator<E> listIterator(int index) {
1447	<	return new SubItr(this, index + offset);
1447	>	return new SubItr<E>(this, index + offset);
1448		}
1449
1450		public E remove(int index) {
1451	<	E result;
1371	<	SequenceLock lock = list.lock;
1451	>	final SequenceLock lock = list.lock;
1452		lock.lock();
1453		try {
1454	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1454	>	Object[] items = list.array;
1455		int i = index + offset;
1456	<	result = (E)list.array[i];
1457	<	list.internalRemoveAt(i);
1456	>	if (index < 0 || index >= size || i >= items.length)
1457	>	throw new ArrayIndexOutOfBoundsException(index);
1458	>	@SuppressWarnings("unchecked")
1459	>	E result = (E) items[i];
1460	>	list.rawRemoveAt(i);
1461		size--;
1462	+	return result;
1463		} finally {
1464		lock.unlock();
1465		}
1383	–	return result;
1466		}
1467
1468		public boolean remove(Object o) {
1469	<	boolean removed = false;
1388	<	SequenceLock lock = list.lock;
1469	>	final SequenceLock lock = list.lock;
1470		lock.lock();
1471		try {
1472	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1473	<	offset+size))) {
1393	<	removed = true;
1472	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1473	>	offset + size))) {
1474		--size;
1475	+	return true;
1476		}
1477	+	else
1478	+	return false;
1479		} finally {
1480		lock.unlock();
1481		}
1399	–	return removed;
1482		}
1483
1484		public boolean removeAll(Collection<?> c) {
1485	<	return list.internalRemoveAll(c, offset, size);
1485	>	return list.internalRemoveAll(c, offset, offset + size);
1486		}
1487
1488		public boolean retainAll(Collection<?> c) {
1489	<	return list.internalRetainAll(c, offset, size);
1489	>	return list.internalRetainAll(c, offset, offset + size);
1490		}
1491
1492		public E set(int index, E element) {
#	Line 1422 | Line 1504 | public class ReadMostlyVector<E> impleme
1504		int ssize = toIndex - fromIndex;
1505		if (fromIndex < 0 || toIndex > c || ssize < 0)
1506		throw new IndexOutOfBoundsException();
1507	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1507	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1508		}
1509
1510		public Object[] toArray() {
1511	<	return list.internalToArray(offset, size);
1511	>	return list.internalToArray(offset, offset + size);
1512		}
1513
1514		public <T> T[] toArray(T[] a) {
1515	<	return list.internalToArray(a, offset, size);
1515	>	return list.internalToArray(a, offset, offset + size);
1516		}
1517
1518		public String toString() {
1519	<	return list.internalToString(offset, size);
1519	>	return list.internalToString(offset, offset + size);
1520		}
1521
1522		}
#	Line 1444 | Line 1526 | public class ReadMostlyVector<E> impleme
1526		final ReadMostlyVector<E> list;
1527		final SequenceLock lock;
1528		Object[] items;
1529	<	Object next, prev;
1529	>	E next, prev;
1530		long seq;
1531		int cursor;
1532		int fence;
1533		int lastRet;
1534	<	boolean haveNext, havePrev;
1534	>	boolean validNext, validPrev;
1535
1536		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1537		this.sublist = sublist;
#	Line 1463 | Line 1545 | public class ReadMostlyVector<E> impleme
1545		}
1546
1547		private void refresh() {
1548	+	validNext = validPrev = false;
1549		do {
1550	+	int n;
1551		seq = lock.awaitAvailability();
1552		items = list.array;
1553	<	int c = list.count;
1553	>	if ((n = list.count) > items.length)
1554	>	continue;
1555		int b = sublist.offset + sublist.size;
1556	<	fence = b < c ? b : c;
1556	>	fence = b < n ? b : n;
1557		} while (lock.getSequence() != seq);
1558		}
1559
1560	+	@SuppressWarnings("unchecked")
1561		public boolean hasNext() {
1562	+	boolean valid;
1563		int i = cursor;
1564	<	while (i < fence && i >= 0) {
1564	>	for (;;) {
1565	>	if (i >= fence || i < 0 || i >= items.length) {
1566	>	valid = false;
1567	>	break;
1568	>	}
1569	>	next = (E) items[i];
1570		if (lock.getSequence() == seq) {
1571	<	next = items[i];
1572	<	return haveNext = true;
1571	>	valid = true;
1572	>	break;
1573		}
1574		refresh();
1575		}
1576	<	return false;
1576	>	return validNext = valid;
1577		}
1578
1579	+	@SuppressWarnings("unchecked")
1580		public boolean hasPrevious() {
1581	<	int i = cursor;
1582	<	while (i <= fence && i > 0) {
1581	>	boolean valid;
1582	>	int i = cursor - 1;
1583	>	for (;;) {
1584	>	if (i >= fence || i < 0 || i >= items.length) {
1585	>	valid = false;
1586	>	break;
1587	>	}
1588	>	prev = (E) items[i];
1589		if (lock.getSequence() == seq) {
1590	<	prev = items[i - 1];
1591	<	return havePrev = true;
1590	>	valid = true;
1591	>	break;
1592		}
1593		refresh();
1594		}
1595	<	return false;
1595	>	return validPrev = valid;
1596		}
1597
1598		public E next() {
1599	<	if (!haveNext && !hasNext())
1600	<	throw new NoSuchElementException();
1601	<	haveNext = false;
1602	<	lastRet = cursor++;
1603	<	return (E) next;
1599	>	if (validNext || hasNext()) {
1600	>	validNext = false;
1601	>	lastRet = cursor++;
1602	>	return next;
1603	>	}
1604	>	throw new NoSuchElementException();
1605		}
1606
1607		public E previous() {
1608	<	if (!havePrev && !hasPrevious())
1609	<	throw new NoSuchElementException();
1610	<	havePrev = false;
1611	<	lastRet = cursor--;
1612	<	return (E) prev;
1608	>	if (validPrev || hasPrevious()) {
1609	>	validPrev = false;
1610	>	lastRet = cursor--;
1611	>	return prev;
1612	>	}
1613	>	throw new NoSuchElementException();
1614		}
1615
1616		public int nextIndex() {

Diff Legend

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