Hi everyone,
currently array-based collections, in particular java.util.ArrayList,
java.util.Arrays$ArrayList, java.util.Vector,
java.util.concurrent.CopyOnWriteArrayList have duplicated code in indexOf() and
lastIndexOf().
My proposal is to extract this code into java.util.Arrays helping JIT and
saving space in ReservedCodeCache.
Moreover, developers quite often use code snippets like
Arras.asList(array).indexOf(obj)
Arras.asList(array).contains(obj) or even
Arrays.stream(names).anyMatch(existing -> existing.equals(name));
or write similar utility code for allocation-free cases like the one in
https://github.com/hibernate/hibernate-orm/blob/0a2a5c622e3eb30724e80bc8661c0ac55ebfb2be/hibernate-core/src/main/java/org/hibernate/bytecode/enhance/internal/tracker/SimpleFieldTracker.java#L40
Also see
https://github.com/JetBrains/intellij-community/blob/200f59d7cf3b0f66feb3a4abebbb90864dc5edc7/platform/util/src/com/intellij/util/ArrayUtil.java#L726
https://github.com/JetBrains/intellij-community/blob/200f59d7cf3b0f66feb3a4abebbb90864dc5edc7/platform/util-rt/src/com/intellij/util/ArrayUtilRt.java#L63
https://github.com/spring-projects/spring-framework/blob/5f4d1a4628513ab34098fa3f92ba03aa20fc4204/spring-oxm/src/main/java/org/springframework/oxm/jibx/JibxMarshaller.java#L256
If java.util.Arrays incorporates contains() and indexOf() then all that
boilerplate can be replaced with usage of JDK-provided standard API.
Patch is attached to this mail.
Regards,
Sergey Tsypanov
diff --git a/src/java.base/share/classes/java/util/ArrayList.java b/src/java.base/share/classes/java/util/ArrayList.java
--- a/src/java.base/share/classes/java/util/ArrayList.java
+++ b/src/java.base/share/classes/java/util/ArrayList.java
@@ -313,16 +313,7 @@
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
- if (o == null) {
- for (int i = 0; i < size; i++)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = 0; i < size; i++)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
+ return Arrays.indexOf(o, elementData, 0, size);
}
/**
@@ -333,16 +324,7 @@
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
- if (o == null) {
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
+ return Arrays.lastIndexOf(o, elementData, size - 1, 0);
}
/**
diff --git a/src/java.base/share/classes/java/util/Arrays.java b/src/java.base/share/classes/java/util/Arrays.java
--- a/src/java.base/share/classes/java/util/Arrays.java
+++ b/src/java.base/share/classes/java/util/Arrays.java
@@ -4359,17 +4359,12 @@
@Override
public int indexOf(Object o) {
- E[] a = this.a;
- if (o == null) {
- for (int i = 0; i < a.length; i++)
- if (a[i] == null)
- return i;
- } else {
- for (int i = 0; i < a.length; i++)
- if (o.equals(a[i]))
- return i;
- }
- return -1;
+ return Arrays.indexOf(o, a, 0, a.length);
+ }
+
+ @Override
+ public int lastIndexOf(Object o) {
+ return Arrays.lastIndexOf(o, a, a.length - 1, 0);
}
@Override
@@ -8899,4 +8894,97 @@
return aLength != bLength ? length : -1;
}
+
+ /**
+ * Returns {@code true} if {@code elements} array contains {@code obj}.
+ * More formally, returns {@code true} if and only if {@code elements}
+ * contains at least one element {@code e} such that
+ * {@code Objects.equals(o, e)}.
+ *
+ * @param obj element whose presence in the array is to be tested
+ * @param elements the array to search in
+ * @param <T> element type
+ * @return {@code true} if {@code elements} contains the specified {@code obj}
+ */
+ public static <T> boolean contains(T obj, T[] elements) {
+ return indexOf(obj, elements, 0, elements.length) >= 0;
+ }
+
+ /**
+ * Returns the index of the first occurrence of {@code obj}
+ * in {@code elements}, or -1 if the array does not contain the element.
+ * More formally, returns the lowest index {@code i} such that
+ * {@code Objects.equals(o, elements[i])},
+ * or -1 if there is no such index.
+ *
+ * @param obj element to search for
+ * @param elements the array to search in
+ * @param <T> element type
+ * @return the index of the first occurrence of the specified element in
+ * {@code elements}, or -1 if the array does not contain the element
+ */
+ public static <T> int indexOf(T obj, T[] elements) {
+ return indexOf(obj, elements, 0, elements.length);
+ }
+
+ /**
+ * Returns the index of the last occurrence of the specified element
+ * in {@code elements}, or -1 if the array does not contain the element.
+ * More formally, returns the highest index {@code i} such that
+ * {@code Objects.equals(o, elements[i])},
+ * or -1 if there is no such index.
+ *
+ * @param obj element to search for
+ * @param elements the array to search in
+ * @param <T> element type
+ * @return the index of the last occurrence of the specified element in
+ * {@code elements}, or -1 if the array does not contain the element
+ */
+ public static <T> int lastIndexOf(T obj, T[] elements) {
+ return lastIndexOf(obj, elements, elements.length - 1, 0);
+ }
+
+ /**
+ * @param obj element to search for
+ * @param elements the array
+ * @param index first index to search
+ * @param fence one past last index to search
+ * @param <T> element type
+ * @return the first index of element, or -1 if absent
+ */
+ public static <T> int indexOf(T obj, T[] elements, int index, int fence) {
+ if (obj == null) {
+ for (int i = index; i < fence; i++)
+ if (elements[i] == null)
+ return i;
+ } else {
+ for (int i = index; i < fence; i++)
+ if (obj.equals(elements[i]))
+ return i;
+ }
+ return -1;
+ }
+
+ /**
+ * @param obj element to search for
+ * @param elements the array
+ * @param index first index to search
+ * @param fence one past last index to search
+ * @param <T> element type
+ * @return the last index of element, or -1 if absent
+ */
+ public static <T> int lastIndexOf(T obj, T[] elements, int index, int fence) {
+ if (obj == null) {
+ for (int i = index; i >= fence; i--)
+ if (elements[i] == null)
+ return i;
+ } else {
+ for (int i = index; i >= fence; i--)
+ if (obj.equals(elements[i]))
+ return i;
+ }
+ return -1;
+ }
+
+
}
diff --git a/src/java.base/share/classes/java/util/Vector.java b/src/java.base/share/classes/java/util/Vector.java
--- a/src/java.base/share/classes/java/util/Vector.java
+++ b/src/java.base/share/classes/java/util/Vector.java
@@ -418,16 +418,7 @@
* @see Object#equals(Object)
*/
public synchronized int indexOf(Object o, int index) {
- if (o == null) {
- for (int i = index ; i < elementCount ; i++)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = index ; i < elementCount ; i++)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
+ return Arrays.indexOf(o, elementData, index, elementCount);
}
/**
@@ -465,16 +456,7 @@
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
- if (o == null) {
- for (int i = index; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = index; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
+ return Arrays.lastIndexOf(o, elementData, index, 0);
}
/**
diff --git a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
--- a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
+++ b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java
@@ -176,49 +176,6 @@
}
/**
- * static version of indexOf, to allow repeated calls without
- * needing to re-acquire array each time.
- * @param o element to search for
- * @param elements the array
- * @param index first index to search
- * @param fence one past last index to search
- * @return index of element, or -1 if absent
- */
- private static int indexOf(Object o, Object[] elements,
- int index, int fence) {
- if (o == null) {
- for (int i = index; i < fence; i++)
- if (elements[i] == null)
- return i;
- } else {
- for (int i = index; i < fence; i++)
- if (o.equals(elements[i]))
- return i;
- }
- return -1;
- }
-
- /**
- * static version of lastIndexOf.
- * @param o element to search for
- * @param elements the array
- * @param index first index to search
- * @return index of element, or -1 if absent
- */
- private static int lastIndexOf(Object o, Object[] elements, int index) {
- if (o == null) {
- for (int i = index; i >= 0; i--)
- if (elements[i] == null)
- return i;
- } else {
- for (int i = index; i >= 0; i--)
- if (o.equals(elements[i]))
- return i;
- }
- return -1;
- }
-
- /**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that {@code Objects.equals(o, e)}.
@@ -228,7 +185,7 @@
*/
public boolean contains(Object o) {
Object[] elements = getArray();
- return indexOf(o, elements, 0, elements.length) >= 0;
+ return Arrays.indexOf(o, elements, 0, elements.length) >= 0;
}
/**
@@ -236,7 +193,7 @@
*/
public int indexOf(Object o) {
Object[] elements = getArray();
- return indexOf(o, elements, 0, elements.length);
+ return Arrays.indexOf(o, elements, 0, elements.length);
}
/**
@@ -256,7 +213,7 @@
*/
public int indexOf(E e, int index) {
Object[] elements = getArray();
- return indexOf(e, elements, index, elements.length);
+ return Arrays.indexOf(e, elements, index, elements.length);
}
/**
@@ -264,7 +221,7 @@
*/
public int lastIndexOf(Object o) {
Object[] elements = getArray();
- return lastIndexOf(o, elements, elements.length - 1);
+ return Arrays.lastIndexOf(o, elements, elements.length - 1, 0);
}
/**
@@ -285,7 +242,7 @@
*/
public int lastIndexOf(E e, int index) {
Object[] elements = getArray();
- return lastIndexOf(e, elements, index);
+ return Arrays.lastIndexOf(e, elements, index, 0);
}
/**
@@ -506,7 +463,7 @@
*/
public boolean remove(Object o) {
Object[] snapshot = getArray();
- int index = indexOf(o, snapshot, 0, snapshot.length);
+ int index = Arrays.indexOf(o, snapshot, 0, snapshot.length);
return (index < 0) ? false : remove(o, snapshot, index);
}
@@ -531,7 +488,7 @@
return false;
if (current[index] == o)
break findIndex;
- index = indexOf(o, current, index, len);
+ index = Arrays.indexOf(o, current, index, len);
if (index < 0)
return false;
}
@@ -586,7 +543,7 @@
*/
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
- return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
+ return Arrays.indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
@@ -605,7 +562,7 @@
if (current[i] != snapshot[i]
&& Objects.equals(e, current[i]))
return false;
- if (indexOf(e, current, common, len) >= 0)
+ if (Arrays.indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
@@ -629,7 +586,7 @@
Object[] elements = getArray();
int len = elements.length;
for (Object e : c) {
- if (indexOf(e, elements, 0, len) < 0)
+ if (Arrays.indexOf(e, elements, 0, len) < 0)
return false;
}
return true;
@@ -699,8 +656,8 @@
// uniquify and compact elements in cs
for (int i = 0; i < cs.length; ++i) {
Object e = cs[i];
- if (indexOf(e, elements, 0, len) < 0 &&
- indexOf(e, cs, 0, added) < 0)
+ if (Arrays.indexOf(e, elements, 0, len) < 0 &&
+ Arrays.indexOf(e, cs, 0, added) < 0)
cs[added++] = e;
}
if (added > 0) {
