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.11 by dl, Wed Jul 20 20:29:33 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 46 | Line 57 | public class ReadMostlyVector<E> impleme
57		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
58
59		// fields are non-private to simpify nested class access
60	<	Object[] array;
60	>	volatile Object[] array;
61		final SequenceLock lock;
62	<	int count;
62	>	volatile int count;
63		final int capacityIncrement;
64
65		/**
#	Line 143 | Line 154 | public class ReadMostlyVector<E> impleme
154		* as well as sublist and iterator classes.
155		*/
156
157	<	static int internalIndexOf(Object o, Object[] items,
158	<	int index, int fence) {
157	>	// Version of indexOf that returns -1 if either not present or invalid
158	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
159	>	long seq) {
160	>	for (int i = index; i < fence; ++i) {
161	>	Object e = items[i];
162	>	if (lock.getSequence() != seq)
163	>	break;
164	>	if ((x == null) ? e == null : x.equals(e))
165	>	return i;
166	>	}
167	>	return -1;
168	>	}
169	>
170	>	final int rawIndexOf(Object x, int index, int fence) {
171	>	Object[] items = array;
172		for (int i = index; i < fence; ++i) {
173	<	Object x = items[i];
174	<	if (o == null? x == null : (x != null && o.equals(x)))
173	>	Object e = items[i];
174	>	if ((x == null) ? e == null : x.equals(e))
175		return i;
176		}
177		return -1;
178		}
179
180	<	static int internalLastIndexOf(Object o, Object[] items,
181	<	int index, int origin) {
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 x = items[i];
184	<	if (o == null? x == null : (x != null && o.equals(x)))
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	<	final void internalAdd(E e) {
193	<	int c = count;
194	<	if (c >= array.length)
195	<	grow(c + 1);
196	<	array[c] = e;
197	<	count = c + 1;
192	>	final int rawLastIndexOf(Object x, int index, int origin) {
193	>	Object[] items = array;
194	>	for (int i = index; i >= origin; --i) {
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 rawAdd(Object e) {
203	>	int n = count;
204	>	Object[] items = array;
205	>	if (n < items.length)
206	>	items[n] = e;
207	>	else {
208	>	grow(n + 1);
209	>	array[n] = e;
210	>	}
211	>	count = n + 1;
212		}
213
214	<	final void internalAddAt(int index, E e) {
215	<	int c = count;
216	<	if (index > c)
214	>	final void rawAddAt(int index, Object e) {
215	>	int n = count;
216	>	if (index > n)
217		throw new ArrayIndexOutOfBoundsException(index);
218	<	if (c >= array.length)
219	<	grow(c + 1);
220	<	System.arraycopy(array, index, array, index + 1, c - index);
221	<	array[index] = e;
222	<	count = c + 1;
218	>	if (n >= array.length)
219	>	grow(n + 1);
220	>	Object[] items = array;
221	>	if (index < n)
222	>	System.arraycopy(items, index, items, index + 1, n - index);
223	>	items[index] = e;
224	>	count = n + 1;
225		}
226
227	<	final boolean internalAddAllAt(int index, Object[] elements) {
228	<	int c = count;
229	<	if (index < 0 || index > c)
227	>	final boolean rawAddAllAt(int index, Object[] elements) {
228	>	int n = count;
229	>	if (index < 0 || index > n)
230		throw new ArrayIndexOutOfBoundsException(index);
231		int len = elements.length;
232		if (len == 0)
233		return false;
234	<	int newCount = c + len;
234	>	int newCount = n + len;
235		if (newCount >= array.length)
236		grow(newCount);
237	<	int mv = count - index;
237	>	Object[] items = array;
238	>	int mv = n - index;
239		if (mv > 0)
240	<	System.arraycopy(array, index, array, index + len, mv);
241	<	System.arraycopy(elements, 0, array, index, len);
240	>	System.arraycopy(items, index, items, index + len, mv);
241	>	System.arraycopy(elements, 0, items, index, len);
242		count = newCount;
243		return true;
244		}
245
246	<	final boolean internalRemoveAt(int index) {
247	<	int c = count - 1;
248	<	if (index < 0 || index > c)
246	>	final boolean rawRemoveAt(int index) {
247	>	Object[] items = array;
248	>	int n = count - 1;
249	>	if (index < 0 || index > n)
250		return false;
251	<	int mv = c - index;
251	>	int mv = n - index;
252		if (mv > 0)
253	<	System.arraycopy(array, index + 1, array, index, mv);
254	<	array[c] = null;
255	<	count = c;
253	>	System.arraycopy(items, index + 1, items, index, mv);
254	>	items[n] = null;
255	>	count = n;
256		return true;
257		}
258
259		/**
260		* Internal version of removeAll for lists and sublists. In this
261	<	* and other similar methods below, the span argument is, if
262	<	* non-negative, the purported size of a list/sublist, or is left
263	<	* negative if the size should be determined via count field under
264	<	* lock.
261	>	* and other similar methods below, the bound argument is, if
262	>	* non-negative, the purported upper bound of a list/sublist, or
263	>	* is left negative if the bound should be determined via count
264	>	* field under lock.
265		*/
266	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
266	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
267		SequenceLock lock = this.lock;
268		boolean removed = false;
269		lock.lock();
270		try {
271	<	int fence = count;
272	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
271	>	int n = count;
272	>	int fence = bound < 0 || bound > n ? n : bound;
273		if (origin >= 0 && origin < fence) {
274		for (Object x : c) {
275	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
275	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
276		removed = true;
277		}
278		}
#	Line 240 | Line 282 | public class ReadMostlyVector<E> impleme
282		return removed;
283		}
284
285	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
285	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
286		SequenceLock lock = this.lock;
287		boolean removed = false;
288		if (c != this) {
289		lock.lock();
290		try {
291	+	Object[] items = array;
292		int i = origin;
293	<	int fence = count;
294	<	if (span >= 0 && origin + span < fence)
295	<	fence = origin + span;
296	<	while (i < fence) {
254	<	if (c.contains(array[i]))
293	>	int n = count;
294	>	int fence = bound < 0 || bound > n ? n : bound;
295	>	while (i >= 0 && i < fence) {
296	>	if (c.contains(items[i]))
297		++i;
298		else {
299		--fence;
300		int mv = --count - i;
301		if (mv > 0)
302	<	System.arraycopy(array, i + 1, array, i, mv);
302	>	System.arraycopy(items, i + 1, items, i, mv);
303		removed = true;
304		}
305		}
#	Line 268 | Line 310 | public class ReadMostlyVector<E> impleme
310		return removed;
311		}
312
313	<	final void internalClear(int origin, int span) {
314	<	int c = count;
315	<	int fence = c;
316	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
313	>	final void internalClear(int origin, int bound) {
314	>	Object[] items = array;
315	>	int n = count;
316	>	int fence = bound < 0 || bound > n ? n : bound;
317		if (origin >= 0 && origin < fence) {
318		int removed = fence - origin;
319	<	int newCount = c - removed;
320	<	int mv = c - (origin + removed);
319	>	int newCount = n - removed;
320	>	int mv = n - (origin + removed);
321		if (mv > 0)
322	<	System.arraycopy(array, origin + removed, array, origin, mv);
323	<	for (int i = c; i < newCount; ++i)
324	<	array[i] = null;
322	>	System.arraycopy(items, origin + removed, items, origin, mv);
323	>	for (int i = n; i < newCount; ++i)
324	>	items[i] = null;
325		count = newCount;
326		}
327		}
328
329	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
329	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
330		SequenceLock lock = this.lock;
331		boolean contained;
332		boolean locked = false;
#	Line 294 | Line 335 | public class ReadMostlyVector<E> impleme
335		long seq = lock.awaitAvailability();
336		Object[] items = array;
337		int len = items.length;
338	<	int c = count;
339	<	if (c > len)
338	>	int n = count;
339	>	if (n > len)
340		continue;
341	<	int fence = c;
342	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
341	>	int fence = bound < 0 || bound > n ? n : bound;
342	>	if (origin < 0)
343		contained = false;
344		else {
345		contained = true;
346	<	for (Object e : coll) {
347	<	if (internalIndexOf(e, items, origin, fence) < 0) {
346	>	for (Object e : c) {
347	>	int idx = (locked ?
348	>	rawIndexOf(e, origin, fence) :
349	>	validatedIndexOf(e, items, origin,
350	>	fence, seq));
351	>	if (idx < 0) {
352		contained = false;
353		break;
354		}
#	Line 323 | Line 366 | public class ReadMostlyVector<E> impleme
366		return contained;
367		}
368
369	<	final boolean internalEquals(List<?> list, int origin, int span) {
369	>	final boolean internalEquals(List<?> list, int origin, int bound) {
370		SequenceLock lock = this.lock;
328	–	boolean equal;
371		boolean locked = false;
372	+	boolean equal;
373		try {
374		for (;;) {
332	–	equal = true;
375		long seq = lock.awaitAvailability();
376		Object[] items = array;
377	<	int len = items.length;
378	<	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)
377	>	int n = count;
378	>	if (n > items.length || origin < 0)
379		equal = false;
380		else {
381	+	equal = true;
382	+	int fence = bound < 0 || bound > n ? n : bound;
383		Iterator<?> it = list.iterator();
384		for (int i = origin; i < fence; ++i) {
385	<	if (!it.hasNext()) {
386	<	equal = false;
387	<	break;
388	<	}
389	<	Object x = it.next();
390	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
385	>	Object x = items[i];
386	>	Object y;
387	>	if ((!locked && lock.getSequence() != seq) ||
388	>	!it.hasNext() ||
389	>	(y = it.next()) == null ?
390	>	x != null : !y.equals(x)) {
391		equal = false;
392		break;
393		}
#	Line 370 | Line 407 | public class ReadMostlyVector<E> impleme
407		return equal;
408		}
409
410	<	final int internalHashCode(int origin, int span) {
410	>	final int internalHashCode(int origin, int bound) {
411		SequenceLock lock = this.lock;
412		int hash;
413		boolean locked = false;
#	Line 380 | Line 417 | public class ReadMostlyVector<E> impleme
417		long seq = lock.awaitAvailability();
418		Object[] items = array;
419		int len = items.length;
420	<	int c = count;
421	<	if (c > len)
420	>	int n = count;
421	>	if (n > len)
422		continue;
423	<	int fence = c;
424	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
423	>	int fence = bound < 0 || bound > n ? n : bound;
424	>	if (origin >= 0) {
425		for (int i = origin; i < fence; ++i) {
426		Object e = items[i];
427		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 439 | public class ReadMostlyVector<E> impleme
439		return hash;
440		}
441
442	<	final String internalToString(int origin, int span) {
442	>	final String internalToString(int origin, int bound) {
443		SequenceLock lock = this.lock;
444		String ret;
445		boolean locked = false;
446		try {
447	<	for (;;) {
447	>	outer:for (;;) {
448		long seq = lock.awaitAvailability();
449		Object[] items = array;
450		int len = items.length;
451	<	int c = count;
452	<	if (c > len)
451	>	int n = count;
452	>	if (n > len)
453		continue;
454	<	int fence = c;
455	<	if (span >= 0 && origin + span < fence)
456	<	fence = origin + span;
457	<	if (origin >= 0 && fence <= c) {
458	<	if (origin == fence)
459	<	ret = "[]";
460	<	else {
461	<	StringBuilder sb = new StringBuilder();
462	<	sb.append('[');
463	<	for (int i = origin;;) {
464	<	Object e = items[i];
465	<	sb.append(e == this ? "(this Collection)" : e);
466	<	if (++i < fence)
467	<	sb.append(',').append(' ');
468	<	else {
469	<	ret = sb.append(']').toString();
470	<	break;
471	<	}
454	>	int fence = bound < 0 || bound > n ? n : bound;
455	>	if (origin < 0 || origin == fence)
456	>	ret = "[]";
457	>	else {
458	>	StringBuilder sb = new StringBuilder();
459	>	sb.append('[');
460	>	for (int i = origin;;) {
461	>	Object e = items[i];
462	>	if (e == this)
463	>	sb.append("(this Collection)");
464	>	else if (!locked && lock.getSequence() != seq)
465	>	continue outer;
466	>	else
467	>	sb.append(e.toString());
468	>	if (++i < fence)
469	>	sb.append(',').append(' ');
470	>	else {
471	>	ret = sb.append(']').toString();
472	>	break;
473		}
474		}
439	–	if (lock.getSequence() == seq)
440	–	break;
475		}
476	+	if (lock.getSequence() == seq)
477	+	break;
478		lock.lock();
479		locked = true;
480		}
#	Line 449 | Line 485 | public class ReadMostlyVector<E> impleme
485		return ret;
486		}
487
488	<	final Object[] internalToArray(int origin, int span) {
488	>	final Object[] internalToArray(int origin, int bound) {
489		Object[] result;
490		SequenceLock lock = this.lock;
491		boolean locked = false;
#	Line 459 | Line 495 | public class ReadMostlyVector<E> impleme
495		long seq = lock.awaitAvailability();
496		Object[] items = array;
497		int len = items.length;
498	<	int c = count;
499	<	int fence = c;
500	<	if (span >= 0 && origin + span < fence)
501	<	fence = origin + span;
502	<	if (c <= len && fence <= len) {
498	>	int n = count;
499	>	if (n > len)
500	>	continue;
501	>	int fence = bound < 0 || bound > n ? n : bound;
502	>	if (origin >= 0)
503		result = Arrays.copyOfRange(items, origin, fence,
504		Object[].class);
505	<	if (lock.getSequence() == seq)
506	<	break;
471	<	}
505	>	if (lock.getSequence() == seq)
506	>	break;
507		lock.lock();
508		locked = true;
509		}
#	Line 479 | Line 514 | public class ReadMostlyVector<E> impleme
514		return result;
515		}
516
517	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
517	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
518	>	int alen = a.length;
519		T[] result;
520		SequenceLock lock = this.lock;
521		boolean locked = false;
#	Line 488 | Line 524 | public class ReadMostlyVector<E> impleme
524		long seq = lock.awaitAvailability();
525		Object[] items = array;
526		int len = items.length;
527	<	int c = count;
528	<	int fence = c;
529	<	if (span >= 0 && origin + span < fence)
530	<	fence = origin + span;
531	<	if (c <= len && fence <= len) {
532	<	if (a.length < count)
533	<	result = (T[]) Arrays.copyOfRange(array, origin,
534	<	fence, a.getClass());
535	<	else {
536	<	int n = fence - origin;
537	<	System.arraycopy(array, 0, a, origin, fence - origin);
538	<	if (a.length > n)
539	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
527	>	int n = count;
528	>	if (n > len)
529	>	continue;
530	>	int fence = bound < 0 || bound > n ? n : bound;
531	>	int rlen = fence - origin;
532	>	if (rlen < 0)
533	>	rlen = 0;
534	>	if (origin < 0 || alen >= rlen) {
535	>	if (rlen > 0)
536	>	System.arraycopy(items, 0, a, origin, rlen);
537	>	if (alen > rlen)
538	>	a[rlen] = null;
539	>	result = a;
540		}
541	+	else
542	+	result = (T[]) Arrays.copyOfRange(items, origin,
543	+	fence, a.getClass());
544	+	if (lock.getSequence() == seq)
545	+	break;
546		lock.lock();
547		locked = true;
548		}
#	Line 522 | Line 559 | public class ReadMostlyVector<E> impleme
559		SequenceLock lock = this.lock;
560		lock.lock();
561		try {
562	<	internalAdd(e);
562	>	rawAdd(e);
563		} finally {
564		lock.unlock();
565		}
#	Line 533 | Line 570 | public class ReadMostlyVector<E> impleme
570		SequenceLock lock = this.lock;
571		lock.lock();
572		try {
573	<	internalAddAt(index, element);
573	>	rawAddAt(index, element);
574		} finally {
575		lock.unlock();
576		}
#	Line 564 | Line 601 | public class ReadMostlyVector<E> impleme
601		Object[] elements = c.toArray();
602		lock.lock();
603		try {
604	<	ret = internalAddAllAt(index, elements);
604	>	ret = rawAddAllAt(index, elements);
605		} finally {
606		lock.unlock();
607		}
#	Line 575 | Line 612 | public class ReadMostlyVector<E> impleme
612		SequenceLock lock = this.lock;
613		lock.lock();
614		try {
615	+	Object[] items = array;
616		for (int i = 0; i < count; i++)
617	<	array[i] = null;
617	>	items[i] = null;
618		count = 0;
619		} finally {
620		lock.unlock();
#	Line 596 | Line 634 | public class ReadMostlyVector<E> impleme
634		return true;
635		if (!(o instanceof List))
636		return false;
637	<	return internalEquals((List<?>)(o), 0, -1);
637	>	return internalEquals((List<?>)o, 0, -1);
638		}
639
640		public E get(int index) {
#	Line 604 | Line 642 | public class ReadMostlyVector<E> impleme
642		for (;;) {
643		long seq = lock.awaitAvailability();
644		Object[] items = array;
645	<	int len = items.length;
646	<	int c = count;
609	<	if (c > len)
645	>	int n = count;
646	>	if (n > items.length)
647		continue;
648	<	E e; boolean ex;
649	<	if (index < 0 || index >= c) {
648	>	Object e; boolean ex;
649	>	if (index < 0 || index >= n) {
650		e = null;
651		ex = true;
652		}
653		else {
654	<	e = (E)items[index];
654	>	e = items[index];
655		ex = false;
656		}
657		if (lock.getSequence() == seq) {
658		if (ex)
659		throw new ArrayIndexOutOfBoundsException(index);
660		else
661	<	return e;
661	>	return (E)e;
662		}
663		}
664		}
#	Line 632 | Line 669 | public class ReadMostlyVector<E> impleme
669
670		public int indexOf(Object o) {
671		SequenceLock lock = this.lock;
672	<	long seq = lock.awaitAvailability();
673	<	Object[] items = array;
674	<	int c = count;
675	<	if (c <= items.length) {
676	<	int idx = internalIndexOf(o, items, 0, c);
677	<	if (lock.getSequence() == seq)
678	<	return idx;
679	<	}
680	<	lock.lock();
681	<	try {
682	<	return internalIndexOf(o, array, 0, count);
683	<	} finally {
684	<	lock.unlock();
672	>	for (;;) {
673	>	long seq = lock.awaitAvailability();
674	>	Object[] items = array;
675	>	int n = count;
676	>	if (n <= items.length) {
677	>	for (int i = 0; i < n; ++i) {
678	>	Object e = items[i];
679	>	if (lock.getSequence() != seq) {
680	>	lock.lock();
681	>	try {
682	>	return rawIndexOf(o, 0, count);
683	>	} finally {
684	>	lock.unlock();
685	>	}
686	>	}
687	>	else if ((o == null) ? e == null : o.equals(e))
688	>	return i;
689	>	}
690	>	return -1;
691	>	}
692		}
693		}
694
695		public boolean isEmpty() {
652	–	long ignore = lock.getSequence();
696		return count == 0;
697		}
698
699		public Iterator<E> iterator() {
700	<	return new Itr(this, 0);
700	>	return new Itr<E>(this, 0);
701		}
702
703		public int lastIndexOf(Object o) {
704		SequenceLock lock = this.lock;
705	<	long seq = lock.awaitAvailability();
706	<	Object[] items = array;
707	<	int c = count;
708	<	if (c <= items.length) {
709	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
710	<	if (lock.getSequence() == seq)
711	<	return idx;
712	<	}
713	<	lock.lock();
714	<	try {
715	<	return internalLastIndexOf(o, array, count-1, 0);
716	<	} finally {
717	<	lock.unlock();
705	>	for (;;) {
706	>	long seq = lock.awaitAvailability();
707	>	Object[] items = array;
708	>	int n = count;
709	>	if (n <= items.length) {
710	>	for (int i = n - 1; i >= 0; --i) {
711	>	Object e = items[i];
712	>	if (lock.getSequence() != seq) {
713	>	lock.lock();
714	>	try {
715	>	return rawLastIndexOf(o, 0, count);
716	>	} finally {
717	>	lock.unlock();
718	>	}
719	>	}
720	>	else if ((o == null) ? e == null : o.equals(e))
721	>	return i;
722	>	}
723	>	return -1;
724	>	}
725		}
726		}
727
728		public ListIterator<E> listIterator() {
729	<	return new Itr(this, 0);
729	>	return new Itr<E>(this, 0);
730		}
731
732		public ListIterator<E> listIterator(int index) {
733	<	return new Itr(this, index);
733	>	return new Itr<E>(this, index);
734		}
735
736		public E remove(int index) {
737		SequenceLock lock = this.lock;
738	<	E oldValue;
738	>	Object oldValue;
739		lock.lock();
740		try {
741		if (index < 0 || index >= count)
742		throw new ArrayIndexOutOfBoundsException(index);
743	<	oldValue = (E)array[index];
744	<	internalRemoveAt(index);
743	>	oldValue = array[index];
744	>	rawRemoveAt(index);
745		} finally {
746		lock.unlock();
747		}
748	<	return oldValue;
748	>	return (E)oldValue;
749		}
750
751		public boolean remove(Object o) {
#	Line 703 | Line 753 | public class ReadMostlyVector<E> impleme
753		boolean removed;
754		lock.lock();
755		try {
756	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
756	>	removed = rawRemoveAt(rawIndexOf(o, 0, count));
757		} finally {
758		lock.unlock();
759		}
#	Line 719 | Line 769 | public class ReadMostlyVector<E> impleme
769		}
770
771		public E set(int index, E element) {
772	<	E oldValue;
772	>	Object oldValue;
773		SequenceLock lock = this.lock;
774		lock.lock();
775		try {
776	+	Object[] items = array;
777		if (index < 0 || index >= count)
778		throw new ArrayIndexOutOfBoundsException(index);
779	<	oldValue = (E)array[index];
780	<	array[index] = element;
779	>	oldValue = items[index];
780	>	items[index] = element;
781		} finally {
782		lock.unlock();
783		}
784	<	return oldValue;
784	>	return (E)oldValue;
785		}
786
787		public int size() {
737	–	long ignore = lock.getSequence();
788		return count;
789		}
790
#	Line 743 | Line 793 | public class ReadMostlyVector<E> impleme
793		int ssize = toIndex - fromIndex;
794		if (fromIndex < 0 || toIndex > c || ssize < 0)
795		throw new IndexOutOfBoundsException();
796	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
796	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
797		}
798
799		public Object[] toArray() {
#	Line 764 | Line 814 | public class ReadMostlyVector<E> impleme
814		* Append the element if not present.
815		*
816		* @param e element to be added to this list, if absent
817	<	* @return <tt>true</tt> if the element was added
817	>	* @return {@code true} if the element was added
818		*/
819		public boolean addIfAbsent(E e) {
820		boolean added;
821		SequenceLock lock = this.lock;
822		lock.lock();
823		try {
824	<	if (internalIndexOf(e, array, 0, count) < 0) {
825	<	internalAdd(e);
824	>	if (rawIndexOf(e, 0, count) < 0) {
825	>	rawAdd(e);
826		added = true;
827		}
828		else
#	Line 803 | Line 853 | public class ReadMostlyVector<E> impleme
853		try {
854		for (int i = 0; i < clen; ++i) {
855		Object e = cs[i];
856	<	if (internalIndexOf(e, array, 0, count) < 0) {
857	<	internalAdd((E)e);
856	>	if (rawIndexOf(e, 0, count) < 0) {
857	>	rawAdd(e);
858		++added;
859		}
860		}
#	Line 815 | Line 865 | public class ReadMostlyVector<E> impleme
865		return added;
866		}
867
868	+	/**
869	+	* Returns an iterator operating over a snapshot copy of the
870	+	* elements of this collection created upon construction of the
871	+	* iterator. The iterator does <em>NOT</em> support the
872	+	* {@code remove} method.
873	+	*
874	+	* @return an iterator over the elements in this list in proper sequence
875	+	*/
876	+	public Iterator<E> snapshotIterator() {
877	+	return new SnapshotIterator<E>(this);
878	+	}
879	+
880	+	static final class SnapshotIterator<E> implements Iterator<E> {
881	+	final Object[] items;
882	+	int cursor;
883	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
884	+	public boolean hasNext() { return cursor < items.length; }
885	+	public E next() {
886	+	if (cursor < items.length)
887	+	return (E) items[cursor++];
888	+	throw new NoSuchElementException();
889	+	}
890	+	public void remove() { throw new UnsupportedOperationException() ; }
891	+	}
892	+
893		// Vector-only methods
894
895		/** See {@link Vector#firstElement} */
#	Line 824 | Line 899 | public class ReadMostlyVector<E> impleme
899		long seq = lock.awaitAvailability();
900		Object[] items = array;
901		int len = items.length;
902	<	int c = count;
903	<	if (c > len || c < 0)
902	>	int n = count;
903	>	if (n > len)
904		continue;
905	<	E e; boolean ex;
906	<	if (c == 0) {
907	<	e = null;
908	<	ex = true;
905	>	Object e; boolean ex;
906	>	if (n > 0) {
907	>	e = items[0];
908	>	ex = false;
909		}
910		else {
911	<	e = (E)items[0];
912	<	ex = false;
911	>	e = null;
912	>	ex = true;
913		}
914		if (lock.getSequence() == seq) {
915		if (ex)
916		throw new NoSuchElementException();
917		else
918	<	return e;
918	>	return (E)e;
919		}
920		}
921		}
#	Line 852 | Line 927 | public class ReadMostlyVector<E> impleme
927		long seq = lock.awaitAvailability();
928		Object[] items = array;
929		int len = items.length;
930	<	int c = count;
931	<	if (c > len || c < 0)
930	>	int n = count;
931	>	if (n > len)
932		continue;
933	<	E e; boolean ex;
934	<	if (c == 0) {
935	<	e = null;
936	<	ex = true;
933	>	Object e; boolean ex;
934	>	if (n > 0) {
935	>	e = items[n - 1];
936	>	ex = false;
937		}
938		else {
939	<	e = (E)items[c - 1];
940	<	ex = false;
939	>	e = null;
940	>	ex = true;
941		}
942		if (lock.getSequence() == seq) {
943		if (ex)
944		throw new NoSuchElementException();
945		else
946	<	return e;
946	>	return (E)e;
947		}
948		}
949		}
#	Line 880 | Line 955 | public class ReadMostlyVector<E> impleme
955		boolean ex = false;
956		long seq = lock.awaitAvailability();
957		Object[] items = array;
958	<	int c = count;
958	>	int n = count;
959		boolean retry = false;
960	<	if (c > items.length)
960	>	if (n > items.length)
961		retry = true;
962		else if (index < 0)
963		ex = true;
964		else
965	<	idx = internalIndexOf(o, items, index, c);
965	>	idx = validatedIndexOf(o, items, index, n, seq);
966		if (retry || lock.getSequence() != seq) {
967		lock.lock();
968		try {
969		if (index < 0)
970		ex = true;
971		else
972	<	idx = internalIndexOf(o, array, 0, count);
972	>	idx = rawIndexOf(o, 0, count);
973		} finally {
974		lock.unlock();
975		}
#	Line 911 | Line 986 | public class ReadMostlyVector<E> impleme
986		boolean ex = false;
987		long seq = lock.awaitAvailability();
988		Object[] items = array;
989	<	int c = count;
989	>	int n = count;
990		boolean retry = false;
991	<	if (c > items.length)
991	>	if (n > items.length)
992		retry = true;
993	<	else if (index >= c)
993	>	else if (index >= n)
994		ex = true;
995		else
996	<	idx = internalLastIndexOf(o, items, index, 0);
996	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
997		if (retry || lock.getSequence() != seq) {
998		lock.lock();
999		try {
1000		if (index >= count)
1001		ex = true;
1002		else
1003	<	idx = internalLastIndexOf(o, array, index, 0);
1003	>	idx = rawLastIndexOf(o, index, 0);
1004		} finally {
1005		lock.unlock();
1006		}
#	Line 942 | Line 1017 | public class ReadMostlyVector<E> impleme
1017		SequenceLock lock = this.lock;
1018		lock.lock();
1019		try {
1020	<	int c = count;
1021	<	if (newSize > c)
1020	>	int n = count;
1021	>	if (newSize > n)
1022		grow(newSize);
1023		else {
1024	<	for (int i = newSize ; i < c ; i++)
1025	<	array[i] = null;
1024	>	Object[] items = array;
1025	>	for (int i = newSize ; i < n ; i++)
1026	>	items[i] = null;
1027		}
1028		count = newSize;
1029		} finally {
#	Line 971 | Line 1047 | public class ReadMostlyVector<E> impleme
1047		SequenceLock lock = this.lock;
1048		lock.lock();
1049		try {
1050	<	if (count < array.length)
1051	<	array = Arrays.copyOf(array, count);
1050	>	Object[] items = array;
1051	>	if (count < items.length)
1052	>	array = Arrays.copyOf(items, count);
1053		} finally {
1054		lock.unlock();
1055		}
#	Line 994 | Line 1071 | public class ReadMostlyVector<E> impleme
1071
1072		/** See {@link Vector#elements} */
1073		public Enumeration<E> elements() {
1074	<	return new Itr(this, 0);
1074	>	return new Itr<E>(this, 0);
1075		}
1076
1077		/** See {@link Vector#capacity} */
1078		public int capacity() {
1002	–	long ignore = lock.getSequence();
1079		return array.length;
1080		}
1081
#	Line 1040 | Line 1116 | public class ReadMostlyVector<E> impleme
1116
1117		// other methods
1118
1119	<	public Object clone() {
1119	>	public ReadMostlyVector<E> clone() {
1120		SequenceLock lock = this.lock;
1121		Object[] a = null;
1046	–	int c;
1122		boolean retry = false;
1123		long seq = lock.awaitAvailability();
1124		Object[] items = array;
1125	<	c = count;
1126	<	if (c <= items.length)
1127	<	a = Arrays.copyOf(items, c);
1125	>	int n = count;
1126	>	if (n <= items.length)
1127	>	a = Arrays.copyOf(items, n);
1128		else
1129		retry = true;
1130		if (retry || lock.getSequence() != seq) {
1131		lock.lock();
1132		try {
1133	<	c = count;
1134	<	a = Arrays.copyOf(array, c);
1133	>	n = count;
1134	>	a = Arrays.copyOf(array, n);
1135		} finally {
1136		lock.unlock();
1137		}
1138		}
1139	<	return new ReadMostlyVector(a, c, capacityIncrement);
1139	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1140		}
1141
1142		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1159 | public class ReadMostlyVector<E> impleme
1159		int cursor;
1160		int fence;
1161		int lastRet;
1162	<	boolean haveNext, havePrev;
1162	>	boolean validNext, validPrev;
1163
1164		Itr(ReadMostlyVector<E> list, int index) {
1165		this.list = list;
#	Line 1097 | Line 1172 | public class ReadMostlyVector<E> impleme
1172		}
1173
1174		private void refresh() {
1175	+	validNext = validPrev = false;
1176		do {
1177		seq = lock.awaitAvailability();
1178		items = list.array;
1179	<	fence = list.count;
1180	<	} while (lock.getSequence() != seq);
1179	>	} while ((fence = list.count) > items.length ||
1180	>	lock.getSequence() != seq);
1181		}
1182
1183		public boolean hasNext() {
1184	+	boolean valid;
1185		int i = cursor;
1186	<	while (i < fence && i >= 0) {
1186	>	for (;;) {
1187	>	if (i >= fence || i < 0 || i >= items.length) {
1188	>	valid = false;
1189	>	break;
1190	>	}
1191	>	next = items[i];
1192		if (lock.getSequence() == seq) {
1193	<	next = items[i];
1194	<	return haveNext = true;
1193	>	valid = true;
1194	>	break;
1195		}
1196		refresh();
1197		}
1198	<	return false;
1198	>	return validNext = valid;
1199		}
1200
1201		public boolean hasPrevious() {
1202	<	int i = cursor;
1203	<	while (i <= fence && i > 0) {
1202	>	boolean valid;
1203	>	int i = cursor - 1;
1204	>	for (;;) {
1205	>	if (i >= fence || i < 0 || i >= items.length) {
1206	>	valid = false;
1207	>	break;
1208	>	}
1209	>	prev = items[i];
1210		if (lock.getSequence() == seq) {
1211	<	prev = items[i - 1];
1212	<	return havePrev = true;
1211	>	valid = true;
1212	>	break;
1213		}
1214		refresh();
1215		}
1216	<	return false;
1216	>	return validPrev = valid;
1217		}
1218
1219		public E next() {
1220	<	if (!haveNext && !hasNext())
1221	<	throw new NoSuchElementException();
1222	<	haveNext = false;
1223	<	lastRet = cursor++;
1224	<	return (E) next;
1220	>	if (validNext || hasNext()) {
1221	>	validNext = false;
1222	>	lastRet = cursor++;
1223	>	return (E) next;
1224	>	}
1225	>	throw new NoSuchElementException();
1226		}
1227
1228		public E previous() {
1229	<	if (!havePrev && !hasPrevious())
1230	<	throw new NoSuchElementException();
1231	<	havePrev = false;
1232	<	lastRet = cursor--;
1233	<	return (E) prev;
1229	>	if (validPrev || hasPrevious()) {
1230	>	validPrev = false;
1231	>	lastRet = cursor--;
1232	>	return (E) prev;
1233	>	}
1234	>	throw new NoSuchElementException();
1235		}
1236
1237		public void remove() {
#	Line 1217 | Line 1307 | public class ReadMostlyVector<E> impleme
1307		lock.lock();
1308		try {
1309		int c = size;
1310	<	list.internalAddAt(c + offset, element);
1310	>	list.rawAddAt(c + offset, element);
1311		size = c + 1;
1312		} finally {
1313		lock.unlock();
#	Line 1231 | Line 1321 | public class ReadMostlyVector<E> impleme
1321		try {
1322		if (index < 0 || index > size)
1323		throw new ArrayIndexOutOfBoundsException(index);
1324	<	list.internalAddAt(index + offset, element);
1324	>	list.rawAddAt(index + offset, element);
1325		++size;
1326		} finally {
1327		lock.unlock();
#	Line 1246 | Line 1336 | public class ReadMostlyVector<E> impleme
1336		try {
1337		int s = size;
1338		int pc = list.count;
1339	<	list.internalAddAllAt(offset + s, elements);
1339	>	list.rawAddAllAt(offset + s, elements);
1340		added = list.count - pc;
1341		size = s + added;
1342		} finally {
#	Line 1265 | Line 1355 | public class ReadMostlyVector<E> impleme
1355		if (index < 0 || index > s)
1356		throw new ArrayIndexOutOfBoundsException(index);
1357		int pc = list.count;
1358	<	list.internalAddAllAt(index + offset, elements);
1358	>	list.rawAddAllAt(index + offset, elements);
1359		added = list.count - pc;
1360		size = s + added;
1361		} finally {
#	Line 1278 | Line 1368 | public class ReadMostlyVector<E> impleme
1368		SequenceLock lock = list.lock;
1369		lock.lock();
1370		try {
1371	<	list.internalClear(offset, size);
1371	>	list.internalClear(offset, offset + size);
1372		size = 0;
1373		} finally {
1374		lock.unlock();
#	Line 1290 | Line 1380 | public class ReadMostlyVector<E> impleme
1380		}
1381
1382		public boolean containsAll(Collection<?> c) {
1383	<	return list.internalContainsAll(c, offset, size);
1383	>	return list.internalContainsAll(c, offset, offset + size);
1384		}
1385
1386		public boolean equals(Object o) {
#	Line 1298 | Line 1388 | public class ReadMostlyVector<E> impleme
1388		return true;
1389		if (!(o instanceof List))
1390		return false;
1391	<	return list.internalEquals((List<?>)(o), offset, size);
1391	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1392		}
1393
1394		public E get(int index) {
#	Line 1308 | Line 1398 | public class ReadMostlyVector<E> impleme
1398		}
1399
1400		public int hashCode() {
1401	<	return list.internalHashCode(offset, size);
1401	>	return list.internalHashCode(offset, offset + size);
1402		}
1403
1404		public int indexOf(Object o) {
#	Line 1317 | Line 1407 | public class ReadMostlyVector<E> impleme
1407		Object[] items = list.array;
1408		int c = list.count;
1409		if (c <= items.length) {
1410	<	int idx = internalIndexOf(o, items, offset, offset+size);
1410	>	int idx = list.validatedIndexOf(o, items, offset,
1411	>	offset + size, seq);
1412		if (lock.getSequence() == seq)
1413		return idx < 0 ? -1 : idx - offset;
1414		}
1415		lock.lock();
1416		try {
1417	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1417	>	int idx = list.rawIndexOf(o, offset, offset + size);
1418		return idx < 0 ? -1 : idx - offset;
1419		} finally {
1420		lock.unlock();
#	Line 1335 | Line 1426 | public class ReadMostlyVector<E> impleme
1426		}
1427
1428		public Iterator<E> iterator() {
1429	<	return new SubItr(this, offset);
1429	>	return new SubItr<E>(this, offset);
1430		}
1431
1432		public int lastIndexOf(Object o) {
#	Line 1344 | Line 1435 | public class ReadMostlyVector<E> impleme
1435		Object[] items = list.array;
1436		int c = list.count;
1437		if (c <= items.length) {
1438	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1438	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1439	>	offset, seq);
1440		if (lock.getSequence() == seq)
1441		return idx < 0 ? -1 : idx - offset;
1442		}
1443		lock.lock();
1444		try {
1445	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1445	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1446		return idx < 0 ? -1 : idx - offset;
1447		} finally {
1448		lock.unlock();
#	Line 1359 | Line 1450 | public class ReadMostlyVector<E> impleme
1450		}
1451
1452		public ListIterator<E> listIterator() {
1453	<	return new SubItr(this, offset);
1453	>	return new SubItr<E>(this, offset);
1454		}
1455
1456		public ListIterator<E> listIterator(int index) {
1457	<	return new SubItr(this, index + offset);
1457	>	return new SubItr<E>(this, index + offset);
1458		}
1459
1460		public E remove(int index) {
1461	<	E result;
1461	>	Object result;
1462		SequenceLock lock = list.lock;
1463		lock.lock();
1464		try {
1465	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1465	>	Object[] items = list.array;
1466		int i = index + offset;
1467	<	result = (E)list.array[i];
1468	<	list.internalRemoveAt(i);
1467	>	if (index < 0 || index >= size || i >= items.length)
1468	>	throw new ArrayIndexOutOfBoundsException(index);
1469	>	result = items[i];
1470	>	list.rawRemoveAt(i);
1471		size--;
1472		} finally {
1473		lock.unlock();
1474		}
1475	<	return result;
1475	>	return (E)result;
1476		}
1477
1478		public boolean remove(Object o) {
#	Line 1388 | Line 1480 | public class ReadMostlyVector<E> impleme
1480		SequenceLock lock = list.lock;
1481		lock.lock();
1482		try {
1483	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1484	<	offset+size))) {
1483	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1484	>	offset + size))) {
1485		removed = true;
1486		--size;
1487		}
#	Line 1400 | Line 1492 | public class ReadMostlyVector<E> impleme
1492		}
1493
1494		public boolean removeAll(Collection<?> c) {
1495	<	return list.internalRemoveAll(c, offset, size);
1495	>	return list.internalRemoveAll(c, offset, offset + size);
1496		}
1497
1498		public boolean retainAll(Collection<?> c) {
1499	<	return list.internalRetainAll(c, offset, size);
1499	>	return list.internalRetainAll(c, offset, offset + size);
1500		}
1501
1502		public E set(int index, E element) {
#	Line 1422 | Line 1514 | public class ReadMostlyVector<E> impleme
1514		int ssize = toIndex - fromIndex;
1515		if (fromIndex < 0 || toIndex > c || ssize < 0)
1516		throw new IndexOutOfBoundsException();
1517	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1517	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1518		}
1519
1520		public Object[] toArray() {
1521	<	return list.internalToArray(offset, size);
1521	>	return list.internalToArray(offset, offset + size);
1522		}
1523
1524		public <T> T[] toArray(T[] a) {
1525	<	return list.internalToArray(a, offset, size);
1525	>	return list.internalToArray(a, offset, offset + size);
1526		}
1527
1528		public String toString() {
1529	<	return list.internalToString(offset, size);
1529	>	return list.internalToString(offset, offset + size);
1530		}
1531
1532		}
#	Line 1449 | Line 1541 | public class ReadMostlyVector<E> impleme
1541		int cursor;
1542		int fence;
1543		int lastRet;
1544	<	boolean haveNext, havePrev;
1544	>	boolean validNext, validPrev;
1545
1546		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1547		this.sublist = sublist;
#	Line 1463 | Line 1555 | public class ReadMostlyVector<E> impleme
1555		}
1556
1557		private void refresh() {
1558	+	validNext = validPrev = false;
1559		do {
1560	+	int n;
1561		seq = lock.awaitAvailability();
1562		items = list.array;
1563	<	int c = list.count;
1563	>	if ((n = list.count) > items.length)
1564	>	continue;
1565		int b = sublist.offset + sublist.size;
1566	<	fence = b < c ? b : c;
1566	>	fence = b < n ? b : n;
1567		} while (lock.getSequence() != seq);
1568		}
1569
1570		public boolean hasNext() {
1571	+	boolean valid;
1572		int i = cursor;
1573	<	while (i < fence && i >= 0) {
1573	>	for (;;) {
1574	>	if (i >= fence || i < 0 || i >= items.length) {
1575	>	valid = false;
1576	>	break;
1577	>	}
1578	>	next = items[i];
1579		if (lock.getSequence() == seq) {
1580	<	next = items[i];
1581	<	return haveNext = true;
1580	>	valid = true;
1581	>	break;
1582		}
1583		refresh();
1584		}
1585	<	return false;
1585	>	return validNext = valid;
1586		}
1587
1588		public boolean hasPrevious() {
1589	<	int i = cursor;
1590	<	while (i <= fence && i > 0) {
1589	>	boolean valid;
1590	>	int i = cursor - 1;
1591	>	for (;;) {
1592	>	if (i >= fence || i < 0 || i >= items.length) {
1593	>	valid = false;
1594	>	break;
1595	>	}
1596	>	prev = items[i];
1597		if (lock.getSequence() == seq) {
1598	<	prev = items[i - 1];
1599	<	return havePrev = true;
1598	>	valid = true;
1599	>	break;
1600		}
1601		refresh();
1602		}
1603	<	return false;
1603	>	return validPrev = valid;
1604		}
1605
1606		public E next() {
1607	<	if (!haveNext && !hasNext())
1608	<	throw new NoSuchElementException();
1609	<	haveNext = false;
1610	<	lastRet = cursor++;
1611	<	return (E) next;
1607	>	if (validNext || hasNext()) {
1608	>	validNext = false;
1609	>	lastRet = cursor++;
1610	>	return (E) next;
1611	>	}
1612	>	throw new NoSuchElementException();
1613		}
1614
1615		public E previous() {
1616	<	if (!havePrev && !hasPrevious())
1617	<	throw new NoSuchElementException();
1618	<	havePrev = false;
1619	<	lastRet = cursor--;
1620	<	return (E) prev;
1616	>	if (validPrev || hasPrevious()) {
1617	>	validPrev = false;
1618	>	lastRet = cursor--;
1619	>	return (E) prev;
1620	>	}
1621	>	throw new NoSuchElementException();
1622		}
1623
1624		public int nextIndex() {

Diff Legend

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