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 |
|
/** |
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 |
|
volatile Object[] array; |
67 |
|
final SequenceLock lock; |
68 |
|
volatile int count; |
160 |
|
* as well as sublist and iterator classes. |
161 |
|
*/ |
162 |
|
|
163 |
< |
// Version of indexOf that returns -1 if either not present or invalid |
163 |
> |
/** |
164 |
> |
* Version of indexOf that returns -1 if either not present or invalid. |
165 |
> |
* |
166 |
> |
* @throws ArrayIndexOutOfBoundsException if index is negative |
167 |
> |
*/ |
168 |
|
final int validatedIndexOf(Object x, Object[] items, int index, int fence, |
169 |
|
long seq) { |
170 |
|
for (int i = index; i < fence; ++i) { |
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) { |
660 |
|
long seq = lock.awaitAvailability(); |
661 |
|
int n = count; |
662 |
|
Object[] items = array; |
651 |
– |
if (n > items.length) |
652 |
– |
continue; |
653 |
– |
boolean outOfBounds = (index < 0 || index >= n); |
663 |
|
@SuppressWarnings("unchecked") |
664 |
< |
E e = outOfBounds ? null : (E) items[index]; |
664 |
> |
E e = (index < items.length) ? (E) items[index] : null; |
665 |
|
if (lock.getSequence() == seq) { |
666 |
< |
if (outOfBounds) |
666 |
> |
if (index >= n) |
667 |
|
throw new ArrayIndexOutOfBoundsException(index); |
668 |
< |
else |
660 |
< |
return e; |
668 |
> |
return e; |
669 |
|
} |
670 |
|
} |
671 |
|
} |
675 |
|
} |
676 |
|
|
677 |
|
public int indexOf(Object o) { |
678 |
< |
final SequenceLock lock = this.lock; |
671 |
< |
for (;;) { |
672 |
< |
long seq = lock.awaitAvailability(); |
673 |
< |
Object[] items = array; |
674 |
< |
int n = count; |
675 |
< |
if (n <= items.length) { |
676 |
< |
for (int i = 0; i < n; ++i) { |
677 |
< |
Object e = items[i]; |
678 |
< |
if (lock.getSequence() != seq) { |
679 |
< |
lock.lock(); |
680 |
< |
try { |
681 |
< |
return rawIndexOf(o, 0, count); |
682 |
< |
} finally { |
683 |
< |
lock.unlock(); |
684 |
< |
} |
685 |
< |
} |
686 |
< |
else if ((o == null) ? e == null : o.equals(e)) |
687 |
< |
return i; |
688 |
< |
} |
689 |
< |
return -1; |
690 |
< |
} |
691 |
< |
} |
678 |
> |
return indexOf(o, 0); |
679 |
|
} |
680 |
|
|
681 |
|
public boolean isEmpty() { |
698 |
|
if (lock.getSequence() != seq) { |
699 |
|
lock.lock(); |
700 |
|
try { |
701 |
< |
return rawLastIndexOf(o, 0, count); |
701 |
> |
return rawLastIndexOf(o, count - 1, 0); |
702 |
|
} finally { |
703 |
|
lock.unlock(); |
704 |
|
} |
795 |
|
// ReadMostlyVector-only methods |
796 |
|
|
797 |
|
/** |
798 |
< |
* Append the element if not present. |
798 |
> |
* Appends the element, if not present. |
799 |
|
* |
800 |
|
* @param e element to be added to this list, if absent |
801 |
|
* @return {@code true} if the element was added |
882 |
|
for (;;) { |
883 |
|
long seq = lock.awaitAvailability(); |
884 |
|
Object[] items = array; |
898 |
– |
int len = items.length; |
885 |
|
int n = count; |
900 |
– |
if (n > len) |
901 |
– |
continue; |
902 |
– |
boolean empty = (n == 0); |
886 |
|
@SuppressWarnings("unchecked") |
887 |
< |
E e = empty ? null : (E) items[0]; |
887 |
> |
E e = (items.length > 0) ? (E) items[0] : null; |
888 |
|
if (lock.getSequence() == seq) { |
889 |
< |
if (empty) |
889 |
> |
if (n <= 0) |
890 |
|
throw new NoSuchElementException(); |
891 |
< |
else |
909 |
< |
return e; |
891 |
> |
return e; |
892 |
|
} |
893 |
|
} |
894 |
|
} |
899 |
|
for (;;) { |
900 |
|
long seq = lock.awaitAvailability(); |
901 |
|
Object[] items = array; |
920 |
– |
int len = items.length; |
902 |
|
int n = count; |
922 |
– |
if (n > len) |
923 |
– |
continue; |
924 |
– |
boolean empty = (n == 0); |
903 |
|
@SuppressWarnings("unchecked") |
904 |
< |
E e = empty ? null : (E) items[n - 1]; |
904 |
> |
E e = (n > 0 && items.length >= n) ? (E) items[n - 1] : null; |
905 |
|
if (lock.getSequence() == seq) { |
906 |
< |
if (empty) |
906 |
> |
if (n <= 0) |
907 |
|
throw new NoSuchElementException(); |
908 |
< |
else |
931 |
< |
return e; |
908 |
> |
return e; |
909 |
|
} |
910 |
|
} |
911 |
|
} |
913 |
|
/** See {@link Vector#indexOf(Object, int)} */ |
914 |
|
public int indexOf(Object o, int index) { |
915 |
|
final SequenceLock lock = this.lock; |
939 |
– |
int idx = 0; |
940 |
– |
boolean ex = false; |
916 |
|
long seq = lock.awaitAvailability(); |
917 |
|
Object[] items = array; |
918 |
|
int n = count; |
919 |
< |
boolean retry = false; |
920 |
< |
if (n > items.length) |
946 |
< |
retry = true; |
947 |
< |
else if (index < 0) |
948 |
< |
ex = true; |
949 |
< |
else |
919 |
> |
int idx = -1; |
920 |
> |
if (n <= items.length) |
921 |
|
idx = validatedIndexOf(o, items, index, n, seq); |
922 |
< |
if (retry || lock.getSequence() != seq) { |
922 |
> |
if (lock.getSequence() != seq) { |
923 |
|
lock.lock(); |
924 |
|
try { |
925 |
< |
if (index < 0) |
955 |
< |
ex = true; |
956 |
< |
else |
957 |
< |
idx = rawIndexOf(o, 0, count); |
925 |
> |
idx = rawIndexOf(o, index, count); |
926 |
|
} finally { |
927 |
|
lock.unlock(); |
928 |
|
} |
929 |
|
} |
930 |
< |
if (ex) |
963 |
< |
throw new ArrayIndexOutOfBoundsException(index); |
930 |
> |
// Above code will throw AIOOBE when index < 0 |
931 |
|
return idx; |
932 |
|
} |
933 |
|
|
934 |
|
/** See {@link Vector#lastIndexOf(Object, int)} */ |
935 |
|
public int lastIndexOf(Object o, int index) { |
936 |
|
final SequenceLock lock = this.lock; |
970 |
– |
int idx = 0; |
971 |
– |
boolean ex = false; |
937 |
|
long seq = lock.awaitAvailability(); |
938 |
|
Object[] items = array; |
939 |
|
int n = count; |
940 |
< |
boolean retry = false; |
941 |
< |
if (n > items.length) |
977 |
< |
retry = true; |
978 |
< |
else if (index >= n) |
979 |
< |
ex = true; |
980 |
< |
else |
940 |
> |
int idx = -1; |
941 |
> |
if (index < Math.min(n, items.length)) |
942 |
|
idx = validatedLastIndexOf(o, items, index, 0, seq); |
943 |
< |
if (retry || lock.getSequence() != seq) { |
943 |
> |
if (lock.getSequence() != seq) { |
944 |
|
lock.lock(); |
945 |
|
try { |
946 |
< |
if (index >= count) |
947 |
< |
ex = true; |
987 |
< |
else |
946 |
> |
n = count; |
947 |
> |
if (index < n) |
948 |
|
idx = rawLastIndexOf(o, index, 0); |
949 |
|
} finally { |
950 |
|
lock.unlock(); |
951 |
|
} |
952 |
|
} |
953 |
< |
if (ex) |
954 |
< |
throw new ArrayIndexOutOfBoundsException(index); |
953 |
> |
if (index >= n) |
954 |
> |
throw new IndexOutOfBoundsException(index + " >= " + n); |
955 |
|
return idx; |
956 |
|
} |
957 |
|
|
1633 |
|
|
1634 |
|
} |
1635 |
|
} |
1676 |
– |
|