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.4 by dl, Sat Jul 16 15:05:04 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	>	// Version of indexOf that returns -1 if either not present or invalid
155	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
156	>	long seq) {
157	>	for (int i = index; i < fence; ++i) {
158	>	Object e = items[i];
159	>	if (lock.getSequence() != seq)
160	>	break;
161	>	if (x == null? e == null : x.equals(e))
162	>	return i;
163	>	}
164	>	return -1;
165	>	}
166	>
167	>	final int rawIndexOf(Object x, int index, int fence) {
168	>	Object[] items = array;
169		for (int i = index; i < fence; ++i) {
170	<	Object x = items[i];
171	<	if (o == null? x == null : (x != null && o.equals(x)))
170	>	Object e = items[i];
171	>	if (x == null? e == null : x.equals(e))
172		return i;
173		}
174		return -1;
175		}
176
177	<	static int internalLastIndexOf(Object o, Object[] items,
178	<	int index, int origin) {
177	>	final int validatedLastIndexOf(Object x, Object[] items,
178	>	int index, int origin, long seq) {
179		for (int i = index; i >= origin; --i) {
180	<	Object x = items[i];
181	<	if (o == null? x == null : (x != null && o.equals(x)))
180	>	Object e = items[i];
181	>	if (lock.getSequence() != seq)
182	>	break;
183	>	if (x == null? e == null : x.equals(e))
184		return i;
185		}
186		return -1;
187		}
188
189	<	final void internalAdd(E e) {
190	<	int c = count;
191	<	if (c >= array.length)
192	<	grow(c + 1);
193	<	array[c] = e;
194	<	count = c + 1;
189	>	final int rawLastIndexOf(Object x, int index, int origin) {
190	>	Object[] items = array;
191	>	for (int i = index; i >= origin; --i) {
192	>	Object e = items[i];
193	>	if (x == null? e == null : x.equals(e))
194	>	return i;
195	>	}
196	>	return -1;
197	>	}
198	>
199	>	final void rawAdd(Object e) {
200	>	int n = count;
201	>	if (n >= array.length)
202	>	grow(n + 1);
203	>	array[n] = e;
204	>	count = n + 1;
205		}
206
207	<	final void internalAddAt(int index, E e) {
208	<	int c = count;
209	<	if (index > c)
207	>	final void rawAddAt(int index, Object e) {
208	>	int n = count;
209	>	if (index > n)
210		throw new ArrayIndexOutOfBoundsException(index);
211	<	if (c >= array.length)
212	<	grow(c + 1);
213	<	System.arraycopy(array, index, array, index + 1, c - index);
211	>	if (n >= array.length)
212	>	grow(n + 1);
213	>	if (index < n)
214	>	System.arraycopy(array, index, array, index + 1, n - index);
215		array[index] = e;
216	<	count = c + 1;
216	>	count = n + 1;
217		}
218
219	<	final boolean internalAddAllAt(int index, Object[] elements) {
220	<	int c = count;
221	<	if (index < 0 || index > c)
219	>	final boolean rawAddAllAt(int index, Object[] elements) {
220	>	int n = count;
221	>	if (index < 0 || index > n)
222		throw new ArrayIndexOutOfBoundsException(index);
223		int len = elements.length;
224		if (len == 0)
225		return false;
226	<	int newCount = c + len;
226	>	int newCount = n + len;
227		if (newCount >= array.length)
228		grow(newCount);
229		int mv = count - index;
#	Line 200 | Line 234 | public class ReadMostlyVector<E> impleme
234		return true;
235		}
236
237	<	final boolean internalRemoveAt(int index) {
238	<	int c = count - 1;
239	<	if (index < 0 || index > c)
237	>	final boolean rawRemoveAt(int index) {
238	>	int n = count - 1;
239	>	if (index < 0 || index > n)
240		return false;
241	<	int mv = c - index;
241	>	int mv = n - index;
242		if (mv > 0)
243		System.arraycopy(array, index + 1, array, index, mv);
244	<	array[c] = null;
245	<	count = c;
244	>	array[n] = null;
245	>	count = n;
246		return true;
247		}
248
249		/**
250		* Internal version of removeAll for lists and sublists. In this
251	<	* and other similar methods below, the span argument is, if
252	<	* non-negative, the purported size of a list/sublist, or is left
253	<	* negative if the size should be determined via count field under
254	<	* lock.
251	>	* and other similar methods below, the bound argument is, if
252	>	* non-negative, the purported upper bound of a list/sublist, or
253	>	* is left negative if the bound should be determined via count
254	>	* field under lock.
255		*/
256	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
256	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
257		SequenceLock lock = this.lock;
258		boolean removed = false;
259		lock.lock();
260		try {
261	<	int fence = count;
262	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
261	>	int n = count;
262	>	int fence = bound < 0 || bound > n ? n : bound;
263		if (origin >= 0 && origin < fence) {
264		for (Object x : c) {
265	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
265	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
266		removed = true;
267		}
268		}
#	Line 240 | Line 272 | public class ReadMostlyVector<E> impleme
272		return removed;
273		}
274
275	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
275	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
276		SequenceLock lock = this.lock;
277		boolean removed = false;
278		if (c != this) {
279		lock.lock();
280		try {
281		int i = origin;
282	<	int fence = count;
283	<	if (span >= 0 && origin + span < fence)
284	<	fence = origin + span;
253	<	while (i < fence) {
282	>	int n = count;
283	>	int fence = bound < 0 || bound > n ? n : bound;
284	>	while (i >= 0 && i < fence) {
285		if (c.contains(array[i]))
286		++i;
287		else {
#	Line 268 | Line 299 | public class ReadMostlyVector<E> impleme
299		return removed;
300		}
301
302	<	final void internalClear(int origin, int span) {
303	<	int c = count;
304	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
302	>	final void internalClear(int origin, int bound) {
303	>	int n = count;
304	>	int fence = bound < 0 || bound > n ? n : bound;
305		if (origin >= 0 && origin < fence) {
306		int removed = fence - origin;
307	<	int newCount = c - removed;
308	<	int mv = c - (origin + removed);
307	>	int newCount = n - removed;
308	>	int mv = n - (origin + removed);
309		if (mv > 0)
310		System.arraycopy(array, origin + removed, array, origin, mv);
311	<	for (int i = c; i < newCount; ++i)
311	>	for (int i = n; i < newCount; ++i)
312		array[i] = null;
313		count = newCount;
314		}
315		}
316
317	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
317	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
318		SequenceLock lock = this.lock;
319		boolean contained;
320		boolean locked = false;
#	Line 294 | Line 323 | public class ReadMostlyVector<E> impleme
323		long seq = lock.awaitAvailability();
324		Object[] items = array;
325		int len = items.length;
326	<	int c = count;
327	<	if (c > len)
326	>	int n = count;
327	>	if (n > len)
328		continue;
329	<	int fence = c;
330	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
329	>	int fence = bound < 0 || bound > n ? n : bound;
330	>	if (origin < 0)
331		contained = false;
332		else {
333		contained = true;
334	<	for (Object e : coll) {
335	<	if (internalIndexOf(e, items, origin, fence) < 0) {
334	>	for (Object e : c) {
335	>	int idx = (locked?
336	>	rawIndexOf(e, origin, fence) :
337	>	validatedIndexOf(e, items, origin,
338	>	fence, seq));
339	>	if (idx < 0) {
340		contained = false;
341		break;
342		}
#	Line 323 | Line 354 | public class ReadMostlyVector<E> impleme
354		return contained;
355		}
356
357	<	final boolean internalEquals(List<?> list, int origin, int span) {
357	>	final boolean internalEquals(List<?> list, int origin, int bound) {
358		SequenceLock lock = this.lock;
328	–	boolean equal;
359		boolean locked = false;
360	+	boolean equal;
361		try {
362		for (;;) {
332	–	equal = true;
363		long seq = lock.awaitAvailability();
364		Object[] items = array;
365	<	int len = items.length;
366	<	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)
365	>	int n = count;
366	>	if (n > items.length || origin < 0)
367		equal = false;
368		else {
369	+	equal = true;
370	+	int fence = bound < 0 || bound > n ? n : bound;
371		Iterator<?> it = list.iterator();
372		for (int i = origin; i < fence; ++i) {
373	<	if (!it.hasNext()) {
374	<	equal = false;
375	<	break;
376	<	}
377	<	Object x = it.next();
378	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
373	>	Object x = items[i];
374	>	Object y;
375	>	if ((!locked && lock.getSequence() != seq) ||
376	>	!it.hasNext() ||
377	>	(y = it.next()) == null ?
378	>	x != null : !y.equals(x)) {
379		equal = false;
380		break;
381		}
#	Line 370 | Line 395 | public class ReadMostlyVector<E> impleme
395		return equal;
396		}
397
398	<	final int internalHashCode(int origin, int span) {
398	>	final int internalHashCode(int origin, int bound) {
399		SequenceLock lock = this.lock;
400		int hash;
401		boolean locked = false;
#	Line 380 | Line 405 | public class ReadMostlyVector<E> impleme
405		long seq = lock.awaitAvailability();
406		Object[] items = array;
407		int len = items.length;
408	<	int c = count;
409	<	if (c > len)
408	>	int n = count;
409	>	if (n > len)
410		continue;
411	<	int fence = c;
412	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
411	>	int fence = bound < 0 || bound > n ? n : bound;
412	>	if (origin >= 0) {
413		for (int i = origin; i < fence; ++i) {
414		Object e = items[i];
415		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 427 | public class ReadMostlyVector<E> impleme
427		return hash;
428		}
429
430	<	final String internalToString(int origin, int span) {
430	>	final String internalToString(int origin, int bound) {
431		SequenceLock lock = this.lock;
432		String ret;
433		boolean locked = false;
434		try {
435	<	for (;;) {
435	>	outer:for (;;) {
436		long seq = lock.awaitAvailability();
437		Object[] items = array;
438		int len = items.length;
439	<	int c = count;
440	<	if (c > len)
439	>	int n = count;
440	>	if (n > len)
441		continue;
442	<	int fence = c;
443	<	if (span >= 0 && origin + span < fence)
444	<	fence = origin + span;
445	<	if (origin >= 0 && fence <= c) {
446	<	if (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	<	sb.append(e == this ? "(this Collection)" : e);
454	<	if (++i < fence)
455	<	sb.append(',').append(' ');
456	<	else {
457	<	ret = sb.append(']').toString();
458	<	break;
459	<	}
442	>	int fence = bound < 0 || bound > n ? n : bound;
443	>	if (origin < 0 || origin == fence)
444	>	ret = "[]";
445	>	else {
446	>	StringBuilder sb = new StringBuilder();
447	>	sb.append('[');
448	>	for (int i = origin;;) {
449	>	Object e = items[i];
450	>	if (e == this)
451	>	sb.append("(this Collection)");
452	>	else if (!locked && lock.getSequence() != seq)
453	>	continue outer;
454	>	else
455	>	sb.append(e.toString());
456	>	if (++i < fence)
457	>	sb.append(',').append(' ');
458	>	else {
459	>	ret = sb.append(']').toString();
460	>	break;
461		}
462		}
439	–	if (lock.getSequence() == seq)
440	–	break;
463		}
464	+	if (lock.getSequence() == seq)
465	+	break;
466		lock.lock();
467		locked = true;
468		}
#	Line 449 | Line 473 | public class ReadMostlyVector<E> impleme
473		return ret;
474		}
475
476	<	final Object[] internalToArray(int origin, int span) {
476	>	final Object[] internalToArray(int origin, int bound) {
477		Object[] result;
478		SequenceLock lock = this.lock;
479		boolean locked = false;
#	Line 459 | Line 483 | public class ReadMostlyVector<E> impleme
483		long seq = lock.awaitAvailability();
484		Object[] items = array;
485		int len = items.length;
486	<	int c = count;
487	<	int fence = c;
488	<	if (span >= 0 && origin + span < fence)
489	<	fence = origin + span;
490	<	if (c <= len && fence <= len) {
486	>	int n = count;
487	>	if (n > len)
488	>	continue;
489	>	int fence = bound < 0 || bound > n ? n : bound;
490	>	if (origin >= 0)
491		result = Arrays.copyOfRange(items, origin, fence,
492		Object[].class);
493	<	if (lock.getSequence() == seq)
494	<	break;
471	<	}
493	>	if (lock.getSequence() == seq)
494	>	break;
495		lock.lock();
496		locked = true;
497		}
#	Line 479 | Line 502 | public class ReadMostlyVector<E> impleme
502		return result;
503		}
504
505	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
505	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
506	>	int alen = a.length;
507		T[] result;
508		SequenceLock lock = this.lock;
509		boolean locked = false;
#	Line 488 | Line 512 | public class ReadMostlyVector<E> impleme
512		long seq = lock.awaitAvailability();
513		Object[] items = array;
514		int len = items.length;
515	<	int c = count;
516	<	int fence = c;
517	<	if (span >= 0 && origin + span < fence)
518	<	fence = origin + span;
519	<	if (c <= len && fence <= len) {
520	<	if (a.length < count)
521	<	result = (T[]) Arrays.copyOfRange(array, origin,
522	<	fence, a.getClass());
523	<	else {
524	<	int n = fence - origin;
525	<	System.arraycopy(array, 0, a, origin, fence - origin);
526	<	if (a.length > n)
527	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
515	>	int n = count;
516	>	if (n > len)
517	>	continue;
518	>	int fence = bound < 0 || bound > n ? n : bound;
519	>	int rlen = fence - origin;
520	>	if (rlen < 0)
521	>	rlen = 0;
522	>	if (origin < 0 || alen >= rlen) {
523	>	if (rlen > 0)
524	>	System.arraycopy(array, 0, a, origin, rlen);
525	>	if (alen > rlen)
526	>	a[rlen] = null;
527	>	result = a;
528		}
529	+	else
530	+	result = (T[]) Arrays.copyOfRange(array, origin,
531	+	fence, a.getClass());
532	+	if (lock.getSequence() == seq)
533	+	break;
534		lock.lock();
535		locked = true;
536		}
#	Line 522 | Line 547 | public class ReadMostlyVector<E> impleme
547		SequenceLock lock = this.lock;
548		lock.lock();
549		try {
550	<	internalAdd(e);
550	>	rawAdd(e);
551		} finally {
552		lock.unlock();
553		}
#	Line 533 | Line 558 | public class ReadMostlyVector<E> impleme
558		SequenceLock lock = this.lock;
559		lock.lock();
560		try {
561	<	internalAddAt(index, element);
561	>	rawAddAt(index, element);
562		} finally {
563		lock.unlock();
564		}
#	Line 564 | Line 589 | public class ReadMostlyVector<E> impleme
589		Object[] elements = c.toArray();
590		lock.lock();
591		try {
592	<	ret = internalAddAllAt(index, elements);
592	>	ret = rawAddAllAt(index, elements);
593		} finally {
594		lock.unlock();
595		}
#	Line 596 | Line 621 | public class ReadMostlyVector<E> impleme
621		return true;
622		if (!(o instanceof List))
623		return false;
624	<	return internalEquals((List<?>)(o), 0, -1);
624	>	return internalEquals((List<?>)o, 0, -1);
625		}
626
627		public E get(int index) {
#	Line 604 | Line 629 | public class ReadMostlyVector<E> impleme
629		for (;;) {
630		long seq = lock.awaitAvailability();
631		Object[] items = array;
632	<	int len = items.length;
633	<	int c = count;
609	<	if (c > len)
632	>	int n = count;
633	>	if (n > items.length)
634		continue;
635	<	E e; boolean ex;
636	<	if (index < 0 || index >= c) {
635	>	Object e; boolean ex;
636	>	if (index < 0 || index >= n) {
637		e = null;
638		ex = true;
639		}
640		else {
641	<	e = (E)items[index];
641	>	e = items[index];
642		ex = false;
643		}
644		if (lock.getSequence() == seq) {
645		if (ex)
646		throw new ArrayIndexOutOfBoundsException(index);
647		else
648	<	return e;
648	>	return (E)e;
649		}
650		}
651		}
#	Line 634 | Line 658 | public class ReadMostlyVector<E> impleme
658		SequenceLock lock = this.lock;
659		long seq = lock.awaitAvailability();
660		Object[] items = array;
661	<	int c = count;
662	<	if (c <= items.length) {
663	<	int idx = internalIndexOf(o, items, 0, c);
664	<	if (lock.getSequence() == seq)
665	<	return idx;
661	>	int n = count;
662	>	if (n <= items.length) {
663	>	boolean valid = true;
664	>	for (int i = 0; i < n; ++i) {
665	>	Object e = items[i];
666	>	if (lock.getSequence() == seq) {
667	>	if (o == null? e == null : o.equals(e))
668	>	return i;
669	>	}
670	>	else {
671	>	valid = false;
672	>	break;
673	>	}
674	>	}
675	>	if (valid)
676	>	return -1;
677		}
678		lock.lock();
679		try {
680	<	return internalIndexOf(o, array, 0, count);
680	>	return rawIndexOf(o, 0, count);
681		} finally {
682		lock.unlock();
683		}
#	Line 661 | Line 696 | public class ReadMostlyVector<E> impleme
696		SequenceLock lock = this.lock;
697		long seq = lock.awaitAvailability();
698		Object[] items = array;
699	<	int c = count;
700	<	if (c <= items.length) {
701	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
699	>	int n = count;
700	>	if (n <= items.length) {
701	>	int idx = validatedLastIndexOf(o, items, n - 1, 0, seq);
702		if (lock.getSequence() == seq)
703		return idx;
704		}
705		lock.lock();
706		try {
707	<	return internalLastIndexOf(o, array, count-1, 0);
707	>	return rawLastIndexOf(o, count - 1, 0);
708		} finally {
709		lock.unlock();
710		}
#	Line 685 | Line 720 | public class ReadMostlyVector<E> impleme
720
721		public E remove(int index) {
722		SequenceLock lock = this.lock;
723	<	E oldValue;
723	>	Object oldValue;
724		lock.lock();
725		try {
726		if (index < 0 || index >= count)
727		throw new ArrayIndexOutOfBoundsException(index);
728	<	oldValue = (E)array[index];
729	<	internalRemoveAt(index);
728	>	oldValue = array[index];
729	>	rawRemoveAt(index);
730		} finally {
731		lock.unlock();
732		}
733	<	return oldValue;
733	>	return (E)oldValue;
734		}
735
736		public boolean remove(Object o) {
#	Line 703 | Line 738 | public class ReadMostlyVector<E> impleme
738		boolean removed;
739		lock.lock();
740		try {
741	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
741	>	removed = rawRemoveAt(rawIndexOf(o, 0, count));
742		} finally {
743		lock.unlock();
744		}
#	Line 719 | Line 754 | public class ReadMostlyVector<E> impleme
754		}
755
756		public E set(int index, E element) {
757	<	E oldValue;
757	>	Object oldValue;
758		SequenceLock lock = this.lock;
759		lock.lock();
760		try {
761		if (index < 0 || index >= count)
762		throw new ArrayIndexOutOfBoundsException(index);
763	<	oldValue = (E)array[index];
763	>	oldValue = array[index];
764		array[index] = element;
765		} finally {
766		lock.unlock();
767		}
768	<	return oldValue;
768	>	return (E)oldValue;
769		}
770
771		public int size() {
#	Line 771 | Line 806 | public class ReadMostlyVector<E> impleme
806		SequenceLock lock = this.lock;
807		lock.lock();
808		try {
809	<	if (internalIndexOf(e, array, 0, count) < 0) {
810	<	internalAdd(e);
809	>	if (rawIndexOf(e, 0, count) < 0) {
810	>	rawAdd(e);
811		added = true;
812		}
813		else
#	Line 803 | Line 838 | public class ReadMostlyVector<E> impleme
838		try {
839		for (int i = 0; i < clen; ++i) {
840		Object e = cs[i];
841	<	if (internalIndexOf(e, array, 0, count) < 0) {
842	<	internalAdd((E)e);
841	>	if (rawIndexOf(e, 0, count) < 0) {
842	>	rawAdd(e);
843		++added;
844		}
845		}
#	Line 824 | Line 859 | public class ReadMostlyVector<E> impleme
859		long seq = lock.awaitAvailability();
860		Object[] items = array;
861		int len = items.length;
862	<	int c = count;
863	<	if (c > len || c < 0)
862	>	int n = count;
863	>	if (n > len)
864		continue;
865	<	E e; boolean ex;
866	<	if (c == 0) {
867	<	e = null;
868	<	ex = true;
865	>	Object e; boolean ex;
866	>	if (n > 0) {
867	>	e = items[0];
868	>	ex = false;
869		}
870		else {
871	<	e = (E)items[0];
872	<	ex = false;
871	>	e = null;
872	>	ex = true;
873		}
874		if (lock.getSequence() == seq) {
875		if (ex)
876		throw new NoSuchElementException();
877		else
878	<	return e;
878	>	return (E)e;
879		}
880		}
881		}
#	Line 852 | 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[n - 1];
896	>	ex = false;
897		}
898		else {
899	<	e = (E)items[c - 1];
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 880 | Line 915 | public class ReadMostlyVector<E> impleme
915		boolean ex = false;
916		long seq = lock.awaitAvailability();
917		Object[] items = array;
918	<	int c = count;
918	>	int n = count;
919		boolean retry = false;
920	<	if (c > items.length)
920	>	if (n > items.length)
921		retry = true;
922		else if (index < 0)
923		ex = true;
924		else
925	<	idx = internalIndexOf(o, items, index, c);
925	>	idx = validatedIndexOf(o, items, index, n, seq);
926		if (retry || lock.getSequence() != seq) {
927		lock.lock();
928		try {
929		if (index < 0)
930		ex = true;
931		else
932	<	idx = internalIndexOf(o, array, 0, count);
932	>	idx = rawIndexOf(o, 0, count);
933		} finally {
934		lock.unlock();
935		}
#	Line 911 | 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 >= c)
953	>	else if (index >= n)
954		ex = true;
955		else
956	<	idx = internalLastIndexOf(o, items, index, 0);
956	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
957		if (retry || lock.getSequence() != seq) {
958		lock.lock();
959		try {
960		if (index >= count)
961		ex = true;
962		else
963	<	idx = internalLastIndexOf(o, array, index, 0);
963	>	idx = rawLastIndexOf(o, index, 0);
964		} finally {
965		lock.unlock();
966		}
#	Line 942 | Line 977 | public class ReadMostlyVector<E> impleme
977		SequenceLock lock = this.lock;
978		lock.lock();
979		try {
980	<	int c = count;
981	<	if (newSize > c)
980	>	int n = count;
981	>	if (newSize > n)
982		grow(newSize);
983		else {
984	<	for (int i = newSize ; i < c ; i++)
984	>	for (int i = newSize ; i < n ; i++)
985		array[i] = null;
986		}
987		count = newSize;
#	Line 1043 | Line 1078 | public class ReadMostlyVector<E> impleme
1078		public Object clone() {
1079		SequenceLock lock = this.lock;
1080		Object[] a = null;
1046	–	int c;
1081		boolean retry = false;
1082		long seq = lock.awaitAvailability();
1083		Object[] items = array;
1084	<	c = count;
1085	<	if (c <= items.length)
1086	<	a = Arrays.copyOf(items, c);
1084	>	int n = count;
1085	>	if (n <= items.length)
1086	>	a = Arrays.copyOf(items, n);
1087		else
1088		retry = true;
1089		if (retry || lock.getSequence() != seq) {
1090		lock.lock();
1091		try {
1092	<	c = count;
1093	<	a = Arrays.copyOf(array, c);
1092	>	n = count;
1093	>	a = Arrays.copyOf(array, n);
1094		} finally {
1095		lock.unlock();
1096		}
1097		}
1098	<	return new ReadMostlyVector(a, c, capacityIncrement);
1098	>	return new ReadMostlyVector(a, n, capacityIncrement);
1099		}
1100
1101		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1118 | public class ReadMostlyVector<E> impleme
1118		int cursor;
1119		int fence;
1120		int lastRet;
1121	<	boolean haveNext, havePrev;
1121	>	boolean validNext, validPrev;
1122
1123		Itr(ReadMostlyVector<E> list, int index) {
1124		this.list = list;
#	Line 1097 | Line 1131 | public class ReadMostlyVector<E> impleme
1131		}
1132
1133		private void refresh() {
1134	+	validNext = validPrev = false;
1135		do {
1136		seq = lock.awaitAvailability();
1137		items = list.array;
1138	<	fence = list.count;
1139	<	} while (lock.getSequence() != seq);
1138	>	} while ((fence = list.count) > items.length ||
1139	>	lock.getSequence() != seq);
1140		}
1141
1142		public boolean hasNext() {
1143	+	boolean valid;
1144		int i = cursor;
1145	<	while (i < fence && i >= 0) {
1145	>	for (;;) {
1146	>	if (i >= fence || i < 0 || i >= items.length) {
1147	>	valid = false;
1148	>	break;
1149	>	}
1150	>	next = items[i];
1151		if (lock.getSequence() == seq) {
1152	<	next = items[i];
1153	<	return haveNext = true;
1152	>	valid = true;
1153	>	break;
1154		}
1155		refresh();
1156		}
1157	<	return false;
1157	>	return validNext = valid;
1158		}
1159
1160		public boolean hasPrevious() {
1161	<	int i = cursor;
1162	<	while (i <= fence && i > 0) {
1161	>	boolean valid;
1162	>	int i = cursor - 1;
1163	>	for (;;) {
1164	>	if (i >= fence || i < 0 || i >= items.length) {
1165	>	valid = false;
1166	>	break;
1167	>	}
1168	>	prev = items[i];
1169		if (lock.getSequence() == seq) {
1170	<	prev = items[i - 1];
1171	<	return havePrev = true;
1170	>	valid = true;
1171	>	break;
1172		}
1173		refresh();
1174		}
1175	<	return false;
1175	>	return validPrev = valid;
1176		}
1177
1178		public E next() {
1179	<	if (!haveNext && !hasNext())
1180	<	throw new NoSuchElementException();
1181	<	haveNext = false;
1182	<	lastRet = cursor++;
1183	<	return (E) next;
1179	>	if (validNext || hasNext()) {
1180	>	validNext = false;
1181	>	lastRet = cursor++;
1182	>	return (E) next;
1183	>	}
1184	>	throw new NoSuchElementException();
1185		}
1186
1187		public E previous() {
1188	<	if (!havePrev && !hasPrevious())
1189	<	throw new NoSuchElementException();
1190	<	havePrev = false;
1191	<	lastRet = cursor--;
1192	<	return (E) prev;
1188	>	if (validPrev || hasPrevious()) {
1189	>	validPrev = false;
1190	>	lastRet = cursor--;
1191	>	return (E) prev;
1192	>	}
1193	>	throw new NoSuchElementException();
1194		}
1195
1196		public void remove() {
#	Line 1217 | Line 1266 | public class ReadMostlyVector<E> impleme
1266		lock.lock();
1267		try {
1268		int c = size;
1269	<	list.internalAddAt(c + offset, element);
1269	>	list.rawAddAt(c + offset, element);
1270		size = c + 1;
1271		} finally {
1272		lock.unlock();
#	Line 1231 | Line 1280 | public class ReadMostlyVector<E> impleme
1280		try {
1281		if (index < 0 || index > size)
1282		throw new ArrayIndexOutOfBoundsException(index);
1283	<	list.internalAddAt(index + offset, element);
1283	>	list.rawAddAt(index + offset, element);
1284		++size;
1285		} finally {
1286		lock.unlock();
#	Line 1246 | Line 1295 | public class ReadMostlyVector<E> impleme
1295		try {
1296		int s = size;
1297		int pc = list.count;
1298	<	list.internalAddAllAt(offset + s, elements);
1298	>	list.rawAddAllAt(offset + s, elements);
1299		added = list.count - pc;
1300		size = s + added;
1301		} finally {
#	Line 1265 | Line 1314 | public class ReadMostlyVector<E> impleme
1314		if (index < 0 || index > s)
1315		throw new ArrayIndexOutOfBoundsException(index);
1316		int pc = list.count;
1317	<	list.internalAddAllAt(index + offset, elements);
1317	>	list.rawAddAllAt(index + offset, elements);
1318		added = list.count - pc;
1319		size = s + added;
1320		} finally {
#	Line 1278 | Line 1327 | public class ReadMostlyVector<E> impleme
1327		SequenceLock lock = list.lock;
1328		lock.lock();
1329		try {
1330	<	list.internalClear(offset, size);
1330	>	list.internalClear(offset, offset + size);
1331		size = 0;
1332		} finally {
1333		lock.unlock();
#	Line 1290 | Line 1339 | public class ReadMostlyVector<E> impleme
1339		}
1340
1341		public boolean containsAll(Collection<?> c) {
1342	<	return list.internalContainsAll(c, offset, size);
1342	>	return list.internalContainsAll(c, offset, offset + size);
1343		}
1344
1345		public boolean equals(Object o) {
#	Line 1298 | Line 1347 | public class ReadMostlyVector<E> impleme
1347		return true;
1348		if (!(o instanceof List))
1349		return false;
1350	<	return list.internalEquals((List<?>)(o), offset, size);
1350	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1351		}
1352
1353		public E get(int index) {
#	Line 1308 | Line 1357 | public class ReadMostlyVector<E> impleme
1357		}
1358
1359		public int hashCode() {
1360	<	return list.internalHashCode(offset, size);
1360	>	return list.internalHashCode(offset, offset + size);
1361		}
1362
1363		public int indexOf(Object o) {
#	Line 1317 | Line 1366 | public class ReadMostlyVector<E> impleme
1366		Object[] items = list.array;
1367		int c = list.count;
1368		if (c <= items.length) {
1369	<	int idx = internalIndexOf(o, items, offset, offset+size);
1369	>	int idx = list.validatedIndexOf(o, items, offset,
1370	>	offset + size, seq);
1371		if (lock.getSequence() == seq)
1372		return idx < 0 ? -1 : idx - offset;
1373		}
1374		lock.lock();
1375		try {
1376	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1376	>	int idx = list.rawIndexOf(o, offset, offset + size);
1377		return idx < 0 ? -1 : idx - offset;
1378		} finally {
1379		lock.unlock();
#	Line 1344 | 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 = internalLastIndexOf(o, items, offset+size-1, offset);
1397	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1398	>	offset, seq);
1399		if (lock.getSequence() == seq)
1400		return idx < 0 ? -1 : idx - offset;
1401		}
1402		lock.lock();
1403		try {
1404	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1404	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1405		return idx < 0 ? -1 : idx - offset;
1406		} finally {
1407		lock.unlock();
#	Line 1367 | Line 1417 | public class ReadMostlyVector<E> impleme
1417		}
1418
1419		public E remove(int index) {
1420	<	E result;
1420	>	Object result;
1421		SequenceLock lock = list.lock;
1422		lock.lock();
1423		try {
1424	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1424	>	Object[] items = list.array;
1425		int i = index + offset;
1426	<	result = (E)list.array[i];
1427	<	list.internalRemoveAt(i);
1426	>	if (index < 0 || index >= size || i >= items.length)
1427	>	throw new ArrayIndexOutOfBoundsException(index);
1428	>	result = items[i];
1429	>	list.rawRemoveAt(i);
1430		size--;
1431		} finally {
1432		lock.unlock();
1433		}
1434	<	return result;
1434	>	return (E)result;
1435		}
1436
1437		public boolean remove(Object o) {
#	Line 1388 | Line 1439 | public class ReadMostlyVector<E> impleme
1439		SequenceLock lock = list.lock;
1440		lock.lock();
1441		try {
1442	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1443	<	offset+size))) {
1442	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1443	>	offset + size))) {
1444		removed = true;
1445		--size;
1446		}
#	Line 1400 | Line 1451 | public class ReadMostlyVector<E> impleme
1451		}
1452
1453		public boolean removeAll(Collection<?> c) {
1454	<	return list.internalRemoveAll(c, offset, size);
1454	>	return list.internalRemoveAll(c, offset, offset + size);
1455		}
1456
1457		public boolean retainAll(Collection<?> c) {
1458	<	return list.internalRetainAll(c, offset, size);
1458	>	return list.internalRetainAll(c, offset, offset + size);
1459		}
1460
1461		public E set(int index, E element) {
#	Line 1426 | Line 1477 | public class ReadMostlyVector<E> impleme
1477		}
1478
1479		public Object[] toArray() {
1480	<	return list.internalToArray(offset, size);
1480	>	return list.internalToArray(offset, offset + size);
1481		}
1482
1483		public <T> T[] toArray(T[] a) {
1484	<	return list.internalToArray(a, offset, size);
1484	>	return list.internalToArray(a, offset, offset + size);
1485		}
1486
1487		public String toString() {
1488	<	return list.internalToString(offset, size);
1488	>	return list.internalToString(offset, offset + size);
1489		}
1490
1491		}
#	Line 1449 | Line 1500 | public class ReadMostlyVector<E> impleme
1500		int cursor;
1501		int fence;
1502		int lastRet;
1503	<	boolean haveNext, havePrev;
1503	>	boolean validNext, validPrev;
1504
1505		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1506		this.sublist = sublist;
#	Line 1463 | Line 1514 | public class ReadMostlyVector<E> impleme
1514		}
1515
1516		private void refresh() {
1517	+	validNext = validPrev = false;
1518		do {
1519	+	int n;
1520		seq = lock.awaitAvailability();
1521		items = list.array;
1522	<	int c = list.count;
1522	>	if ((n = list.count) > items.length)
1523	>	continue;
1524		int b = sublist.offset + sublist.size;
1525	<	fence = b < c ? b : c;
1525	>	fence = b < n ? b : n;
1526		} while (lock.getSequence() != seq);
1527		}
1528
1529		public boolean hasNext() {
1530	+	boolean valid;
1531		int i = cursor;
1532	<	while (i < fence && i >= 0) {
1532	>	for (;;) {
1533	>	if (i >= fence || i < 0 || i >= items.length) {
1534	>	valid = false;
1535	>	break;
1536	>	}
1537	>	next = items[i];
1538		if (lock.getSequence() == seq) {
1539	<	next = items[i];
1540	<	return haveNext = true;
1539	>	valid = true;
1540	>	break;
1541		}
1542		refresh();
1543		}
1544	<	return false;
1544	>	return validNext = valid;
1545		}
1546
1547		public boolean hasPrevious() {
1548	<	int i = cursor;
1549	<	while (i <= fence && i > 0) {
1548	>	boolean valid;
1549	>	int i = cursor - 1;
1550	>	for (;;) {
1551	>	if (i >= fence || i < 0 || i >= items.length) {
1552	>	valid = false;
1553	>	break;
1554	>	}
1555	>	prev = items[i];
1556		if (lock.getSequence() == seq) {
1557	<	prev = items[i - 1];
1558	<	return havePrev = true;
1557	>	valid = true;
1558	>	break;
1559		}
1560		refresh();
1561		}
1562	<	return false;
1562	>	return validPrev = valid;
1563		}
1564
1565		public E next() {
1566	<	if (!haveNext && !hasNext())
1567	<	throw new NoSuchElementException();
1568	<	haveNext = false;
1569	<	lastRet = cursor++;
1570	<	return (E) next;
1566	>	if (validNext || hasNext()) {
1567	>	validNext = false;
1568	>	lastRet = cursor++;
1569	>	return (E) next;
1570	>	}
1571	>	throw new NoSuchElementException();
1572		}
1573
1574		public E previous() {
1575	<	if (!havePrev && !hasPrevious())
1576	<	throw new NoSuchElementException();
1577	<	havePrev = false;
1578	<	lastRet = cursor--;
1579	<	return (E) prev;
1575	>	if (validPrev || hasPrevious()) {
1576	>	validPrev = false;
1577	>	lastRet = cursor--;
1578	>	return (E) prev;
1579	>	}
1580	>	throw new NoSuchElementException();
1581		}
1582
1583		public int nextIndex() {

Diff Legend

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