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.5 by dl, Sat Jul 16 16:05:32 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 x = items[i];
162	<	if (o == null? x == null : (x != null && o.equals(x)))
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 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 634 | Line 661 | public class ReadMostlyVector<E> impleme
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;
664	>	int n = count;
665	>	if (n <= items.length) {
666	>	boolean valid = true;
667	>	for (int i = 0; i < n; ++i) {
668	>	Object e = items[i];
669	>	if (lock.getSequence() == seq) {
670	>	if (o == null? e == null : o.equals(e))
671	>	return i;
672	>	}
673	>	else {
674	>	valid = false;
675	>	break;
676	>	}
677	>	}
678	>	if (valid)
679	>	return -1;
680		}
681		lock.lock();
682		try {
683	<	return internalIndexOf(o, array, 0, count);
683	>	return rawIndexOf(o, 0, count);
684		} finally {
685		lock.unlock();
686		}
#	Line 661 | Line 699 | public class ReadMostlyVector<E> impleme
699		SequenceLock lock = this.lock;
700		long seq = lock.awaitAvailability();
701		Object[] items = array;
702	<	int c = count;
703	<	if (c <= items.length) {
704	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
702	>	int n = count;
703	>	if (n <= items.length) {
704	>	int idx = validatedLastIndexOf(o, items, n - 1, 0, seq);
705		if (lock.getSequence() == seq)
706		return idx;
707		}
708		lock.lock();
709		try {
710	<	return internalLastIndexOf(o, array, count-1, 0);
710	>	return rawLastIndexOf(o, count - 1, 0);
711		} finally {
712		lock.unlock();
713		}
#	Line 685 | Line 723 | public class ReadMostlyVector<E> impleme
723
724		public E remove(int index) {
725		SequenceLock lock = this.lock;
726	<	E oldValue;
726	>	Object oldValue;
727		lock.lock();
728		try {
729		if (index < 0 || index >= count)
730		throw new ArrayIndexOutOfBoundsException(index);
731	<	oldValue = (E)array[index];
732	<	internalRemoveAt(index);
731	>	oldValue = array[index];
732	>	rawRemoveAt(index);
733		} finally {
734		lock.unlock();
735		}
736	<	return oldValue;
736	>	return (E)oldValue;
737		}
738
739		public boolean remove(Object o) {
#	Line 703 | Line 741 | public class ReadMostlyVector<E> impleme
741		boolean removed;
742		lock.lock();
743		try {
744	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
744	>	removed = rawRemoveAt(rawIndexOf(o, 0, count));
745		} finally {
746		lock.unlock();
747		}
#	Line 719 | Line 757 | public class ReadMostlyVector<E> impleme
757		}
758
759		public E set(int index, E element) {
760	<	E oldValue;
760	>	Object oldValue;
761		SequenceLock lock = this.lock;
762		lock.lock();
763		try {
764		if (index < 0 || index >= count)
765		throw new ArrayIndexOutOfBoundsException(index);
766	<	oldValue = (E)array[index];
766	>	oldValue = array[index];
767		array[index] = element;
768		} finally {
769		lock.unlock();
770		}
771	<	return oldValue;
771	>	return (E)oldValue;
772		}
773
774		public int size() {
#	Line 771 | Line 809 | public class ReadMostlyVector<E> impleme
809		SequenceLock lock = this.lock;
810		lock.lock();
811		try {
812	<	if (internalIndexOf(e, array, 0, count) < 0) {
813	<	internalAdd(e);
812	>	if (rawIndexOf(e, 0, count) < 0) {
813	>	rawAdd(e);
814		added = true;
815		}
816		else
#	Line 803 | Line 841 | public class ReadMostlyVector<E> impleme
841		try {
842		for (int i = 0; i < clen; ++i) {
843		Object e = cs[i];
844	<	if (internalIndexOf(e, array, 0, count) < 0) {
845	<	internalAdd((E)e);
844	>	if (rawIndexOf(e, 0, count) < 0) {
845	>	rawAdd(e);
846		++added;
847		}
848		}
#	Line 815 | Line 853 | public class ReadMostlyVector<E> impleme
853		return added;
854		}
855
856	+	/**
857	+	* Returns an iterator operating over a snapshot copy of the
858	+	* elements of this collection created upon construction of the
859	+	* iterator. The iterator does <em>NOT</em> support the
860	+	* <tt>remove</tt> method.
861	+	*
862	+	* @return an iterator over the elements in this list in proper sequence
863	+	*/
864	+	public Iterator<E> snapshotIterator() {
865	+	return new SnapshotIterator<E>(this);
866	+	}
867	+
868	+	static final class SnapshotIterator<E> implements Iterator<E> {
869	+	final Object[] items;
870	+	int cursor;
871	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
872	+	public boolean hasNext() { return cursor < items.length; }
873	+	public E next() {
874	+	if (cursor < items.length)
875	+	return (E) items[cursor++];
876	+	throw new NoSuchElementException();
877	+	}
878	+	public void remove() { throw new UnsupportedOperationException() ; }
879	+	}
880	+
881		// Vector-only methods
882
883		/** See {@link Vector#firstElement} */
#	Line 824 | Line 887 | public class ReadMostlyVector<E> impleme
887		long seq = lock.awaitAvailability();
888		Object[] items = array;
889		int len = items.length;
890	<	int c = count;
891	<	if (c > len || c < 0)
890	>	int n = count;
891	>	if (n > len)
892		continue;
893	<	E e; boolean ex;
894	<	if (c == 0) {
895	<	e = null;
896	<	ex = true;
893	>	Object e; boolean ex;
894	>	if (n > 0) {
895	>	e = items[0];
896	>	ex = false;
897		}
898		else {
899	<	e = (E)items[0];
900	<	ex = false;
899	>	e = null;
900	>	ex = true;
901		}
902		if (lock.getSequence() == seq) {
903		if (ex)
904		throw new NoSuchElementException();
905		else
906	<	return e;
906	>	return (E)e;
907		}
908		}
909		}
#	Line 852 | Line 915 | public class ReadMostlyVector<E> impleme
915		long seq = lock.awaitAvailability();
916		Object[] items = array;
917		int len = items.length;
918	<	int c = count;
919	<	if (c > len || c < 0)
918	>	int n = count;
919	>	if (n > len)
920		continue;
921	<	E e; boolean ex;
922	<	if (c == 0) {
923	<	e = null;
924	<	ex = true;
921	>	Object e; boolean ex;
922	>	if (n > 0) {
923	>	e = items[n - 1];
924	>	ex = false;
925		}
926		else {
927	<	e = (E)items[c - 1];
928	<	ex = false;
927	>	e = null;
928	>	ex = true;
929		}
930		if (lock.getSequence() == seq) {
931		if (ex)
932		throw new NoSuchElementException();
933		else
934	<	return e;
934	>	return (E)e;
935		}
936		}
937		}
#	Line 880 | Line 943 | public class ReadMostlyVector<E> impleme
943		boolean ex = false;
944		long seq = lock.awaitAvailability();
945		Object[] items = array;
946	<	int c = count;
946	>	int n = count;
947		boolean retry = false;
948	<	if (c > items.length)
948	>	if (n > items.length)
949		retry = true;
950		else if (index < 0)
951		ex = true;
952		else
953	<	idx = internalIndexOf(o, items, index, c);
953	>	idx = validatedIndexOf(o, items, index, n, seq);
954		if (retry || lock.getSequence() != seq) {
955		lock.lock();
956		try {
957		if (index < 0)
958		ex = true;
959		else
960	<	idx = internalIndexOf(o, array, 0, count);
960	>	idx = rawIndexOf(o, 0, count);
961		} finally {
962		lock.unlock();
963		}
#	Line 911 | Line 974 | public class ReadMostlyVector<E> impleme
974		boolean ex = false;
975		long seq = lock.awaitAvailability();
976		Object[] items = array;
977	<	int c = count;
977	>	int n = count;
978		boolean retry = false;
979	<	if (c > items.length)
979	>	if (n > items.length)
980		retry = true;
981	<	else if (index >= c)
981	>	else if (index >= n)
982		ex = true;
983		else
984	<	idx = internalLastIndexOf(o, items, index, 0);
984	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
985		if (retry || lock.getSequence() != seq) {
986		lock.lock();
987		try {
988		if (index >= count)
989		ex = true;
990		else
991	<	idx = internalLastIndexOf(o, array, index, 0);
991	>	idx = rawLastIndexOf(o, index, 0);
992		} finally {
993		lock.unlock();
994		}
#	Line 942 | Line 1005 | public class ReadMostlyVector<E> impleme
1005		SequenceLock lock = this.lock;
1006		lock.lock();
1007		try {
1008	<	int c = count;
1009	<	if (newSize > c)
1008	>	int n = count;
1009	>	if (newSize > n)
1010		grow(newSize);
1011		else {
1012	<	for (int i = newSize ; i < c ; i++)
1012	>	for (int i = newSize ; i < n ; i++)
1013		array[i] = null;
1014		}
1015		count = newSize;
#	Line 1043 | Line 1106 | public class ReadMostlyVector<E> impleme
1106		public Object clone() {
1107		SequenceLock lock = this.lock;
1108		Object[] a = null;
1046	–	int c;
1109		boolean retry = false;
1110		long seq = lock.awaitAvailability();
1111		Object[] items = array;
1112	<	c = count;
1113	<	if (c <= items.length)
1114	<	a = Arrays.copyOf(items, c);
1112	>	int n = count;
1113	>	if (n <= items.length)
1114	>	a = Arrays.copyOf(items, n);
1115		else
1116		retry = true;
1117		if (retry || lock.getSequence() != seq) {
1118		lock.lock();
1119		try {
1120	<	c = count;
1121	<	a = Arrays.copyOf(array, c);
1120	>	n = count;
1121	>	a = Arrays.copyOf(array, n);
1122		} finally {
1123		lock.unlock();
1124		}
1125		}
1126	<	return new ReadMostlyVector(a, c, capacityIncrement);
1126	>	return new ReadMostlyVector(a, n, capacityIncrement);
1127		}
1128
1129		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1146 | public class ReadMostlyVector<E> impleme
1146		int cursor;
1147		int fence;
1148		int lastRet;
1149	<	boolean haveNext, havePrev;
1149	>	boolean validNext, validPrev;
1150
1151		Itr(ReadMostlyVector<E> list, int index) {
1152		this.list = list;
#	Line 1097 | Line 1159 | public class ReadMostlyVector<E> impleme
1159		}
1160
1161		private void refresh() {
1162	+	validNext = validPrev = false;
1163		do {
1164		seq = lock.awaitAvailability();
1165		items = list.array;
1166	<	fence = list.count;
1167	<	} while (lock.getSequence() != seq);
1166	>	} while ((fence = list.count) > items.length ||
1167	>	lock.getSequence() != seq);
1168		}
1169
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 = 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		public boolean hasPrevious() {
1189	<	int i = cursor;
1190	<	while (i <= fence && i > 0) {
1189	>	boolean valid;
1190	>	int i = cursor - 1;
1191	>	for (;;) {
1192	>	if (i >= fence || i < 0 || i >= items.length) {
1193	>	valid = false;
1194	>	break;
1195	>	}
1196	>	prev = items[i];
1197		if (lock.getSequence() == seq) {
1198	<	prev = items[i - 1];
1199	<	return havePrev = true;
1198	>	valid = true;
1199	>	break;
1200		}
1201		refresh();
1202		}
1203	<	return false;
1203	>	return validPrev = valid;
1204		}
1205
1206		public E next() {
1207	<	if (!haveNext && !hasNext())
1208	<	throw new NoSuchElementException();
1209	<	haveNext = false;
1210	<	lastRet = cursor++;
1211	<	return (E) next;
1207	>	if (validNext || hasNext()) {
1208	>	validNext = false;
1209	>	lastRet = cursor++;
1210	>	return (E) next;
1211	>	}
1212	>	throw new NoSuchElementException();
1213		}
1214
1215		public E previous() {
1216	<	if (!havePrev && !hasPrevious())
1217	<	throw new NoSuchElementException();
1218	<	havePrev = false;
1219	<	lastRet = cursor--;
1220	<	return (E) prev;
1216	>	if (validPrev || hasPrevious()) {
1217	>	validPrev = false;
1218	>	lastRet = cursor--;
1219	>	return (E) prev;
1220	>	}
1221	>	throw new NoSuchElementException();
1222		}
1223
1224		public void remove() {
#	Line 1217 | Line 1294 | public class ReadMostlyVector<E> impleme
1294		lock.lock();
1295		try {
1296		int c = size;
1297	<	list.internalAddAt(c + offset, element);
1297	>	list.rawAddAt(c + offset, element);
1298		size = c + 1;
1299		} finally {
1300		lock.unlock();
#	Line 1231 | Line 1308 | public class ReadMostlyVector<E> impleme
1308		try {
1309		if (index < 0 || index > size)
1310		throw new ArrayIndexOutOfBoundsException(index);
1311	<	list.internalAddAt(index + offset, element);
1311	>	list.rawAddAt(index + offset, element);
1312		++size;
1313		} finally {
1314		lock.unlock();
#	Line 1246 | Line 1323 | public class ReadMostlyVector<E> impleme
1323		try {
1324		int s = size;
1325		int pc = list.count;
1326	<	list.internalAddAllAt(offset + s, elements);
1326	>	list.rawAddAllAt(offset + s, elements);
1327		added = list.count - pc;
1328		size = s + added;
1329		} finally {
#	Line 1265 | Line 1342 | public class ReadMostlyVector<E> impleme
1342		if (index < 0 || index > s)
1343		throw new ArrayIndexOutOfBoundsException(index);
1344		int pc = list.count;
1345	<	list.internalAddAllAt(index + offset, elements);
1345	>	list.rawAddAllAt(index + offset, elements);
1346		added = list.count - pc;
1347		size = s + added;
1348		} finally {
#	Line 1278 | Line 1355 | public class ReadMostlyVector<E> impleme
1355		SequenceLock lock = list.lock;
1356		lock.lock();
1357		try {
1358	<	list.internalClear(offset, size);
1358	>	list.internalClear(offset, offset + size);
1359		size = 0;
1360		} finally {
1361		lock.unlock();
#	Line 1290 | Line 1367 | public class ReadMostlyVector<E> impleme
1367		}
1368
1369		public boolean containsAll(Collection<?> c) {
1370	<	return list.internalContainsAll(c, offset, size);
1370	>	return list.internalContainsAll(c, offset, offset + size);
1371		}
1372
1373		public boolean equals(Object o) {
#	Line 1298 | Line 1375 | public class ReadMostlyVector<E> impleme
1375		return true;
1376		if (!(o instanceof List))
1377		return false;
1378	<	return list.internalEquals((List<?>)(o), offset, size);
1378	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1379		}
1380
1381		public E get(int index) {
#	Line 1308 | Line 1385 | public class ReadMostlyVector<E> impleme
1385		}
1386
1387		public int hashCode() {
1388	<	return list.internalHashCode(offset, size);
1388	>	return list.internalHashCode(offset, offset + size);
1389		}
1390
1391		public int indexOf(Object o) {
#	Line 1317 | Line 1394 | public class ReadMostlyVector<E> impleme
1394		Object[] items = list.array;
1395		int c = list.count;
1396		if (c <= items.length) {
1397	<	int idx = internalIndexOf(o, items, offset, offset+size);
1397	>	int idx = list.validatedIndexOf(o, items, offset,
1398	>	offset + size, seq);
1399		if (lock.getSequence() == seq)
1400		return idx < 0 ? -1 : idx - offset;
1401		}
1402		lock.lock();
1403		try {
1404	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1404	>	int idx = list.rawIndexOf(o, offset, offset + size);
1405		return idx < 0 ? -1 : idx - offset;
1406		} finally {
1407		lock.unlock();
#	Line 1344 | Line 1422 | public class ReadMostlyVector<E> impleme
1422		Object[] items = list.array;
1423		int c = list.count;
1424		if (c <= items.length) {
1425	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1425	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1426	>	offset, seq);
1427		if (lock.getSequence() == seq)
1428		return idx < 0 ? -1 : idx - offset;
1429		}
1430		lock.lock();
1431		try {
1432	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1432	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1433		return idx < 0 ? -1 : idx - offset;
1434		} finally {
1435		lock.unlock();
#	Line 1367 | Line 1445 | public class ReadMostlyVector<E> impleme
1445		}
1446
1447		public E remove(int index) {
1448	<	E result;
1448	>	Object result;
1449		SequenceLock lock = list.lock;
1450		lock.lock();
1451		try {
1452	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1452	>	Object[] items = list.array;
1453		int i = index + offset;
1454	<	result = (E)list.array[i];
1455	<	list.internalRemoveAt(i);
1454	>	if (index < 0 || index >= size || i >= items.length)
1455	>	throw new ArrayIndexOutOfBoundsException(index);
1456	>	result = items[i];
1457	>	list.rawRemoveAt(i);
1458		size--;
1459		} finally {
1460		lock.unlock();
1461		}
1462	<	return result;
1462	>	return (E)result;
1463		}
1464
1465		public boolean remove(Object o) {
#	Line 1388 | Line 1467 | public class ReadMostlyVector<E> impleme
1467		SequenceLock lock = list.lock;
1468		lock.lock();
1469		try {
1470	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1471	<	offset+size))) {
1470	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1471	>	offset + size))) {
1472		removed = true;
1473		--size;
1474		}
#	Line 1400 | Line 1479 | public class ReadMostlyVector<E> impleme
1479		}
1480
1481		public boolean removeAll(Collection<?> c) {
1482	<	return list.internalRemoveAll(c, offset, size);
1482	>	return list.internalRemoveAll(c, offset, offset + size);
1483		}
1484
1485		public boolean retainAll(Collection<?> c) {
1486	<	return list.internalRetainAll(c, offset, size);
1486	>	return list.internalRetainAll(c, offset, offset + size);
1487		}
1488
1489		public E set(int index, E element) {
#	Line 1426 | Line 1505 | public class ReadMostlyVector<E> impleme
1505		}
1506
1507		public Object[] toArray() {
1508	<	return list.internalToArray(offset, size);
1508	>	return list.internalToArray(offset, offset + size);
1509		}
1510
1511		public <T> T[] toArray(T[] a) {
1512	<	return list.internalToArray(a, offset, size);
1512	>	return list.internalToArray(a, offset, offset + size);
1513		}
1514
1515		public String toString() {
1516	<	return list.internalToString(offset, size);
1516	>	return list.internalToString(offset, offset + size);
1517		}
1518
1519		}
#	Line 1449 | Line 1528 | public class ReadMostlyVector<E> impleme
1528		int cursor;
1529		int fence;
1530		int lastRet;
1531	<	boolean haveNext, havePrev;
1531	>	boolean validNext, validPrev;
1532
1533		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1534		this.sublist = sublist;
#	Line 1463 | Line 1542 | public class ReadMostlyVector<E> impleme
1542		}
1543
1544		private void refresh() {
1545	+	validNext = validPrev = false;
1546		do {
1547	+	int n;
1548		seq = lock.awaitAvailability();
1549		items = list.array;
1550	<	int c = list.count;
1550	>	if ((n = list.count) > items.length)
1551	>	continue;
1552		int b = sublist.offset + sublist.size;
1553	<	fence = b < c ? b : c;
1553	>	fence = b < n ? b : n;
1554		} while (lock.getSequence() != seq);
1555		}
1556
1557		public boolean hasNext() {
1558	+	boolean valid;
1559		int i = cursor;
1560	<	while (i < fence && i >= 0) {
1560	>	for (;;) {
1561	>	if (i >= fence || i < 0 || i >= items.length) {
1562	>	valid = false;
1563	>	break;
1564	>	}
1565	>	next = items[i];
1566		if (lock.getSequence() == seq) {
1567	<	next = items[i];
1568	<	return haveNext = true;
1567	>	valid = true;
1568	>	break;
1569		}
1570		refresh();
1571		}
1572	<	return false;
1572	>	return validNext = valid;
1573		}
1574
1575		public boolean hasPrevious() {
1576	<	int i = cursor;
1577	<	while (i <= fence && i > 0) {
1576	>	boolean valid;
1577	>	int i = cursor - 1;
1578	>	for (;;) {
1579	>	if (i >= fence || i < 0 || i >= items.length) {
1580	>	valid = false;
1581	>	break;
1582	>	}
1583	>	prev = items[i];
1584		if (lock.getSequence() == seq) {
1585	<	prev = items[i - 1];
1586	<	return havePrev = true;
1585	>	valid = true;
1586	>	break;
1587		}
1588		refresh();
1589		}
1590	<	return false;
1590	>	return validPrev = valid;
1591		}
1592
1593		public E next() {
1594	<	if (!haveNext && !hasNext())
1595	<	throw new NoSuchElementException();
1596	<	haveNext = false;
1597	<	lastRet = cursor++;
1598	<	return (E) next;
1594	>	if (validNext || hasNext()) {
1595	>	validNext = false;
1596	>	lastRet = cursor++;
1597	>	return (E) next;
1598	>	}
1599	>	throw new NoSuchElementException();
1600		}
1601
1602		public E previous() {
1603	<	if (!havePrev && !hasPrevious())
1604	<	throw new NoSuchElementException();
1605	<	havePrev = false;
1606	<	lastRet = cursor--;
1607	<	return (E) prev;
1603	>	if (validPrev || hasPrevious()) {
1604	>	validPrev = false;
1605	>	lastRet = cursor--;
1606	>	return (E) prev;
1607	>	}
1608	>	throw new NoSuchElementException();
1609		}
1610
1611		public int nextIndex() {

Diff Legend

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