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.2 by dl, Sat Jul 16 13:20:35 2011 UTC vs.
Revision 1.17 by jsr166, Sat Dec 31 05:38:24 2011 UTC

#	Line 12 | Line 12 | import java.util.*;
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.
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. Alternatively,
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 29 | Line 32 | import java.util.*;
32		*
33		* @author Doug Lea
34		*/
35	<	public class ReadMostlyVector<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
35	>	public class ReadMostlyVector<E>
36	>	implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
37		private static final long serialVersionUID = 8673264195747942595L;
38
39		/*
#	Line 40 | Line 44 | public class ReadMostlyVector<E> impleme
44		* Short methods,including get(index), continually retry obtaining
45		* a snapshot of array, count, and element, using sequence number
46		* to validate.
47	<	*
47	>	*
48		* Methods that are potentially O(n) (or worse) try once in
49		* read-only mode, and then lock. When in read-only mode, they
50		* validate only at the end of an array scan unless the element is
#	Line 54 | Line 58 | public class ReadMostlyVector<E> impleme
58		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
59
60		// fields are non-private to simpify nested class access
61	<	Object[] array;
61	>	volatile Object[] array;
62		final SequenceLock lock;
63	<	int count;
63	>	volatile int count;
64		final int capacityIncrement;
65
66		/**
#	Line 126 | Line 130 | public class ReadMostlyVector<E> impleme
130		}
131
132		// For explanation, see CopyOnWriteArrayList
133	<	final void grow(int minCapacity) {
133	>	final Object[] grow(int minCapacity) {
134		int oldCapacity = array.length;
135		int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
136		capacityIncrement : oldCapacity);
#	Line 134 | Line 138 | public class ReadMostlyVector<E> impleme
138		newCapacity = minCapacity;
139		if (newCapacity - MAX_ARRAY_SIZE > 0)
140		newCapacity = hugeCapacity(minCapacity);
141	<	array = Arrays.copyOf(array, newCapacity);
141	>	return array = Arrays.copyOf(array, newCapacity);
142		}
143
144		static int hugeCapacity(int minCapacity) {
#	Line 151 | Line 155 | public class ReadMostlyVector<E> impleme
155		* as well as sublist and iterator classes.
156		*/
157
158	<	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
158	>	// Version of indexOf that returns -1 if either not present or invalid
159	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
160		long seq) {
161		for (int i = index; i < fence; ++i) {
162		Object e = items[i];
163		if (lock.getSequence() != seq)
164		break;
165	<	if (x == null? e == null : (e != null && x.equals(e)))
165	>	if ((x == null) ? e == null : x.equals(e))
166		return i;
167		}
168		return -1;
#	Line 167 | Line 172 | public class ReadMostlyVector<E> impleme
172		Object[] items = array;
173		for (int i = index; i < fence; ++i) {
174		Object e = items[i];
175	<	if (x == null? e == null : (e != null && x.equals(e)))
175	>	if ((x == null) ? e == null : x.equals(e))
176		return i;
177		}
178		return -1;
179		}
180
181	<	final int validatedLastIndexOf(Object x, Object[] items,
181	>	final int validatedLastIndexOf(Object x, Object[] items,
182		int index, int origin, long seq) {
183		for (int i = index; i >= origin; --i) {
184		Object e = items[i];
185		if (lock.getSequence() != seq)
186		break;
187	<	if (x == null? e == null : (e != null && x.equals(e)))
187	>	if ((x == null) ? e == null : x.equals(e))
188		return i;
189		}
190		return -1;
#	Line 189 | Line 194 | public class ReadMostlyVector<E> impleme
194		Object[] items = array;
195		for (int i = index; i >= origin; --i) {
196		Object e = items[i];
197	<	if (x == null? e == null : (e != null && x.equals(e)))
197	>	if ((x == null) ? e == null : x.equals(e))
198		return i;
199		}
200		return -1;
201		}
202
203	<	final void internalAdd(Object e) {
203	>	final void rawAdd(E e) {
204		int n = count;
205	<	if (n >= array.length)
206	<	grow(n + 1);
207	<	array[n] = e;
205	>	Object[] items = array;
206	>	if (n >= items.length)
207	>	items = grow(n + 1);
208	>	items[n] = e;
209		count = n + 1;
210		}
211
212	<	final void internalAddAt(int index, Object e) {
212	>	final void rawAddAt(int index, E e) {
213		int n = count;
214	+	Object[] items = array;
215		if (index > n)
216		throw new ArrayIndexOutOfBoundsException(index);
217	<	if (n >= array.length)
218	<	grow(n + 1);
217	>	if (n >= items.length)
218	>	items = grow(n + 1);
219		if (index < n)
220	<	System.arraycopy(array, index, array, index + 1, n - index);
221	<	array[index] = e;
220	>	System.arraycopy(items, index, items, index + 1, n - index);
221	>	items[index] = e;
222		count = n + 1;
223		}
224
225	<	final boolean internalAddAllAt(int index, Object[] elements) {
225	>	final boolean rawAddAllAt(int index, Object[] elements) {
226		int n = count;
227	+	Object[] items = array;
228		if (index < 0 || index > n)
229		throw new ArrayIndexOutOfBoundsException(index);
230		int len = elements.length;
231		if (len == 0)
232		return false;
233		int newCount = n + len;
234	<	if (newCount >= array.length)
235	<	grow(newCount);
236	<	int mv = count - index;
234	>	if (newCount >= items.length)
235	>	items = grow(newCount);
236	>	int mv = n - index;
237		if (mv > 0)
238	<	System.arraycopy(array, index, array, index + len, mv);
239	<	System.arraycopy(elements, 0, array, index, len);
238	>	System.arraycopy(items, index, items, index + len, mv);
239	>	System.arraycopy(elements, 0, items, index, len);
240		count = newCount;
241		return true;
242		}
243
244	<	final boolean internalRemoveAt(int index) {
244	>	final boolean rawRemoveAt(int index) {
245		int n = count - 1;
246	+	Object[] items = array;
247		if (index < 0 || index > n)
248		return false;
249		int mv = n - index;
250		if (mv > 0)
251	<	System.arraycopy(array, index + 1, array, index, mv);
252	<	array[n] = null;
251	>	System.arraycopy(items, index + 1, items, index, mv);
252	>	items[n] = null;
253		count = n;
254		return true;
255		}
#	Line 253 | Line 262 | public class ReadMostlyVector<E> impleme
262		* field under lock.
263		*/
264		final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
265	<	SequenceLock lock = this.lock;
265	>	final SequenceLock lock = this.lock;
266		boolean removed = false;
267		lock.lock();
268		try {
#	Line 261 | Line 270 | public class ReadMostlyVector<E> impleme
270		int fence = bound < 0 || bound > n ? n : bound;
271		if (origin >= 0 && origin < fence) {
272		for (Object x : c) {
273	<	while (internalRemoveAt(rawIndexOf(x, origin, fence)))
273	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
274		removed = true;
275		}
276		}
#	Line 272 | Line 281 | public class ReadMostlyVector<E> impleme
281		}
282
283		final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
284	<	SequenceLock lock = this.lock;
284	>	final SequenceLock lock = this.lock;
285		boolean removed = false;
286		if (c != this) {
287		lock.lock();
288		try {
289	+	Object[] items = array;
290		int i = origin;
291		int n = count;
292		int fence = bound < 0 || bound > n ? n : bound;
293	<	while (i < fence) {
294	<	if (c.contains(array[i]))
293	>	while (i >= 0 && i < fence) {
294	>	if (c.contains(items[i]))
295		++i;
296		else {
297		--fence;
298	<	int mv = --count - i;
298	>	int mv = --n - i;
299		if (mv > 0)
300	<	System.arraycopy(array, i + 1, array, i, mv);
291	<	removed = true;
300	>	System.arraycopy(items, i + 1, items, i, mv);
301		}
302		}
303	+	if (count != n) {
304	+	count = n;
305	+	removed = true;
306	+	}
307		} finally {
308		lock.unlock();
309		}
#	Line 302 | Line 315 | public class ReadMostlyVector<E> impleme
315		int n = count;
316		int fence = bound < 0 || bound > n ? n : bound;
317		if (origin >= 0 && origin < fence) {
318	+	Object[] items = array;
319		int removed = fence - origin;
320		int newCount = n - removed;
321		int mv = n - (origin + removed);
322		if (mv > 0)
323	<	System.arraycopy(array, origin + removed, array, origin, mv);
323	>	System.arraycopy(items, origin + removed, items, origin, mv);
324		for (int i = n; i < newCount; ++i)
325	<	array[i] = null;
325	>	items[i] = null;
326		count = newCount;
327		}
328		}
329
330		final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
331	<	SequenceLock lock = this.lock;
331	>	final SequenceLock lock = this.lock;
332		boolean contained;
333		boolean locked = false;
334		try {
335		for (;;) {
336		long seq = lock.awaitAvailability();
337	+	int n = count;
338		Object[] items = array;
339		int len = items.length;
325	–	int n = count;
340		if (n > len)
341		continue;
342		int fence = bound < 0 || bound > n ? n : bound;
#	Line 331 | Line 345 | public class ReadMostlyVector<E> impleme
345		else {
346		contained = true;
347		for (Object e : c) {
348	<	if (validatedIndexOf(e, items, origin, fence, seq) < 0) {
348	>	int idx = (locked ?
349	>	rawIndexOf(e, origin, fence) :
350	>	validatedIndexOf(e, items, origin,
351	>	fence, seq));
352	>	if (idx < 0) {
353		contained = false;
354		break;
355		}
#	Line 350 | Line 368 | public class ReadMostlyVector<E> impleme
368		}
369
370		final boolean internalEquals(List<?> list, int origin, int bound) {
371	<	SequenceLock lock = this.lock;
354	<	boolean equal;
371	>	final SequenceLock lock = this.lock;
372		boolean locked = false;
373	+	boolean equal;
374		try {
375	<	outer:for (;;) {
358	<	equal = true;
375	>	for (;;) {
376		long seq = lock.awaitAvailability();
377		Object[] items = array;
361	–	int len = items.length;
378		int n = count;
379	<	if (n > len)
364	<	continue;
365	<	int fence = bound < 0 || bound > n ? n : bound;
366	<	if (origin < 0)
379	>	if (n > items.length || origin < 0)
380		equal = false;
381		else {
382	+	equal = true;
383	+	int fence = bound < 0 || bound > n ? n : bound;
384		Iterator<?> it = list.iterator();
385		for (int i = origin; i < fence; ++i) {
386	<	if (!it.hasNext()) {
387	<	equal = false;
388	<	break;
389	<	}
390	<	Object x = it.next();
391	<	Object y = items[i];
377	<	if (lock.getSequence() != seq)
378	<	continue outer;
379	<	if (x == null? y != null : (y == null || !x.equals(y))) {
386	>	Object x = items[i];
387	>	Object y;
388	>	if ((!locked && lock.getSequence() != seq) ||
389	>	!it.hasNext() ||
390	>	(y = it.next()) == null ?
391	>	x != null : !y.equals(x)) {
392		equal = false;
393		break;
394		}
#	Line 397 | Line 409 | public class ReadMostlyVector<E> impleme
409		}
410
411		final int internalHashCode(int origin, int bound) {
412	<	SequenceLock lock = this.lock;
412	>	final SequenceLock lock = this.lock;
413		int hash;
414		boolean locked = false;
415		try {
#	Line 405 | Line 417 | public class ReadMostlyVector<E> impleme
417		hash = 1;
418		long seq = lock.awaitAvailability();
419		Object[] items = array;
408	–	int len = items.length;
420		int n = count;
421	+	int len = items.length;
422		if (n > len)
423		continue;
424		int fence = bound < 0 || bound > n ? n : bound;
#	Line 429 | Line 441 | public class ReadMostlyVector<E> impleme
441		}
442
443		final String internalToString(int origin, int bound) {
444	<	SequenceLock lock = this.lock;
444	>	final SequenceLock lock = this.lock;
445		String ret;
446		boolean locked = false;
447		try {
448		outer:for (;;) {
449		long seq = lock.awaitAvailability();
450		Object[] items = array;
439	–	int len = items.length;
451		int n = count;
452	+	int len = items.length;
453		if (n > len)
454		continue;
455		int fence = bound < 0 || bound > n ? n : bound;
#	Line 450 | Line 462 | public class ReadMostlyVector<E> impleme
462		Object e = items[i];
463		if (e == this)
464		sb.append("(this Collection)");
465	<	else if (lock.getSequence() != seq)
465	>	else if (!locked && lock.getSequence() != seq)
466		continue outer;
467		else
468		sb.append(e.toString());
#	Line 476 | Line 488 | public class ReadMostlyVector<E> impleme
488
489		final Object[] internalToArray(int origin, int bound) {
490		Object[] result;
491	<	SequenceLock lock = this.lock;
491	>	final SequenceLock lock = this.lock;
492		boolean locked = false;
493		try {
494		for (;;) {
495		result = null;
496		long seq = lock.awaitAvailability();
497		Object[] items = array;
486	–	int len = items.length;
498		int n = count;
499	+	int len = items.length;
500		if (n > len)
501		continue;
502		int fence = bound < 0 || bound > n ? n : bound;
#	Line 503 | Line 515 | public class ReadMostlyVector<E> impleme
515		return result;
516		}
517
518	+	@SuppressWarnings("unchecked")
519		final <T> T[] internalToArray(T[] a, int origin, int bound) {
520		int alen = a.length;
521		T[] result;
522	<	SequenceLock lock = this.lock;
522	>	final SequenceLock lock = this.lock;
523		boolean locked = false;
524		try {
525		for (;;) {
526		long seq = lock.awaitAvailability();
527		Object[] items = array;
515	–	int len = items.length;
528		int n = count;
529	+	int len = items.length;
530		if (n > len)
531		continue;
532		int fence = bound < 0 || bound > n ? n : bound;
533		int rlen = fence - origin;
534	+	if (rlen < 0)
535	+	rlen = 0;
536		if (origin < 0 || alen >= rlen) {
537	<	if (rlen < 0)
538	<	rlen = 0;
524	<	else if (rlen > 0)
525	<	System.arraycopy(array, 0, a, origin, rlen);
537	>	if (rlen > 0)
538	>	System.arraycopy(items, 0, a, origin, rlen);
539		if (alen > rlen)
540		a[rlen] = null;
541		result = a;
542		}
543	<	else
544	<	result = (T[]) Arrays.copyOfRange(array, origin,
543	>	else
544	>	result = (T[]) Arrays.copyOfRange(items, origin,
545		fence, a.getClass());
546		if (lock.getSequence() == seq)
547		break;
#	Line 545 | Line 558 | public class ReadMostlyVector<E> impleme
558		// public List methods
559
560		public boolean add(E e) {
561	<	SequenceLock lock = this.lock;
561	>	final SequenceLock lock = this.lock;
562		lock.lock();
563		try {
564	<	internalAdd(e);
564	>	rawAdd(e);
565		} finally {
566		lock.unlock();
567		}
#	Line 556 | Line 569 | public class ReadMostlyVector<E> impleme
569		}
570
571		public void add(int index, E element) {
572	<	SequenceLock lock = this.lock;
572	>	final SequenceLock lock = this.lock;
573		lock.lock();
574		try {
575	<	internalAddAt(index, element);
575	>	rawAddAt(index, element);
576		} finally {
577		lock.unlock();
578		}
#	Line 570 | Line 583 | public class ReadMostlyVector<E> impleme
583		int len = elements.length;
584		if (len == 0)
585		return false;
586	<	SequenceLock lock = this.lock;
586	>	final SequenceLock lock = this.lock;
587		lock.lock();
588		try {
589	<	int newCount = count + len;
590	<	if (newCount >= array.length)
591	<	grow(newCount);
592	<	System.arraycopy(elements, 0, array, count, len);
589	>	Object[] items = array;
590	>	int n = count;
591	>	int newCount = n + len;
592	>	if (newCount >= items.length)
593	>	items = grow(newCount);
594	>	System.arraycopy(elements, 0, items, n, len);
595		count = newCount;
596		} finally {
597		lock.unlock();
#	Line 585 | Line 600 | public class ReadMostlyVector<E> impleme
600		}
601
602		public boolean addAll(int index, Collection<? extends E> c) {
603	<	SequenceLock lock = this.lock;
603	>	final SequenceLock lock = this.lock;
604		boolean ret;
605		Object[] elements = c.toArray();
606		lock.lock();
607		try {
608	<	ret = internalAddAllAt(index, elements);
608	>	ret = rawAddAllAt(index, elements);
609		} finally {
610		lock.unlock();
611		}
#	Line 598 | Line 613 | public class ReadMostlyVector<E> impleme
613		}
614
615		public void clear() {
616	<	SequenceLock lock = this.lock;
616	>	final SequenceLock lock = this.lock;
617		lock.lock();
618		try {
619	<	for (int i = 0; i < count; i++)
620	<	array[i] = null;
619	>	int n = count;
620	>	Object[] items = array;
621	>	for (int i = 0; i < n; i++)
622	>	items[i] = null;
623		count = 0;
624		} finally {
625		lock.unlock();
#	Line 622 | Line 639 | public class ReadMostlyVector<E> impleme
639		return true;
640		if (!(o instanceof List))
641		return false;
642	<	return internalEquals((List<?>)(o), 0, -1);
642	>	return internalEquals((List<?>)o, 0, -1);
643		}
644
645		public E get(int index) {
646	<	SequenceLock lock = this.lock;
646	>	final SequenceLock lock = this.lock;
647		for (;;) {
648		long seq = lock.awaitAvailability();
632	–	Object[] items = array;
649		int n = count;
650	+	Object[] items = array;
651		if (n > items.length)
652		continue;
653	<	Object e; boolean ex;
654	<	if (index < 0 || index >= n) {
655	<	e = null;
639	<	ex = true;
640	<	}
641	<	else {
642	<	e = items[index];
643	<	ex = false;
644	<	}
653	>	boolean outOfBounds = (index < 0 || index >= n);
654	>	@SuppressWarnings("unchecked")
655	>	E e = outOfBounds ? null : (E) items[index];
656		if (lock.getSequence() == seq) {
657	<	if (ex)
657	>	if (outOfBounds)
658		throw new ArrayIndexOutOfBoundsException(index);
659		else
660	<	return (E)e;
660	>	return e;
661		}
662		}
663		}
#	Line 656 | Line 667 | public class ReadMostlyVector<E> impleme
667		}
668
669		public int indexOf(Object o) {
670	<	SequenceLock lock = this.lock;
660	<	long seq = lock.awaitAvailability();
661	<	Object[] items = array;
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 rawIndexOf(o, 0, count);
671	<	} finally {
672	<	lock.unlock();
673	<	}
670	>	return indexOf(o, 0);
671		}
672
673		public boolean isEmpty() {
677	–	long ignore = lock.getSequence();
674		return count == 0;
675		}
676
677		public Iterator<E> iterator() {
678	<	return new Itr(this, 0);
678	>	return new Itr<E>(this, 0);
679		}
680
681		public int lastIndexOf(Object o) {
682	<	SequenceLock lock = this.lock;
683	<	long seq = lock.awaitAvailability();
684	<	Object[] items = array;
685	<	int n = count;
686	<	if (n <= items.length) {
687	<	int idx = validatedLastIndexOf(o, items, n - 1, 0, seq);
688	<	if (lock.getSequence() == seq)
689	<	return idx;
690	<	}
691	<	lock.lock();
692	<	try {
693	<	return rawLastIndexOf(o, count - 1, 0);
694	<	} finally {
695	<	lock.unlock();
682	>	final SequenceLock lock = this.lock;
683	>	for (;;) {
684	>	long seq = lock.awaitAvailability();
685	>	Object[] items = array;
686	>	int n = count;
687	>	if (n <= items.length) {
688	>	for (int i = n - 1; i >= 0; --i) {
689	>	Object e = items[i];
690	>	if (lock.getSequence() != seq) {
691	>	lock.lock();
692	>	try {
693	>	return rawLastIndexOf(o, 0, count);
694	>	} finally {
695	>	lock.unlock();
696	>	}
697	>	}
698	>	else if ((o == null) ? e == null : o.equals(e))
699	>	return i;
700	>	}
701	>	return -1;
702	>	}
703		}
704		}
705
706		public ListIterator<E> listIterator() {
707	<	return new Itr(this, 0);
707	>	return new Itr<E>(this, 0);
708		}
709
710		public ListIterator<E> listIterator(int index) {
711	<	return new Itr(this, index);
711	>	return new Itr<E>(this, index);
712		}
713
714		public E remove(int index) {
715	<	SequenceLock lock = this.lock;
713	<	Object oldValue;
715	>	final SequenceLock lock = this.lock;
716		lock.lock();
717		try {
718		if (index < 0 || index >= count)
719		throw new ArrayIndexOutOfBoundsException(index);
720	<	oldValue = array[index];
721	<	internalRemoveAt(index);
720	>	@SuppressWarnings("unchecked")
721	>	E oldValue = (E) array[index];
722	>	rawRemoveAt(index);
723	>	return oldValue;
724		} finally {
725		lock.unlock();
726		}
723	–	return (E)oldValue;
727		}
728
729		public boolean remove(Object o) {
730	<	SequenceLock lock = this.lock;
728	<	boolean removed;
730	>	final SequenceLock lock = this.lock;
731		lock.lock();
732		try {
733	<	removed = internalRemoveAt(rawIndexOf(o, 0, count));
733	>	return rawRemoveAt(rawIndexOf(o, 0, count));
734		} finally {
735		lock.unlock();
736		}
735	–	return removed;
737		}
738
739		public boolean removeAll(Collection<?> c) {
#	Line 744 | Line 745 | public class ReadMostlyVector<E> impleme
745		}
746
747		public E set(int index, E element) {
748	<	Object oldValue;
748	<	SequenceLock lock = this.lock;
748	>	final SequenceLock lock = this.lock;
749		lock.lock();
750		try {
751	+	Object[] items = array;
752		if (index < 0 || index >= count)
753		throw new ArrayIndexOutOfBoundsException(index);
754	<	oldValue = array[index];
755	<	array[index] = element;
754	>	@SuppressWarnings("unchecked")
755	>	E oldValue = (E) items[index];
756	>	items[index] = element;
757	>	return oldValue;
758		} finally {
759		lock.unlock();
760		}
758	–	return (E)oldValue;
761		}
762
763		public int size() {
762	–	long ignore = lock.getSequence();
764		return count;
765		}
766
#	Line 768 | Line 769 | public class ReadMostlyVector<E> impleme
769		int ssize = toIndex - fromIndex;
770		if (fromIndex < 0 || toIndex > c || ssize < 0)
771		throw new IndexOutOfBoundsException();
772	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
772	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
773		}
774
775		public Object[] toArray() {
#	Line 789 | Line 790 | public class ReadMostlyVector<E> impleme
790		* Append the element if not present.
791		*
792		* @param e element to be added to this list, if absent
793	<	* @return <tt>true</tt> if the element was added
793	>	* @return {@code true} if the element was added
794		*/
795		public boolean addIfAbsent(E e) {
796	<	boolean added;
796	<	SequenceLock lock = this.lock;
796	>	final SequenceLock lock = this.lock;
797		lock.lock();
798		try {
799		if (rawIndexOf(e, 0, count) < 0) {
800	<	internalAdd(e);
801	<	added = true;
800	>	rawAdd(e);
801	>	return true;
802		}
803		else
804	<	added = false;
804	>	return false;
805		} finally {
806		lock.unlock();
807		}
808	–	return added;
808		}
809
810		/**
#	Line 827 | Line 826 | public class ReadMostlyVector<E> impleme
826		lock.lock();
827		try {
828		for (int i = 0; i < clen; ++i) {
829	<	Object e = cs[i];
829	>	@SuppressWarnings("unchecked")
830	>	E e = (E) cs[i];
831		if (rawIndexOf(e, 0, count) < 0) {
832	<	internalAdd(e);
832	>	rawAdd(e);
833		++added;
834		}
835		}
#	Line 840 | Line 840 | public class ReadMostlyVector<E> impleme
840		return added;
841		}
842
843	+	/**
844	+	* Returns an iterator operating over a snapshot copy of the
845	+	* elements of this collection created upon construction of the
846	+	* iterator. The iterator does <em>NOT</em> support the
847	+	* {@code remove} method.
848	+	*
849	+	* @return an iterator over the elements in this list in proper sequence
850	+	*/
851	+	public Iterator<E> snapshotIterator() {
852	+	return new SnapshotIterator<E>(this);
853	+	}
854	+
855	+	static final class SnapshotIterator<E> implements Iterator<E> {
856	+	private final Object[] items;
857	+	private int cursor;
858	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
859	+	public boolean hasNext() { return cursor < items.length; }
860	+	@SuppressWarnings("unchecked")
861	+	public E next() {
862	+	if (cursor < items.length)
863	+	return (E) items[cursor++];
864	+	throw new NoSuchElementException();
865	+	}
866	+	public void remove() { throw new UnsupportedOperationException() ; }
867	+	}
868	+
869		// Vector-only methods
870
871		/** See {@link Vector#firstElement} */
872		public E firstElement() {
873	<	SequenceLock lock = this.lock;
873	>	final SequenceLock lock = this.lock;
874		for (;;) {
875		long seq = lock.awaitAvailability();
876		Object[] items = array;
#	Line 852 | Line 878 | public class ReadMostlyVector<E> impleme
878		int n = count;
879		if (n > len)
880		continue;
881	<	Object e; boolean ex;
882	<	if (n > 0) {
883	<	e = items[0];
858	<	ex = false;
859	<	}
860	<	else {
861	<	e = null;
862	<	ex = true;
863	<	}
881	>	boolean empty = (n == 0);
882	>	@SuppressWarnings("unchecked")
883	>	E e = empty ? null : (E) items[0];
884		if (lock.getSequence() == seq) {
885	<	if (ex)
885	>	if (empty)
886		throw new NoSuchElementException();
887		else
888	<	return (E)e;
888	>	return e;
889		}
890		}
891		}
892
893		/** See {@link Vector#lastElement} */
894		public E lastElement() {
895	<	SequenceLock lock = this.lock;
895	>	final SequenceLock lock = this.lock;
896		for (;;) {
897		long seq = lock.awaitAvailability();
898		Object[] items = array;
#	Line 880 | Line 900 | public class ReadMostlyVector<E> impleme
900		int n = count;
901		if (n > len)
902		continue;
903	<	Object e; boolean ex;
904	<	if (n > 0) {
905	<	e = items[n - 1];
886	<	ex = false;
887	<	}
888	<	else {
889	<	e = null;
890	<	ex = true;
891	<	}
903	>	boolean empty = (n == 0);
904	>	@SuppressWarnings("unchecked")
905	>	E e = empty ? null : (E) items[n - 1];
906		if (lock.getSequence() == seq) {
907	<	if (ex)
907	>	if (empty)
908		throw new NoSuchElementException();
909		else
910	<	return (E)e;
910	>	return e;
911		}
912		}
913		}
914
915		/** See {@link Vector#indexOf(Object, int)} */
916		public int indexOf(Object o, int index) {
917	<	SequenceLock lock = this.lock;
917	>	final SequenceLock lock = this.lock;
918		int idx = 0;
919		boolean ex = false;
920		long seq = lock.awaitAvailability();
#	Line 919 | Line 933 | public class ReadMostlyVector<E> impleme
933		if (index < 0)
934		ex = true;
935		else
936	<	idx = rawIndexOf(o, 0, count);
936	>	idx = rawIndexOf(o, index, count);
937		} finally {
938		lock.unlock();
939		}
#	Line 931 | Line 945 | public class ReadMostlyVector<E> impleme
945
946		/** See {@link Vector#lastIndexOf(Object, int)} */
947		public int lastIndexOf(Object o, int index) {
948	<	SequenceLock lock = this.lock;
948	>	final SequenceLock lock = this.lock;
949		int idx = 0;
950		boolean ex = false;
951		long seq = lock.awaitAvailability();
#	Line 964 | Line 978 | public class ReadMostlyVector<E> impleme
978		public void setSize(int newSize) {
979		if (newSize < 0)
980		throw new ArrayIndexOutOfBoundsException(newSize);
981	<	SequenceLock lock = this.lock;
981	>	final SequenceLock lock = this.lock;
982		lock.lock();
983		try {
984		int n = count;
985		if (newSize > n)
986		grow(newSize);
987		else {
988	+	Object[] items = array;
989		for (int i = newSize ; i < n ; i++)
990	<	array[i] = null;
990	>	items[i] = null;
991		}
992		count = newSize;
993		} finally {
#	Line 982 | Line 997 | public class ReadMostlyVector<E> impleme
997
998		/** See {@link Vector#copyInto} */
999		public void copyInto(Object[] anArray) {
1000	<	SequenceLock lock = this.lock;
1000	>	final SequenceLock lock = this.lock;
1001		lock.lock();
1002		try {
1003		System.arraycopy(array, 0, anArray, 0, count);
#	Line 993 | Line 1008 | public class ReadMostlyVector<E> impleme
1008
1009		/** See {@link Vector#trimToSize} */
1010		public void trimToSize() {
1011	<	SequenceLock lock = this.lock;
1011	>	final SequenceLock lock = this.lock;
1012		lock.lock();
1013		try {
1014	<	if (count < array.length)
1015	<	array = Arrays.copyOf(array, count);
1014	>	Object[] items = array;
1015	>	int n = count;
1016	>	if (n < items.length)
1017	>	array = Arrays.copyOf(items, n);
1018		} finally {
1019		lock.unlock();
1020		}
#	Line 1006 | Line 1023 | public class ReadMostlyVector<E> impleme
1023		/** See {@link Vector#ensureCapacity} */
1024		public void ensureCapacity(int minCapacity) {
1025		if (minCapacity > 0) {
1026	<	SequenceLock lock = this.lock;
1026	>	final SequenceLock lock = this.lock;
1027		lock.lock();
1028		try {
1029		if (minCapacity - array.length > 0)
#	Line 1019 | Line 1036 | public class ReadMostlyVector<E> impleme
1036
1037		/** See {@link Vector#elements} */
1038		public Enumeration<E> elements() {
1039	<	return new Itr(this, 0);
1039	>	return new Itr<E>(this, 0);
1040		}
1041
1042		/** See {@link Vector#capacity} */
1043		public int capacity() {
1027	–	long ignore = lock.getSequence();
1044		return array.length;
1045		}
1046
#	Line 1065 | Line 1081 | public class ReadMostlyVector<E> impleme
1081
1082		// other methods
1083
1084	<	public Object clone() {
1085	<	SequenceLock lock = this.lock;
1084	>	public ReadMostlyVector<E> clone() {
1085	>	final SequenceLock lock = this.lock;
1086		Object[] a = null;
1087		boolean retry = false;
1088		long seq = lock.awaitAvailability();
#	Line 1085 | Line 1101 | public class ReadMostlyVector<E> impleme
1101		lock.unlock();
1102		}
1103		}
1104	<	return new ReadMostlyVector(a, n, capacityIncrement);
1104	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1105		}
1106
1107		private void writeObject(java.io.ObjectOutputStream s)
1108		throws java.io.IOException {
1109	<	SequenceLock lock = this.lock;
1109	>	final SequenceLock lock = this.lock;
1110		lock.lock();
1111		try {
1112		s.defaultWriteObject();
#	Line 1099 | Line 1115 | public class ReadMostlyVector<E> impleme
1115		}
1116		}
1117
1118	<	static final class Itr<E> implements ListIterator<E>, Enumeration<E>  {
1118	>	static final class Itr<E> implements ListIterator<E>, Enumeration<E> {
1119		final ReadMostlyVector<E> list;
1120		final SequenceLock lock;
1121		Object[] items;
1122	<	Object next, prev;
1122	>	E next, prev;
1123		long seq;
1124		int cursor;
1125		int fence;
#	Line 1129 | Line 1145 | public class ReadMostlyVector<E> impleme
1145		lock.getSequence() != seq);
1146		}
1147
1148	+	@SuppressWarnings("unchecked")
1149		public boolean hasNext() {
1150		boolean valid;
1151		int i = cursor;
#	Line 1137 | Line 1154 | public class ReadMostlyVector<E> impleme
1154		valid = false;
1155		break;
1156		}
1157	<	next = items[i];
1157	>	next = (E) items[i];
1158		if (lock.getSequence() == seq) {
1159		valid = true;
1160		break;
#	Line 1147 | Line 1164 | public class ReadMostlyVector<E> impleme
1164		return validNext = valid;
1165		}
1166
1167	+	@SuppressWarnings("unchecked")
1168		public boolean hasPrevious() {
1169		boolean valid;
1170		int i = cursor - 1;
#	Line 1155 | Line 1173 | public class ReadMostlyVector<E> impleme
1173		valid = false;
1174		break;
1175		}
1176	<	prev = items[i];
1176	>	prev = (E) items[i];
1177		if (lock.getSequence() == seq) {
1178		valid = true;
1179		break;
#	Line 1169 | Line 1187 | public class ReadMostlyVector<E> impleme
1187		if (validNext || hasNext()) {
1188		validNext = false;
1189		lastRet = cursor++;
1190	<	return (E) next;
1190	>	return next;
1191		}
1192		throw new NoSuchElementException();
1193		}
#	Line 1178 | Line 1196 | public class ReadMostlyVector<E> impleme
1196		if (validPrev || hasPrevious()) {
1197		validPrev = false;
1198		lastRet = cursor--;
1199	<	return (E) prev;
1199	>	return prev;
1200		}
1201		throw new NoSuchElementException();
1202		}
#	Line 1235 | Line 1253 | public class ReadMostlyVector<E> impleme
1253		public int previousIndex() { return cursor - 1; }
1254		}
1255
1256	<	static final class ReadMostlyVectorSublist<E> implements List<E>, RandomAccess, java.io.Serializable {
1256	>	static final class ReadMostlyVectorSublist<E>
1257	>	implements List<E>, RandomAccess, java.io.Serializable {
1258	>	static final long serialVersionUID = 3041673470172026059L;
1259	>
1260		final ReadMostlyVector<E> list;
1261		final int offset;
1262		volatile int size;
1263
1264	<	ReadMostlyVectorSublist(ReadMostlyVector<E> list, int offset, int size) {
1264	>	ReadMostlyVectorSublist(ReadMostlyVector<E> list,
1265	>	int offset, int size) {
1266		this.list = list;
1267		this.offset = offset;
1268		this.size = size;
#	Line 1252 | Line 1274 | public class ReadMostlyVector<E> impleme
1274		}
1275
1276		public boolean add(E element) {
1277	<	SequenceLock lock = list.lock;
1277	>	final SequenceLock lock = list.lock;
1278		lock.lock();
1279		try {
1280		int c = size;
1281	<	list.internalAddAt(c + offset, element);
1281	>	list.rawAddAt(c + offset, element);
1282		size = c + 1;
1283		} finally {
1284		lock.unlock();
#	Line 1265 | Line 1287 | public class ReadMostlyVector<E> impleme
1287		}
1288
1289		public void add(int index, E element) {
1290	<	SequenceLock lock = list.lock;
1290	>	final SequenceLock lock = list.lock;
1291		lock.lock();
1292		try {
1293		if (index < 0 || index > size)
1294		throw new ArrayIndexOutOfBoundsException(index);
1295	<	list.internalAddAt(index + offset, element);
1295	>	list.rawAddAt(index + offset, element);
1296		++size;
1297		} finally {
1298		lock.unlock();
#	Line 1279 | Line 1301 | public class ReadMostlyVector<E> impleme
1301
1302		public boolean addAll(Collection<? extends E> c) {
1303		Object[] elements = c.toArray();
1304	<	int added;
1283	<	SequenceLock lock = list.lock;
1304	>	final SequenceLock lock = list.lock;
1305		lock.lock();
1306		try {
1307		int s = size;
1308		int pc = list.count;
1309	<	list.internalAddAllAt(offset + s, elements);
1310	<	added = list.count - pc;
1309	>	list.rawAddAllAt(offset + s, elements);
1310	>	int added = list.count - pc;
1311		size = s + added;
1312	+	return added != 0;
1313		} finally {
1314		lock.unlock();
1315		}
1294	–	return added != 0;
1316		}
1317
1318		public boolean addAll(int index, Collection<? extends E> c) {
1319		Object[] elements = c.toArray();
1320	<	int added;
1300	<	SequenceLock lock = list.lock;
1320	>	final SequenceLock lock = list.lock;
1321		lock.lock();
1322		try {
1323		int s = size;
1324		if (index < 0 || index > s)
1325		throw new ArrayIndexOutOfBoundsException(index);
1326		int pc = list.count;
1327	<	list.internalAddAllAt(index + offset, elements);
1328	<	added = list.count - pc;
1327	>	list.rawAddAllAt(index + offset, elements);
1328	>	int added = list.count - pc;
1329		size = s + added;
1330	+	return added != 0;
1331		} finally {
1332		lock.unlock();
1333		}
1313	–	return added != 0;
1334		}
1335
1336		public void clear() {
1337	<	SequenceLock lock = list.lock;
1337	>	final SequenceLock lock = list.lock;
1338		lock.lock();
1339		try {
1340		list.internalClear(offset, offset + size);
#	Line 1351 | Line 1371 | public class ReadMostlyVector<E> impleme
1371		}
1372
1373		public int indexOf(Object o) {
1374	<	SequenceLock lock = list.lock;
1374	>	final SequenceLock lock = list.lock;
1375		long seq = lock.awaitAvailability();
1376		Object[] items = list.array;
1377		int c = list.count;
1378		if (c <= items.length) {
1379	<	int idx = list.validatedIndexOf(o, items, offset, offset+size, seq);
1379	>	int idx = list.validatedIndexOf(o, items, offset,
1380	>	offset + size, seq);
1381		if (lock.getSequence() == seq)
1382		return idx < 0 ? -1 : idx - offset;
1383		}
1384		lock.lock();
1385		try {
1386	<	int idx = list.rawIndexOf(o, offset, offset+size);
1386	>	int idx = list.rawIndexOf(o, offset, offset + size);
1387		return idx < 0 ? -1 : idx - offset;
1388		} finally {
1389		lock.unlock();
#	Line 1374 | Line 1395 | public class ReadMostlyVector<E> impleme
1395		}
1396
1397		public Iterator<E> iterator() {
1398	<	return new SubItr(this, offset);
1398	>	return new SubItr<E>(this, offset);
1399		}
1400
1401		public int lastIndexOf(Object o) {
1402	<	SequenceLock lock = list.lock;
1402	>	final SequenceLock lock = list.lock;
1403		long seq = lock.awaitAvailability();
1404		Object[] items = list.array;
1405		int c = list.count;
1406		if (c <= items.length) {
1407	<	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1407	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1408		offset, seq);
1409		if (lock.getSequence() == seq)
1410		return idx < 0 ? -1 : idx - offset;
#	Line 1398 | Line 1419 | public class ReadMostlyVector<E> impleme
1419		}
1420
1421		public ListIterator<E> listIterator() {
1422	<	return new SubItr(this, offset);
1422	>	return new SubItr<E>(this, offset);
1423		}
1424
1425		public ListIterator<E> listIterator(int index) {
1426	<	return new SubItr(this, index + offset);
1426	>	return new SubItr<E>(this, index + offset);
1427		}
1428
1429		public E remove(int index) {
1430	<	Object result;
1410	<	SequenceLock lock = list.lock;
1430	>	final SequenceLock lock = list.lock;
1431		lock.lock();
1432		try {
1433	<	if (index < 0 || index >= size)
1414	<	throw new ArrayIndexOutOfBoundsException(index);
1433	>	Object[] items = list.array;
1434		int i = index + offset;
1435	<	result = list.array[i];
1436	<	list.internalRemoveAt(i);
1435	>	if (index < 0 || index >= size || i >= items.length)
1436	>	throw new ArrayIndexOutOfBoundsException(index);
1437	>	@SuppressWarnings("unchecked")
1438	>	E result = (E) items[i];
1439	>	list.rawRemoveAt(i);
1440		size--;
1441	+	return result;
1442		} finally {
1443		lock.unlock();
1444		}
1422	–	return (E)result;
1445		}
1446
1447		public boolean remove(Object o) {
1448	<	boolean removed = false;
1427	<	SequenceLock lock = list.lock;
1448	>	final SequenceLock lock = list.lock;
1449		lock.lock();
1450		try {
1451	<	if (list.internalRemoveAt(list.rawIndexOf(o, offset,
1452	<	offset + size))) {
1432	<	removed = true;
1451	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1452	>	offset + size))) {
1453		--size;
1454	+	return true;
1455		}
1456	+	else
1457	+	return false;
1458		} finally {
1459		lock.unlock();
1460		}
1438	–	return removed;
1461		}
1462
1463		public boolean removeAll(Collection<?> c) {
#	Line 1461 | Line 1483 | public class ReadMostlyVector<E> impleme
1483		int ssize = toIndex - fromIndex;
1484		if (fromIndex < 0 || toIndex > c || ssize < 0)
1485		throw new IndexOutOfBoundsException();
1486	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1486	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1487		}
1488
1489		public Object[] toArray() {
#	Line 1483 | Line 1505 | public class ReadMostlyVector<E> impleme
1505		final ReadMostlyVector<E> list;
1506		final SequenceLock lock;
1507		Object[] items;
1508	<	Object next, prev;
1508	>	E next, prev;
1509		long seq;
1510		int cursor;
1511		int fence;
#	Line 1514 | Line 1536 | public class ReadMostlyVector<E> impleme
1536		} while (lock.getSequence() != seq);
1537		}
1538
1539	+	@SuppressWarnings("unchecked")
1540		public boolean hasNext() {
1541		boolean valid;
1542		int i = cursor;
#	Line 1522 | Line 1545 | public class ReadMostlyVector<E> impleme
1545		valid = false;
1546		break;
1547		}
1548	<	next = items[i];
1548	>	next = (E) items[i];
1549		if (lock.getSequence() == seq) {
1550		valid = true;
1551		break;
#	Line 1532 | Line 1555 | public class ReadMostlyVector<E> impleme
1555		return validNext = valid;
1556		}
1557
1558	+	@SuppressWarnings("unchecked")
1559		public boolean hasPrevious() {
1560		boolean valid;
1561		int i = cursor - 1;
#	Line 1540 | Line 1564 | public class ReadMostlyVector<E> impleme
1564		valid = false;
1565		break;
1566		}
1567	<	prev = items[i];
1567	>	prev = (E) items[i];
1568		if (lock.getSequence() == seq) {
1569		valid = true;
1570		break;
#	Line 1554 | Line 1578 | public class ReadMostlyVector<E> impleme
1578		if (validNext || hasNext()) {
1579		validNext = false;
1580		lastRet = cursor++;
1581	<	return (E) next;
1581	>	return next;
1582		}
1583		throw new NoSuchElementException();
1584		}
#	Line 1563 | Line 1587 | public class ReadMostlyVector<E> impleme
1587		if (validPrev || hasPrevious()) {
1588		validPrev = false;
1589		lastRet = cursor--;
1590	<	return (E) prev;
1590	>	return prev;
1591		}
1592		throw new NoSuchElementException();
1593		}

Diff Legend

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