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.8 by jsr166, Mon Jul 18 15:24:08 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. Alternatvely,
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 35 | Line 37 | public class ReadMostlyVector<E> impleme
37
38		/*
39		* This class exists mainly as a vehicle to exercise various
40	<	* constructions using SequenceLocks, which are not yet explained
41	<	* well here.
40	>	* constructions using SequenceLocks. Read-only methods
41	>	* take one of a few forms:
42	>	*
43	>	* Short methods,including get(index), continually retry obtaining
44	>	* a snapshot of array, count, and element, using sequence number
45	>	* to validate.
46	>	*
47	>	* Methods that are potentially O(n) (or worse) try once in
48	>	* read-only mode, and then lock. When in read-only mode, they
49	>	* validate only at the end of an array scan unless the element is
50	>	* actually used (for example, as an argument of method equals).
51		*/
52
53		/**
#	Line 143 | Line 154 | public class ReadMostlyVector<E> impleme
154		* as well as sublist and iterator classes.
155		*/
156
157	<	static int internalIndexOf(Object o, Object[] items,
158	<	int index, int fence) {
157	>	// Version of indexOf that returns -1 if either not present or invalid
158	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
159	>	long seq) {
160	>	for (int i = index; i < fence; ++i) {
161	>	Object e = items[i];
162	>	if (lock.getSequence() != seq)
163	>	break;
164	>	if ((x == null) ? e == null : x.equals(e))
165	>	return i;
166	>	}
167	>	return -1;
168	>	}
169	>
170	>	final int rawIndexOf(Object x, int index, int fence) {
171	>	Object[] items = array;
172		for (int i = index; i < fence; ++i) {
173	<	Object x = items[i];
174	<	if (o == null? x == null : (x != null && o.equals(x)))
173	>	Object e = items[i];
174	>	if ((x == null) ? e == null : x.equals(e))
175	>	return i;
176	>	}
177	>	return -1;
178	>	}
179	>
180	>	final int validatedLastIndexOf(Object x, Object[] items,
181	>	int index, int origin, long seq) {
182	>	for (int i = index; i >= origin; --i) {
183	>	Object e = items[i];
184	>	if (lock.getSequence() != seq)
185	>	break;
186	>	if ((x == null) ? e == null : x.equals(e))
187		return i;
188		}
189		return -1;
190		}
191
192	<	static int internalLastIndexOf(Object o, Object[] items,
193	<	int index, int origin) {
192	>	final int rawLastIndexOf(Object x, int index, int origin) {
193	>	Object[] items = array;
194		for (int i = index; i >= origin; --i) {
195	<	Object x = items[i];
196	<	if (o == null? x == null : (x != null && o.equals(x)))
195	>	Object e = items[i];
196	>	if ((x == null) ? e == null : x.equals(e))
197		return i;
198		}
199		return -1;
200		}
201
202	<	final void internalAdd(E e) {
203	<	int c = count;
204	<	if (c >= array.length)
205	<	grow(c + 1);
206	<	array[c] = e;
207	<	count = c + 1;
202	>	final void rawAdd(Object e) {
203	>	int n = count;
204	>	if (n >= array.length)
205	>	grow(n + 1);
206	>	array[n] = e;
207	>	count = n + 1;
208		}
209
210	<	final void internalAddAt(int index, E e) {
211	<	int c = count;
212	<	if (index > c)
210	>	final void rawAddAt(int index, Object e) {
211	>	int n = count;
212	>	if (index > n)
213		throw new ArrayIndexOutOfBoundsException(index);
214	<	if (c >= array.length)
215	<	grow(c + 1);
216	<	System.arraycopy(array, index, array, index + 1, c - index);
214	>	if (n >= array.length)
215	>	grow(n + 1);
216	>	if (index < n)
217	>	System.arraycopy(array, index, array, index + 1, n - index);
218		array[index] = e;
219	<	count = c + 1;
219	>	count = n + 1;
220		}
221
222	<	final boolean internalAddAllAt(int index, Object[] elements) {
223	<	int c = count;
224	<	if (index < 0 || index > c)
222	>	final boolean rawAddAllAt(int index, Object[] elements) {
223	>	int n = count;
224	>	if (index < 0 || index > n)
225		throw new ArrayIndexOutOfBoundsException(index);
226		int len = elements.length;
227		if (len == 0)
228		return false;
229	<	int newCount = c + len;
229	>	int newCount = n + len;
230		if (newCount >= array.length)
231		grow(newCount);
232		int mv = count - index;
#	Line 200 | Line 237 | public class ReadMostlyVector<E> impleme
237		return true;
238		}
239
240	<	final boolean internalRemoveAt(int index) {
241	<	int c = count - 1;
242	<	if (index < 0 || index > c)
240	>	final boolean rawRemoveAt(int index) {
241	>	int n = count - 1;
242	>	if (index < 0 || index > n)
243		return false;
244	<	int mv = c - index;
244	>	int mv = n - index;
245		if (mv > 0)
246		System.arraycopy(array, index + 1, array, index, mv);
247	<	array[c] = null;
248	<	count = c;
247	>	array[n] = null;
248	>	count = n;
249		return true;
250		}
251
252		/**
253		* Internal version of removeAll for lists and sublists. In this
254	<	* and other similar methods below, the span argument is, if
255	<	* non-negative, the purported size of a list/sublist, or is left
256	<	* negative if the size should be determined via count field under
257	<	* lock.
254	>	* and other similar methods below, the bound argument is, if
255	>	* non-negative, the purported upper bound of a list/sublist, or
256	>	* is left negative if the bound should be determined via count
257	>	* field under lock.
258		*/
259	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
259	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
260		SequenceLock lock = this.lock;
261		boolean removed = false;
262		lock.lock();
263		try {
264	<	int fence = count;
265	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
264	>	int n = count;
265	>	int fence = bound < 0 || bound > n ? n : bound;
266		if (origin >= 0 && origin < fence) {
267		for (Object x : c) {
268	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
268	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
269		removed = true;
270		}
271		}
#	Line 240 | Line 275 | public class ReadMostlyVector<E> impleme
275		return removed;
276		}
277
278	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
278	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
279		SequenceLock lock = this.lock;
280		boolean removed = false;
281		if (c != this) {
282		lock.lock();
283		try {
284		int i = origin;
285	<	int fence = count;
286	<	if (span >= 0 && origin + span < fence)
287	<	fence = origin + span;
253	<	while (i < fence) {
285	>	int n = count;
286	>	int fence = bound < 0 || bound > n ? n : bound;
287	>	while (i >= 0 && i < fence) {
288		if (c.contains(array[i]))
289		++i;
290		else {
#	Line 268 | Line 302 | public class ReadMostlyVector<E> impleme
302		return removed;
303		}
304
305	<	final void internalClear(int origin, int span) {
306	<	int c = count;
307	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
305	>	final void internalClear(int origin, int bound) {
306	>	int n = count;
307	>	int fence = bound < 0 || bound > n ? n : bound;
308		if (origin >= 0 && origin < fence) {
309		int removed = fence - origin;
310	<	int newCount = c - removed;
311	<	int mv = c - (origin + removed);
310	>	int newCount = n - removed;
311	>	int mv = n - (origin + removed);
312		if (mv > 0)
313		System.arraycopy(array, origin + removed, array, origin, mv);
314	<	for (int i = c; i < newCount; ++i)
314	>	for (int i = n; i < newCount; ++i)
315		array[i] = null;
316		count = newCount;
317		}
318		}
319
320	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
320	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
321		SequenceLock lock = this.lock;
322		boolean contained;
323		boolean locked = false;
#	Line 294 | Line 326 | public class ReadMostlyVector<E> impleme
326		long seq = lock.awaitAvailability();
327		Object[] items = array;
328		int len = items.length;
329	<	int c = count;
330	<	if (c > len)
329	>	int n = count;
330	>	if (n > len)
331		continue;
332	<	int fence = c;
333	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
332	>	int fence = bound < 0 || bound > n ? n : bound;
333	>	if (origin < 0)
334		contained = false;
335		else {
336		contained = true;
337	<	for (Object e : coll) {
338	<	if (internalIndexOf(e, items, origin, fence) < 0) {
337	>	for (Object e : c) {
338	>	int idx = (locked ?
339	>	rawIndexOf(e, origin, fence) :
340	>	validatedIndexOf(e, items, origin,
341	>	fence, seq));
342	>	if (idx < 0) {
343		contained = false;
344		break;
345		}
#	Line 323 | Line 357 | public class ReadMostlyVector<E> impleme
357		return contained;
358		}
359
360	<	final boolean internalEquals(List<?> list, int origin, int span) {
360	>	final boolean internalEquals(List<?> list, int origin, int bound) {
361		SequenceLock lock = this.lock;
328	–	boolean equal;
362		boolean locked = false;
363	+	boolean equal;
364		try {
365		for (;;) {
332	–	equal = true;
366		long seq = lock.awaitAvailability();
367		Object[] items = array;
368	<	int len = items.length;
369	<	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)
368	>	int n = count;
369	>	if (n > items.length || origin < 0)
370		equal = false;
371		else {
372	+	equal = true;
373	+	int fence = bound < 0 || bound > n ? n : bound;
374		Iterator<?> it = list.iterator();
375		for (int i = origin; i < fence; ++i) {
376	<	if (!it.hasNext()) {
377	<	equal = false;
378	<	break;
379	<	}
380	<	Object x = it.next();
381	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
376	>	Object x = items[i];
377	>	Object y;
378	>	if ((!locked && lock.getSequence() != seq) ||
379	>	!it.hasNext() ||
380	>	(y = it.next()) == null ?
381	>	x != null : !y.equals(x)) {
382		equal = false;
383		break;
384		}
#	Line 370 | Line 398 | public class ReadMostlyVector<E> impleme
398		return equal;
399		}
400
401	<	final int internalHashCode(int origin, int span) {
401	>	final int internalHashCode(int origin, int bound) {
402		SequenceLock lock = this.lock;
403		int hash;
404		boolean locked = false;
#	Line 380 | Line 408 | public class ReadMostlyVector<E> impleme
408		long seq = lock.awaitAvailability();
409		Object[] items = array;
410		int len = items.length;
411	<	int c = count;
412	<	if (c > len)
411	>	int n = count;
412	>	if (n > len)
413		continue;
414	<	int fence = c;
415	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
414	>	int fence = bound < 0 || bound > n ? n : bound;
415	>	if (origin >= 0) {
416		for (int i = origin; i < fence; ++i) {
417		Object e = items[i];
418		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 430 | public class ReadMostlyVector<E> impleme
430		return hash;
431		}
432
433	<	final String internalToString(int origin, int span) {
433	>	final String internalToString(int origin, int bound) {
434		SequenceLock lock = this.lock;
435		String ret;
436		boolean locked = false;
437		try {
438	<	for (;;) {
438	>	outer:for (;;) {
439		long seq = lock.awaitAvailability();
440		Object[] items = array;
441		int len = items.length;
442	<	int c = count;
443	<	if (c > len)
442	>	int n = count;
443	>	if (n > len)
444		continue;
445	<	int fence = c;
446	<	if (span >= 0 && origin + span < fence)
447	<	fence = origin + span;
448	<	if (origin >= 0 && fence <= c) {
449	<	if (origin == fence)
450	<	ret = "[]";
451	<	else {
452	<	StringBuilder sb = new StringBuilder();
453	<	sb.append('[');
454	<	for (int i = origin;;) {
455	<	Object e = items[i];
456	<	sb.append(e == this ? "(this Collection)" : e);
457	<	if (++i < fence)
458	<	sb.append(',').append(' ');
459	<	else {
460	<	ret = sb.append(']').toString();
461	<	break;
462	<	}
445	>	int fence = bound < 0 || bound > n ? n : bound;
446	>	if (origin < 0 || origin == fence)
447	>	ret = "[]";
448	>	else {
449	>	StringBuilder sb = new StringBuilder();
450	>	sb.append('[');
451	>	for (int i = origin;;) {
452	>	Object e = items[i];
453	>	if (e == this)
454	>	sb.append("(this Collection)");
455	>	else if (!locked && lock.getSequence() != seq)
456	>	continue outer;
457	>	else
458	>	sb.append(e.toString());
459	>	if (++i < fence)
460	>	sb.append(',').append(' ');
461	>	else {
462	>	ret = sb.append(']').toString();
463	>	break;
464		}
465		}
439	–	if (lock.getSequence() == seq)
440	–	break;
466		}
467	+	if (lock.getSequence() == seq)
468	+	break;
469		lock.lock();
470		locked = true;
471		}
#	Line 449 | Line 476 | public class ReadMostlyVector<E> impleme
476		return ret;
477		}
478
479	<	final Object[] internalToArray(int origin, int span) {
479	>	final Object[] internalToArray(int origin, int bound) {
480		Object[] result;
481		SequenceLock lock = this.lock;
482		boolean locked = false;
#	Line 459 | Line 486 | public class ReadMostlyVector<E> impleme
486		long seq = lock.awaitAvailability();
487		Object[] items = array;
488		int len = items.length;
489	<	int c = count;
490	<	int fence = c;
491	<	if (span >= 0 && origin + span < fence)
492	<	fence = origin + span;
493	<	if (c <= len && fence <= len) {
489	>	int n = count;
490	>	if (n > len)
491	>	continue;
492	>	int fence = bound < 0 || bound > n ? n : bound;
493	>	if (origin >= 0)
494		result = Arrays.copyOfRange(items, origin, fence,
495		Object[].class);
496	<	if (lock.getSequence() == seq)
497	<	break;
471	<	}
496	>	if (lock.getSequence() == seq)
497	>	break;
498		lock.lock();
499		locked = true;
500		}
#	Line 479 | Line 505 | public class ReadMostlyVector<E> impleme
505		return result;
506		}
507
508	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
508	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
509	>	int alen = a.length;
510		T[] result;
511		SequenceLock lock = this.lock;
512		boolean locked = false;
#	Line 488 | Line 515 | public class ReadMostlyVector<E> impleme
515		long seq = lock.awaitAvailability();
516		Object[] items = array;
517		int len = items.length;
518	<	int c = count;
519	<	int fence = c;
520	<	if (span >= 0 && origin + span < fence)
521	<	fence = origin + span;
522	<	if (c <= len && fence <= len) {
523	<	if (a.length < count)
524	<	result = (T[]) Arrays.copyOfRange(array, origin,
525	<	fence, a.getClass());
526	<	else {
527	<	int n = fence - origin;
528	<	System.arraycopy(array, 0, a, origin, fence - origin);
529	<	if (a.length > n)
530	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
518	>	int n = count;
519	>	if (n > len)
520	>	continue;
521	>	int fence = bound < 0 || bound > n ? n : bound;
522	>	int rlen = fence - origin;
523	>	if (rlen < 0)
524	>	rlen = 0;
525	>	if (origin < 0 || alen >= rlen) {
526	>	if (rlen > 0)
527	>	System.arraycopy(array, 0, a, origin, rlen);
528	>	if (alen > rlen)
529	>	a[rlen] = null;
530	>	result = a;
531		}
532	+	else
533	+	result = (T[]) Arrays.copyOfRange(array, origin,
534	+	fence, a.getClass());
535	+	if (lock.getSequence() == seq)
536	+	break;
537		lock.lock();
538		locked = true;
539		}
#	Line 522 | Line 550 | public class ReadMostlyVector<E> impleme
550		SequenceLock lock = this.lock;
551		lock.lock();
552		try {
553	<	internalAdd(e);
553	>	rawAdd(e);
554		} finally {
555		lock.unlock();
556		}
#	Line 533 | Line 561 | public class ReadMostlyVector<E> impleme
561		SequenceLock lock = this.lock;
562		lock.lock();
563		try {
564	<	internalAddAt(index, element);
564	>	rawAddAt(index, element);
565		} finally {
566		lock.unlock();
567		}
#	Line 564 | Line 592 | public class ReadMostlyVector<E> impleme
592		Object[] elements = c.toArray();
593		lock.lock();
594		try {
595	<	ret = internalAddAllAt(index, elements);
595	>	ret = rawAddAllAt(index, elements);
596		} finally {
597		lock.unlock();
598		}
#	Line 596 | Line 624 | public class ReadMostlyVector<E> impleme
624		return true;
625		if (!(o instanceof List))
626		return false;
627	<	return internalEquals((List<?>)(o), 0, -1);
627	>	return internalEquals((List<?>)o, 0, -1);
628		}
629
630		public E get(int index) {
#	Line 604 | Line 632 | public class ReadMostlyVector<E> impleme
632		for (;;) {
633		long seq = lock.awaitAvailability();
634		Object[] items = array;
635	<	int len = items.length;
636	<	int c = count;
609	<	if (c > len)
635	>	int n = count;
636	>	if (n > items.length)
637		continue;
638	<	E e; boolean ex;
639	<	if (index < 0 || index >= c) {
638	>	Object e; boolean ex;
639	>	if (index < 0 || index >= n) {
640		e = null;
641		ex = true;
642		}
643		else {
644	<	e = (E)items[index];
644	>	e = items[index];
645		ex = false;
646		}
647		if (lock.getSequence() == seq) {
648		if (ex)
649		throw new ArrayIndexOutOfBoundsException(index);
650		else
651	<	return e;
651	>	return (E)e;
652		}
653		}
654		}
#	Line 632 | Line 659 | public class ReadMostlyVector<E> impleme
659
660		public int indexOf(Object o) {
661		SequenceLock lock = this.lock;
662	<	long seq = lock.awaitAvailability();
663	<	Object[] items = array;
664	<	int c = count;
665	<	if (c <= items.length) {
666	<	int idx = internalIndexOf(o, items, 0, c);
667	<	if (lock.getSequence() == seq)
668	<	return idx;
669	<	}
670	<	lock.lock();
671	<	try {
672	<	return internalIndexOf(o, array, 0, count);
673	<	} finally {
674	<	lock.unlock();
662	>	for (;;) {
663	>	long seq = lock.awaitAvailability();
664	>	Object[] items = array;
665	>	int n = count;
666	>	if (n <= items.length) {
667	>	for (int i = 0; i < n; ++i) {
668	>	Object e = items[i];
669	>	if (lock.getSequence() != seq) {
670	>	lock.lock();
671	>	try {
672	>	return rawIndexOf(o, 0, count);
673	>	} finally {
674	>	lock.unlock();
675	>	}
676	>	}
677	>	else if ((o == null) ? e == null : o.equals(e))
678	>	return i;
679	>	}
680	>	return -1;
681	>	}
682		}
683		}
684
#	Line 659 | Line 693 | public class ReadMostlyVector<E> impleme
693
694		public int lastIndexOf(Object o) {
695		SequenceLock lock = this.lock;
696	<	long seq = lock.awaitAvailability();
697	<	Object[] items = array;
698	<	int c = count;
699	<	if (c <= items.length) {
700	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
701	<	if (lock.getSequence() == seq)
702	<	return idx;
703	<	}
704	<	lock.lock();
705	<	try {
706	<	return internalLastIndexOf(o, array, count-1, 0);
707	<	} finally {
708	<	lock.unlock();
696	>	for (;;) {
697	>	long seq = lock.awaitAvailability();
698	>	Object[] items = array;
699	>	int n = count;
700	>	if (n <= items.length) {
701	>	for (int i = n - 1; i >= 0; --i) {
702	>	Object e = items[i];
703	>	if (lock.getSequence() != seq) {
704	>	lock.lock();
705	>	try {
706	>	return rawLastIndexOf(o, 0, count);
707	>	} finally {
708	>	lock.unlock();
709	>	}
710	>	}
711	>	else if ((o == null) ? e == null : o.equals(e))
712	>	return i;
713	>	}
714	>	return -1;
715	>	}
716		}
717		}
718
#	Line 685 | Line 726 | public class ReadMostlyVector<E> impleme
726
727		public E remove(int index) {
728		SequenceLock lock = this.lock;
729	<	E oldValue;
729	>	Object oldValue;
730		lock.lock();
731		try {
732		if (index < 0 || index >= count)
733		throw new ArrayIndexOutOfBoundsException(index);
734	<	oldValue = (E)array[index];
735	<	internalRemoveAt(index);
734	>	oldValue = array[index];
735	>	rawRemoveAt(index);
736		} finally {
737		lock.unlock();
738		}
739	<	return oldValue;
739	>	return (E)oldValue;
740		}
741
742		public boolean remove(Object o) {
#	Line 703 | Line 744 | public class ReadMostlyVector<E> impleme
744		boolean removed;
745		lock.lock();
746		try {
747	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
747	>	removed = rawRemoveAt(rawIndexOf(o, 0, count));
748		} finally {
749		lock.unlock();
750		}
#	Line 719 | Line 760 | public class ReadMostlyVector<E> impleme
760		}
761
762		public E set(int index, E element) {
763	<	E oldValue;
763	>	Object oldValue;
764		SequenceLock lock = this.lock;
765		lock.lock();
766		try {
767		if (index < 0 || index >= count)
768		throw new ArrayIndexOutOfBoundsException(index);
769	<	oldValue = (E)array[index];
769	>	oldValue = array[index];
770		array[index] = element;
771		} finally {
772		lock.unlock();
773		}
774	<	return oldValue;
774	>	return (E)oldValue;
775		}
776
777		public int size() {
#	Line 771 | Line 812 | public class ReadMostlyVector<E> impleme
812		SequenceLock lock = this.lock;
813		lock.lock();
814		try {
815	<	if (internalIndexOf(e, array, 0, count) < 0) {
816	<	internalAdd(e);
815	>	if (rawIndexOf(e, 0, count) < 0) {
816	>	rawAdd(e);
817		added = true;
818		}
819		else
#	Line 803 | Line 844 | public class ReadMostlyVector<E> impleme
844		try {
845		for (int i = 0; i < clen; ++i) {
846		Object e = cs[i];
847	<	if (internalIndexOf(e, array, 0, count) < 0) {
848	<	internalAdd((E)e);
847	>	if (rawIndexOf(e, 0, count) < 0) {
848	>	rawAdd(e);
849		++added;
850		}
851		}
#	Line 815 | Line 856 | public class ReadMostlyVector<E> impleme
856		return added;
857		}
858
859	+	/**
860	+	* Returns an iterator operating over a snapshot copy of the
861	+	* elements of this collection created upon construction of the
862	+	* iterator. The iterator does <em>NOT</em> support the
863	+	* <tt>remove</tt> method.
864	+	*
865	+	* @return an iterator over the elements in this list in proper sequence
866	+	*/
867	+	public Iterator<E> snapshotIterator() {
868	+	return new SnapshotIterator<E>(this);
869	+	}
870	+
871	+	static final class SnapshotIterator<E> implements Iterator<E> {
872	+	final Object[] items;
873	+	int cursor;
874	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
875	+	public boolean hasNext() { return cursor < items.length; }
876	+	public E next() {
877	+	if (cursor < items.length)
878	+	return (E) items[cursor++];
879	+	throw new NoSuchElementException();
880	+	}
881	+	public void remove() { throw new UnsupportedOperationException() ; }
882	+	}
883	+
884		// Vector-only methods
885
886		/** See {@link Vector#firstElement} */
#	Line 824 | Line 890 | public class ReadMostlyVector<E> impleme
890		long seq = lock.awaitAvailability();
891		Object[] items = array;
892		int len = items.length;
893	<	int c = count;
894	<	if (c > len || c < 0)
893	>	int n = count;
894	>	if (n > len)
895		continue;
896	<	E e; boolean ex;
897	<	if (c == 0) {
898	<	e = null;
899	<	ex = true;
896	>	Object e; boolean ex;
897	>	if (n > 0) {
898	>	e = items[0];
899	>	ex = false;
900		}
901		else {
902	<	e = (E)items[0];
903	<	ex = false;
902	>	e = null;
903	>	ex = true;
904		}
905		if (lock.getSequence() == seq) {
906		if (ex)
907		throw new NoSuchElementException();
908		else
909	<	return e;
909	>	return (E)e;
910		}
911		}
912		}
#	Line 852 | Line 918 | public class ReadMostlyVector<E> impleme
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;
927	<	ex = true;
924	>	Object e; boolean ex;
925	>	if (n > 0) {
926	>	e = items[n - 1];
927	>	ex = false;
928		}
929		else {
930	<	e = (E)items[c - 1];
931	<	ex = false;
930	>	e = null;
931	>	ex = true;
932		}
933		if (lock.getSequence() == seq) {
934		if (ex)
935		throw new NoSuchElementException();
936		else
937	<	return e;
937	>	return (E)e;
938		}
939		}
940		}
#	Line 880 | Line 946 | public class ReadMostlyVector<E> impleme
946		boolean ex = false;
947		long seq = lock.awaitAvailability();
948		Object[] items = array;
949	<	int c = count;
949	>	int n = count;
950		boolean retry = false;
951	<	if (c > items.length)
951	>	if (n > items.length)
952		retry = true;
953		else if (index < 0)
954		ex = true;
955		else
956	<	idx = internalIndexOf(o, items, index, c);
956	>	idx = validatedIndexOf(o, items, index, n, seq);
957		if (retry || lock.getSequence() != seq) {
958		lock.lock();
959		try {
960		if (index < 0)
961		ex = true;
962		else
963	<	idx = internalIndexOf(o, array, 0, count);
963	>	idx = rawIndexOf(o, 0, count);
964		} finally {
965		lock.unlock();
966		}
#	Line 911 | Line 977 | public class ReadMostlyVector<E> impleme
977		boolean ex = false;
978		long seq = lock.awaitAvailability();
979		Object[] items = array;
980	<	int c = count;
980	>	int n = count;
981		boolean retry = false;
982	<	if (c > items.length)
982	>	if (n > items.length)
983		retry = true;
984	<	else if (index >= c)
984	>	else if (index >= n)
985		ex = true;
986		else
987	<	idx = internalLastIndexOf(o, items, index, 0);
987	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
988		if (retry || lock.getSequence() != seq) {
989		lock.lock();
990		try {
991		if (index >= count)
992		ex = true;
993		else
994	<	idx = internalLastIndexOf(o, array, index, 0);
994	>	idx = rawLastIndexOf(o, index, 0);
995		} finally {
996		lock.unlock();
997		}
#	Line 942 | Line 1008 | public class ReadMostlyVector<E> impleme
1008		SequenceLock lock = this.lock;
1009		lock.lock();
1010		try {
1011	<	int c = count;
1012	<	if (newSize > c)
1011	>	int n = count;
1012	>	if (newSize > n)
1013		grow(newSize);
1014		else {
1015	<	for (int i = newSize ; i < c ; i++)
1015	>	for (int i = newSize ; i < n ; i++)
1016		array[i] = null;
1017		}
1018		count = newSize;
#	Line 1043 | Line 1109 | public class ReadMostlyVector<E> impleme
1109		public Object clone() {
1110		SequenceLock lock = this.lock;
1111		Object[] a = null;
1046	–	int c;
1112		boolean retry = false;
1113		long seq = lock.awaitAvailability();
1114		Object[] items = array;
1115	<	c = count;
1116	<	if (c <= items.length)
1117	<	a = Arrays.copyOf(items, c);
1115	>	int n = count;
1116	>	if (n <= items.length)
1117	>	a = Arrays.copyOf(items, n);
1118		else
1119		retry = true;
1120		if (retry || lock.getSequence() != seq) {
1121		lock.lock();
1122		try {
1123	<	c = count;
1124	<	a = Arrays.copyOf(array, c);
1123	>	n = count;
1124	>	a = Arrays.copyOf(array, n);
1125		} finally {
1126		lock.unlock();
1127		}
1128		}
1129	<	return new ReadMostlyVector(a, c, capacityIncrement);
1129	>	return new ReadMostlyVector(a, n, capacityIncrement);
1130		}
1131
1132		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1149 | public class ReadMostlyVector<E> impleme
1149		int cursor;
1150		int fence;
1151		int lastRet;
1152	<	boolean haveNext, havePrev;
1152	>	boolean validNext, validPrev;
1153
1154		Itr(ReadMostlyVector<E> list, int index) {
1155		this.list = list;
#	Line 1097 | Line 1162 | public class ReadMostlyVector<E> impleme
1162		}
1163
1164		private void refresh() {
1165	+	validNext = validPrev = false;
1166		do {
1167		seq = lock.awaitAvailability();
1168		items = list.array;
1169	<	fence = list.count;
1170	<	} while (lock.getSequence() != seq);
1169	>	} while ((fence = list.count) > items.length ||
1170	>	lock.getSequence() != seq);
1171		}
1172
1173		public boolean hasNext() {
1174	+	boolean valid;
1175		int i = cursor;
1176	<	while (i < fence && i >= 0) {
1176	>	for (;;) {
1177	>	if (i >= fence || i < 0 || i >= items.length) {
1178	>	valid = false;
1179	>	break;
1180	>	}
1181	>	next = items[i];
1182		if (lock.getSequence() == seq) {
1183	<	next = items[i];
1184	<	return haveNext = true;
1183	>	valid = true;
1184	>	break;
1185		}
1186		refresh();
1187		}
1188	<	return false;
1188	>	return validNext = valid;
1189		}
1190
1191		public boolean hasPrevious() {
1192	<	int i = cursor;
1193	<	while (i <= fence && i > 0) {
1192	>	boolean valid;
1193	>	int i = cursor - 1;
1194	>	for (;;) {
1195	>	if (i >= fence || i < 0 || i >= items.length) {
1196	>	valid = false;
1197	>	break;
1198	>	}
1199	>	prev = items[i];
1200		if (lock.getSequence() == seq) {
1201	<	prev = items[i - 1];
1202	<	return havePrev = true;
1201	>	valid = true;
1202	>	break;
1203		}
1204		refresh();
1205		}
1206	<	return false;
1206	>	return validPrev = valid;
1207		}
1208
1209		public E next() {
1210	<	if (!haveNext && !hasNext())
1211	<	throw new NoSuchElementException();
1212	<	haveNext = false;
1213	<	lastRet = cursor++;
1214	<	return (E) next;
1210	>	if (validNext || hasNext()) {
1211	>	validNext = false;
1212	>	lastRet = cursor++;
1213	>	return (E) next;
1214	>	}
1215	>	throw new NoSuchElementException();
1216		}
1217
1218		public E previous() {
1219	<	if (!havePrev && !hasPrevious())
1220	<	throw new NoSuchElementException();
1221	<	havePrev = false;
1222	<	lastRet = cursor--;
1223	<	return (E) prev;
1219	>	if (validPrev || hasPrevious()) {
1220	>	validPrev = false;
1221	>	lastRet = cursor--;
1222	>	return (E) prev;
1223	>	}
1224	>	throw new NoSuchElementException();
1225		}
1226
1227		public void remove() {
#	Line 1217 | Line 1297 | public class ReadMostlyVector<E> impleme
1297		lock.lock();
1298		try {
1299		int c = size;
1300	<	list.internalAddAt(c + offset, element);
1300	>	list.rawAddAt(c + offset, element);
1301		size = c + 1;
1302		} finally {
1303		lock.unlock();
#	Line 1231 | Line 1311 | public class ReadMostlyVector<E> impleme
1311		try {
1312		if (index < 0 || index > size)
1313		throw new ArrayIndexOutOfBoundsException(index);
1314	<	list.internalAddAt(index + offset, element);
1314	>	list.rawAddAt(index + offset, element);
1315		++size;
1316		} finally {
1317		lock.unlock();
#	Line 1246 | Line 1326 | public class ReadMostlyVector<E> impleme
1326		try {
1327		int s = size;
1328		int pc = list.count;
1329	<	list.internalAddAllAt(offset + s, elements);
1329	>	list.rawAddAllAt(offset + s, elements);
1330		added = list.count - pc;
1331		size = s + added;
1332		} finally {
#	Line 1265 | Line 1345 | public class ReadMostlyVector<E> impleme
1345		if (index < 0 || index > s)
1346		throw new ArrayIndexOutOfBoundsException(index);
1347		int pc = list.count;
1348	<	list.internalAddAllAt(index + offset, elements);
1348	>	list.rawAddAllAt(index + offset, elements);
1349		added = list.count - pc;
1350		size = s + added;
1351		} finally {
#	Line 1278 | Line 1358 | public class ReadMostlyVector<E> impleme
1358		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) {
#	Line 1317 | Line 1397 | public class ReadMostlyVector<E> impleme
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 1344 | Line 1425 | public class ReadMostlyVector<E> impleme
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 1367 | Line 1448 | public class ReadMostlyVector<E> impleme
1448		}
1449
1450		public E remove(int index) {
1451	<	E result;
1451	>	Object result;
1452		SequenceLock lock = list.lock;
1453		lock.lock();
1454		try {
1455	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1455	>	Object[] items = list.array;
1456		int i = index + offset;
1457	<	result = (E)list.array[i];
1458	<	list.internalRemoveAt(i);
1457	>	if (index < 0 || index >= size || i >= items.length)
1458	>	throw new ArrayIndexOutOfBoundsException(index);
1459	>	result = items[i];
1460	>	list.rawRemoveAt(i);
1461		size--;
1462		} finally {
1463		lock.unlock();
1464		}
1465	<	return result;
1465	>	return (E)result;
1466		}
1467
1468		public boolean remove(Object o) {
#	Line 1388 | Line 1470 | public class ReadMostlyVector<E> impleme
1470		SequenceLock lock = list.lock;
1471		lock.lock();
1472		try {
1473	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1474	<	offset+size))) {
1473	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1474	>	offset + size))) {
1475		removed = true;
1476		--size;
1477		}
#	Line 1400 | Line 1482 | public class ReadMostlyVector<E> impleme
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 1426 | Line 1508 | public class ReadMostlyVector<E> impleme
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 1449 | Line 1531 | public class ReadMostlyVector<E> impleme
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		public boolean hasNext() {
1561	+	boolean valid;
1562		int i = cursor;
1563	<	while (i < fence && i >= 0) {
1563	>	for (;;) {
1564	>	if (i >= fence || i < 0 || i >= items.length) {
1565	>	valid = false;
1566	>	break;
1567	>	}
1568	>	next = items[i];
1569		if (lock.getSequence() == seq) {
1570	<	next = items[i];
1571	<	return haveNext = true;
1570	>	valid = true;
1571	>	break;
1572		}
1573		refresh();
1574		}
1575	<	return false;
1575	>	return validNext = valid;
1576		}
1577
1578		public boolean hasPrevious() {
1579	<	int i = cursor;
1580	<	while (i <= fence && i > 0) {
1579	>	boolean valid;
1580	>	int i = cursor - 1;
1581	>	for (;;) {
1582	>	if (i >= fence || i < 0 || i >= items.length) {
1583	>	valid = false;
1584	>	break;
1585	>	}
1586	>	prev = items[i];
1587		if (lock.getSequence() == seq) {
1588	<	prev = items[i - 1];
1589	<	return havePrev = true;
1588	>	valid = true;
1589	>	break;
1590		}
1591		refresh();
1592		}
1593	<	return false;
1593	>	return validPrev = valid;
1594		}
1595
1596		public E next() {
1597	<	if (!haveNext && !hasNext())
1598	<	throw new NoSuchElementException();
1599	<	haveNext = false;
1600	<	lastRet = cursor++;
1601	<	return (E) next;
1597	>	if (validNext || hasNext()) {
1598	>	validNext = false;
1599	>	lastRet = cursor++;
1600	>	return (E) next;
1601	>	}
1602	>	throw new NoSuchElementException();
1603		}
1604
1605		public E previous() {
1606	<	if (!havePrev && !hasPrevious())
1607	<	throw new NoSuchElementException();
1608	<	havePrev = false;
1609	<	lastRet = cursor--;
1610	<	return (E) prev;
1606	>	if (validPrev || hasPrevious()) {
1607	>	validPrev = false;
1608	>	lastRet = cursor--;
1609	>	return (E) prev;
1610	>	}
1611	>	throw new NoSuchElementException();
1612		}
1613
1614		public int nextIndex() {

Diff Legend

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