ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/extra/ReadMostlyVector.java

Comparing jsr166/src/jsr166e/extra/ReadMostlyVector.java (file contents):
Revision 1.1 by dl, Fri Jul 15 23:56:18 2011 UTC vs.
Revision 1.28 by dl, Fri Oct 12 14:09:35 2012 UTC

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

Diff Legend

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