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.2 by dl, Sat Jul 16 13:20:35 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
#	Line 35 | Line 34 | public class ReadMostlyVector<E> impleme
34
35		/*
36		* This class exists mainly as a vehicle to exercise various
37	<	* constructions using SequenceLocks, which are not yet explained
38	<	* well here.
37	>	* constructions using SequenceLocks. Read-only methods
38	>	* take one of a few forms:
39	>	*
40	>	* Short methods,including get(index), continually retry obtaining
41	>	* a snapshot of array, count, and element, using sequence number
42	>	* to validate.
43	>	*
44	>	* Methods that are potentially O(n) (or worse) try once in
45	>	* read-only mode, and then lock. When in read-only mode, they
46	>	* validate only at the end of an array scan unless the element is
47	>	* actually used (for example, as an argument of method equals).
48		*/
49
50		/**
#	Line 143 | Line 151 | public class ReadMostlyVector<E> impleme
151		* as well as sublist and iterator classes.
152		*/
153
154	<	static int internalIndexOf(Object o, Object[] items,
155	<	int index, int fence) {
154	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
155	>	long seq) {
156	>	for (int i = index; i < fence; ++i) {
157	>	Object e = items[i];
158	>	if (lock.getSequence() != seq)
159	>	break;
160	>	if (x == null? e == null : (e != null && x.equals(e)))
161	>	return i;
162	>	}
163	>	return -1;
164	>	}
165	>
166	>	final int rawIndexOf(Object x, int index, int fence) {
167	>	Object[] items = array;
168		for (int i = index; i < fence; ++i) {
169	<	Object x = items[i];
170	<	if (o == null? x == null : (x != null && o.equals(x)))
169	>	Object e = items[i];
170	>	if (x == null? e == null : (e != null && x.equals(e)))
171		return i;
172		}
173		return -1;
174		}
175
176	<	static int internalLastIndexOf(Object o, Object[] items,
177	<	int index, int origin) {
176	>	final int validatedLastIndexOf(Object x, Object[] items,
177	>	int index, int origin, long seq) {
178		for (int i = index; i >= origin; --i) {
179	<	Object x = items[i];
180	<	if (o == null? x == null : (x != null && o.equals(x)))
179	>	Object e = items[i];
180	>	if (lock.getSequence() != seq)
181	>	break;
182	>	if (x == null? e == null : (e != null && x.equals(e)))
183		return i;
184		}
185		return -1;
186		}
187
188	<	final void internalAdd(E e) {
189	<	int c = count;
190	<	if (c >= array.length)
191	<	grow(c + 1);
192	<	array[c] = e;
193	<	count = c + 1;
188	>	final int rawLastIndexOf(Object x, int index, int origin) {
189	>	Object[] items = array;
190	>	for (int i = index; i >= origin; --i) {
191	>	Object e = items[i];
192	>	if (x == null? e == null : (e != null && x.equals(e)))
193	>	return i;
194	>	}
195	>	return -1;
196	>	}
197	>
198	>	final void internalAdd(Object e) {
199	>	int n = count;
200	>	if (n >= array.length)
201	>	grow(n + 1);
202	>	array[n] = e;
203	>	count = n + 1;
204		}
205
206	<	final void internalAddAt(int index, E e) {
207	<	int c = count;
208	<	if (index > c)
206	>	final void internalAddAt(int index, Object e) {
207	>	int n = count;
208	>	if (index > n)
209		throw new ArrayIndexOutOfBoundsException(index);
210	<	if (c >= array.length)
211	<	grow(c + 1);
212	<	System.arraycopy(array, index, array, index + 1, c - index);
210	>	if (n >= array.length)
211	>	grow(n + 1);
212	>	if (index < n)
213	>	System.arraycopy(array, index, array, index + 1, n - index);
214		array[index] = e;
215	<	count = c + 1;
215	>	count = n + 1;
216		}
217
218		final boolean internalAddAllAt(int index, Object[] elements) {
219	<	int c = count;
220	<	if (index < 0 || index > c)
219	>	int n = count;
220	>	if (index < 0 || index > n)
221		throw new ArrayIndexOutOfBoundsException(index);
222		int len = elements.length;
223		if (len == 0)
224		return false;
225	<	int newCount = c + len;
225	>	int newCount = n + len;
226		if (newCount >= array.length)
227		grow(newCount);
228		int mv = count - index;
#	Line 201 | Line 234 | public class ReadMostlyVector<E> impleme
234		}
235
236		final boolean internalRemoveAt(int index) {
237	<	int c = count - 1;
238	<	if (index < 0 || index > c)
237	>	int n = count - 1;
238	>	if (index < 0 || index > n)
239		return false;
240	<	int mv = c - index;
240	>	int mv = n - index;
241		if (mv > 0)
242		System.arraycopy(array, index + 1, array, index, mv);
243	<	array[c] = null;
244	<	count = c;
243	>	array[n] = null;
244	>	count = n;
245		return true;
246		}
247
248		/**
249		* Internal version of removeAll for lists and sublists. In this
250	<	* and other similar methods below, the span argument is, if
251	<	* non-negative, the purported size of a list/sublist, or is left
252	<	* negative if the size should be determined via count field under
253	<	* lock.
250	>	* and other similar methods below, the bound argument is, if
251	>	* non-negative, the purported upper bound of a list/sublist, or
252	>	* is left negative if the bound should be determined via count
253	>	* field under lock.
254		*/
255	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
255	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
256		SequenceLock lock = this.lock;
257		boolean removed = false;
258		lock.lock();
259		try {
260	<	int fence = count;
261	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
260	>	int n = count;
261	>	int fence = bound < 0 || bound > n ? n : bound;
262		if (origin >= 0 && origin < fence) {
263		for (Object x : c) {
264	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
264	>	while (internalRemoveAt(rawIndexOf(x, origin, fence)))
265		removed = true;
266		}
267		}
#	Line 240 | Line 271 | public class ReadMostlyVector<E> impleme
271		return removed;
272		}
273
274	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
274	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
275		SequenceLock lock = this.lock;
276		boolean removed = false;
277		if (c != this) {
278		lock.lock();
279		try {
280		int i = origin;
281	<	int fence = count;
282	<	if (span >= 0 && origin + span < fence)
252	<	fence = origin + span;
281	>	int n = count;
282	>	int fence = bound < 0 || bound > n ? n : bound;
283		while (i < fence) {
284		if (c.contains(array[i]))
285		++i;
#	Line 268 | Line 298 | public class ReadMostlyVector<E> impleme
298		return removed;
299		}
300
301	<	final void internalClear(int origin, int span) {
302	<	int c = count;
303	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
301	>	final void internalClear(int origin, int bound) {
302	>	int n = count;
303	>	int fence = bound < 0 || bound > n ? n : bound;
304		if (origin >= 0 && origin < fence) {
305		int removed = fence - origin;
306	<	int newCount = c - removed;
307	<	int mv = c - (origin + removed);
306	>	int newCount = n - removed;
307	>	int mv = n - (origin + removed);
308		if (mv > 0)
309		System.arraycopy(array, origin + removed, array, origin, mv);
310	<	for (int i = c; i < newCount; ++i)
310	>	for (int i = n; i < newCount; ++i)
311		array[i] = null;
312		count = newCount;
313		}
314		}
315
316	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
316	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
317		SequenceLock lock = this.lock;
318		boolean contained;
319		boolean locked = false;
#	Line 294 | Line 322 | public class ReadMostlyVector<E> impleme
322		long seq = lock.awaitAvailability();
323		Object[] items = array;
324		int len = items.length;
325	<	int c = count;
326	<	if (c > len)
325	>	int n = count;
326	>	if (n > len)
327		continue;
328	<	int fence = c;
329	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
328	>	int fence = bound < 0 || bound > n ? n : bound;
329	>	if (origin < 0)
330		contained = false;
331		else {
332		contained = true;
333	<	for (Object e : coll) {
334	<	if (internalIndexOf(e, items, origin, fence) < 0) {
333	>	for (Object e : c) {
334	>	if (validatedIndexOf(e, items, origin, fence, seq) < 0) {
335		contained = false;
336		break;
337		}
#	Line 323 | Line 349 | public class ReadMostlyVector<E> impleme
349		return contained;
350		}
351
352	<	final boolean internalEquals(List<?> list, int origin, int span) {
352	>	final boolean internalEquals(List<?> list, int origin, int bound) {
353		SequenceLock lock = this.lock;
354		boolean equal;
355		boolean locked = false;
356		try {
357	<	for (;;) {
357	>	outer:for (;;) {
358		equal = true;
359		long seq = lock.awaitAvailability();
360		Object[] items = array;
361		int len = items.length;
362	<	int c = count;
363	<	if (c > len)
362	>	int n = count;
363	>	if (n > len)
364		continue;
365	<	int fence = c;
366	<	if (span >= 0 && origin + span < fence)
341	<	fence = origin + span;
342	<	if (origin < 0 || fence > c)
365	>	int fence = bound < 0 || bound > n ? n : bound;
366	>	if (origin < 0)
367		equal = false;
368		else {
369		Iterator<?> it = list.iterator();
#	Line 350 | Line 374 | public class ReadMostlyVector<E> impleme
374		}
375		Object x = it.next();
376		Object y = items[i];
377	+	if (lock.getSequence() != seq)
378	+	continue outer;
379		if (x == null? y != null : (y == null || !x.equals(y))) {
380		equal = false;
381		break;
#	Line 370 | Line 396 | public class ReadMostlyVector<E> impleme
396		return equal;
397		}
398
399	<	final int internalHashCode(int origin, int span) {
399	>	final int internalHashCode(int origin, int bound) {
400		SequenceLock lock = this.lock;
401		int hash;
402		boolean locked = false;
#	Line 380 | Line 406 | public class ReadMostlyVector<E> impleme
406		long seq = lock.awaitAvailability();
407		Object[] items = array;
408		int len = items.length;
409	<	int c = count;
410	<	if (c > len)
409	>	int n = count;
410	>	if (n > len)
411		continue;
412	<	int fence = c;
413	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
412	>	int fence = bound < 0 || bound > n ? n : bound;
413	>	if (origin >= 0) {
414		for (int i = origin; i < fence; ++i) {
415		Object e = items[i];
416		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 428 | public class ReadMostlyVector<E> impleme
428		return hash;
429		}
430
431	<	final String internalToString(int origin, int span) {
431	>	final String internalToString(int origin, int bound) {
432		SequenceLock lock = this.lock;
433		String ret;
434		boolean locked = false;
435		try {
436	<	for (;;) {
436	>	outer:for (;;) {
437		long seq = lock.awaitAvailability();
438		Object[] items = array;
439		int len = items.length;
440	<	int c = count;
441	<	if (c > len)
440	>	int n = count;
441	>	if (n > len)
442		continue;
443	<	int fence = c;
444	<	if (span >= 0 && origin + span < fence)
445	<	fence = origin + span;
446	<	if (origin >= 0 && fence <= c) {
447	<	if (origin == fence)
448	<	ret = "[]";
449	<	else {
450	<	StringBuilder sb = new StringBuilder();
451	<	sb.append('[');
452	<	for (int i = origin;;) {
453	<	Object e = items[i];
454	<	sb.append(e == this ? "(this Collection)" : e);
455	<	if (++i < fence)
456	<	sb.append(',').append(' ');
457	<	else {
458	<	ret = sb.append(']').toString();
459	<	break;
460	<	}
443	>	int fence = bound < 0 || bound > n ? n : bound;
444	>	if (origin < 0 || origin == fence)
445	>	ret = "[]";
446	>	else {
447	>	StringBuilder sb = new StringBuilder();
448	>	sb.append('[');
449	>	for (int i = origin;;) {
450	>	Object e = items[i];
451	>	if (e == this)
452	>	sb.append("(this Collection)");
453	>	else if (lock.getSequence() != seq)
454	>	continue outer;
455	>	else
456	>	sb.append(e.toString());
457	>	if (++i < fence)
458	>	sb.append(',').append(' ');
459	>	else {
460	>	ret = sb.append(']').toString();
461	>	break;
462		}
463		}
439	–	if (lock.getSequence() == seq)
440	–	break;
464		}
465	+	if (lock.getSequence() == seq)
466	+	break;
467		lock.lock();
468		locked = true;
469		}
#	Line 449 | Line 474 | public class ReadMostlyVector<E> impleme
474		return ret;
475		}
476
477	<	final Object[] internalToArray(int origin, int span) {
477	>	final Object[] internalToArray(int origin, int bound) {
478		Object[] result;
479		SequenceLock lock = this.lock;
480		boolean locked = false;
#	Line 459 | Line 484 | public class ReadMostlyVector<E> impleme
484		long seq = lock.awaitAvailability();
485		Object[] items = array;
486		int len = items.length;
487	<	int c = count;
488	<	int fence = c;
489	<	if (span >= 0 && origin + span < fence)
490	<	fence = origin + span;
491	<	if (c <= len && fence <= len) {
487	>	int n = count;
488	>	if (n > len)
489	>	continue;
490	>	int fence = bound < 0 || bound > n ? n : bound;
491	>	if (origin >= 0)
492		result = Arrays.copyOfRange(items, origin, fence,
493		Object[].class);
494	<	if (lock.getSequence() == seq)
495	<	break;
471	<	}
494	>	if (lock.getSequence() == seq)
495	>	break;
496		lock.lock();
497		locked = true;
498		}
#	Line 479 | Line 503 | public class ReadMostlyVector<E> impleme
503		return result;
504		}
505
506	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
506	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
507	>	int alen = a.length;
508		T[] result;
509		SequenceLock lock = this.lock;
510		boolean locked = false;
#	Line 488 | Line 513 | public class ReadMostlyVector<E> impleme
513		long seq = lock.awaitAvailability();
514		Object[] items = array;
515		int len = items.length;
516	<	int c = count;
517	<	int fence = c;
518	<	if (span >= 0 && origin + span < fence)
519	<	fence = origin + span;
520	<	if (c <= len && fence <= len) {
521	<	if (a.length < count)
522	<	result = (T[]) Arrays.copyOfRange(array, origin,
523	<	fence, a.getClass());
524	<	else {
525	<	int n = fence - origin;
526	<	System.arraycopy(array, 0, a, origin, fence - origin);
527	<	if (a.length > n)
528	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
516	>	int n = count;
517	>	if (n > len)
518	>	continue;
519	>	int fence = bound < 0 || bound > n ? n : bound;
520	>	int rlen = fence - origin;
521	>	if (origin < 0 || alen >= rlen) {
522	>	if (rlen < 0)
523	>	rlen = 0;
524	>	else if (rlen > 0)
525	>	System.arraycopy(array, 0, a, origin, rlen);
526	>	if (alen > rlen)
527	>	a[rlen] = null;
528	>	result = a;
529		}
530	+	else
531	+	result = (T[]) Arrays.copyOfRange(array, origin,
532	+	fence, a.getClass());
533	+	if (lock.getSequence() == seq)
534	+	break;
535		lock.lock();
536		locked = true;
537		}
#	Line 604 | Line 630 | public class ReadMostlyVector<E> impleme
630		for (;;) {
631		long seq = lock.awaitAvailability();
632		Object[] items = array;
633	<	int len = items.length;
634	<	int c = count;
609	<	if (c > len)
633	>	int n = count;
634	>	if (n > items.length)
635		continue;
636	<	E e; boolean ex;
637	<	if (index < 0 || index >= c) {
636	>	Object e; boolean ex;
637	>	if (index < 0 || index >= n) {
638		e = null;
639		ex = true;
640		}
641		else {
642	<	e = (E)items[index];
642	>	e = items[index];
643		ex = false;
644		}
645		if (lock.getSequence() == seq) {
646		if (ex)
647		throw new ArrayIndexOutOfBoundsException(index);
648		else
649	<	return e;
649	>	return (E)e;
650		}
651		}
652		}
#	Line 634 | Line 659 | public class ReadMostlyVector<E> impleme
659		SequenceLock lock = this.lock;
660		long seq = lock.awaitAvailability();
661		Object[] items = array;
662	<	int c = count;
663	<	if (c <= items.length) {
664	<	int idx = internalIndexOf(o, items, 0, c);
662	>	int n = count;
663	>	if (n <= items.length) {
664	>	int idx = validatedIndexOf(o, items, 0, n, seq);
665		if (lock.getSequence() == seq)
666		return idx;
667		}
668		lock.lock();
669		try {
670	<	return internalIndexOf(o, array, 0, count);
670	>	return rawIndexOf(o, 0, count);
671		} finally {
672		lock.unlock();
673		}
#	Line 661 | Line 686 | public class ReadMostlyVector<E> impleme
686		SequenceLock lock = this.lock;
687		long seq = lock.awaitAvailability();
688		Object[] items = array;
689	<	int c = count;
690	<	if (c <= items.length) {
691	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
689	>	int n = count;
690	>	if (n <= items.length) {
691	>	int idx = validatedLastIndexOf(o, items, n - 1, 0, seq);
692		if (lock.getSequence() == seq)
693		return idx;
694		}
695		lock.lock();
696		try {
697	<	return internalLastIndexOf(o, array, count-1, 0);
697	>	return rawLastIndexOf(o, count - 1, 0);
698		} finally {
699		lock.unlock();
700		}
#	Line 685 | Line 710 | public class ReadMostlyVector<E> impleme
710
711		public E remove(int index) {
712		SequenceLock lock = this.lock;
713	<	E oldValue;
713	>	Object oldValue;
714		lock.lock();
715		try {
716		if (index < 0 || index >= count)
717		throw new ArrayIndexOutOfBoundsException(index);
718	<	oldValue = (E)array[index];
718	>	oldValue = array[index];
719		internalRemoveAt(index);
720		} finally {
721		lock.unlock();
722		}
723	<	return oldValue;
723	>	return (E)oldValue;
724		}
725
726		public boolean remove(Object o) {
#	Line 703 | Line 728 | public class ReadMostlyVector<E> impleme
728		boolean removed;
729		lock.lock();
730		try {
731	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
731	>	removed = internalRemoveAt(rawIndexOf(o, 0, count));
732		} finally {
733		lock.unlock();
734		}
#	Line 719 | Line 744 | public class ReadMostlyVector<E> impleme
744		}
745
746		public E set(int index, E element) {
747	<	E oldValue;
747	>	Object oldValue;
748		SequenceLock lock = this.lock;
749		lock.lock();
750		try {
751		if (index < 0 || index >= count)
752		throw new ArrayIndexOutOfBoundsException(index);
753	<	oldValue = (E)array[index];
753	>	oldValue = array[index];
754		array[index] = element;
755		} finally {
756		lock.unlock();
757		}
758	<	return oldValue;
758	>	return (E)oldValue;
759		}
760
761		public int size() {
#	Line 771 | Line 796 | public class ReadMostlyVector<E> impleme
796		SequenceLock lock = this.lock;
797		lock.lock();
798		try {
799	<	if (internalIndexOf(e, array, 0, count) < 0) {
799	>	if (rawIndexOf(e, 0, count) < 0) {
800		internalAdd(e);
801		added = true;
802		}
#	Line 803 | Line 828 | public class ReadMostlyVector<E> impleme
828		try {
829		for (int i = 0; i < clen; ++i) {
830		Object e = cs[i];
831	<	if (internalIndexOf(e, array, 0, count) < 0) {
832	<	internalAdd((E)e);
831	>	if (rawIndexOf(e, 0, count) < 0) {
832	>	internalAdd(e);
833		++added;
834		}
835		}
#	Line 824 | Line 849 | public class ReadMostlyVector<E> impleme
849		long seq = lock.awaitAvailability();
850		Object[] items = array;
851		int len = items.length;
852	<	int c = count;
853	<	if (c > len || c < 0)
852	>	int n = count;
853	>	if (n > len)
854		continue;
855	<	E e; boolean ex;
856	<	if (c == 0) {
857	<	e = null;
858	<	ex = true;
855	>	Object e; boolean ex;
856	>	if (n > 0) {
857	>	e = items[0];
858	>	ex = false;
859		}
860		else {
861	<	e = (E)items[0];
862	<	ex = false;
861	>	e = null;
862	>	ex = true;
863		}
864		if (lock.getSequence() == seq) {
865		if (ex)
866		throw new NoSuchElementException();
867		else
868	<	return e;
868	>	return (E)e;
869		}
870		}
871		}
#	Line 852 | Line 877 | public class ReadMostlyVector<E> impleme
877		long seq = lock.awaitAvailability();
878		Object[] items = array;
879		int len = items.length;
880	<	int c = count;
881	<	if (c > len || c < 0)
880	>	int n = count;
881	>	if (n > len)
882		continue;
883	<	E e; boolean ex;
884	<	if (c == 0) {
885	<	e = null;
886	<	ex = true;
883	>	Object e; boolean ex;
884	>	if (n > 0) {
885	>	e = items[n - 1];
886	>	ex = false;
887		}
888		else {
889	<	e = (E)items[c - 1];
890	<	ex = false;
889	>	e = null;
890	>	ex = true;
891		}
892		if (lock.getSequence() == seq) {
893		if (ex)
894		throw new NoSuchElementException();
895		else
896	<	return e;
896	>	return (E)e;
897		}
898		}
899		}
#	Line 880 | Line 905 | public class ReadMostlyVector<E> impleme
905		boolean ex = false;
906		long seq = lock.awaitAvailability();
907		Object[] items = array;
908	<	int c = count;
908	>	int n = count;
909		boolean retry = false;
910	<	if (c > items.length)
910	>	if (n > items.length)
911		retry = true;
912		else if (index < 0)
913		ex = true;
914		else
915	<	idx = internalIndexOf(o, items, index, c);
915	>	idx = validatedIndexOf(o, items, index, n, seq);
916		if (retry || lock.getSequence() != seq) {
917		lock.lock();
918		try {
919		if (index < 0)
920		ex = true;
921		else
922	<	idx = internalIndexOf(o, array, 0, count);
922	>	idx = rawIndexOf(o, 0, count);
923		} finally {
924		lock.unlock();
925		}
#	Line 911 | Line 936 | public class ReadMostlyVector<E> impleme
936		boolean ex = false;
937		long seq = lock.awaitAvailability();
938		Object[] items = array;
939	<	int c = count;
939	>	int n = count;
940		boolean retry = false;
941	<	if (c > items.length)
941	>	if (n > items.length)
942		retry = true;
943	<	else if (index >= c)
943	>	else if (index >= n)
944		ex = true;
945		else
946	<	idx = internalLastIndexOf(o, items, index, 0);
946	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
947		if (retry || lock.getSequence() != seq) {
948		lock.lock();
949		try {
950		if (index >= count)
951		ex = true;
952		else
953	<	idx = internalLastIndexOf(o, array, index, 0);
953	>	idx = rawLastIndexOf(o, index, 0);
954		} finally {
955		lock.unlock();
956		}
#	Line 942 | Line 967 | public class ReadMostlyVector<E> impleme
967		SequenceLock lock = this.lock;
968		lock.lock();
969		try {
970	<	int c = count;
971	<	if (newSize > c)
970	>	int n = count;
971	>	if (newSize > n)
972		grow(newSize);
973		else {
974	<	for (int i = newSize ; i < c ; i++)
974	>	for (int i = newSize ; i < n ; i++)
975		array[i] = null;
976		}
977		count = newSize;
#	Line 1043 | Line 1068 | public class ReadMostlyVector<E> impleme
1068		public Object clone() {
1069		SequenceLock lock = this.lock;
1070		Object[] a = null;
1046	–	int c;
1071		boolean retry = false;
1072		long seq = lock.awaitAvailability();
1073		Object[] items = array;
1074	<	c = count;
1075	<	if (c <= items.length)
1076	<	a = Arrays.copyOf(items, c);
1074	>	int n = count;
1075	>	if (n <= items.length)
1076	>	a = Arrays.copyOf(items, n);
1077		else
1078		retry = true;
1079		if (retry || lock.getSequence() != seq) {
1080		lock.lock();
1081		try {
1082	<	c = count;
1083	<	a = Arrays.copyOf(array, c);
1082	>	n = count;
1083	>	a = Arrays.copyOf(array, n);
1084		} finally {
1085		lock.unlock();
1086		}
1087		}
1088	<	return new ReadMostlyVector(a, c, capacityIncrement);
1088	>	return new ReadMostlyVector(a, n, capacityIncrement);
1089		}
1090
1091		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1108 | public class ReadMostlyVector<E> impleme
1108		int cursor;
1109		int fence;
1110		int lastRet;
1111	<	boolean haveNext, havePrev;
1111	>	boolean validNext, validPrev;
1112
1113		Itr(ReadMostlyVector<E> list, int index) {
1114		this.list = list;
#	Line 1097 | Line 1121 | public class ReadMostlyVector<E> impleme
1121		}
1122
1123		private void refresh() {
1124	+	validNext = validPrev = false;
1125		do {
1126		seq = lock.awaitAvailability();
1127		items = list.array;
1128	<	fence = list.count;
1129	<	} while (lock.getSequence() != seq);
1128	>	} while ((fence = list.count) > items.length ||
1129	>	lock.getSequence() != seq);
1130		}
1131
1132		public boolean hasNext() {
1133	+	boolean valid;
1134		int i = cursor;
1135	<	while (i < fence && i >= 0) {
1135	>	for (;;) {
1136	>	if (i >= fence || i < 0 || i >= items.length) {
1137	>	valid = false;
1138	>	break;
1139	>	}
1140	>	next = items[i];
1141		if (lock.getSequence() == seq) {
1142	<	next = items[i];
1143	<	return haveNext = true;
1142	>	valid = true;
1143	>	break;
1144		}
1145		refresh();
1146		}
1147	<	return false;
1147	>	return validNext = valid;
1148		}
1149
1150		public boolean hasPrevious() {
1151	<	int i = cursor;
1152	<	while (i <= fence && i > 0) {
1151	>	boolean valid;
1152	>	int i = cursor - 1;
1153	>	for (;;) {
1154	>	if (i >= fence || i < 0 || i >= items.length) {
1155	>	valid = false;
1156	>	break;
1157	>	}
1158	>	prev = items[i];
1159		if (lock.getSequence() == seq) {
1160	<	prev = items[i - 1];
1161	<	return havePrev = true;
1160	>	valid = true;
1161	>	break;
1162		}
1163		refresh();
1164		}
1165	<	return false;
1165	>	return validPrev = valid;
1166		}
1167
1168		public E next() {
1169	<	if (!haveNext && !hasNext())
1170	<	throw new NoSuchElementException();
1171	<	haveNext = false;
1172	<	lastRet = cursor++;
1173	<	return (E) next;
1169	>	if (validNext || hasNext()) {
1170	>	validNext = false;
1171	>	lastRet = cursor++;
1172	>	return (E) next;
1173	>	}
1174	>	throw new NoSuchElementException();
1175		}
1176
1177		public E previous() {
1178	<	if (!havePrev && !hasPrevious())
1179	<	throw new NoSuchElementException();
1180	<	havePrev = false;
1181	<	lastRet = cursor--;
1182	<	return (E) prev;
1178	>	if (validPrev || hasPrevious()) {
1179	>	validPrev = false;
1180	>	lastRet = cursor--;
1181	>	return (E) prev;
1182	>	}
1183	>	throw new NoSuchElementException();
1184		}
1185
1186		public void remove() {
#	Line 1278 | Line 1317 | public class ReadMostlyVector<E> impleme
1317		SequenceLock lock = list.lock;
1318		lock.lock();
1319		try {
1320	<	list.internalClear(offset, size);
1320	>	list.internalClear(offset, offset + size);
1321		size = 0;
1322		} finally {
1323		lock.unlock();
#	Line 1290 | Line 1329 | public class ReadMostlyVector<E> impleme
1329		}
1330
1331		public boolean containsAll(Collection<?> c) {
1332	<	return list.internalContainsAll(c, offset, size);
1332	>	return list.internalContainsAll(c, offset, offset + size);
1333		}
1334
1335		public boolean equals(Object o) {
#	Line 1298 | Line 1337 | public class ReadMostlyVector<E> impleme
1337		return true;
1338		if (!(o instanceof List))
1339		return false;
1340	<	return list.internalEquals((List<?>)(o), offset, size);
1340	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1341		}
1342
1343		public E get(int index) {
#	Line 1308 | Line 1347 | public class ReadMostlyVector<E> impleme
1347		}
1348
1349		public int hashCode() {
1350	<	return list.internalHashCode(offset, size);
1350	>	return list.internalHashCode(offset, offset + size);
1351		}
1352
1353		public int indexOf(Object o) {
#	Line 1317 | Line 1356 | public class ReadMostlyVector<E> impleme
1356		Object[] items = list.array;
1357		int c = list.count;
1358		if (c <= items.length) {
1359	<	int idx = internalIndexOf(o, items, offset, offset+size);
1359	>	int idx = list.validatedIndexOf(o, items, offset, offset+size, seq);
1360		if (lock.getSequence() == seq)
1361		return idx < 0 ? -1 : idx - offset;
1362		}
1363		lock.lock();
1364		try {
1365	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1365	>	int idx = list.rawIndexOf(o, offset, offset+size);
1366		return idx < 0 ? -1 : idx - offset;
1367		} finally {
1368		lock.unlock();
#	Line 1344 | Line 1383 | public class ReadMostlyVector<E> impleme
1383		Object[] items = list.array;
1384		int c = list.count;
1385		if (c <= items.length) {
1386	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1386	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1387	>	offset, seq);
1388		if (lock.getSequence() == seq)
1389		return idx < 0 ? -1 : idx - offset;
1390		}
1391		lock.lock();
1392		try {
1393	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1393	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1394		return idx < 0 ? -1 : idx - offset;
1395		} finally {
1396		lock.unlock();
#	Line 1367 | Line 1406 | public class ReadMostlyVector<E> impleme
1406		}
1407
1408		public E remove(int index) {
1409	<	E result;
1409	>	Object result;
1410		SequenceLock lock = list.lock;
1411		lock.lock();
1412		try {
1413		if (index < 0 || index >= size)
1414		throw new ArrayIndexOutOfBoundsException(index);
1415		int i = index + offset;
1416	<	result = (E)list.array[i];
1416	>	result = list.array[i];
1417		list.internalRemoveAt(i);
1418		size--;
1419		} finally {
1420		lock.unlock();
1421		}
1422	<	return result;
1422	>	return (E)result;
1423		}
1424
1425		public boolean remove(Object o) {
#	Line 1388 | Line 1427 | public class ReadMostlyVector<E> impleme
1427		SequenceLock lock = list.lock;
1428		lock.lock();
1429		try {
1430	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1431	<	offset+size))) {
1430	>	if (list.internalRemoveAt(list.rawIndexOf(o, offset,
1431	>	offset + size))) {
1432		removed = true;
1433		--size;
1434		}
#	Line 1400 | Line 1439 | public class ReadMostlyVector<E> impleme
1439		}
1440
1441		public boolean removeAll(Collection<?> c) {
1442	<	return list.internalRemoveAll(c, offset, size);
1442	>	return list.internalRemoveAll(c, offset, offset + size);
1443		}
1444
1445		public boolean retainAll(Collection<?> c) {
1446	<	return list.internalRetainAll(c, offset, size);
1446	>	return list.internalRetainAll(c, offset, offset + size);
1447		}
1448
1449		public E set(int index, E element) {
#	Line 1426 | Line 1465 | public class ReadMostlyVector<E> impleme
1465		}
1466
1467		public Object[] toArray() {
1468	<	return list.internalToArray(offset, size);
1468	>	return list.internalToArray(offset, offset + size);
1469		}
1470
1471		public <T> T[] toArray(T[] a) {
1472	<	return list.internalToArray(a, offset, size);
1472	>	return list.internalToArray(a, offset, offset + size);
1473		}
1474
1475		public String toString() {
1476	<	return list.internalToString(offset, size);
1476	>	return list.internalToString(offset, offset + size);
1477		}
1478
1479		}
#	Line 1449 | Line 1488 | public class ReadMostlyVector<E> impleme
1488		int cursor;
1489		int fence;
1490		int lastRet;
1491	<	boolean haveNext, havePrev;
1491	>	boolean validNext, validPrev;
1492
1493		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1494		this.sublist = sublist;
#	Line 1463 | Line 1502 | public class ReadMostlyVector<E> impleme
1502		}
1503
1504		private void refresh() {
1505	+	validNext = validPrev = false;
1506		do {
1507	+	int n;
1508		seq = lock.awaitAvailability();
1509		items = list.array;
1510	<	int c = list.count;
1510	>	if ((n = list.count) > items.length)
1511	>	continue;
1512		int b = sublist.offset + sublist.size;
1513	<	fence = b < c ? b : c;
1513	>	fence = b < n ? b : n;
1514		} while (lock.getSequence() != seq);
1515		}
1516
1517		public boolean hasNext() {
1518	+	boolean valid;
1519		int i = cursor;
1520	<	while (i < fence && i >= 0) {
1520	>	for (;;) {
1521	>	if (i >= fence || i < 0 || i >= items.length) {
1522	>	valid = false;
1523	>	break;
1524	>	}
1525	>	next = items[i];
1526		if (lock.getSequence() == seq) {
1527	<	next = items[i];
1528	<	return haveNext = true;
1527	>	valid = true;
1528	>	break;
1529		}
1530		refresh();
1531		}
1532	<	return false;
1532	>	return validNext = valid;
1533		}
1534
1535		public boolean hasPrevious() {
1536	<	int i = cursor;
1537	<	while (i <= fence && i > 0) {
1536	>	boolean valid;
1537	>	int i = cursor - 1;
1538	>	for (;;) {
1539	>	if (i >= fence || i < 0 || i >= items.length) {
1540	>	valid = false;
1541	>	break;
1542	>	}
1543	>	prev = items[i];
1544		if (lock.getSequence() == seq) {
1545	<	prev = items[i - 1];
1546	<	return havePrev = true;
1545	>	valid = true;
1546	>	break;
1547		}
1548		refresh();
1549		}
1550	<	return false;
1550	>	return validPrev = valid;
1551		}
1552
1553		public E next() {
1554	<	if (!haveNext && !hasNext())
1555	<	throw new NoSuchElementException();
1556	<	haveNext = false;
1557	<	lastRet = cursor++;
1558	<	return (E) next;
1554	>	if (validNext || hasNext()) {
1555	>	validNext = false;
1556	>	lastRet = cursor++;
1557	>	return (E) next;
1558	>	}
1559	>	throw new NoSuchElementException();
1560		}
1561
1562		public E previous() {
1563	<	if (!havePrev && !hasPrevious())
1564	<	throw new NoSuchElementException();
1565	<	havePrev = false;
1566	<	lastRet = cursor--;
1567	<	return (E) prev;
1563	>	if (validPrev || hasPrevious()) {
1564	>	validPrev = false;
1565	>	lastRet = cursor--;
1566	>	return (E) prev;
1567	>	}
1568	>	throw new NoSuchElementException();
1569		}
1570
1571		public int nextIndex() {

Diff Legend

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