--- jsr166/src/jsr166e/extra/ReadMostlyVector.java 2011/07/19 12:05:09 1.9
+++ jsr166/src/jsr166e/extra/ReadMostlyVector.java 2011/08/05 17:08:04 1.13
@@ -19,7 +19,7 @@ import java.util.*;
* 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. Alternatvely,
+ * they appear in the underlying array upon each access. Alternatively,
* method {@link #snapshotIterator} may be used for deterministic
* traversals, at the expense of making a copy, and unavailability of
* method {@code Iterator.remove}.
@@ -57,9 +57,9 @@ public class ReadMostlyVector impleme
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// fields are non-private to simpify nested class access
- Object[] array;
+ volatile Object[] array;
final SequenceLock lock;
- int count;
+ volatile int count;
final int capacityIncrement;
/**
@@ -129,7 +129,7 @@ public class ReadMostlyVector impleme
}
// For explanation, see CopyOnWriteArrayList
- final void grow(int minCapacity) {
+ final Object[] grow(int minCapacity) {
int oldCapacity = array.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
@@ -137,7 +137,7 @@ public class ReadMostlyVector impleme
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
- array = Arrays.copyOf(array, newCapacity);
+ return array = Arrays.copyOf(array, newCapacity);
}
static int hugeCapacity(int minCapacity) {
@@ -201,50 +201,54 @@ public class ReadMostlyVector impleme
final void rawAdd(Object e) {
int n = count;
- if (n >= array.length)
- grow(n + 1);
- array[n] = e;
+ Object[] items = array;
+ if (n >= items.length)
+ items = grow(n + 1);
+ items[n] = e;
count = n + 1;
}
final void rawAddAt(int index, Object e) {
int n = count;
+ Object[] items = array;
if (index > n)
throw new ArrayIndexOutOfBoundsException(index);
- if (n >= array.length)
- grow(n + 1);
+ if (n >= items.length)
+ items = grow(n + 1);
if (index < n)
- System.arraycopy(array, index, array, index + 1, n - index);
- array[index] = e;
+ System.arraycopy(items, index, items, index + 1, n - index);
+ items[index] = e;
count = n + 1;
}
final boolean rawAddAllAt(int index, Object[] elements) {
int n = count;
+ Object[] items = array;
if (index < 0 || index > n)
throw new ArrayIndexOutOfBoundsException(index);
int len = elements.length;
if (len == 0)
return false;
int newCount = n + len;
- if (newCount >= array.length)
- grow(newCount);
- int mv = count - index;
+ if (newCount >= items.length)
+ items = grow(newCount);
+ int mv = n - index;
if (mv > 0)
- System.arraycopy(array, index, array, index + len, mv);
- System.arraycopy(elements, 0, array, index, len);
+ System.arraycopy(items, index, items, index + len, mv);
+ System.arraycopy(elements, 0, items, index, len);
count = newCount;
return true;
}
final boolean rawRemoveAt(int index) {
int n = count - 1;
+ Object[] items = array;
if (index < 0 || index > n)
return false;
int mv = n - index;
if (mv > 0)
- System.arraycopy(array, index + 1, array, index, mv);
- array[n] = null;
+ System.arraycopy(items, index + 1, items, index, mv);
+ items[n] = null;
count = n;
return true;
}
@@ -281,20 +285,24 @@ public class ReadMostlyVector impleme
if (c != this) {
lock.lock();
try {
+ Object[] items = array;
int i = origin;
int n = count;
int fence = bound < 0 || bound > n ? n : bound;
while (i >= 0 && i < fence) {
- if (c.contains(array[i]))
+ if (c.contains(items[i]))
++i;
else {
--fence;
- int mv = --count - i;
+ int mv = --n - i;
if (mv > 0)
- System.arraycopy(array, i + 1, array, i, mv);
- removed = true;
+ System.arraycopy(items, i + 1, items, i, mv);
}
}
+ if (count != n) {
+ count = n;
+ removed = true;
+ }
} finally {
lock.unlock();
}
@@ -306,13 +314,14 @@ public class ReadMostlyVector impleme
int n = count;
int fence = bound < 0 || bound > n ? n : bound;
if (origin >= 0 && origin < fence) {
+ Object[] items = array;
int removed = fence - origin;
int newCount = n - removed;
int mv = n - (origin + removed);
if (mv > 0)
- System.arraycopy(array, origin + removed, array, origin, mv);
+ System.arraycopy(items, origin + removed, items, origin, mv);
for (int i = n; i < newCount; ++i)
- array[i] = null;
+ items[i] = null;
count = newCount;
}
}
@@ -324,9 +333,9 @@ public class ReadMostlyVector impleme
try {
for (;;) {
long seq = lock.awaitAvailability();
+ int n = count;
Object[] items = array;
int len = items.length;
- int n = count;
if (n > len)
continue;
int fence = bound < 0 || bound > n ? n : bound;
@@ -407,8 +416,8 @@ public class ReadMostlyVector impleme
hash = 1;
long seq = lock.awaitAvailability();
Object[] items = array;
- int len = items.length;
int n = count;
+ int len = items.length;
if (n > len)
continue;
int fence = bound < 0 || bound > n ? n : bound;
@@ -438,8 +447,8 @@ public class ReadMostlyVector impleme
outer:for (;;) {
long seq = lock.awaitAvailability();
Object[] items = array;
- int len = items.length;
int n = count;
+ int len = items.length;
if (n > len)
continue;
int fence = bound < 0 || bound > n ? n : bound;
@@ -485,8 +494,8 @@ public class ReadMostlyVector impleme
result = null;
long seq = lock.awaitAvailability();
Object[] items = array;
- int len = items.length;
int n = count;
+ int len = items.length;
if (n > len)
continue;
int fence = bound < 0 || bound > n ? n : bound;
@@ -514,8 +523,8 @@ public class ReadMostlyVector impleme
for (;;) {
long seq = lock.awaitAvailability();
Object[] items = array;
- int len = items.length;
int n = count;
+ int len = items.length;
if (n > len)
continue;
int fence = bound < 0 || bound > n ? n : bound;
@@ -524,13 +533,13 @@ public class ReadMostlyVector impleme
rlen = 0;
if (origin < 0 || alen >= rlen) {
if (rlen > 0)
- System.arraycopy(array, 0, a, origin, rlen);
+ System.arraycopy(items, 0, a, origin, rlen);
if (alen > rlen)
a[rlen] = null;
result = a;
}
else
- result = (T[]) Arrays.copyOfRange(array, origin,
+ result = (T[]) Arrays.copyOfRange(items, origin,
fence, a.getClass());
if (lock.getSequence() == seq)
break;
@@ -575,10 +584,12 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
- int newCount = count + len;
- if (newCount >= array.length)
- grow(newCount);
- System.arraycopy(elements, 0, array, count, len);
+ Object[] items = array;
+ int n = count;
+ int newCount = n + len;
+ if (newCount >= items.length)
+ items = grow(newCount);
+ System.arraycopy(elements, 0, items, n, len);
count = newCount;
} finally {
lock.unlock();
@@ -603,8 +614,10 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
- for (int i = 0; i < count; i++)
- array[i] = null;
+ int n = count;
+ Object[] items = array;
+ for (int i = 0; i < n; i++)
+ items[i] = null;
count = 0;
} finally {
lock.unlock();
@@ -631,8 +644,8 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
for (;;) {
long seq = lock.awaitAvailability();
- Object[] items = array;
int n = count;
+ Object[] items = array;
if (n > items.length)
continue;
Object e; boolean ex;
@@ -683,12 +696,11 @@ public class ReadMostlyVector impleme
}
public boolean isEmpty() {
- long ignore = lock.getSequence();
return count == 0;
}
public Iterator iterator() {
- return new Itr(this, 0);
+ return new Itr(this, 0);
}
public int lastIndexOf(Object o) {
@@ -717,11 +729,11 @@ public class ReadMostlyVector impleme
}
public ListIterator listIterator() {
- return new Itr(this, 0);
+ return new Itr(this, 0);
}
public ListIterator listIterator(int index) {
- return new Itr(this, index);
+ return new Itr(this, index);
}
public E remove(int index) {
@@ -764,10 +776,11 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
+ Object[] items = array;
if (index < 0 || index >= count)
throw new ArrayIndexOutOfBoundsException(index);
- oldValue = array[index];
- array[index] = element;
+ oldValue = items[index];
+ items[index] = element;
} finally {
lock.unlock();
}
@@ -775,7 +788,6 @@ public class ReadMostlyVector impleme
}
public int size() {
- long ignore = lock.getSequence();
return count;
}
@@ -784,7 +796,7 @@ public class ReadMostlyVector impleme
int ssize = toIndex - fromIndex;
if (fromIndex < 0 || toIndex > c || ssize < 0)
throw new IndexOutOfBoundsException();
- return new ReadMostlyVectorSublist(this, fromIndex, ssize);
+ return new ReadMostlyVectorSublist(this, fromIndex, ssize);
}
public Object[] toArray() {
@@ -1012,8 +1024,9 @@ public class ReadMostlyVector impleme
if (newSize > n)
grow(newSize);
else {
+ Object[] items = array;
for (int i = newSize ; i < n ; i++)
- array[i] = null;
+ items[i] = null;
}
count = newSize;
} finally {
@@ -1037,8 +1050,10 @@ public class ReadMostlyVector impleme
SequenceLock lock = this.lock;
lock.lock();
try {
- if (count < array.length)
- array = Arrays.copyOf(array, count);
+ Object[] items = array;
+ int n = count;
+ if (n < items.length)
+ array = Arrays.copyOf(items, n);
} finally {
lock.unlock();
}
@@ -1060,12 +1075,11 @@ public class ReadMostlyVector impleme
/** See {@link Vector#elements} */
public Enumeration elements() {
- return new Itr(this, 0);
+ return new Itr(this, 0);
}
/** See {@link Vector#capacity} */
public int capacity() {
- long ignore = lock.getSequence();
return array.length;
}
@@ -1106,7 +1120,7 @@ public class ReadMostlyVector impleme
// other methods
- public Object clone() {
+ public ReadMostlyVector clone() {
SequenceLock lock = this.lock;
Object[] a = null;
boolean retry = false;
@@ -1126,7 +1140,7 @@ public class ReadMostlyVector impleme
lock.unlock();
}
}
- return new ReadMostlyVector(a, n, capacityIncrement);
+ return new ReadMostlyVector(a, n, capacityIncrement);
}
private void writeObject(java.io.ObjectOutputStream s)
@@ -1416,7 +1430,7 @@ public class ReadMostlyVector impleme
}
public Iterator iterator() {
- return new SubItr(this, offset);
+ return new SubItr(this, offset);
}
public int lastIndexOf(Object o) {
@@ -1440,11 +1454,11 @@ public class ReadMostlyVector impleme
}
public ListIterator listIterator() {
- return new SubItr(this, offset);
+ return new SubItr(this, offset);
}
public ListIterator listIterator(int index) {
- return new SubItr(this, index + offset);
+ return new SubItr(this, index + offset);
}
public E remove(int index) {
@@ -1504,7 +1518,7 @@ public class ReadMostlyVector impleme
int ssize = toIndex - fromIndex;
if (fromIndex < 0 || toIndex > c || ssize < 0)
throw new IndexOutOfBoundsException();
- return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
+ return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
}
public Object[] toArray() {