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.15 by jsr166, Mon Dec 19 19:18:35 2011 UTC vs.
Revision 1.33 by jsr166, Wed Jan 2 04:35:20 2013 UTC

#	Line 5 | Line 5
5		*/
6
7		package jsr166e.extra;
8	<	import jsr166e.*;
8	>	import jsr166e.StampedLock;
9		import java.util.*;
10
11		/**
#	Line 14 | Line 14 | import java.util.*;
14		* throughput when invocations of read-only methods by multiple
15		* threads are most common.
16		*
17	<	* <p> The iterators returned by this class's {@link #iterator()
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
#	Line 49 | Line 49 | public class ReadMostlyVector<E>
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
51		* actually used (for example, as an argument of method equals).
52	+	*
53	+	* We rely on some invariants that are always true, even for field
54	+	* reads in read-only mode that have not yet been validated:
55	+	* - array != null
56	+	* - count >= 0
57		*/
58
59		/**
#	Line 57 | Line 62 | public class ReadMostlyVector<E>
62		*/
63		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
64
65	<	// fields are non-private to simpify nested class access
66	<	volatile Object[] array;
67	<	final SequenceLock lock;
68	<	volatile int count;
65	>	// fields are non-private to simplify nested class access
66	>	Object[] array;
67	>	final StampedLock lock;
68	>	int count;
69		final int capacityIncrement;
70
71		/**
#	Line 81 | Line 86 | public class ReadMostlyVector<E>
86		initialCapacity);
87		this.array = new Object[initialCapacity];
88		this.capacityIncrement = capacityIncrement;
89	<	this.lock = new SequenceLock();
89	>	this.lock = new StampedLock();
90		}
91
92		/**
93		* Creates an empty vector with the given initial capacity.
94		*
95		* @param initialCapacity the initial capacity of the underlying array
91	–	*
96		* @throws IllegalArgumentException if initial capacity is negative
97		*/
98		public ReadMostlyVector(int initialCapacity) {
#	Line 96 | Line 100 | public class ReadMostlyVector<E>
100		}
101
102		/**
103	<	* Creates an empty vector with an underlying array of size {@code 10}.
103	>	* Creates an empty vector.
104		*/
105		public ReadMostlyVector() {
106	<	this(10, 0);
106	>	this.capacityIncrement = 0;
107	>	this.lock = new StampedLock();
108		}
109
110		/**
#	Line 118 | Line 123 | public class ReadMostlyVector<E>
123		this.array = elements;
124		this.count = elements.length;
125		this.capacityIncrement = 0;
126	<	this.lock = new SequenceLock();
126	>	this.lock = new StampedLock();
127		}
128
129		// internal constructor for clone
#	Line 126 | Line 131 | public class ReadMostlyVector<E>
131		this.array = array;
132		this.count = count;
133		this.capacityIncrement = capacityIncrement;
134	<	this.lock = new SequenceLock();
134	>	this.lock = new StampedLock();
135		}
136
137	+	static final int INITIAL_CAP = 16;
138	+
139		// For explanation, see CopyOnWriteArrayList
140		final Object[] grow(int minCapacity) {
141	<	int oldCapacity = array.length;
142	<	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
141	>	Object[] items;
142	>	int newCapacity;
143	>	if ((items = array) == null)
144	>	newCapacity = INITIAL_CAP;
145	>	else {
146	>	int oldCapacity = array.length;
147	>	newCapacity = oldCapacity + ((capacityIncrement > 0) ?
148		capacityIncrement : oldCapacity);
149	+	}
150		if (newCapacity - minCapacity < 0)
151		newCapacity = minCapacity;
152	<	if (newCapacity - MAX_ARRAY_SIZE > 0)
153	<	newCapacity = hugeCapacity(minCapacity);
154	<	return array = Arrays.copyOf(array, newCapacity);
155	<	}
156	<
157	<	static int hugeCapacity(int minCapacity) {
158	<	if (minCapacity < 0) // overflow
159	<	throw new OutOfMemoryError();
160	<	return (minCapacity > MAX_ARRAY_SIZE) ?
161	<	Integer.MAX_VALUE :
162	<	MAX_ARRAY_SIZE;
152	>	if (newCapacity - MAX_ARRAY_SIZE > 0) {
153	>	if (minCapacity < 0) // overflow
154	>	throw new OutOfMemoryError();
155	>	else if (minCapacity > MAX_ARRAY_SIZE)
156	>	newCapacity = Integer.MAX_VALUE;
157	>	else
158	>	newCapacity = MAX_ARRAY_SIZE;
159	>	}
160	>	return array = ((items == null) ?
161	>	new Object[newCapacity] :
162	>	Arrays.copyOf(items, newCapacity));
163		}
164
165		/*
#	Line 155 | Line 168 | public class ReadMostlyVector<E>
168		* as well as sublist and iterator classes.
169		*/
170
171	<	// Version of indexOf that returns -1 if either not present or invalid
172	<	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
173	<	long seq) {
174	<	for (int i = index; i < fence; ++i) {
175	<	Object e = items[i];
176	<	if (lock.getSequence() != seq)
177	<	break;
178	<	if ((x == null) ? e == null : x.equals(e))
179	<	return i;
180	<	}
168	<	return -1;
169	<	}
170	<
171	<	final int rawIndexOf(Object x, int index, int fence) {
172	<	Object[] items = array;
173	<	for (int i = index; i < fence; ++i) {
174	<	Object e = items[i];
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,
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 : x.equals(e))
188	<	return i;
171	>	static int findFirstIndex(Object[] items, Object x, int index, int fence) {
172	>	int len;
173	>	if (items != null && (len = items.length) > 0) {
174	>	int start = (index < 0) ? 0 : index;
175	>	int bound = (fence < len) ? fence : len;
176	>	for (int i = start; i < bound; ++i) {
177	>	Object e = items[i];
178	>	if ((x == null) ? e == null : x.equals(e))
179	>	return i;
180	>	}
181		}
182		return -1;
183		}
184
185	<	final int rawLastIndexOf(Object x, int index, int origin) {
186	<	Object[] items = array;
187	<	for (int i = index; i >= origin; --i) {
188	<	Object e = items[i];
189	<	if ((x == null) ? e == null : x.equals(e))
190	<	return i;
185	>	static int findLastIndex(Object[] items, Object x, int index, int origin) {
186	>	int len;
187	>	if (items != null && (len = items.length) > 0) {
188	>	int last = (index < len) ? index : len - 1;
189	>	int start = (origin < 0) ? 0 : origin;
190	>	for (int i = last; i >= start; --i) {
191	>	Object e = items[i];
192	>	if ((x == null) ? e == null : x.equals(e))
193	>	return i;
194	>	}
195		}
196		return -1;
197		}
#	Line 203 | Line 199 | public class ReadMostlyVector<E>
199		final void rawAdd(E e) {
200		int n = count;
201		Object[] items = array;
202	<	if (n >= items.length)
202	>	if (items == null || n >= items.length)
203		items = grow(n + 1);
204		items[n] = e;
205		count = n + 1;
#	Line 214 | Line 210 | public class ReadMostlyVector<E>
210		Object[] items = array;
211		if (index > n)
212		throw new ArrayIndexOutOfBoundsException(index);
213	<	if (n >= items.length)
213	>	if (items == null || n >= items.length)
214		items = grow(n + 1);
215		if (index < n)
216		System.arraycopy(items, index, items, index + 1, n - index);
#	Line 231 | Line 227 | public class ReadMostlyVector<E>
227		if (len == 0)
228		return false;
229		int newCount = n + len;
230	<	if (newCount >= items.length)
230	>	if (items == null || newCount >= items.length)
231		items = grow(newCount);
232		int mv = n - index;
233		if (mv > 0)
#	Line 244 | Line 240 | public class ReadMostlyVector<E>
240		final boolean rawRemoveAt(int index) {
241		int n = count - 1;
242		Object[] items = array;
243	<	if (index < 0 || index > n)
243	>	if (items == null || index < 0 || index > n)
244		return false;
245		int mv = n - index;
246		if (mv > 0)
#	Line 261 | Line 257 | public class ReadMostlyVector<E>
257		* is left negative if the bound should be determined via count
258		* field under lock.
259		*/
260	<	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
265	<	final SequenceLock lock = this.lock;
260	>	final boolean lockedRemoveAll(Collection<?> c, int origin, int bound) {
261		boolean removed = false;
262	<	lock.lock();
262	>	final StampedLock lock = this.lock;
263	>	long stamp = lock.writeLock();
264		try {
265		int n = count;
266		int fence = bound < 0 || bound > n ? n : bound;
267		if (origin >= 0 && origin < fence) {
268		for (Object x : c) {
269	<	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
269	>	while (rawRemoveAt(findFirstIndex(array, x, origin, fence)))
270		removed = true;
271		}
272		}
273		} finally {
274	<	lock.unlock();
274	>	lock.unlockWrite(stamp);
275		}
276		return removed;
277		}
278
279	<	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
280	<	final SequenceLock lock = this.lock;
279	>	final boolean lockedRetainAll(Collection<?> c, int origin, int bound) {
280	>	final StampedLock lock = this.lock;
281		boolean removed = false;
282		if (c != this) {
283	<	lock.lock();
283	>	long stamp = lock.writeLock();
284		try {
285	<	Object[] items = array;
286	<	int i = origin;
287	<	int n = count;
288	<	int fence = bound < 0 || bound > n ? n : bound;
289	<	while (i >= 0 && i < fence) {
290	<	if (c.contains(items[i]))
291	<	++i;
292	<	else {
293	<	--fence;
294	<	int mv = --n - i;
295	<	if (mv > 0)
296	<	System.arraycopy(items, i + 1, items, i, mv);
285	>	Object[] items;
286	>	int i, n;
287	>	if ((items = array) != null && (n = count) > 0 &&
288	>	n < items.length && (i = origin) >= 0) {
289	>	int fence = bound < 0 || bound > n ? n : bound;
290	>	while (i < fence) {
291	>	if (c.contains(items[i]))
292	>	++i;
293	>	else {
294	>	--fence;
295	>	int mv = --n - i;
296	>	if (mv > 0)
297	>	System.arraycopy(items, i + 1, items, i, mv);
298	>	}
299	>	}
300	>	if (count != n) {
301	>	count = n;
302	>	removed = true;
303		}
302	–	}
303	–	if (count != n) {
304	–	count = n;
305	–	removed = true;
304		}
305		} finally {
306	<	lock.unlock();
306	>	lock.unlockWrite(stamp);
307		}
308		}
309		return removed;
310		}
311
312		final void internalClear(int origin, int bound) {
313	<	int n = count;
314	<	int fence = bound < 0 || bound > n ? n : bound;
315	<	if (origin >= 0 && origin < fence) {
316	<	Object[] items = array;
313	>	Object[] items;
314	>	int n, len;
315	>	if ((items = array) != null && (len = items.length) > 0) {
316	>	if (origin < 0)
317	>	origin = 0;
318	>	if ((n = count) > len)
319	>	n = len;
320	>	int fence = bound < 0 || bound > n ? n : bound;
321		int removed = fence - origin;
322		int newCount = n - removed;
323		int mv = n - (origin + removed);
#	Line 328 | Line 330 | public class ReadMostlyVector<E>
330		}
331
332		final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
333	<	final SequenceLock lock = this.lock;
334	<	boolean contained;
335	<	boolean locked = false;
336	<	try {
337	<	for (;;) {
338	<	long seq = lock.awaitAvailability();
339	<	int n = count;
340	<	Object[] items = array;
341	<	int len = items.length;
342	<	if (n > len)
343	<	continue;
342	<	int fence = bound < 0 || bound > n ? n : bound;
343	<	if (origin < 0)
344	<	contained = false;
345	<	else {
346	<	contained = true;
347	<	for (Object e : c) {
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	<	}
356	<	}
357	<	}
358	<	if (lock.getSequence() == seq)
359	<	break;
360	<	lock.lock();
361	<	locked = true;
333	>	Object[] items;
334	>	int n, len;
335	>	if ((items = array) != null && (len = items.length) > 0) {
336	>	if (origin < 0)
337	>	origin = 0;
338	>	if ((n = count) > len)
339	>	n = len;
340	>	int fence = bound < 0 || bound > n ? n : bound;
341	>	for (Object e : c) {
342	>	if (findFirstIndex(items, e, origin, fence) < 0)
343	>	return false;
344		}
363	–	} finally {
364	–	if (locked)
365	–	lock.unlock();
345		}
346	<	return contained;
346	>	else if (!c.isEmpty())
347	>	return false;
348	>	return true;
349		}
350
351		final boolean internalEquals(List<?> list, int origin, int bound) {
352	<	final SequenceLock lock = this.lock;
353	<	boolean locked = false;
354	<	boolean equal;
355	<	try {
356	<	for (;;) {
357	<	long seq = lock.awaitAvailability();
358	<	Object[] items = array;
359	<	int n = count;
360	<	if (n > items.length || origin < 0)
361	<	equal = false;
362	<	else {
363	<	equal = true;
364	<	int fence = bound < 0 || bound > n ? n : bound;
365	<	Iterator<?> it = list.iterator();
366	<	for (int i = origin; i < fence; ++i) {
367	<	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	<	}
395	<	}
396	<	if (equal && it.hasNext())
397	<	equal = false;
398	<	}
399	<	if (lock.getSequence() == seq)
400	<	break;
401	<	lock.lock();
402	<	locked = true;
352	>	Object[] items;
353	>	int n, len;
354	>	if ((items = array) != null && (len = items.length) > 0) {
355	>	if (origin < 0)
356	>	origin = 0;
357	>	if ((n = count) > len)
358	>	n = len;
359	>	int fence = bound < 0 || bound > n ? n : bound;
360	>	Iterator<?> it = list.iterator();
361	>	for (int i = origin; i < fence; ++i) {
362	>	if (!it.hasNext())
363	>	return false;
364	>	Object y = it.next();
365	>	Object x = items[i];
366	>	if (x != y && (x == null || !x.equals(y)))
367	>	return false;
368		}
369	<	} finally {
370	<	if (locked)
406	<	lock.unlock();
369	>	if (it.hasNext())
370	>	return false;
371		}
372	<	return equal;
372	>	else if (!list.isEmpty())
373	>	return false;
374	>	return true;
375		}
376
377		final int internalHashCode(int origin, int bound) {
378	<	final SequenceLock lock = this.lock;
379	<	int hash;
380	<	boolean locked = false;
381	<	try {
382	<	for (;;) {
383	<	hash = 1;
384	<	long seq = lock.awaitAvailability();
385	<	Object[] items = array;
386	<	int n = count;
387	<	int len = items.length;
388	<	if (n > len)
389	<	continue;
424	<	int fence = bound < 0 || bound > n ? n : bound;
425	<	if (origin >= 0) {
426	<	for (int i = origin; i < fence; ++i) {
427	<	Object e = items[i];
428	<	hash = 31*hash + (e == null ? 0 : e.hashCode());
429	<	}
430	<	}
431	<	if (lock.getSequence() == seq)
432	<	break;
433	<	lock.lock();
434	<	locked = true;
378	>	int hash = 1;
379	>	Object[] items;
380	>	int n, len;
381	>	if ((items = array) != null && (len = items.length) > 0) {
382	>	if (origin < 0)
383	>	origin = 0;
384	>	if ((n = count) > len)
385	>	n = len;
386	>	int fence = bound < 0 || bound > n ? n : bound;
387	>	for (int i = origin; i < fence; ++i) {
388	>	Object e = items[i];
389	>	hash = 31*hash + (e == null ? 0 : e.hashCode());
390		}
436	–	} finally {
437	–	if (locked)
438	–	lock.unlock();
391		}
392		return hash;
393		}
394
395		final String internalToString(int origin, int bound) {
396	<	final SequenceLock lock = this.lock;
397	<	String ret;
398	<	boolean locked = false;
399	<	try {
400	<	outer:for (;;) {
401	<	long seq = lock.awaitAvailability();
402	<	Object[] items = array;
403	<	int n = count;
404	<	int len = items.length;
405	<	if (n > len)
406	<	continue;
407	<	int fence = bound < 0 || bound > n ? n : bound;
408	<	if (origin < 0 || origin == fence)
409	<	ret = "[]";
410	<	else {
411	<	StringBuilder sb = new StringBuilder();
412	<	sb.append('[');
461	<	for (int i = origin;;) {
462	<	Object e = items[i];
463	<	if (e == this)
464	<	sb.append("(this Collection)");
465	<	else if (!locked && lock.getSequence() != seq)
466	<	continue outer;
467	<	else
468	<	sb.append(e.toString());
469	<	if (++i < fence)
470	<	sb.append(',').append(' ');
471	<	else {
472	<	ret = sb.append(']').toString();
473	<	break;
474	<	}
475	<	}
396	>	Object[] items;
397	>	int n, len;
398	>	if ((items = array) != null && (len = items.length) > 0) {
399	>	if ((n = count) > len)
400	>	n = len;
401	>	int fence = bound < 0 || bound > n ? n : bound;
402	>	int i = (origin < 0) ? 0 : origin;
403	>	if (i != fence) {
404	>	StringBuilder sb = new StringBuilder();
405	>	sb.append('[');
406	>	for (;;) {
407	>	Object e = items[i];
408	>	sb.append((e == this) ? "(this Collection)" : e.toString());
409	>	if (++i < fence)
410	>	sb.append(',').append(' ');
411	>	else
412	>	return sb.append(']').toString();
413		}
477	–	if (lock.getSequence() == seq)
478	–	break;
479	–	lock.lock();
480	–	locked = true;
414		}
482	–	} finally {
483	–	if (locked)
484	–	lock.unlock();
415		}
416	<	return ret;
416	>	return "[]";
417		}
418
419		final Object[] internalToArray(int origin, int bound) {
420	<	Object[] result;
421	<	final SequenceLock lock = this.lock;
422	<	boolean locked = false;
423	<	try {
424	<	for (;;) {
425	<	result = null;
426	<	long seq = lock.awaitAvailability();
427	<	Object[] items = array;
428	<	int n = count;
429	<	int len = items.length;
430	<	if (n > len)
501	<	continue;
502	<	int fence = bound < 0 || bound > n ? n : bound;
503	<	if (origin >= 0)
504	<	result = Arrays.copyOfRange(items, origin, fence,
505	<	Object[].class);
506	<	if (lock.getSequence() == seq)
507	<	break;
508	<	lock.lock();
509	<	locked = true;
510	<	}
511	<	} finally {
512	<	if (locked)
513	<	lock.unlock();
420	>	Object[] items;
421	>	int n, len;
422	>	if ((items = array) != null && (len = items.length) > 0) {
423	>	if (origin < 0)
424	>	origin = 0;
425	>	if ((n = count) > len)
426	>	n = len;
427	>	int fence = bound < 0 || bound > n ? n : bound;
428	>	int i = (origin < 0) ? 0 : origin;
429	>	if (i != fence)
430	>	return Arrays.copyOfRange(items, i, fence, Object[].class);
431		}
432	<	return result;
432	>	return new Object[0];
433		}
434
435		@SuppressWarnings("unchecked")
436		final <T> T[] internalToArray(T[] a, int origin, int bound) {
437		int alen = a.length;
438	<	T[] result;
439	<	final SequenceLock lock = this.lock;
440	<	boolean locked = false;
441	<	try {
442	<	for (;;) {
443	<	long seq = lock.awaitAvailability();
444	<	Object[] items = array;
445	<	int n = count;
446	<	int len = items.length;
447	<	if (n > len)
448	<	continue;
449	<	int fence = bound < 0 || bound > n ? n : bound;
450	<	int rlen = fence - origin;
534	<	if (rlen < 0)
535	<	rlen = 0;
536	<	if (origin < 0 || alen >= rlen) {
537	<	if (rlen > 0)
538	<	System.arraycopy(items, 0, a, origin, rlen);
438	>	Object[] items;
439	>	int n, len;
440	>	if ((items = array) != null && (len = items.length) > 0) {
441	>	if (origin < 0)
442	>	origin = 0;
443	>	if ((n = count) > len)
444	>	n = len;
445	>	int fence = bound < 0 || bound > n ? n : bound;
446	>	int i = (origin < 0) ? 0 : origin;
447	>	int rlen = fence - origin;
448	>	if (rlen > 0) {
449	>	if (alen >= rlen) {
450	>	System.arraycopy(items, 0, a, origin, rlen);
451		if (alen > rlen)
452		a[rlen] = null;
453	<	result = a;
453	>	return a;
454		}
455	<	else
544	<	result = (T[]) Arrays.copyOfRange(items, origin,
545	<	fence, a.getClass());
546	<	if (lock.getSequence() == seq)
547	<	break;
548	<	lock.lock();
549	<	locked = true;
455	>	return (T[]) Arrays.copyOfRange(items, i, fence, a.getClass());
456		}
551	–	} finally {
552	–	if (locked)
553	–	lock.unlock();
457		}
458	<	return result;
458	>	if (alen > 0)
459	>	a[0] = null;
460	>	return a;
461		}
462
463		// public List methods
464
465		public boolean add(E e) {
466	<	final SequenceLock lock = this.lock;
467	<	lock.lock();
466	>	final StampedLock lock = this.lock;
467	>	long stamp = lock.writeLock();
468		try {
469		rawAdd(e);
470		} finally {
471	<	lock.unlock();
471	>	lock.unlockWrite(stamp);
472		}
473		return true;
474		}
475
476		public void add(int index, E element) {
477	<	final SequenceLock lock = this.lock;
478	<	lock.lock();
477	>	final StampedLock lock = this.lock;
478	>	long stamp = lock.writeLock();
479		try {
480		rawAddAt(index, element);
481		} finally {
482	<	lock.unlock();
482	>	lock.unlockWrite(stamp);
483		}
484		}
485
#	Line 583 | Line 488 | public class ReadMostlyVector<E>
488		int len = elements.length;
489		if (len == 0)
490		return false;
491	<	final SequenceLock lock = this.lock;
492	<	lock.lock();
491	>	final StampedLock lock = this.lock;
492	>	long stamp = lock.writeLock();
493		try {
494		Object[] items = array;
495		int n = count;
496		int newCount = n + len;
497	<	if (newCount >= items.length)
497	>	if (items == null || newCount >= items.length)
498		items = grow(newCount);
499		System.arraycopy(elements, 0, items, n, len);
500		count = newCount;
501		} finally {
502	<	lock.unlock();
502	>	lock.unlockWrite(stamp);
503		}
504		return true;
505		}
506
507		public boolean addAll(int index, Collection<? extends E> c) {
603	–	final SequenceLock lock = this.lock;
604	–	boolean ret;
508		Object[] elements = c.toArray();
509	<	lock.lock();
509	>	boolean ret;
510	>	final StampedLock lock = this.lock;
511	>	long stamp = lock.writeLock();
512		try {
513		ret = rawAddAllAt(index, elements);
514		} finally {
515	<	lock.unlock();
515	>	lock.unlockWrite(stamp);
516		}
517		return ret;
518		}
519
520		public void clear() {
521	<	final SequenceLock lock = this.lock;
522	<	lock.lock();
521	>	final StampedLock lock = this.lock;
522	>	long stamp = lock.writeLock();
523		try {
524		int n = count;
525		Object[] items = array;
526	<	for (int i = 0; i < n; i++)
527	<	items[i] = null;
526	>	if (items != null) {
527	>	for (int i = 0; i < n; i++)
528	>	items[i] = null;
529	>	}
530		count = 0;
531		} finally {
532	<	lock.unlock();
532	>	lock.unlockWrite(stamp);
533		}
534		}
535
#	Line 631 | Line 538 | public class ReadMostlyVector<E>
538		}
539
540		public boolean containsAll(Collection<?> c) {
541	<	return internalContainsAll(c, 0, -1);
541	>	boolean ret;
542	>	final StampedLock lock = this.lock;
543	>	long stamp = lock.readLock();
544	>	try {
545	>	ret = internalContainsAll(c, 0, -1);
546	>	} finally {
547	>	lock.unlockRead(stamp);
548	>	}
549	>	return ret;
550		}
551
552		public boolean equals(Object o) {
#	Line 639 | Line 554 | public class ReadMostlyVector<E>
554		return true;
555		if (!(o instanceof List))
556		return false;
557	<	return internalEquals((List<?>)o, 0, -1);
557	>	final StampedLock lock = this.lock;
558	>	long stamp = lock.readLock();
559	>	try {
560	>	return internalEquals((List<?>)o, 0, -1);
561	>	} finally {
562	>	lock.unlockRead(stamp);
563	>	}
564		}
565
566		public E get(int index) {
567	<	final SequenceLock lock = this.lock;
568	<	for (;;) {
569	<	long seq = lock.awaitAvailability();
570	<	int n = count;
571	<	Object[] items = array;
572	<	if (n > items.length)
573	<	continue;
574	<	boolean outOfBounds = (index < 0 || index >= n);
575	<	@SuppressWarnings("unchecked")
576	<	E e = outOfBounds ? null : (E) items[index];
577	<	if (lock.getSequence() == seq) {
578	<	if (outOfBounds)
579	<	throw new ArrayIndexOutOfBoundsException(index);
580	<	else
581	<	return e;
582	<	}
567	>	final StampedLock lock = this.lock;
568	>	long stamp = lock.tryOptimisticRead();
569	>	Object[] items;
570	>	if (index >= 0 && (items = array) != null &&
571	>	index < count && index < items.length) {
572	>	@SuppressWarnings("unchecked") E e = (E)items[index];
573	>	if (lock.validate(stamp))
574	>	return e;
575	>	}
576	>	return lockedGet(index);
577	>	}
578	>
579	>	@SuppressWarnings("unchecked") private E lockedGet(int index) {
580	>	boolean oobe = false;
581	>	E e = null;
582	>	final StampedLock lock = this.lock;
583	>	long stamp = lock.readLock();
584	>	try {
585	>	Object[] items;
586	>	if ((items = array) != null && index < items.length &&
587	>	index < count && index >= 0)
588	>	e = (E)items[index];
589	>	else
590	>	oobe = true;
591	>	} finally {
592	>	lock.unlockRead(stamp);
593		}
594	+	if (oobe)
595	+	throw new ArrayIndexOutOfBoundsException(index);
596	+	return (E)e;
597		}
598
599		public int hashCode() {
600	<	return internalHashCode(0, -1);
600	>	int h;
601	>	final StampedLock lock = this.lock;
602	>	long s = lock.readLock();
603	>	try {
604	>	h = internalHashCode(0, -1);
605	>	} finally {
606	>	lock.unlockRead(s);
607	>	}
608	>	return h;
609		}
610
611		public int indexOf(Object o) {
612	<	final SequenceLock lock = this.lock;
613	<	for (;;) {
614	<	long seq = lock.awaitAvailability();
615	<	Object[] items = array;
616	<	int n = count;
617	<	if (n <= items.length) {
618	<	for (int i = 0; i < n; ++i) {
677	<	Object e = items[i];
678	<	if (lock.getSequence() != seq) {
679	<	lock.lock();
680	<	try {
681	<	return rawIndexOf(o, 0, count);
682	<	} finally {
683	<	lock.unlock();
684	<	}
685	<	}
686	<	else if ((o == null) ? e == null : o.equals(e))
687	<	return i;
688	<	}
689	<	return -1;
690	<	}
612	>	int idx;
613	>	final StampedLock lock = this.lock;
614	>	long stamp = lock.readLock();
615	>	try {
616	>	idx = findFirstIndex(array, o, 0, count);
617	>	} finally {
618	>	lock.unlockRead(stamp);
619		}
620	+	return idx;
621		}
622
623		public boolean isEmpty() {
624	<	return count == 0;
624	>	final StampedLock lock = this.lock;
625	>	long stamp = lock.tryOptimisticRead();
626	>	return count == 0; // no need for validation
627		}
628
629		public Iterator<E> iterator() {
#	Line 700 | Line 631 | public class ReadMostlyVector<E>
631		}
632
633		public int lastIndexOf(Object o) {
634	<	final SequenceLock lock = this.lock;
635	<	for (;;) {
636	<	long seq = lock.awaitAvailability();
637	<	Object[] items = array;
638	<	int n = count;
639	<	if (n <= items.length) {
640	<	for (int i = n - 1; i >= 0; --i) {
710	<	Object e = items[i];
711	<	if (lock.getSequence() != seq) {
712	<	lock.lock();
713	<	try {
714	<	return rawLastIndexOf(o, 0, count);
715	<	} finally {
716	<	lock.unlock();
717	<	}
718	<	}
719	<	else if ((o == null) ? e == null : o.equals(e))
720	<	return i;
721	<	}
722	<	return -1;
723	<	}
634	>	int idx;
635	>	final StampedLock lock = this.lock;
636	>	long stamp = lock.readLock();
637	>	try {
638	>	idx = findLastIndex(array, o, count - 1, 0);
639	>	} finally {
640	>	lock.unlockRead(stamp);
641		}
642	+	return idx;
643		}
644
645		public ListIterator<E> listIterator() {
#	Line 732 | Line 650 | public class ReadMostlyVector<E>
650		return new Itr<E>(this, index);
651		}
652
653	<	public E remove(int index) {
654	<	final SequenceLock lock = this.lock;
655	<	lock.lock();
653	>	@SuppressWarnings("unchecked") public E remove(int index) {
654	>	E oldValue = null;
655	>	boolean oobe = false;
656	>	final StampedLock lock = this.lock;
657	>	long stamp = lock.writeLock();
658		try {
659		if (index < 0 || index >= count)
660	<	throw new ArrayIndexOutOfBoundsException(index);
661	<	@SuppressWarnings("unchecked")
662	<	E oldValue = (E) array[index];
663	<	rawRemoveAt(index);
664	<	return oldValue;
660	>	oobe = true;
661	>	else {
662	>	oldValue = (E) array[index];
663	>	rawRemoveAt(index);
664	>	}
665		} finally {
666	<	lock.unlock();
666	>	lock.unlockWrite(stamp);
667		}
668	+	if (oobe)
669	+	throw new ArrayIndexOutOfBoundsException(index);
670	+	return oldValue;
671		}
672
673		public boolean remove(Object o) {
674	<	final SequenceLock lock = this.lock;
675	<	lock.lock();
674	>	final StampedLock lock = this.lock;
675	>	long stamp = lock.writeLock();
676		try {
677	<	return rawRemoveAt(rawIndexOf(o, 0, count));
677	>	return rawRemoveAt(findFirstIndex(array, o, 0, count));
678		} finally {
679	<	lock.unlock();
679	>	lock.unlockWrite(stamp);
680		}
681		}
682
683		public boolean removeAll(Collection<?> c) {
684	<	return internalRemoveAll(c, 0, -1);
684	>	return lockedRemoveAll(c, 0, -1);
685		}
686
687		public boolean retainAll(Collection<?> c) {
688	<	return internalRetainAll(c, 0, -1);
688	>	return lockedRetainAll(c, 0, -1);
689		}
690
691	<	public E set(int index, E element) {
692	<	final SequenceLock lock = this.lock;
693	<	lock.lock();
691	>	@SuppressWarnings("unchecked") public E set(int index, E element) {
692	>	E oldValue = null;
693	>	boolean oobe = false;
694	>	final StampedLock lock = this.lock;
695	>	long stamp = lock.writeLock();
696		try {
697		Object[] items = array;
698	<	if (index < 0 || index >= count)
699	<	throw new ArrayIndexOutOfBoundsException(index);
700	<	@SuppressWarnings("unchecked")
701	<	E oldValue = (E) items[index];
702	<	items[index] = element;
703	<	return oldValue;
698	>	if (items == null || index < 0 || index >= count)
699	>	oobe = true;
700	>	else {
701	>	oldValue = (E) items[index];
702	>	items[index] = element;
703	>	}
704		} finally {
705	<	lock.unlock();
705	>	lock.unlockWrite(stamp);
706		}
707	+	if (oobe)
708	+	throw new ArrayIndexOutOfBoundsException(index);
709	+	return oldValue;
710		}
711
712		public int size() {
713	<	return count;
713	>	final StampedLock lock = this.lock;
714	>	long stamp = lock.tryOptimisticRead();
715	>	return count; // no need for validation
716	>	}
717	>
718	>	private int lockedSize() {
719	>	int n;
720	>	final StampedLock lock = this.lock;
721	>	long stamp = lock.readLock();
722	>	try {
723	>	n = count;
724	>	} finally {
725	>	lock.unlockRead(stamp);
726	>	}
727	>	return n;
728		}
729
730		public List<E> subList(int fromIndex, int toIndex) {
789	–	int c = size();
731		int ssize = toIndex - fromIndex;
732	<	if (fromIndex < 0 || toIndex > c || ssize < 0)
733	<	throw new IndexOutOfBoundsException();
734	<	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
732	>	if (ssize >= 0 && fromIndex >= 0) {
733	>	ReadMostlyVectorSublist<E> ret = null;
734	>	final StampedLock lock = this.lock;
735	>	long stamp = lock.readLock();
736	>	try {
737	>	if (toIndex <= count)
738	>	ret = new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
739	>	} finally {
740	>	lock.unlockRead(stamp);
741	>	}
742	>	if (ret != null)
743	>	return ret;
744	>	}
745	>
746	>	throw new ArrayIndexOutOfBoundsException(fromIndex < 0 ? fromIndex : toIndex);
747		}
748
749		public Object[] toArray() {
750	<	return internalToArray(0, -1);
750	>	final StampedLock lock = this.lock;
751	>	long stamp = lock.readLock();
752	>	try {
753	>	return internalToArray(0, -1);
754	>	} finally {
755	>	lock.unlockRead(stamp);
756	>	}
757		}
758
759		public <T> T[] toArray(T[] a) {
760	<	return internalToArray(a, 0, -1);
760	>	final StampedLock lock = this.lock;
761	>	long stamp = lock.readLock();
762	>	try {
763	>	return internalToArray(a, 0, -1);
764	>	} finally {
765	>	lock.unlockRead(stamp);
766	>	}
767		}
768
769		public String toString() {
770	<	return internalToString(0, -1);
770	>	final StampedLock lock = this.lock;
771	>	long stamp = lock.readLock();
772	>	try {
773	>	return internalToString(0, -1);
774	>	} finally {
775	>	lock.unlockRead(stamp);
776	>	}
777		}
778
779		// ReadMostlyVector-only methods
780
781		/**
782	<	* Append the element if not present.
782	>	* Appends the element, if not present.
783		*
784		* @param e element to be added to this list, if absent
785		* @return {@code true} if the element was added
786		*/
787		public boolean addIfAbsent(E e) {
788	<	final SequenceLock lock = this.lock;
789	<	lock.lock();
788	>	boolean ret;
789	>	final StampedLock lock = this.lock;
790	>	long stamp = lock.writeLock();
791		try {
792	<	if (rawIndexOf(e, 0, count) < 0) {
792	>	if (findFirstIndex(array, e, 0, count) < 0) {
793		rawAdd(e);
794	<	return true;
794	>	ret = true;
795		}
796		else
797	<	return false;
797	>	ret = false;
798		} finally {
799	<	lock.unlock();
799	>	lock.unlockWrite(stamp);
800		}
801	+	return ret;
802		}
803
804		/**
#	Line 844 | Line 817 | public class ReadMostlyVector<E>
817		Object[] cs = c.toArray();
818		int clen = cs.length;
819		if (clen != 0) {
820	<	lock.lock();
820	>	long stamp = lock.writeLock();
821		try {
822		for (int i = 0; i < clen; ++i) {
823		@SuppressWarnings("unchecked")
824		E e = (E) cs[i];
825	<	if (rawIndexOf(e, 0, count) < 0) {
825	>	if (findFirstIndex(array, e, 0, count) < 0) {
826		rawAdd(e);
827		++added;
828		}
829		}
830		} finally {
831	<	lock.unlock();
831	>	lock.unlockWrite(stamp);
832		}
833		}
834		return added;
#	Line 878 | Line 851 | public class ReadMostlyVector<E>
851		private int cursor;
852		SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
853		public boolean hasNext() { return cursor < items.length; }
854	<	@SuppressWarnings("unchecked")
882	<	public E next() {
854	>	@SuppressWarnings("unchecked") public E next() {
855		if (cursor < items.length)
856		return (E) items[cursor++];
857		throw new NoSuchElementException();
#	Line 887 | Line 859 | public class ReadMostlyVector<E>
859		public void remove() { throw new UnsupportedOperationException() ; }
860		}
861
862	+	/** Interface describing a void action of one argument */
863	+	public interface Action<A> { void apply(A a); }
864	+
865	+	public void forEachReadOnly(Action<E> action) {
866	+	final StampedLock lock = this.lock;
867	+	long stamp = lock.readLock();
868	+	try {
869	+	Object[] items;
870	+	int len, n;
871	+	if ((items = array) != null && (len = items.length) > 0 &&
872	+	(n = count) <= len) {
873	+	for (int i = 0; i < n; ++i) {
874	+	@SuppressWarnings("unchecked") E e = (E)items[i];
875	+	action.apply(e);
876	+	}
877	+	}
878	+	} finally {
879	+	lock.unlockRead(stamp);
880	+	}
881	+	}
882	+
883		// Vector-only methods
884
885		/** See {@link Vector#firstElement} */
886		public E firstElement() {
887	<	final SequenceLock lock = this.lock;
888	<	for (;;) {
889	<	long seq = lock.awaitAvailability();
887	>	final StampedLock lock = this.lock;
888	>	long stamp = lock.tryOptimisticRead();
889	>	Object[] items;
890	>	if ((items = array) != null && count > 0 && items.length > 0) {
891	>	@SuppressWarnings("unchecked") E e = (E)items[0];
892	>	if (lock.validate(stamp))
893	>	return e;
894	>	}
895	>	return lockedFirstElement();
896	>	}
897	>
898	>	@SuppressWarnings("unchecked") private E lockedFirstElement() {
899	>	Object e = null;
900	>	boolean oobe = false;
901	>	final StampedLock lock = this.lock;
902	>	long stamp = lock.readLock();
903	>	try {
904		Object[] items = array;
905	<	int len = items.length;
906	<	int n = count;
907	<	if (n > len)
908	<	continue;
909	<	boolean empty = (n == 0);
910	<	@SuppressWarnings("unchecked")
904	<	E e = empty ? null : (E) items[0];
905	<	if (lock.getSequence() == seq) {
906	<	if (empty)
907	<	throw new NoSuchElementException();
908	<	else
909	<	return e;
910	<	}
905	>	if (items != null && count > 0 && items.length > 0)
906	>	e = items[0];
907	>	else
908	>	oobe = true;
909	>	} finally {
910	>	lock.unlockRead(stamp);
911		}
912	+	if (oobe)
913	+	throw new NoSuchElementException();
914	+	return (E) e;
915		}
916
917		/** See {@link Vector#lastElement} */
918		public E lastElement() {
919	<	final SequenceLock lock = this.lock;
920	<	for (;;) {
921	<	long seq = lock.awaitAvailability();
919	>	final StampedLock lock = this.lock;
920	>	long stamp = lock.tryOptimisticRead();
921	>	Object[] items;
922	>	int i;
923	>	if ((items = array) != null && (i = count - 1) >= 0 &&
924	>	i < items.length) {
925	>	@SuppressWarnings("unchecked") E e = (E)items[i];
926	>	if (lock.validate(stamp))
927	>	return e;
928	>	}
929	>	return lockedLastElement();
930	>	}
931	>
932	>	@SuppressWarnings("unchecked") private E lockedLastElement() {
933	>	Object e = null;
934	>	boolean oobe = false;
935	>	final StampedLock lock = this.lock;
936	>	long stamp = lock.readLock();
937	>	try {
938		Object[] items = array;
939	<	int len = items.length;
940	<	int n = count;
941	<	if (n > len)
942	<	continue;
943	<	boolean empty = (n == 0);
944	<	@SuppressWarnings("unchecked")
945	<	E e = empty ? null : (E) items[n - 1];
927	<	if (lock.getSequence() == seq) {
928	<	if (empty)
929	<	throw new NoSuchElementException();
930	<	else
931	<	return e;
932	<	}
939	>	int i = count - 1;
940	>	if (items != null && i >= 0 && i < items.length)
941	>	e = items[i];
942	>	else
943	>	oobe = true;
944	>	} finally {
945	>	lock.unlockRead(stamp);
946		}
947	+	if (oobe)
948	+	throw new NoSuchElementException();
949	+	return (E) e;
950		}
951
952		/** See {@link Vector#indexOf(Object, int)} */
953		public int indexOf(Object o, int index) {
954	<	final SequenceLock lock = this.lock;
939	<	int idx = 0;
940	<	boolean ex = false;
941	<	long seq = lock.awaitAvailability();
942	<	Object[] items = array;
943	<	int n = count;
944	<	boolean retry = false;
945	<	if (n > items.length)
946	<	retry = true;
947	<	else if (index < 0)
948	<	ex = true;
949	<	else
950	<	idx = validatedIndexOf(o, items, index, n, seq);
951	<	if (retry || lock.getSequence() != seq) {
952	<	lock.lock();
953	<	try {
954	<	if (index < 0)
955	<	ex = true;
956	<	else
957	<	idx = rawIndexOf(o, 0, count);
958	<	} finally {
959	<	lock.unlock();
960	<	}
961	<	}
962	<	if (ex)
954	>	if (index < 0)
955		throw new ArrayIndexOutOfBoundsException(index);
956	+	int idx;
957	+	final StampedLock lock = this.lock;
958	+	long stamp = lock.readLock();
959	+	try {
960	+	idx = findFirstIndex(array, o, index, count);
961	+	} finally {
962	+	lock.unlockRead(stamp);
963	+	}
964		return idx;
965		}
966
967		/** See {@link Vector#lastIndexOf(Object, int)} */
968		public int lastIndexOf(Object o, int index) {
969	<	final SequenceLock lock = this.lock;
970	<	int idx = 0;
971	<	boolean ex = false;
972	<	long seq = lock.awaitAvailability();
973	<	Object[] items = array;
974	<	int n = count;
975	<	boolean retry = false;
976	<	if (n > items.length)
977	<	retry = true;
978	<	else if (index >= n)
979	<	ex = true;
980	<	else
981	<	idx = validatedLastIndexOf(o, items, index, 0, seq);
982	<	if (retry || lock.getSequence() != seq) {
983	<	lock.lock();
984	<	try {
985	<	if (index >= count)
986	<	ex = true;
987	<	else
988	<	idx = rawLastIndexOf(o, index, 0);
989	<	} finally {
990	<	lock.unlock();
991	<	}
969	>	boolean oobe = false;
970	>	int idx = -1;
971	>	final StampedLock lock = this.lock;
972	>	long stamp = lock.readLock();
973	>	try {
974	>	if (index < count)
975	>	idx = findLastIndex(array, o, index, 0);
976	>	else
977	>	oobe = true;
978	>	} finally {
979	>	lock.unlockRead(stamp);
980		}
981	<	if (ex)
981	>	if (oobe)
982		throw new ArrayIndexOutOfBoundsException(index);
983		return idx;
984		}
#	Line 999 | Line 987 | public class ReadMostlyVector<E>
987		public void setSize(int newSize) {
988		if (newSize < 0)
989		throw new ArrayIndexOutOfBoundsException(newSize);
990	<	final SequenceLock lock = this.lock;
991	<	lock.lock();
990	>	final StampedLock lock = this.lock;
991	>	long stamp = lock.writeLock();
992		try {
993	+	Object[] items;
994		int n = count;
995		if (newSize > n)
996		grow(newSize);
997	<	else {
1009	<	Object[] items = array;
997	>	else if ((items = array) != null) {
998		for (int i = newSize ; i < n ; i++)
999		items[i] = null;
1000		}
1001		count = newSize;
1002		} finally {
1003	<	lock.unlock();
1003	>	lock.unlockWrite(stamp);
1004		}
1005		}
1006
1007		/** See {@link Vector#copyInto} */
1008		public void copyInto(Object[] anArray) {
1009	<	final SequenceLock lock = this.lock;
1010	<	lock.lock();
1009	>	final StampedLock lock = this.lock;
1010	>	long stamp = lock.writeLock();
1011		try {
1012	<	System.arraycopy(array, 0, anArray, 0, count);
1012	>	Object[] items;
1013	>	if ((items = array) != null)
1014	>	System.arraycopy(items, 0, anArray, 0, count);
1015		} finally {
1016	<	lock.unlock();
1016	>	lock.unlockWrite(stamp);
1017		}
1018		}
1019
1020		/** See {@link Vector#trimToSize} */
1021		public void trimToSize() {
1022	<	final SequenceLock lock = this.lock;
1023	<	lock.lock();
1022	>	final StampedLock lock = this.lock;
1023	>	long stamp = lock.writeLock();
1024		try {
1025		Object[] items = array;
1026		int n = count;
1027	<	if (n < items.length)
1027	>	if (items != null && n < items.length)
1028		array = Arrays.copyOf(items, n);
1029		} finally {
1030	<	lock.unlock();
1030	>	lock.unlockWrite(stamp);
1031		}
1032		}
1033
1034		/** See {@link Vector#ensureCapacity} */
1035		public void ensureCapacity(int minCapacity) {
1036		if (minCapacity > 0) {
1037	<	final SequenceLock lock = this.lock;
1038	<	lock.lock();
1037	>	final StampedLock lock = this.lock;
1038	>	long stamp = lock.writeLock();
1039		try {
1040	<	if (minCapacity - array.length > 0)
1040	>	Object[] items = array;
1041	>	int cap = (items == null) ? 0 : items.length;
1042	>	if (minCapacity - cap > 0)
1043		grow(minCapacity);
1044		} finally {
1045	<	lock.unlock();
1045	>	lock.unlockWrite(stamp);
1046		}
1047		}
1048		}
#	Line 1103 | Line 1095 | public class ReadMostlyVector<E>
1095		// other methods
1096
1097		public ReadMostlyVector<E> clone() {
1106	–	final SequenceLock lock = this.lock;
1098		Object[] a = null;
1099	<	boolean retry = false;
1100	<	long seq = lock.awaitAvailability();
1101	<	Object[] items = array;
1102	<	int n = count;
1103	<	if (n <= items.length)
1104	<	a = Arrays.copyOf(items, n);
1105	<	else
1106	<	retry = true;
1107	<	if (retry || lock.getSequence() != seq) {
1108	<	lock.lock();
1109	<	try {
1110	<	n = count;
1120	<	a = Arrays.copyOf(array, n);
1121	<	} finally {
1122	<	lock.unlock();
1099	>	int n;
1100	>	final StampedLock lock = this.lock;
1101	>	long stamp = lock.readLock();
1102	>	try {
1103	>	Object[] items = array;
1104	>	if (items == null)
1105	>	n = 0;
1106	>	else {
1107	>	int len = items.length;
1108	>	if ((n = count) > len)
1109	>	n = len;
1110	>	a = Arrays.copyOf(items, n);
1111		}
1112	+	} finally {
1113	+	lock.unlockRead(stamp);
1114		}
1115		return new ReadMostlyVector<E>(a, n, capacityIncrement);
1116		}
1117
1118		private void writeObject(java.io.ObjectOutputStream s)
1119	<	throws java.io.IOException {
1120	<	final SequenceLock lock = this.lock;
1121	<	lock.lock();
1119	>	throws java.io.IOException {
1120	>	final StampedLock lock = this.lock;
1121	>	long stamp = lock.readLock();
1122		try {
1123		s.defaultWriteObject();
1124		} finally {
1125	<	lock.unlock();
1125	>	lock.unlockRead(stamp);
1126		}
1127		}
1128
1129		static final class Itr<E> implements ListIterator<E>, Enumeration<E> {
1130	+	final StampedLock lock;
1131		final ReadMostlyVector<E> list;
1141	–	final SequenceLock lock;
1132		Object[] items;
1143	–	E next, prev;
1133		long seq;
1134		int cursor;
1135		int fence;
1136		int lastRet;
1148	–	boolean validNext, validPrev;
1137
1138		Itr(ReadMostlyVector<E> list, int index) {
1139	<	this.list = list;
1140	<	this.lock = list.lock;
1141	<	this.cursor = index;
1142	<	this.lastRet = -1;
1143	<	refresh();
1139	>	final StampedLock lock = list.lock;
1140	>	long stamp = lock.readLock();
1141	>	try {
1142	>	this.list = list;
1143	>	this.lock = lock;
1144	>	this.items = list.array;
1145	>	this.fence = list.count;
1146	>	this.cursor = index;
1147	>	this.lastRet = -1;
1148	>	} finally {
1149	>	this.seq = lock.tryConvertToOptimisticRead(stamp);
1150	>	}
1151		if (index < 0 || index > fence)
1152		throw new ArrayIndexOutOfBoundsException(index);
1153		}
1154
1155	<	private void refresh() {
1156	<	validNext = validPrev = false;
1162	<	do {
1163	<	seq = lock.awaitAvailability();
1164	<	items = list.array;
1165	<	} while ((fence = list.count) > items.length ||
1166	<	lock.getSequence() != seq);
1155	>	public boolean hasPrevious() {
1156	>	return cursor > 0;
1157		}
1158
1159	<	@SuppressWarnings("unchecked")
1160	<	public boolean hasNext() {
1171	<	boolean valid;
1172	<	int i = cursor;
1173	<	for (;;) {
1174	<	if (i >= fence || i < 0 || i >= items.length) {
1175	<	valid = false;
1176	<	break;
1177	<	}
1178	<	next = (E) items[i];
1179	<	if (lock.getSequence() == seq) {
1180	<	valid = true;
1181	<	break;
1182	<	}
1183	<	refresh();
1184	<	}
1185	<	return validNext = valid;
1159	>	public int nextIndex() {
1160	>	return cursor;
1161		}
1162
1163	<	@SuppressWarnings("unchecked")
1164	<	public boolean hasPrevious() {
1165	<	boolean valid;
1166	<	int i = cursor - 1;
1167	<	for (;;) {
1168	<	if (i >= fence || i < 0 || i >= items.length) {
1194	<	valid = false;
1195	<	break;
1196	<	}
1197	<	prev = (E) items[i];
1198	<	if (lock.getSequence() == seq) {
1199	<	valid = true;
1200	<	break;
1201	<	}
1202	<	refresh();
1203	<	}
1204	<	return validPrev = valid;
1163	>	public int previousIndex() {
1164	>	return cursor - 1;
1165	>	}
1166	>
1167	>	public boolean hasNext() {
1168	>	return cursor < fence;
1169		}
1170
1171		public E next() {
1172	<	if (validNext || hasNext()) {
1173	<	validNext = false;
1174	<	lastRet = cursor++;
1175	<	return next;
1176	<	}
1177	<	throw new NoSuchElementException();
1172	>	int i = cursor;
1173	>	Object[] es = items;
1174	>	if (es == null || i < 0 || i >= fence || i >= es.length)
1175	>	throw new NoSuchElementException();
1176	>	@SuppressWarnings("unchecked") E e = (E)es[i];
1177	>	lastRet = i;
1178	>	cursor = i + 1;
1179	>	if (!lock.validate(seq))
1180	>	throw new ConcurrentModificationException();
1181	>	return e;
1182		}
1183
1184		public E previous() {
1185	<	if (validPrev || hasPrevious()) {
1186	<	validPrev = false;
1187	<	lastRet = cursor--;
1188	<	return prev;
1189	<	}
1190	<	throw new NoSuchElementException();
1185	>	int i = cursor - 1;
1186	>	Object[] es = items;
1187	>	if (es == null || i < 0 || i >= fence || i >= es.length)
1188	>	throw new NoSuchElementException();
1189	>	@SuppressWarnings("unchecked") E e = (E)es[i];
1190	>	lastRet = i;
1191	>	cursor = i;
1192	>	if (!lock.validate(seq))
1193	>	throw new ConcurrentModificationException();
1194	>	return e;
1195		}
1196
1197		public void remove() {
1198		int i = lastRet;
1199		if (i < 0)
1200		throw new IllegalStateException();
1201	<	lock.lock();
1201	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1202	>	throw new ConcurrentModificationException();
1203		try {
1204	<	if (i < list.count)
1205	<	list.remove(i);
1204	>	list.rawRemoveAt(i);
1205	>	fence = list.count;
1206	>	cursor = i;
1207	>	lastRet = -1;
1208		} finally {
1209	<	lock.unlock();
1209	>	seq = lock.tryConvertToOptimisticRead(seq);
1210		}
1236	–	cursor = i;
1237	–	lastRet = -1;
1238	–	refresh();
1211		}
1212
1213		public void set(E e) {
1214		int i = lastRet;
1215	<	if (i < 0)
1215	>	Object[] es = items;
1216	>	if (es == null || i < 0 | i >= fence)
1217		throw new IllegalStateException();
1218	<	lock.lock();
1218	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1219	>	throw new ConcurrentModificationException();
1220		try {
1221	<	if (i < list.count)
1248	<	list.set(i, e);
1221	>	es[i] = e;
1222		} finally {
1223	<	lock.unlock();
1223	>	seq = lock.tryConvertToOptimisticRead(seq);
1224		}
1252	–	refresh();
1225		}
1226
1227		public void add(E e) {
1228		int i = cursor;
1229		if (i < 0)
1230		throw new IllegalStateException();
1231	<	lock.lock();
1231	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1232	>	throw new ConcurrentModificationException();
1233		try {
1234	<	if (i <= list.count)
1235	<	list.add(i, e);
1234	>	list.rawAddAt(i, e);
1235	>	items = list.array;
1236	>	fence = list.count;
1237	>	cursor = i + 1;
1238	>	lastRet = -1;
1239		} finally {
1240	<	lock.unlock();
1240	>	seq = lock.tryConvertToOptimisticRead(seq);
1241		}
1266	–	cursor = i + 1;
1267	–	lastRet = -1;
1268	–	refresh();
1242		}
1243
1244		public boolean hasMoreElements() { return hasNext(); }
1245		public E nextElement() { return next(); }
1273	–	public int nextIndex() { return cursor; }
1274	–	public int previousIndex() { return cursor - 1; }
1246		}
1247
1248		static final class ReadMostlyVectorSublist<E>
1249		implements List<E>, RandomAccess, java.io.Serializable {
1250	<	static final long serialVersionUID = 3041673470172026059L;
1250	>	private static final long serialVersionUID = 3041673470172026059L;
1251
1252		final ReadMostlyVector<E> list;
1253		final int offset;
#	Line 1295 | Line 1266 | public class ReadMostlyVector<E>
1266		}
1267
1268		public boolean add(E element) {
1269	<	final SequenceLock lock = list.lock;
1270	<	lock.lock();
1269	>	final StampedLock lock = list.lock;
1270	>	long stamp = lock.writeLock();
1271		try {
1272		int c = size;
1273		list.rawAddAt(c + offset, element);
1274		size = c + 1;
1275		} finally {
1276	<	lock.unlock();
1276	>	lock.unlockWrite(stamp);
1277		}
1278		return true;
1279		}
1280
1281		public void add(int index, E element) {
1282	<	final SequenceLock lock = list.lock;
1283	<	lock.lock();
1282	>	final StampedLock lock = list.lock;
1283	>	long stamp = lock.writeLock();
1284		try {
1285		if (index < 0 || index > size)
1286		throw new ArrayIndexOutOfBoundsException(index);
1287		list.rawAddAt(index + offset, element);
1288		++size;
1289		} finally {
1290	<	lock.unlock();
1290	>	lock.unlockWrite(stamp);
1291		}
1292		}
1293
1294		public boolean addAll(Collection<? extends E> c) {
1295		Object[] elements = c.toArray();
1296	<	final SequenceLock lock = list.lock;
1297	<	lock.lock();
1296	>	final StampedLock lock = list.lock;
1297	>	long stamp = lock.writeLock();
1298		try {
1299		int s = size;
1300		int pc = list.count;
#	Line 1332 | Line 1303 | public class ReadMostlyVector<E>
1303		size = s + added;
1304		return added != 0;
1305		} finally {
1306	<	lock.unlock();
1306	>	lock.unlockWrite(stamp);
1307		}
1308		}
1309
1310		public boolean addAll(int index, Collection<? extends E> c) {
1311		Object[] elements = c.toArray();
1312	<	final SequenceLock lock = list.lock;
1313	<	lock.lock();
1312	>	final StampedLock lock = list.lock;
1313	>	long stamp = lock.writeLock();
1314		try {
1315		int s = size;
1316		if (index < 0 || index > s)
#	Line 1350 | Line 1321 | public class ReadMostlyVector<E>
1321		size = s + added;
1322		return added != 0;
1323		} finally {
1324	<	lock.unlock();
1324	>	lock.unlockWrite(stamp);
1325		}
1326		}
1327
1328		public void clear() {
1329	<	final SequenceLock lock = list.lock;
1330	<	lock.lock();
1329	>	final StampedLock lock = list.lock;
1330	>	long stamp = lock.writeLock();
1331		try {
1332		list.internalClear(offset, offset + size);
1333		size = 0;
1334		} finally {
1335	<	lock.unlock();
1335	>	lock.unlockWrite(stamp);
1336		}
1337		}
1338
#	Line 1370 | Line 1341 | public class ReadMostlyVector<E>
1341		}
1342
1343		public boolean containsAll(Collection<?> c) {
1344	<	return list.internalContainsAll(c, offset, offset + size);
1344	>	final StampedLock lock = list.lock;
1345	>	long stamp = lock.readLock();
1346	>	try {
1347	>	return list.internalContainsAll(c, offset, offset + size);
1348	>	} finally {
1349	>	lock.unlockRead(stamp);
1350	>	}
1351		}
1352
1353		public boolean equals(Object o) {
#	Line 1378 | Line 1355 | public class ReadMostlyVector<E>
1355		return true;
1356		if (!(o instanceof List))
1357		return false;
1358	<	return list.internalEquals((List<?>)(o), offset, offset + size);
1358	>	final StampedLock lock = list.lock;
1359	>	long stamp = lock.readLock();
1360	>	try {
1361	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1362	>	} finally {
1363	>	lock.unlockRead(stamp);
1364	>	}
1365		}
1366
1367		public E get(int index) {
#	Line 1388 | Line 1371 | public class ReadMostlyVector<E>
1371		}
1372
1373		public int hashCode() {
1374	<	return list.internalHashCode(offset, offset + size);
1374	>	final StampedLock lock = list.lock;
1375	>	long stamp = lock.readLock();
1376	>	try {
1377	>	return list.internalHashCode(offset, offset + size);
1378	>	} finally {
1379	>	lock.unlockRead(stamp);
1380	>	}
1381		}
1382
1383		public int indexOf(Object o) {
1384	<	final SequenceLock lock = list.lock;
1385	<	long seq = lock.awaitAvailability();
1397	<	Object[] items = list.array;
1398	<	int c = list.count;
1399	<	if (c <= items.length) {
1400	<	int idx = list.validatedIndexOf(o, items, offset,
1401	<	offset + size, seq);
1402	<	if (lock.getSequence() == seq)
1403	<	return idx < 0 ? -1 : idx - offset;
1404	<	}
1405	<	lock.lock();
1384	>	final StampedLock lock = list.lock;
1385	>	long stamp = lock.readLock();
1386		try {
1387	<	int idx = list.rawIndexOf(o, offset, offset + size);
1387	>	int idx = findFirstIndex(list.array, o, offset, offset + size);
1388		return idx < 0 ? -1 : idx - offset;
1389		} finally {
1390	<	lock.unlock();
1390	>	lock.unlockRead(stamp);
1391		}
1392		}
1393
1394		public boolean isEmpty() {
1395	<	return size == 0;
1395	>	return size() == 0;
1396		}
1397
1398		public Iterator<E> iterator() {
#	Line 1420 | Line 1400 | public class ReadMostlyVector<E>
1400		}
1401
1402		public int lastIndexOf(Object o) {
1403	<	final SequenceLock lock = list.lock;
1404	<	long seq = lock.awaitAvailability();
1425	<	Object[] items = list.array;
1426	<	int c = list.count;
1427	<	if (c <= items.length) {
1428	<	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1429	<	offset, seq);
1430	<	if (lock.getSequence() == seq)
1431	<	return idx < 0 ? -1 : idx - offset;
1432	<	}
1433	<	lock.lock();
1403	>	final StampedLock lock = list.lock;
1404	>	long stamp = lock.readLock();
1405		try {
1406	<	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1406	>	int idx = findLastIndex(list.array, o, offset + size - 1, offset);
1407		return idx < 0 ? -1 : idx - offset;
1408		} finally {
1409	<	lock.unlock();
1409	>	lock.unlockRead(stamp);
1410		}
1411		}
1412
#	Line 1448 | Line 1419 | public class ReadMostlyVector<E>
1419		}
1420
1421		public E remove(int index) {
1422	<	final SequenceLock lock = list.lock;
1423	<	lock.lock();
1422	>	final StampedLock lock = list.lock;
1423	>	long stamp = lock.writeLock();
1424		try {
1425		Object[] items = list.array;
1426		int i = index + offset;
1427	<	if (index < 0 || index >= size || i >= items.length)
1427	>	if (items == null || index < 0 || index >= size || i >= items.length)
1428		throw new ArrayIndexOutOfBoundsException(index);
1429	<	@SuppressWarnings("unchecked")
1459	<	E result = (E) items[i];
1429	>	@SuppressWarnings("unchecked") E result = (E)items[i];
1430		list.rawRemoveAt(i);
1431		size--;
1432		return result;
1433		} finally {
1434	<	lock.unlock();
1434	>	lock.unlockWrite(stamp);
1435		}
1436		}
1437
1438		public boolean remove(Object o) {
1439	<	final SequenceLock lock = list.lock;
1440	<	lock.lock();
1439	>	final StampedLock lock = list.lock;
1440	>	long stamp = lock.writeLock();
1441		try {
1442	<	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1443	<	offset + size))) {
1442	>	if (list.rawRemoveAt(findFirstIndex(list.array, o, offset,
1443	>	offset + size))) {
1444		--size;
1445		return true;
1446		}
1447		else
1448		return false;
1449		} finally {
1450	<	lock.unlock();
1450	>	lock.unlockWrite(stamp);
1451		}
1452		}
1453
1454		public boolean removeAll(Collection<?> c) {
1455	<	return list.internalRemoveAll(c, offset, offset + size);
1455	>	return list.lockedRemoveAll(c, offset, offset + size);
1456		}
1457
1458		public boolean retainAll(Collection<?> c) {
1459	<	return list.internalRetainAll(c, offset, offset + size);
1459	>	return list.lockedRetainAll(c, offset, offset + size);
1460		}
1461
1462		public E set(int index, E element) {
#	Line 1502 | Line 1472 | public class ReadMostlyVector<E>
1472		public List<E> subList(int fromIndex, int toIndex) {
1473		int c = size;
1474		int ssize = toIndex - fromIndex;
1475	<	if (fromIndex < 0 || toIndex > c || ssize < 0)
1476	<	throw new IndexOutOfBoundsException();
1475	>	if (fromIndex < 0)
1476	>	throw new ArrayIndexOutOfBoundsException(fromIndex);
1477	>	if (toIndex > c || ssize < 0)
1478	>	throw new ArrayIndexOutOfBoundsException(toIndex);
1479		return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1480		}
1481
1482		public Object[] toArray() {
1483	<	return list.internalToArray(offset, offset + size);
1483	>	final StampedLock lock = list.lock;
1484	>	long stamp = lock.readLock();
1485	>	try {
1486	>	return list.internalToArray(offset, offset + size);
1487	>	} finally {
1488	>	lock.unlockRead(stamp);
1489	>	}
1490		}
1491
1492		public <T> T[] toArray(T[] a) {
1493	<	return list.internalToArray(a, offset, offset + size);
1493	>	final StampedLock lock = list.lock;
1494	>	long stamp = lock.readLock();
1495	>	try {
1496	>	return list.internalToArray(a, offset, offset + size);
1497	>	} finally {
1498	>	lock.unlockRead(stamp);
1499	>	}
1500		}
1501
1502		public String toString() {
1503	<	return list.internalToString(offset, offset + size);
1503	>	final StampedLock lock = list.lock;
1504	>	long stamp = lock.readLock();
1505	>	try {
1506	>	return list.internalToString(offset, offset + size);
1507	>	} finally {
1508	>	lock.unlockRead(stamp);
1509	>	}
1510		}
1511
1512		}
#	Line 1524 | Line 1514 | public class ReadMostlyVector<E>
1514		static final class SubItr<E> implements ListIterator<E> {
1515		final ReadMostlyVectorSublist<E> sublist;
1516		final ReadMostlyVector<E> list;
1517	<	final SequenceLock lock;
1517	>	final StampedLock lock;
1518		Object[] items;
1529	–	E next, prev;
1519		long seq;
1520		int cursor;
1521	+	int origin;
1522		int fence;
1523		int lastRet;
1534	–	boolean validNext, validPrev;
1524
1525		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1526	<	this.sublist = sublist;
1527	<	this.list = sublist.list;
1528	<	this.lock = list.lock;
1529	<	this.cursor = index;
1530	<	this.lastRet = -1;
1531	<	refresh();
1532	<	if (index < 0 || index > fence)
1526	>	final StampedLock lock = sublist.list.lock;
1527	>	long stamp = lock.readLock();
1528	>	try {
1529	>	this.sublist = sublist;
1530	>	this.list = sublist.list;
1531	>	this.lock = lock;
1532	>	this.cursor = index;
1533	>	this.origin = sublist.offset;
1534	>	this.fence = origin + sublist.size;
1535	>	this.lastRet = -1;
1536	>	} finally {
1537	>	this.seq = lock.tryConvertToOptimisticRead(stamp);
1538	>	}
1539	>	if (index < 0 || cursor > fence)
1540		throw new ArrayIndexOutOfBoundsException(index);
1541		}
1542
1543	<	private void refresh() {
1544	<	validNext = validPrev = false;
1545	<	do {
1546	<	int n;
1547	<	seq = lock.awaitAvailability();
1548	<	items = list.array;
1553	<	if ((n = list.count) > items.length)
1554	<	continue;
1555	<	int b = sublist.offset + sublist.size;
1556	<	fence = b < n ? b : n;
1557	<	} while (lock.getSequence() != seq);
1543	>	public int nextIndex() {
1544	>	return cursor - origin;
1545	>	}
1546	>
1547	>	public int previousIndex() {
1548	>	return cursor - origin - 1;
1549		}
1550
1560	–	@SuppressWarnings("unchecked")
1551		public boolean hasNext() {
1552	<	boolean valid;
1563	<	int i = cursor;
1564	<	for (;;) {
1565	<	if (i >= fence || i < 0 || i >= items.length) {
1566	<	valid = false;
1567	<	break;
1568	<	}
1569	<	next = (E) items[i];
1570	<	if (lock.getSequence() == seq) {
1571	<	valid = true;
1572	<	break;
1573	<	}
1574	<	refresh();
1575	<	}
1576	<	return validNext = valid;
1552	>	return cursor < fence;
1553		}
1554
1579	–	@SuppressWarnings("unchecked")
1555		public boolean hasPrevious() {
1556	<	boolean valid;
1582	<	int i = cursor - 1;
1583	<	for (;;) {
1584	<	if (i >= fence || i < 0 || i >= items.length) {
1585	<	valid = false;
1586	<	break;
1587	<	}
1588	<	prev = (E) items[i];
1589	<	if (lock.getSequence() == seq) {
1590	<	valid = true;
1591	<	break;
1592	<	}
1593	<	refresh();
1594	<	}
1595	<	return validPrev = valid;
1556	>	return cursor > origin;
1557		}
1558
1559		public E next() {
1560	<	if (validNext || hasNext()) {
1561	<	validNext = false;
1562	<	lastRet = cursor++;
1563	<	return next;
1564	<	}
1565	<	throw new NoSuchElementException();
1560	>	int i = cursor;
1561	>	Object[] es = items;
1562	>	if (es == null || i < origin || i >= fence || i >= es.length)
1563	>	throw new NoSuchElementException();
1564	>	@SuppressWarnings("unchecked") E e = (E)es[i];
1565	>	lastRet = i;
1566	>	cursor = i + 1;
1567	>	if (!lock.validate(seq))
1568	>	throw new ConcurrentModificationException();
1569	>	return e;
1570		}
1571
1572		public E previous() {
1573	<	if (validPrev || hasPrevious()) {
1574	<	validPrev = false;
1575	<	lastRet = cursor--;
1576	<	return prev;
1577	<	}
1578	<	throw new NoSuchElementException();
1579	<	}
1580	<
1581	<	public int nextIndex() {
1582	<	return cursor - sublist.offset;
1618	<	}
1619	<
1620	<	public int previousIndex() {
1621	<	return cursor - 1 - sublist.offset;
1573	>	int i = cursor - 1;
1574	>	Object[] es = items;
1575	>	if (es == null || i < 0 || i >= fence || i >= es.length)
1576	>	throw new NoSuchElementException();
1577	>	@SuppressWarnings("unchecked") E e = (E)es[i];
1578	>	lastRet = i;
1579	>	cursor = i;
1580	>	if (!lock.validate(seq))
1581	>	throw new ConcurrentModificationException();
1582	>	return e;
1583		}
1584
1585		public void remove() {
1586		int i = lastRet;
1587		if (i < 0)
1588		throw new IllegalStateException();
1589	<	cursor = i;
1590	<	lastRet = -1;
1630	<	lock.lock();
1589	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1590	>	throw new ConcurrentModificationException();
1591		try {
1592	<	if (i < list.count) {
1593	<	list.remove(i);
1594	<	--sublist.size;
1595	<	}
1592	>	list.rawRemoveAt(i);
1593	>	fence = origin + sublist.size;
1594	>	cursor = i;
1595	>	lastRet = -1;
1596		} finally {
1597	<	lock.unlock();
1597	>	seq = lock.tryConvertToOptimisticRead(seq);
1598		}
1639	–	refresh();
1599		}
1600
1601		public void set(E e) {
1602		int i = lastRet;
1603	<	if (i < 0)
1603	>	if (i < origin || i >= fence)
1604		throw new IllegalStateException();
1605	<	lock.lock();
1605	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1606	>	throw new ConcurrentModificationException();
1607		try {
1608	<	if (i < list.count)
1649	<	list.set(i, e);
1608	>	list.set(i, e);
1609		} finally {
1610	<	lock.unlock();
1610	>	seq = lock.tryConvertToOptimisticRead(seq);
1611		}
1653	–	refresh();
1612		}
1613
1614		public void add(E e) {
1615		int i = cursor;
1616	<	if (i < 0)
1616	>	if (i < origin || i >= fence)
1617		throw new IllegalStateException();
1618	<	cursor = i + 1;
1619	<	lastRet = -1;
1662	<	lock.lock();
1618	>	if ((seq = lock.tryConvertToWriteLock(seq)) == 0)
1619	>	throw new ConcurrentModificationException();
1620		try {
1621	<	if (i <= list.count) {
1622	<	list.add(i, e);
1623	<	++sublist.size;
1624	<	}
1621	>	list.rawAddAt(i, e);
1622	>	items = list.array;
1623	>	fence = origin + sublist.size;
1624	>	cursor = i + 1;
1625	>	lastRet = -1;
1626		} finally {
1627	<	lock.unlock();
1627	>	seq = lock.tryConvertToOptimisticRead(seq);
1628		}
1671	–	refresh();
1629		}
1673	–
1630		}
1631		}
1676	–

Diff Legend

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