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.27 by dl, Mon Aug 13 11:20:39 2012 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		/**
#	Line 63 | Line 63 | public class ReadMostlyVector<E>
63		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
64
65		// fields are non-private to simplify nested class access
66	<	volatile Object[] array;
67	<	final SequenceLock lock;
68	<	volatile int count;
66	>	Object[] array;
67	>	final StampedLock lock;
68	>	int count;
69		final int capacityIncrement;
70
71		/**
#	Line 86 | 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		/**
#	Line 101 | Line 101 | public class ReadMostlyVector<E>
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 123 | Line 124 | public class ReadMostlyVector<E>
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 131 | Line 132 | public class ReadMostlyVector<E>
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 Object[] grow(int minCapacity) {
142	<	int oldCapacity = array.length;
143	<	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
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	<	return 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 160 | Line 169 | public class ReadMostlyVector<E>
169		* as well as sublist and iterator classes.
170		*/
171
172	<	/**
173	<	* Version of indexOf that returns -1 if either not present or invalid.
174	<	*
175	<	* @throws ArrayIndexOutOfBoundsException if index is negative
176	<	*/
177	<	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
178	<	long seq) {
179	<	for (int i = index; i < fence; ++i) {
180	<	Object e = items[i];
181	<	if (lock.getSequence() != seq)
173	<	break;
174	<	if ((x == null) ? e == null : x.equals(e))
175	<	return i;
176	<	}
177	<	return -1;
178	<	}
179	<
180	<	/**
181	<	* @throws ArrayIndexOutOfBoundsException if index is negative
182	<	*/
183	<	final int rawIndexOf(Object x, int index, int fence) {
184	<	Object[] items = array;
185	<	for (int i = index; i < fence; ++i) {
186	<	Object e = items[i];
187	<	if ((x == null) ? e == null : x.equals(e))
188	<	return i;
189	<	}
190	<	return -1;
191	<	}
192	<
193	<	final int validatedLastIndexOf(Object x, Object[] items,
194	<	int index, int origin, long seq) {
195	<	for (int i = index; i >= origin; --i) {
196	<	Object e = items[i];
197	<	if (lock.getSequence() != seq)
198	<	break;
199	<	if ((x == null) ? e == null : x.equals(e))
200	<	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	<	final int rawLastIndexOf(Object x, int index, int origin) {
187	<	Object[] items = array;
188	<	for (int i = index; i >= origin; --i) {
189	<	Object e = items[i];
190	<	if ((x == null) ? e == null : x.equals(e))
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		}
#	Line 215 | Line 200 | public class ReadMostlyVector<E>
200		final void rawAdd(E e) {
201		int n = count;
202		Object[] items = array;
203	<	if (n >= items.length)
203	>	if (items == null || n >= items.length)
204		items = grow(n + 1);
205		items[n] = e;
206		count = n + 1;
#	Line 226 | Line 211 | public class ReadMostlyVector<E>
211		Object[] items = array;
212		if (index > n)
213		throw new ArrayIndexOutOfBoundsException(index);
214	<	if (n >= items.length)
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);
#	Line 243 | Line 228 | public class ReadMostlyVector<E>
228		if (len == 0)
229		return false;
230		int newCount = n + len;
231	<	if (newCount >= items.length)
231	>	if (items == null || newCount >= items.length)
232		items = grow(newCount);
233		int mv = n - index;
234		if (mv > 0)
#	Line 256 | Line 241 | public class ReadMostlyVector<E>
241		final boolean rawRemoveAt(int index) {
242		int n = count - 1;
243		Object[] items = array;
244	<	if (index < 0 || index > n)
244	>	if (items == null || index < 0 || index > n)
245		return false;
246		int mv = n - index;
247		if (mv > 0)
#	Line 273 | Line 258 | public class ReadMostlyVector<E>
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 bound) {
277	<	final 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 n = count;
267		int fence = bound < 0 || bound > n ? n : bound;
268		if (origin >= 0 && origin < fence) {
269		for (Object x : c) {
270	<	while (rawRemoveAt(rawIndexOf(x, 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 bound) {
281	<	final 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	<	Object[] items = array;
287	<	int i = origin;
288	<	int n = count;
289	<	int fence = bound < 0 || bound > n ? n : bound;
290	<	while (i >= 0 && 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);
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		}
314	–	}
315	–	if (count != n) {
316	–	count = n;
317	–	removed = true;
305		}
306		} finally {
307	<	lock.unlock();
307	>	lock.unlockWrite(stamp);
308		}
309		}
310		return removed;
311		}
312
313		final void internalClear(int origin, int bound) {
314	<	int n = count;
315	<	int fence = bound < 0 || bound > n ? n : bound;
316	<	if (origin >= 0 && origin < fence) {
317	<	Object[] items = array;
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 = n - removed;
324		int mv = n - (origin + removed);
#	Line 340 | Line 331 | public class ReadMostlyVector<E>
331		}
332
333		final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
334	<	final SequenceLock lock = this.lock;
335	<	boolean contained;
336	<	boolean locked = false;
337	<	try {
338	<	for (;;) {
339	<	long seq = lock.awaitAvailability();
340	<	int n = count;
341	<	Object[] items = array;
342	<	int len = items.length;
343	<	if (n > len)
344	<	continue;
354	<	int fence = bound < 0 || bound > n ? n : bound;
355	<	if (origin < 0)
356	<	contained = false;
357	<	else {
358	<	contained = true;
359	<	for (Object e : c) {
360	<	int idx = (locked ?
361	<	rawIndexOf(e, origin, fence) :
362	<	validatedIndexOf(e, items, origin,
363	<	fence, seq));
364	<	if (idx < 0) {
365	<	contained = false;
366	<	break;
367	<	}
368	<	}
369	<	}
370	<	if (lock.getSequence() == seq)
371	<	break;
372	<	lock.lock();
373	<	locked = true;
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		}
375	–	} finally {
376	–	if (locked)
377	–	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 bound) {
353	<	final SequenceLock lock = this.lock;
354	<	boolean locked = false;
355	<	boolean equal;
356	<	try {
357	<	for (;;) {
358	<	long seq = lock.awaitAvailability();
359	<	Object[] items = array;
360	<	int n = count;
361	<	if (n > items.length || origin < 0)
362	<	equal = false;
363	<	else {
364	<	equal = true;
365	<	int fence = bound < 0 || bound > n ? n : bound;
366	<	Iterator<?> it = list.iterator();
367	<	for (int i = origin; i < fence; ++i) {
368	<	Object x = items[i];
399	<	Object y;
400	<	if ((!locked && lock.getSequence() != seq) ||
401	<	!it.hasNext() ||
402	<	(y = it.next()) == null ?
403	<	x != null : !y.equals(x)) {
404	<	equal = false;
405	<	break;
406	<	}
407	<	}
408	<	if (equal && it.hasNext())
409	<	equal = false;
410	<	}
411	<	if (lock.getSequence() == seq)
412	<	break;
413	<	lock.lock();
414	<	locked = true;
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)
418	<	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 bound) {
379	<	final 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 n = count;
388	<	int len = items.length;
389	<	if (n > len)
390	<	continue;
436	<	int fence = bound < 0 || bound > n ? n : bound;
437	<	if (origin >= 0) {
438	<	for (int i = origin; i < fence; ++i) {
439	<	Object e = items[i];
440	<	hash = 31*hash + (e == null ? 0 : e.hashCode());
441	<	}
442	<	}
443	<	if (lock.getSequence() == seq)
444	<	break;
445	<	lock.lock();
446	<	locked = true;
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		}
448	–	} finally {
449	–	if (locked)
450	–	lock.unlock();
392		}
393		return hash;
394		}
395
396		final String internalToString(int origin, int bound) {
397	<	final SequenceLock lock = this.lock;
398	<	String ret;
399	<	boolean locked = false;
400	<	try {
401	<	outer:for (;;) {
402	<	long seq = lock.awaitAvailability();
403	<	Object[] items = array;
404	<	int n = count;
405	<	int len = items.length;
406	<	if (n > len)
407	<	continue;
408	<	int fence = bound < 0 || bound > n ? n : bound;
409	<	if (origin < 0 || origin == fence)
410	<	ret = "[]";
411	<	else {
412	<	StringBuilder sb = new StringBuilder();
413	<	sb.append('[');
473	<	for (int i = origin;;) {
474	<	Object e = items[i];
475	<	if (e == this)
476	<	sb.append("(this Collection)");
477	<	else if (!locked && lock.getSequence() != seq)
478	<	continue outer;
479	<	else
480	<	sb.append(e.toString());
481	<	if (++i < fence)
482	<	sb.append(',').append(' ');
483	<	else {
484	<	ret = sb.append(']').toString();
485	<	break;
486	<	}
487	<	}
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		}
489	–	if (lock.getSequence() == seq)
490	–	break;
491	–	lock.lock();
492	–	locked = true;
415		}
494	–	} finally {
495	–	if (locked)
496	–	lock.unlock();
416		}
417	<	return ret;
417	>	return "[]";
418		}
419
420		final Object[] internalToArray(int origin, int bound) {
421	<	Object[] result;
422	<	final SequenceLock lock = this.lock;
423	<	boolean locked = false;
424	<	try {
425	<	for (;;) {
426	<	result = null;
427	<	long seq = lock.awaitAvailability();
428	<	Object[] items = array;
429	<	int n = count;
430	<	int len = items.length;
431	<	if (n > len)
513	<	continue;
514	<	int fence = bound < 0 || bound > n ? n : bound;
515	<	if (origin >= 0)
516	<	result = Arrays.copyOfRange(items, origin, fence,
517	<	Object[].class);
518	<	if (lock.getSequence() == seq)
519	<	break;
520	<	lock.lock();
521	<	locked = true;
522	<	}
523	<	} finally {
524	<	if (locked)
525	<	lock.unlock();
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 result;
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	<	T[] result;
440	<	final SequenceLock lock = this.lock;
441	<	boolean locked = false;
442	<	try {
443	<	for (;;) {
444	<	long seq = lock.awaitAvailability();
445	<	Object[] items = array;
446	<	int n = count;
447	<	int len = items.length;
448	<	if (n > len)
449	<	continue;
450	<	int fence = bound < 0 || bound > n ? n : bound;
451	<	int rlen = fence - origin;
546	<	if (rlen < 0)
547	<	rlen = 0;
548	<	if (origin < 0 || alen >= rlen) {
549	<	if (rlen > 0)
550	<	System.arraycopy(items, 0, a, origin, rlen);
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	<	result = a;
454	>	return a;
455		}
456	<	else
556	<	result = (T[]) Arrays.copyOfRange(items, origin,
557	<	fence, a.getClass());
558	<	if (lock.getSequence() == seq)
559	<	break;
560	<	lock.lock();
561	<	locked = true;
456	>	return (T[]) Arrays.copyOfRange(items, i, fence, a.getClass());
457		}
563	–	} finally {
564	–	if (locked)
565	–	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	<	final SequenceLock lock = this.lock;
468	<	lock.lock();
467	>	final StampedLock lock = this.lock;
468	>	long stamp = lock.writeLock();
469		try {
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	<	final SequenceLock lock = this.lock;
479	<	lock.lock();
478	>	final StampedLock lock = this.lock;
479	>	long stamp = lock.writeLock();
480		try {
481		rawAddAt(index, element);
482		} finally {
483	<	lock.unlock();
483	>	lock.unlockWrite(stamp);
484		}
485		}
486
#	Line 595 | Line 489 | public class ReadMostlyVector<E>
489		int len = elements.length;
490		if (len == 0)
491		return false;
492	<	final SequenceLock lock = this.lock;
493	<	lock.lock();
492	>	final StampedLock lock = this.lock;
493	>	long stamp = lock.writeLock();
494		try {
495		Object[] items = array;
496		int n = count;
497		int newCount = n + len;
498	<	if (newCount >= items.length)
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) {
615	–	final SequenceLock lock = this.lock;
616	–	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 = rawAddAllAt(index, elements);
515		} finally {
516	<	lock.unlock();
516	>	lock.unlockWrite(stamp);
517		}
518		return ret;
519		}
520
521		public void clear() {
522	<	final SequenceLock lock = this.lock;
523	<	lock.lock();
522	>	final StampedLock lock = this.lock;
523	>	long stamp = lock.writeLock();
524		try {
525		int n = count;
526		Object[] items = array;
527	<	for (int i = 0; i < n; i++)
528	<	items[i] = null;
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 643 | Line 539 | public class ReadMostlyVector<E>
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 651 | Line 555 | public class ReadMostlyVector<E>
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	<	final SequenceLock lock = this.lock;
569	<	for (;;) {
570	<	long seq = lock.awaitAvailability();
571	<	int n = count;
572	<	Object[] items = array;
573	<	@SuppressWarnings("unchecked")
574	<	E e = (index < items.length) ? (E) items[index] : null;
665	<	if (lock.getSequence() == seq) {
666	<	if (index >= n)
667	<	throw new ArrayIndexOutOfBoundsException(index);
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;
669	–	}
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	+	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	+
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	<	return indexOf(o, 0);
613	>	int idx;
614	>	final StampedLock lock = this.lock;
615	>	long stamp = lock.readLock();
616	>	try {
617	>	idx = findFirstIndex(array, o, 0, count);
618	>	} finally {
619	>	lock.unlockRead(stamp);
620	>	}
621	>	return idx;
622		}
623
624		public boolean isEmpty() {
625	<	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() {
#	Line 687 | Line 632 | public class ReadMostlyVector<E>
632		}
633
634		public int lastIndexOf(Object o) {
635	<	final SequenceLock lock = this.lock;
636	<	for (;;) {
637	<	long seq = lock.awaitAvailability();
638	<	Object[] items = array;
639	<	int n = count;
640	<	if (n <= items.length) {
641	<	for (int i = n - 1; i >= 0; --i) {
697	<	Object e = items[i];
698	<	if (lock.getSequence() != seq) {
699	<	lock.lock();
700	<	try {
701	<	return rawLastIndexOf(o, count - 1, 0);
702	<	} finally {
703	<	lock.unlock();
704	<	}
705	<	}
706	<	else if ((o == null) ? e == null : o.equals(e))
707	<	return i;
708	<	}
709	<	return -1;
710	<	}
635	>	int idx;
636	>	final StampedLock lock = this.lock;
637	>	long stamp = lock.readLock();
638	>	try {
639	>	idx = findLastIndex(array, o, count - 1, 0);
640	>	} finally {
641	>	lock.unlockRead(stamp);
642		}
643	+	return idx;
644		}
645
646		public ListIterator<E> listIterator() {
#	Line 719 | Line 651 | public class ReadMostlyVector<E>
651		return new Itr<E>(this, index);
652		}
653
654	<	public E remove(int index) {
655	<	final SequenceLock lock = this.lock;
656	<	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	<	@SuppressWarnings("unchecked")
663	<	E oldValue = (E) array[index];
664	<	rawRemoveAt(index);
665	<	return oldValue;
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	<	final SequenceLock lock = this.lock;
676	<	lock.lock();
675	>	final StampedLock lock = this.lock;
676	>	long stamp = lock.writeLock();
677		try {
678	<	return rawRemoveAt(rawIndexOf(o, 0, count));
678	>	return rawRemoveAt(findFirstIndex(array, o, 0, count));
679		} finally {
680	<	lock.unlock();
680	>	lock.unlockWrite(stamp);
681		}
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	<	final SequenceLock lock = this.lock;
694	<	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		Object[] items = array;
699	<	if (index < 0 || index >= count)
700	<	throw new ArrayIndexOutOfBoundsException(index);
701	<	@SuppressWarnings("unchecked")
702	<	E oldValue = (E) items[index];
703	<	items[index] = element;
704	<	return oldValue;
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	<	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) {
776	–	int c = size();
732		int ssize = toIndex - fromIndex;
733	<	if (fromIndex < 0 || toIndex > c || ssize < 0)
734	<	throw new IndexOutOfBoundsException();
735	<	return new ReadMostlyVectorSublist<E>(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
#	Line 801 | Line 786 | public class ReadMostlyVector<E>
786		* @return {@code true} if the element was added
787		*/
788		public boolean addIfAbsent(E e) {
789	<	final SequenceLock lock = this.lock;
790	<	lock.lock();
789	>	boolean ret;
790	>	final StampedLock lock = this.lock;
791	>	long stamp = lock.writeLock();
792		try {
793	<	if (rawIndexOf(e, 0, count) < 0) {
793	>	if (findFirstIndex(array, e, 0, count) < 0) {
794		rawAdd(e);
795	<	return true;
795	>	ret = true;
796		}
797		else
798	<	return false;
798	>	ret = false;
799		} finally {
800	<	lock.unlock();
800	>	lock.unlockWrite(stamp);
801		}
802	+	return ret;
803		}
804
805		/**
#	Line 831 | Line 818 | public class ReadMostlyVector<E>
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		@SuppressWarnings("unchecked")
825		E e = (E) cs[i];
826	<	if (rawIndexOf(e, 0, count) < 0) {
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;
#	Line 865 | Line 852 | public class ReadMostlyVector<E>
852		private int cursor;
853		SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
854		public boolean hasNext() { return cursor < items.length; }
855	<	@SuppressWarnings("unchecked")
869	<	public E next() {
855	>	@SuppressWarnings("unchecked") public E next() {
856		if (cursor < items.length)
857		return (E) items[cursor++];
858		throw new NoSuchElementException();
#	Line 874 | Line 860 | public class ReadMostlyVector<E>
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	<	final SequenceLock lock = this.lock;
889	<	for (;;) {
890	<	long seq = lock.awaitAvailability();
891	<	Object[] items = array;
892	<	int n = count;
893	<	@SuppressWarnings("unchecked")
887	<	E e = (items.length > 0) ? (E) items[0] : null;
888	<	if (lock.getSequence() == seq) {
889	<	if (n <= 0)
890	<	throw new NoSuchElementException();
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;
892	–	}
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	+	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	<	final SequenceLock lock = this.lock;
921	<	for (;;) {
922	<	long seq = lock.awaitAvailability();
923	<	Object[] items = array;
924	<	int n = count;
925	<	@SuppressWarnings("unchecked")
926	<	E e = (n > 0 && items.length >= n) ? (E) items[n - 1] : null;
927	<	if (lock.getSequence() == seq) {
906	<	if (n <= 0)
907	<	throw new NoSuchElementException();
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;
909	–	}
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 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	<	final SequenceLock lock = this.lock;
956	<	long seq = lock.awaitAvailability();
957	<	Object[] items = array;
958	<	int n = count;
959	<	int idx = -1;
960	<	if (n <= items.length)
961	<	idx = validatedIndexOf(o, items, index, n, seq);
962	<	if (lock.getSequence() != seq) {
963	<	lock.lock();
924	<	try {
925	<	idx = rawIndexOf(o, index, count);
926	<	} finally {
927	<	lock.unlock();
928	<	}
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		}
930	–	// Above code will throw AIOOBE when index < 0
965		return idx;
966		}
967
968		/** See {@link Vector#lastIndexOf(Object, int)} */
969		public int lastIndexOf(Object o, int index) {
970	<	final SequenceLock lock = this.lock;
937	<	long seq = lock.awaitAvailability();
938	<	Object[] items = array;
939	<	int n = count;
970	>	boolean oobe = false;
971		int idx = -1;
972	<	if (index < Math.min(n, items.length))
973	<	idx = validatedLastIndexOf(o, items, index, 0, seq);
974	<	if (lock.getSequence() != seq) {
975	<	lock.lock();
976	<	try {
977	<	n = count;
978	<	if (index < n)
979	<	idx = rawLastIndexOf(o, index, 0);
980	<	} finally {
950	<	lock.unlock();
951	<	}
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 (index >= n)
983	<	throw new IndexOutOfBoundsException(index + " >= " + n);
982	>	if (oobe)
983	>	throw new ArrayIndexOutOfBoundsException(index);
984		return idx;
985		}
986
#	Line 959 | Line 988 | public class ReadMostlyVector<E>
988		public void setSize(int newSize) {
989		if (newSize < 0)
990		throw new ArrayIndexOutOfBoundsException(newSize);
991	<	final SequenceLock lock = this.lock;
992	<	lock.lock();
991	>	final StampedLock lock = this.lock;
992	>	long stamp = lock.writeLock();
993		try {
994	+	Object[] items;
995		int n = count;
996		if (newSize > n)
997		grow(newSize);
998	<	else {
969	<	Object[] items = array;
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	<	final 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	<	final SequenceLock lock = this.lock;
1024	<	lock.lock();
1023	>	final StampedLock lock = this.lock;
1024	>	long stamp = lock.writeLock();
1025		try {
1026		Object[] items = array;
1027		int n = count;
1028	<	if (n < items.length)
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	<	final 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		}
#	Line 1063 | Line 1096 | public class ReadMostlyVector<E>
1096		// other methods
1097
1098		public ReadMostlyVector<E> clone() {
1066	–	final SequenceLock lock = this.lock;
1099		Object[] a = null;
1100	<	boolean retry = false;
1101	<	long seq = lock.awaitAvailability();
1102	<	Object[] items = array;
1103	<	int n = count;
1104	<	if (n <= items.length)
1105	<	a = Arrays.copyOf(items, n);
1106	<	else
1107	<	retry = true;
1108	<	if (retry || lock.getSequence() != seq) {
1109	<	lock.lock();
1110	<	try {
1111	<	n = count;
1080	<	a = Arrays.copyOf(array, n);
1081	<	} finally {
1082	<	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<E>(a, n, capacityIncrement);
1117		}
1118
1119		private void writeObject(java.io.ObjectOutputStream s)
1120	<	throws java.io.IOException {
1121	<	final 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> {
1131	+	final StampedLock lock;
1132		final ReadMostlyVector<E> list;
1101	–	final SequenceLock lock;
1133		Object[] items;
1103	–	E next, prev;
1134		long seq;
1135		int cursor;
1136		int fence;
1137		int lastRet;
1108	–	boolean validNext, validPrev;
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	<	validNext = validPrev = false;
1122	<	do {
1123	<	seq = lock.awaitAvailability();
1124	<	items = list.array;
1125	<	} while ((fence = list.count) > items.length ||
1126	<	lock.getSequence() != seq);
1156	>	public boolean hasPrevious() {
1157	>	return cursor > 0;
1158		}
1159
1160	<	@SuppressWarnings("unchecked")
1161	<	public boolean hasNext() {
1131	<	boolean valid;
1132	<	int i = cursor;
1133	<	for (;;) {
1134	<	if (i >= fence || i < 0 || i >= items.length) {
1135	<	valid = false;
1136	<	break;
1137	<	}
1138	<	next = (E) items[i];
1139	<	if (lock.getSequence() == seq) {
1140	<	valid = true;
1141	<	break;
1142	<	}
1143	<	refresh();
1144	<	}
1145	<	return validNext = valid;
1160	>	public int nextIndex() {
1161	>	return cursor;
1162		}
1163
1164	<	@SuppressWarnings("unchecked")
1165	<	public boolean hasPrevious() {
1166	<	boolean valid;
1167	<	int i = cursor - 1;
1168	<	for (;;) {
1169	<	if (i >= fence || i < 0 || i >= items.length) {
1154	<	valid = false;
1155	<	break;
1156	<	}
1157	<	prev = (E) items[i];
1158	<	if (lock.getSequence() == seq) {
1159	<	valid = true;
1160	<	break;
1161	<	}
1162	<	refresh();
1163	<	}
1164	<	return validPrev = valid;
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 (validNext || hasNext()) {
1174	<	validNext = validPrev = false;
1175	<	lastRet = cursor++;
1176	<	return next;
1177	<	}
1178	<	throw new NoSuchElementException();
1173	>	int i = cursor;
1174	>	Object[] es = items;
1175	>	if (es == null || i < 0 || i >= fence || i >= es.length)
1176	>	throw new NoSuchElementException();
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 (validPrev || hasPrevious()) {
1187	<	validNext = validPrev = false;
1188	<	lastRet = cursor--;
1189	<	return prev;
1190	<	}
1191	<	throw new NoSuchElementException();
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	>	@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		}
1196	–	cursor = i;
1197	–	lastRet = -1;
1198	–	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)
1208	<	list.set(i, e);
1222	>	es[i] = e;
1223		} finally {
1224	<	lock.unlock();
1224	>	seq = lock.tryConvertToOptimisticRead(seq);
1225		}
1212	–	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		}
1226	–	cursor = i + 1;
1227	–	lastRet = -1;
1228	–	refresh();
1243		}
1244
1245		public boolean hasMoreElements() { return hasNext(); }
1246		public E nextElement() { return next(); }
1233	–	public int nextIndex() { return cursor; }
1234	–	public int previousIndex() { return cursor - 1; }
1247		}
1248
1249		static final class ReadMostlyVectorSublist<E>
#	Line 1255 | Line 1267 | public class ReadMostlyVector<E>
1267		}
1268
1269		public boolean add(E element) {
1270	<	final 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.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	<	final 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.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	<	final SequenceLock lock = list.lock;
1298	<	lock.lock();
1297	>	final StampedLock lock = list.lock;
1298	>	long stamp = lock.writeLock();
1299		try {
1300		int s = size;
1301		int pc = list.count;
#	Line 1292 | Line 1304 | public class ReadMostlyVector<E>
1304		size = s + added;
1305		return added != 0;
1306		} finally {
1307	<	lock.unlock();
1307	>	lock.unlockWrite(stamp);
1308		}
1309		}
1310
1311		public boolean addAll(int index, Collection<? extends E> c) {
1312		Object[] elements = c.toArray();
1313	<	final SequenceLock lock = list.lock;
1314	<	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)
#	Line 1310 | Line 1322 | public class ReadMostlyVector<E>
1322		size = s + added;
1323		return added != 0;
1324		} finally {
1325	<	lock.unlock();
1325	>	lock.unlockWrite(stamp);
1326		}
1327		}
1328
1329		public void clear() {
1330	<	final SequenceLock lock = list.lock;
1331	<	lock.lock();
1330	>	final StampedLock lock = list.lock;
1331	>	long stamp = lock.writeLock();
1332		try {
1333		list.internalClear(offset, offset + size);
1334		size = 0;
1335		} finally {
1336	<	lock.unlock();
1336	>	lock.unlockWrite(stamp);
1337		}
1338		}
1339
#	Line 1330 | Line 1342 | public class ReadMostlyVector<E>
1342		}
1343
1344		public boolean containsAll(Collection<?> c) {
1345	<	return list.internalContainsAll(c, offset, 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 1338 | Line 1356 | public class ReadMostlyVector<E>
1356		return true;
1357		if (!(o instanceof List))
1358		return false;
1359	<	return list.internalEquals((List<?>)(o), offset, 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 1348 | Line 1372 | public class ReadMostlyVector<E>
1372		}
1373
1374		public int hashCode() {
1375	<	return list.internalHashCode(offset, 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	<	final SequenceLock lock = list.lock;
1386	<	long seq = lock.awaitAvailability();
1357	<	Object[] items = list.array;
1358	<	int c = list.count;
1359	<	if (c <= items.length) {
1360	<	int idx = list.validatedIndexOf(o, items, offset,
1361	<	offset + size, seq);
1362	<	if (lock.getSequence() == seq)
1363	<	return idx < 0 ? -1 : idx - offset;
1364	<	}
1365	<	lock.lock();
1385	>	final StampedLock lock = list.lock;
1386	>	long stamp = lock.readLock();
1387		try {
1388	<	int idx = list.rawIndexOf(o, 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() {
#	Line 1380 | Line 1401 | public class ReadMostlyVector<E>
1401		}
1402
1403		public int lastIndexOf(Object o) {
1404	<	final SequenceLock lock = list.lock;
1405	<	long seq = lock.awaitAvailability();
1385	<	Object[] items = list.array;
1386	<	int c = list.count;
1387	<	if (c <= items.length) {
1388	<	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1389	<	offset, seq);
1390	<	if (lock.getSequence() == seq)
1391	<	return idx < 0 ? -1 : idx - offset;
1392	<	}
1393	<	lock.lock();
1404	>	final StampedLock lock = list.lock;
1405	>	long stamp = lock.readLock();
1406		try {
1407	<	int idx = list.rawLastIndexOf(o, offset + size - 1, 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
#	Line 1408 | Line 1420 | public class ReadMostlyVector<E>
1420		}
1421
1422		public E remove(int index) {
1423	<	final SequenceLock lock = list.lock;
1424	<	lock.lock();
1423	>	final StampedLock lock = list.lock;
1424	>	long stamp = lock.writeLock();
1425		try {
1426		Object[] items = list.array;
1427		int i = index + offset;
1428	<	if (index < 0 || index >= size || i >= items.length)
1428	>	if (items == null || index < 0 || index >= size || i >= items.length)
1429		throw new ArrayIndexOutOfBoundsException(index);
1430	<	@SuppressWarnings("unchecked")
1419	<	E result = (E) items[i];
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		}
1437		}
1438
1439		public boolean remove(Object o) {
1440	<	final SequenceLock lock = list.lock;
1441	<	lock.lock();
1440	>	final StampedLock lock = list.lock;
1441	>	long stamp = lock.writeLock();
1442		try {
1443	<	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1444	<	offset + size))) {
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		}
1453		}
1454
1455		public boolean removeAll(Collection<?> c) {
1456	<	return list.internalRemoveAll(c, offset, offset + size);
1456	>	return list.lockedRemoveAll(c, offset, offset + size);
1457		}
1458
1459		public boolean retainAll(Collection<?> c) {
1460	<	return list.internalRetainAll(c, offset, offset + size);
1460	>	return list.lockedRetainAll(c, offset, offset + size);
1461		}
1462
1463		public E set(int index, E element) {
#	Line 1462 | Line 1473 | public class ReadMostlyVector<E>
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();
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, 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, 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, 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 1484 | Line 1515 | public class ReadMostlyVector<E>
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;
1489	–	E next, prev;
1520		long seq;
1521		int cursor;
1522	+	int origin;
1523		int fence;
1524		int lastRet;
1494	–	boolean validNext, validPrev;
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	<	validNext = validPrev = false;
1546	<	do {
1547	<	int n;
1548	<	seq = lock.awaitAvailability();
1549	<	items = list.array;
1513	<	if ((n = list.count) > items.length)
1514	<	continue;
1515	<	int b = sublist.offset + sublist.size;
1516	<	fence = b < n ? b : n;
1517	<	} 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
1520	–	@SuppressWarnings("unchecked")
1552		public boolean hasNext() {
1553	<	boolean valid;
1523	<	int i = cursor;
1524	<	for (;;) {
1525	<	if (i >= fence || i < 0 || i >= items.length) {
1526	<	valid = false;
1527	<	break;
1528	<	}
1529	<	next = (E) items[i];
1530	<	if (lock.getSequence() == seq) {
1531	<	valid = true;
1532	<	break;
1533	<	}
1534	<	refresh();
1535	<	}
1536	<	return validNext = valid;
1553	>	return cursor < fence;
1554		}
1555
1539	–	@SuppressWarnings("unchecked")
1556		public boolean hasPrevious() {
1557	<	boolean valid;
1542	<	int i = cursor - 1;
1543	<	for (;;) {
1544	<	if (i >= fence || i < 0 || i >= items.length) {
1545	<	valid = false;
1546	<	break;
1547	<	}
1548	<	prev = (E) items[i];
1549	<	if (lock.getSequence() == seq) {
1550	<	valid = true;
1551	<	break;
1552	<	}
1553	<	refresh();
1554	<	}
1555	<	return validPrev = valid;
1557	>	return cursor > origin;
1558		}
1559
1560		public E next() {
1561	<	if (validNext || hasNext()) {
1562	<	validNext = validPrev = false;
1563	<	lastRet = cursor++;
1564	<	return next;
1565	<	}
1566	<	throw new NoSuchElementException();
1561	>	int i = cursor;
1562	>	Object[] es = items;
1563	>	if (es == null || i < origin || i >= fence || i >= es.length)
1564	>	throw new NoSuchElementException();
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 (validPrev || hasPrevious()) {
1575	<	validNext = validPrev = false;
1576	<	lastRet = cursor--;
1577	<	return prev;
1578	<	}
1579	<	throw new NoSuchElementException();
1580	<	}
1581	<
1582	<	public int nextIndex() {
1583	<	return cursor - sublist.offset;
1578	<	}
1579	<
1580	<	public int previousIndex() {
1581	<	return cursor - 1 - sublist.offset;
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	>	@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;
1590	<	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		}
1599	–	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)
1609	<	list.set(i, e);
1609	>	list.set(i, e);
1610		} finally {
1611	<	lock.unlock();
1611	>	seq = lock.tryConvertToOptimisticRead(seq);
1612		}
1613	–	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;
1622	<	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		}
1631	–	refresh();
1630		}
1633	–
1631		}
1632		}

Diff Legend

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