Skip to content

Commit 07a06bc

Browse files
lowassercgdecker
lowasser
authored and
cgdecker
committed
Add RandomAccess implementations for Lists.{equals,indexOf,lastIndexOf}Impl, to eliminate allocation of the iterator.
------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=90193421
1 parent bd929fa commit 07a06bc

File tree

4 files changed

+140
-81
lines changed

4 files changed

+140
-81
lines changed

‎guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/Lists.java

Lines changed: 70 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -909,18 +909,29 @@ static int hashCodeImpl(List<?> list) {
909909
/**
910910
* An implementation of {@link List#equals(Object)}.
911911
*/
912-
static boolean equalsImpl(List<?> list, @Nullable Object object) {
913-
if (object == checkNotNull(list)) {
912+
static boolean equalsImpl(List<?> thisList, @Nullable Object other) {
913+
if (other == checkNotNull(thisList)) {
914914
return true;
915915
}
916-
if (!(object instanceof List)) {
916+
if (!(other instanceof List)) {
917917
return false;
918918
}
919-
920-
List<?> o = (List<?>) object;
921-
922-
return list.size() == o.size()
923-
&& Iterators.elementsEqual(list.iterator(), o.iterator());
919+
List<?> otherList = (List<?>) other;
920+
int size = thisList.size();
921+
if (size != otherList.size()) {
922+
return false;
923+
}
924+
if (thisList instanceof RandomAccess && otherList instanceof RandomAccess) {
925+
// avoid allocation and use the faster loop
926+
for (int i = 0; i < size; i++) {
927+
if (!Objects.equal(thisList.get(i), otherList.get(i))) {
928+
return false;
929+
}
930+
}
931+
return true;
932+
} else {
933+
return Iterators.elementsEqual(thisList.iterator(), otherList.iterator());
934+
}
924935
}
925936

926937
/**
@@ -941,10 +952,32 @@ static <E> boolean addAllImpl(
941952
* An implementation of {@link List#indexOf(Object)}.
942953
*/
943954
static int indexOfImpl(List<?> list, @Nullable Object element) {
944-
ListIterator<?> listIterator = list.listIterator();
945-
while (listIterator.hasNext()) {
946-
if (Objects.equal(element, listIterator.next())) {
947-
return listIterator.previousIndex();
955+
if (list instanceof RandomAccess) {
956+
return indexOfRandomAccess(list, element);
957+
} else {
958+
ListIterator<?> listIterator = list.listIterator();
959+
while (listIterator.hasNext()) {
960+
if (Objects.equal(element, listIterator.next())) {
961+
return listIterator.previousIndex();
962+
}
963+
}
964+
return -1;
965+
}
966+
}
967+
968+
private static int indexOfRandomAccess(List<?> list, @Nullable Object element) {
969+
int size = list.size();
970+
if (element == null) {
971+
for (int i = 0; i < size; i++) {
972+
if (list.get(i) == null) {
973+
return i;
974+
}
975+
}
976+
} else {
977+
for (int i = 0; i < size; i++) {
978+
if (element.equals(list.get(i))) {
979+
return i;
980+
}
948981
}
949982
}
950983
return -1;
@@ -954,10 +987,31 @@ static int indexOfImpl(List<?> list, @Nullable Object element) {
954987
* An implementation of {@link List#lastIndexOf(Object)}.
955988
*/
956989
static int lastIndexOfImpl(List<?> list, @Nullable Object element) {
957-
ListIterator<?> listIterator = list.listIterator(list.size());
958-
while (listIterator.hasPrevious()) {
959-
if (Objects.equal(element, listIterator.previous())) {
960-
return listIterator.nextIndex();
990+
if (list instanceof RandomAccess) {
991+
return lastIndexOfRandomAccess(list, element);
992+
} else {
993+
ListIterator<?> listIterator = list.listIterator(list.size());
994+
while (listIterator.hasPrevious()) {
995+
if (Objects.equal(element, listIterator.previous())) {
996+
return listIterator.nextIndex();
997+
}
998+
}
999+
return -1;
1000+
}
1001+
}
1002+
1003+
private static int lastIndexOfRandomAccess(List<?> list, @Nullable Object element) {
1004+
if (element == null) {
1005+
for (int i = list.size() - 1; i >= 0; i--) {
1006+
if (list.get(i) == null) {
1007+
return i;
1008+
}
1009+
}
1010+
} else {
1011+
for (int i = list.size() - 1; i >= 0; i--) {
1012+
if (element.equals(list.get(i))) {
1013+
return i;
1014+
}
9611015
}
9621016
}
9631017
return -1;

‎guava/src/com/google/common/collect/Lists.java

Lines changed: 70 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -943,18 +943,29 @@ static int hashCodeImpl(List<?> list) {
943943
/**
944944
* An implementation of {@link List#equals(Object)}.
945945
*/
946-
static boolean equalsImpl(List<?> list, @Nullable Object object) {
947-
if (object == checkNotNull(list)) {
946+
static boolean equalsImpl(List<?> thisList, @Nullable Object other) {
947+
if (other == checkNotNull(thisList)) {
948948
return true;
949949
}
950-
if (!(object instanceof List)) {
950+
if (!(other instanceof List)) {
951951
return false;
952952
}
953-
954-
List<?> o = (List<?>) object;
955-
956-
return list.size() == o.size()
957-
&& Iterators.elementsEqual(list.iterator(), o.iterator());
953+
List<?> otherList = (List<?>) other;
954+
int size = thisList.size();
955+
if (size != otherList.size()) {
956+
return false;
957+
}
958+
if (thisList instanceof RandomAccess && otherList instanceof RandomAccess) {
959+
// avoid allocation and use the faster loop
960+
for (int i = 0; i < size; i++) {
961+
if (!Objects.equal(thisList.get(i), otherList.get(i))) {
962+
return false;
963+
}
964+
}
965+
return true;
966+
} else {
967+
return Iterators.elementsEqual(thisList.iterator(), otherList.iterator());
968+
}
958969
}
959970

960971
/**
@@ -975,10 +986,32 @@ static <E> boolean addAllImpl(
975986
* An implementation of {@link List#indexOf(Object)}.
976987
*/
977988
static int indexOfImpl(List<?> list, @Nullable Object element) {
978-
ListIterator<?> listIterator = list.listIterator();
979-
while (listIterator.hasNext()) {
980-
if (Objects.equal(element, listIterator.next())) {
981-
return listIterator.previousIndex();
989+
if (list instanceof RandomAccess) {
990+
return indexOfRandomAccess(list, element);
991+
} else {
992+
ListIterator<?> listIterator = list.listIterator();
993+
while (listIterator.hasNext()) {
994+
if (Objects.equal(element, listIterator.next())) {
995+
return listIterator.previousIndex();
996+
}
997+
}
998+
return -1;
999+
}
1000+
}
1001+
1002+
private static int indexOfRandomAccess(List<?> list, @Nullable Object element) {
1003+
int size = list.size();
1004+
if (element == null) {
1005+
for (int i = 0; i < size; i++) {
1006+
if (list.get(i) == null) {
1007+
return i;
1008+
}
1009+
}
1010+
} else {
1011+
for (int i = 0; i < size; i++) {
1012+
if (element.equals(list.get(i))) {
1013+
return i;
1014+
}
9821015
}
9831016
}
9841017
return -1;
@@ -988,10 +1021,31 @@ static int indexOfImpl(List<?> list, @Nullable Object element) {
9881021
* An implementation of {@link List#lastIndexOf(Object)}.
9891022
*/
9901023
static int lastIndexOfImpl(List<?> list, @Nullable Object element) {
991-
ListIterator<?> listIterator = list.listIterator(list.size());
992-
while (listIterator.hasPrevious()) {
993-
if (Objects.equal(element, listIterator.previous())) {
994-
return listIterator.nextIndex();
1024+
if (list instanceof RandomAccess) {
1025+
return lastIndexOfRandomAccess(list, element);
1026+
} else {
1027+
ListIterator<?> listIterator = list.listIterator(list.size());
1028+
while (listIterator.hasPrevious()) {
1029+
if (Objects.equal(element, listIterator.previous())) {
1030+
return listIterator.nextIndex();
1031+
}
1032+
}
1033+
return -1;
1034+
}
1035+
}
1036+
1037+
private static int lastIndexOfRandomAccess(List<?> list, @Nullable Object element) {
1038+
if (element == null) {
1039+
for (int i = list.size() - 1; i >= 0; i--) {
1040+
if (list.get(i) == null) {
1041+
return i;
1042+
}
1043+
}
1044+
} else {
1045+
for (int i = list.size() - 1; i >= 0; i--) {
1046+
if (element.equals(list.get(i))) {
1047+
return i;
1048+
}
9951049
}
9961050
}
9971051
return -1;

‎guava/src/com/google/common/collect/RegularImmutableList.java

Lines changed: 0 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,6 @@
1919
import com.google.common.annotations.GwtCompatible;
2020
import com.google.common.base.Preconditions;
2121

22-
import javax.annotation.Nullable;
23-
2422
/**
2523
* Implementation of {@link ImmutableList} used for 0 or 2+ elements (not 1).
2624
*
@@ -69,32 +67,6 @@ public E get(int index) {
6967
return (E) array[index + offset];
7068
}
7169

72-
@Override
73-
public int indexOf(@Nullable Object object) {
74-
if (object == null) {
75-
return -1;
76-
}
77-
for (int i = 0; i < size; i++) {
78-
if (array[offset + i].equals(object)) {
79-
return i;
80-
}
81-
}
82-
return -1;
83-
}
84-
85-
@Override
86-
public int lastIndexOf(@Nullable Object object) {
87-
if (object == null) {
88-
return -1;
89-
}
90-
for (int i = size - 1; i >= 0; i--) {
91-
if (array[offset + i].equals(object)) {
92-
return i;
93-
}
94-
}
95-
return -1;
96-
}
97-
9870
@Override
9971
ImmutableList<E> subListUnchecked(int fromIndex, int toIndex) {
10072
return new RegularImmutableList<E>(

‎guava/src/com/google/common/collect/SingletonImmutableList.java

Lines changed: 0 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,6 @@
2121
import com.google.common.annotations.GwtCompatible;
2222
import com.google.common.base.Preconditions;
2323

24-
import java.util.List;
25-
2624
import javax.annotation.Nullable;
2725

2826
/**
@@ -46,18 +44,10 @@ public E get(int index) {
4644
return element;
4745
}
4846

49-
@Override public int indexOf(@Nullable Object object) {
50-
return element.equals(object) ? 0 : -1;
51-
}
52-
5347
@Override public UnmodifiableIterator<E> iterator() {
5448
return Iterators.singletonIterator(element);
5549
}
5650

57-
@Override public int lastIndexOf(@Nullable Object object) {
58-
return indexOf(object);
59-
}
60-
6151
@Override
6252
public int size() {
6353
return 1;
@@ -76,17 +66,6 @@ public int size() {
7666
return element.equals(object);
7767
}
7868

79-
@Override public boolean equals(@Nullable Object object) {
80-
if (object == this) {
81-
return true;
82-
}
83-
if (object instanceof List) {
84-
List<?> that = (List<?>) object;
85-
return that.size() == 1 && element.equals(that.get(0));
86-
}
87-
return false;
88-
}
89-
9069
@Override public int hashCode() {
9170
// not caching hash code since it could change if the element is mutable
9271
// in a way that modifies its hash code.

0 commit comments

Comments
 (0)