--- jsr166/src/jsr166e/extra/ReadMostlyVector.java 2011/07/16 13:20:35 1.2
+++ jsr166/src/jsr166e/extra/ReadMostlyVector.java 2011/07/16 16:05:32 1.5
@@ -12,14 +12,17 @@ import java.util.*;
* A class with the same methods and array-based characteristics as
* {@link java.util.Vector} but with reduced contention and improved
* throughput when invocations of read-only methods by multiple
- * threads are most common.
+ * threads are most common.
*
*
The iterators returned by this class's {@link #iterator()
* iterator} and {@link #listIterator(int) listIterator} methods are
* best-effort in the presence of concurrent modifications, and do
* NOT throw {@link ConcurrentModificationException}. An
* iterator's {@code next()} method returns consecutive elements as
- * they appear in the underlying array upon each access.
+ * they appear in the underlying array upon each access. Alternatvely,
+ * method {@link #snapshotIterator} may be used for deterministic
+ * traversals, at the expense of making a copy, and unavailability of
+ * method {@code Iterator.remove}.
*
*
Otherwise, this class supports all methods, under the same
* documented specifications, as {@code Vector}. Consult {@link
@@ -40,7 +43,7 @@ public class ReadMostlyVector impleme
* Short methods,including get(index), continually retry obtaining
* a snapshot of array, count, and element, using sequence number
* to validate.
- *
+ *
* Methods that are potentially O(n) (or worse) try once in
* read-only mode, and then lock. When in read-only mode, they
* validate only at the end of an array scan unless the element is
@@ -151,13 +154,14 @@ public class ReadMostlyVector impleme
* as well as sublist and iterator classes.
*/
- final int validatedIndexOf(Object x, Object[] items, int index, int fence,
+ // Version of indexOf that returns -1 if either not present or invalid
+ final int validatedIndexOf(Object x, Object[] items, int index, int fence,
long seq) {
for (int i = index; i < fence; ++i) {
Object e = items[i];
if (lock.getSequence() != seq)
break;
- if (x == null? e == null : (e != null && x.equals(e)))
+ if (x == null? e == null : x.equals(e))
return i;
}
return -1;
@@ -167,19 +171,19 @@ public class ReadMostlyVector impleme
Object[] items = array;
for (int i = index; i < fence; ++i) {
Object e = items[i];
- if (x == null? e == null : (e != null && x.equals(e)))
+ if (x == null? e == null : x.equals(e))
return i;
}
return -1;
}
- final int validatedLastIndexOf(Object x, Object[] items,
+ final int validatedLastIndexOf(Object x, Object[] items,
int index, int origin, long seq) {
for (int i = index; i >= origin; --i) {
Object e = items[i];
if (lock.getSequence() != seq)
break;
- if (x == null? e == null : (e != null && x.equals(e)))
+ if (x == null? e == null : x.equals(e))
return i;
}
return -1;
@@ -189,13 +193,13 @@ public class ReadMostlyVector impleme
Object[] items = array;
for (int i = index; i >= origin; --i) {
Object e = items[i];
- if (x == null? e == null : (e != null && x.equals(e)))
+ if (x == null? e == null : x.equals(e))
return i;
}
return -1;
}
- final void internalAdd(Object e) {
+ final void rawAdd(Object e) {
int n = count;
if (n >= array.length)
grow(n + 1);
@@ -203,7 +207,7 @@ public class ReadMostlyVector impleme
count = n + 1;
}
- final void internalAddAt(int index, Object e) {
+ final void rawAddAt(int index, Object e) {
int n = count;
if (index > n)
throw new ArrayIndexOutOfBoundsException(index);
@@ -215,7 +219,7 @@ public class ReadMostlyVector impleme
count = n + 1;
}
- final boolean internalAddAllAt(int index, Object[] elements) {
+ final boolean rawAddAllAt(int index, Object[] elements) {
int n = count;
if (index < 0 || index > n)
throw new ArrayIndexOutOfBoundsException(index);
@@ -233,7 +237,7 @@ public class ReadMostlyVector impleme
return true;
}
- final boolean internalRemoveAt(int index) {
+ final boolean rawRemoveAt(int index) {
int n = count - 1;
if (index < 0 || index > n)
return false;
@@ -261,7 +265,7 @@ public class ReadMostlyVector impleme
int fence = bound < 0 || bound > n ? n : bound;
if (origin >= 0 && origin < fence) {
for (Object x : c) {
- while (internalRemoveAt(rawIndexOf(x, origin, fence)))
+ while (rawRemoveAt(rawIndexOf(x, origin, fence)))
removed = true;
}
}
@@ -280,7 +284,7 @@ public class ReadMostlyVector impleme
int i = origin;
int n = count;
int fence = bound < 0 || bound > n ? n : bound;
- while (i < fence) {
+ while (i >= 0 && i < fence) {
if (c.contains(array[i]))
++i;
else {
@@ -331,7 +335,11 @@ public class ReadMostlyVector impleme
else {
contained = true;
for (Object e : c) {
- if (validatedIndexOf(e, items, origin, fence, seq) < 0) {
+ int idx = (locked?
+ rawIndexOf(e, origin, fence) :
+ validatedIndexOf(e, items, origin,
+ fence, seq));
+ if (idx < 0) {
contained = false;
break;
}
@@ -351,32 +359,26 @@ public class ReadMostlyVector impleme
final boolean internalEquals(List> list, int origin, int bound) {
SequenceLock lock = this.lock;
- boolean equal;
boolean locked = false;
+ boolean equal;
try {
- outer:for (;;) {
- equal = true;
+ for (;;) {
long seq = lock.awaitAvailability();
Object[] items = array;
- int len = items.length;
int n = count;
- if (n > len)
- continue;
- int fence = bound < 0 || bound > n ? n : bound;
- if (origin < 0)
+ if (n > items.length || origin < 0)
equal = false;
else {
+ equal = true;
+ int fence = bound < 0 || bound > n ? n : bound;
Iterator> it = list.iterator();
for (int i = origin; i < fence; ++i) {
- if (!it.hasNext()) {
- equal = false;
- break;
- }
- Object x = it.next();
- Object y = items[i];
- if (lock.getSequence() != seq)
- continue outer;
- if (x == null? y != null : (y == null || !x.equals(y))) {
+ Object x = items[i];
+ Object y;
+ if ((!locked && lock.getSequence() != seq) ||
+ !it.hasNext() ||
+ (y = it.next()) == null ?
+ x != null : !y.equals(x)) {
equal = false;
break;
}
@@ -450,7 +452,7 @@ public class ReadMostlyVector impleme
Object e = items[i];
if (e == this)
sb.append("(this Collection)");
- else if (lock.getSequence() != seq)
+ else if (!locked && lock.getSequence() != seq)
continue outer;
else
sb.append(e.toString());
@@ -518,16 +520,16 @@ public class ReadMostlyVector impleme
continue;
int fence = bound < 0 || bound > n ? n : bound;
int rlen = fence - origin;
+ if (rlen < 0)
+ rlen = 0;
if (origin < 0 || alen >= rlen) {
- if (rlen < 0)
- rlen = 0;
- else if (rlen > 0)
+ if (rlen > 0)
System.arraycopy(array, 0, a, origin, rlen);
if (alen > rlen)
a[rlen] = null;
result = a;
}
- else
+ else
result = (T[]) Arrays.copyOfRange(array, origin,
fence, a.getClass());
if (lock.getSequence() == seq)
@@ -548,7 +550,7 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
- internalAdd(e);
+ rawAdd(e);
} finally {
lock.unlock();
}
@@ -559,7 +561,7 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
- internalAddAt(index, element);
+ rawAddAt(index, element);
} finally {
lock.unlock();
}
@@ -590,7 +592,7 @@ public class ReadMostlyVector impleme
Object[] elements = c.toArray();
lock.lock();
try {
- ret = internalAddAllAt(index, elements);
+ ret = rawAddAllAt(index, elements);
} finally {
lock.unlock();
}
@@ -622,7 +624,7 @@ public class ReadMostlyVector impleme
return true;
if (!(o instanceof List))
return false;
- return internalEquals((List>)(o), 0, -1);
+ return internalEquals((List>)o, 0, -1);
}
public E get(int index) {
@@ -661,9 +663,20 @@ public class ReadMostlyVector impleme
Object[] items = array;
int n = count;
if (n <= items.length) {
- int idx = validatedIndexOf(o, items, 0, n, seq);
- if (lock.getSequence() == seq)
- return idx;
+ boolean valid = true;
+ for (int i = 0; i < n; ++i) {
+ Object e = items[i];
+ if (lock.getSequence() == seq) {
+ if (o == null? e == null : o.equals(e))
+ return i;
+ }
+ else {
+ valid = false;
+ break;
+ }
+ }
+ if (valid)
+ return -1;
}
lock.lock();
try {
@@ -716,7 +729,7 @@ public class ReadMostlyVector impleme
if (index < 0 || index >= count)
throw new ArrayIndexOutOfBoundsException(index);
oldValue = array[index];
- internalRemoveAt(index);
+ rawRemoveAt(index);
} finally {
lock.unlock();
}
@@ -728,7 +741,7 @@ public class ReadMostlyVector impleme
boolean removed;
lock.lock();
try {
- removed = internalRemoveAt(rawIndexOf(o, 0, count));
+ removed = rawRemoveAt(rawIndexOf(o, 0, count));
} finally {
lock.unlock();
}
@@ -797,7 +810,7 @@ public class ReadMostlyVector impleme
lock.lock();
try {
if (rawIndexOf(e, 0, count) < 0) {
- internalAdd(e);
+ rawAdd(e);
added = true;
}
else
@@ -829,7 +842,7 @@ public class ReadMostlyVector impleme
for (int i = 0; i < clen; ++i) {
Object e = cs[i];
if (rawIndexOf(e, 0, count) < 0) {
- internalAdd(e);
+ rawAdd(e);
++added;
}
}
@@ -840,6 +853,31 @@ public class ReadMostlyVector impleme
return added;
}
+ /**
+ * Returns an iterator operating over a snapshot copy of the
+ * elements of this collection created upon construction of the
+ * iterator. The iterator does NOT support the
+ * remove method.
+ *
+ * @return an iterator over the elements in this list in proper sequence
+ */
+ public Iterator snapshotIterator() {
+ return new SnapshotIterator(this);
+ }
+
+ static final class SnapshotIterator implements Iterator {
+ final Object[] items;
+ int cursor;
+ SnapshotIterator(ReadMostlyVector v) { items = v.toArray(); }
+ public boolean hasNext() { return cursor < items.length; }
+ public E next() {
+ if (cursor < items.length)
+ return (E) items[cursor++];
+ throw new NoSuchElementException();
+ }
+ public void remove() { throw new UnsupportedOperationException() ; }
+ }
+
// Vector-only methods
/** See {@link Vector#firstElement} */
@@ -1256,7 +1294,7 @@ public class ReadMostlyVector impleme
lock.lock();
try {
int c = size;
- list.internalAddAt(c + offset, element);
+ list.rawAddAt(c + offset, element);
size = c + 1;
} finally {
lock.unlock();
@@ -1270,7 +1308,7 @@ public class ReadMostlyVector impleme
try {
if (index < 0 || index > size)
throw new ArrayIndexOutOfBoundsException(index);
- list.internalAddAt(index + offset, element);
+ list.rawAddAt(index + offset, element);
++size;
} finally {
lock.unlock();
@@ -1285,7 +1323,7 @@ public class ReadMostlyVector impleme
try {
int s = size;
int pc = list.count;
- list.internalAddAllAt(offset + s, elements);
+ list.rawAddAllAt(offset + s, elements);
added = list.count - pc;
size = s + added;
} finally {
@@ -1304,7 +1342,7 @@ public class ReadMostlyVector impleme
if (index < 0 || index > s)
throw new ArrayIndexOutOfBoundsException(index);
int pc = list.count;
- list.internalAddAllAt(index + offset, elements);
+ list.rawAddAllAt(index + offset, elements);
added = list.count - pc;
size = s + added;
} finally {
@@ -1356,13 +1394,14 @@ public class ReadMostlyVector impleme
Object[] items = list.array;
int c = list.count;
if (c <= items.length) {
- int idx = list.validatedIndexOf(o, items, offset, offset+size, seq);
+ int idx = list.validatedIndexOf(o, items, offset,
+ offset + size, seq);
if (lock.getSequence() == seq)
return idx < 0 ? -1 : idx - offset;
}
lock.lock();
try {
- int idx = list.rawIndexOf(o, offset, offset+size);
+ int idx = list.rawIndexOf(o, offset, offset + size);
return idx < 0 ? -1 : idx - offset;
} finally {
lock.unlock();
@@ -1383,7 +1422,7 @@ public class ReadMostlyVector impleme
Object[] items = list.array;
int c = list.count;
if (c <= items.length) {
- int idx = list.validatedLastIndexOf(o, items, offset+size-1,
+ int idx = list.validatedLastIndexOf(o, items, offset+size-1,
offset, seq);
if (lock.getSequence() == seq)
return idx < 0 ? -1 : idx - offset;
@@ -1410,11 +1449,12 @@ public class ReadMostlyVector impleme
SequenceLock lock = list.lock;
lock.lock();
try {
- if (index < 0 || index >= size)
- throw new ArrayIndexOutOfBoundsException(index);
+ Object[] items = list.array;
int i = index + offset;
- result = list.array[i];
- list.internalRemoveAt(i);
+ if (index < 0 || index >= size || i >= items.length)
+ throw new ArrayIndexOutOfBoundsException(index);
+ result = items[i];
+ list.rawRemoveAt(i);
size--;
} finally {
lock.unlock();
@@ -1427,8 +1467,8 @@ public class ReadMostlyVector impleme
SequenceLock lock = list.lock;
lock.lock();
try {
- if (list.internalRemoveAt(list.rawIndexOf(o, offset,
- offset + size))) {
+ if (list.rawRemoveAt(list.rawIndexOf(o, offset,
+ offset + size))) {
removed = true;
--size;
}