[FELIX-4942] Speed up collections a bit
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1690730 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java b/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
index 9f2931e..86bef20 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
@@ -21,11 +21,12 @@
import java.util.*;
import java.util.function.Function;
+@SuppressWarnings("NullableProblems")
public class ArrayMap<K, V> extends AbstractMap<K, V> {
private Object[] table;
private int size;
- protected transient volatile Collection<V> values;
+ protected transient Collection<V> values;
public ArrayMap() {
this(32);
@@ -121,6 +122,7 @@
return index < size;
}
+ @SuppressWarnings("unchecked")
public V next() {
if (index >= size) {
throw new NoSuchElementException();
@@ -152,7 +154,7 @@
return index < size;
}
- public Entry<K, V> next() {
+ public FastEntry next() {
if (index >= size) {
throw new NoSuchElementException();
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
index b22ab30..1defe57 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
@@ -18,11 +18,14 @@
*/
package org.apache.felix.resolver.util;
-import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
-public class CopyOnWriteList<T> extends AbstractList<T> {
+@SuppressWarnings("NullableProblems")
+public class CopyOnWriteList<E> implements List<E>, Cloneable {
Object[] data;
@@ -30,33 +33,32 @@
data = new Object[0];
}
- public CopyOnWriteList(Collection<T> col) {
- if (col instanceof CopyOnWriteList) {
- data = ((CopyOnWriteList) col).data;
- } else {
- data = col.toArray(new Object[col.size()]);
- }
+ public CopyOnWriteList(CopyOnWriteList<? extends E> col) {
+ data = col.data;
}
- @Override
+ public CopyOnWriteList(Collection<? extends E> col) {
+ data = col.toArray(new Object[col.size()]);
+ }
+
public int size() {
return data.length;
}
- public T get(int index) {
- return (T) data[index];
+ @SuppressWarnings("unchecked")
+ public E get(int index) {
+ return (E) data[index];
}
- @Override
- public T set(int index, T element) {
+ @SuppressWarnings("unchecked")
+ public E set(int index, E element) {
data = Arrays.copyOf(data, data.length);
- T prev = (T) data[index];
+ E prev = (E) data[index];
data[index] = element;
return prev;
}
- @Override
- public void add(int index, T element) {
+ public void add(int index, E element) {
Object[] elements = data;
int len = elements.length;
Object[] newElements = new Object[len + 1];
@@ -71,10 +73,11 @@
data = newElements;
}
- public T remove(int index) {
+ @SuppressWarnings("unchecked")
+ public E remove(int index) {
Object[] elements = data;
int len = elements.length;
- T oldValue = (T) elements[index];
+ E oldValue = (E) elements[index];
Object[] newElements = new Object[len - 1];
int numMoved = len - index - 1;
if (index > 0) {
@@ -87,8 +90,174 @@
return oldValue;
}
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ public boolean contains(Object o) {
+ return indexOf(o) >= 0;
+ }
+
+ public Iterator<E> iterator() {
+ return new Iterator<E>() {
+ int idx = 0;
+ public boolean hasNext() {
+ return idx < data.length;
+ }
+ @SuppressWarnings("unchecked")
+ public E next() {
+ return (E) data[idx++];
+ }
+ public void remove() {
+ CopyOnWriteList.this.remove(--idx);
+ }
+ };
+ }
+
+ public Object[] toArray() {
+ return data.clone();
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ int size = data.length;
+ if (a.length < size)
+ // Make a new array of a's runtime type, but my contents:
+ return (T[]) Arrays.copyOf(data, size, a.getClass());
+ System.arraycopy(data, 0, a, 0, size);
+ if (a.length > size)
+ a[size] = null;
+ return a;
+ }
+
+ public boolean add(E e) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean remove(Object o) {
+ int index;
+ if ((index = indexOf(o)) >= 0) {
+ remove(index);
+ return true;
+ }
+ return false;
+ }
+
+ public boolean containsAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(Collection<? extends E> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(int index, Collection<? extends E> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean removeAll(Collection<?> c) {
+ boolean modified = false;
+ Object[] d = data, o = data;
+ int idx = 0;
+ for (int i = 0, l = o.length; i < l; i++) {
+ if (c.contains(o[i])) {
+ modified = true;
+ } else if (modified) {
+ if (idx == 0) {
+ d = o.clone();
+ }
+ d[idx++] = o[i];
+ }
+ }
+ if (modified) {
+ data = Arrays.copyOf(d, idx);
+ }
+ return modified;
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void clear() {
+ data = new Object[0];
+ }
+
+ public int indexOf(Object o) {
+ if (o == null) {
+ Object[] d = data;
+ for (int i = d.length; i-- > 0;) {
+ if (d[i] == null)
+ return i;
+ }
+ } else {
+ Object[] d = data;
+ for (int i = d.length; i-- > 0;) {
+ if (o.equals(d[i]))
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ public int lastIndexOf(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ public ListIterator<E> listIterator() {
+ throw new UnsupportedOperationException();
+ }
+
+ public ListIterator<E> listIterator(int index) {
+ throw new UnsupportedOperationException();
+ }
+
+ public List<E> subList(int fromIndex, int toIndex) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Clone this object
+ *
+ * @return a cloned object.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public CopyOnWriteList<E> clone() {
+ try {
+ return (CopyOnWriteList<E>) super.clone();
+ } catch (CloneNotSupportedException exc) {
+ InternalError e = new InternalError();
+ e.initCause(exc);
+ throw e; //should never happen since we are cloneable
+ }
+ }
+
@Override
public int hashCode() {
return Arrays.hashCode(data);
}
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof CopyOnWriteList)) {
+ return false;
+ }
+ Object[] o1 = data;
+ Object[] o2 = ((CopyOnWriteList) o).data;
+ if (o1 == o2) {
+ return true;
+ }
+ int i;
+ if ((i = o1.length) != o2.length) {
+ return false;
+ }
+ while (i-- > 0) {
+ Object v1 = o1[i];
+ Object v2 = o2[i];
+ if (!(v1 == null ? v2 == null : v1.equals(v2)))
+ return false;
+ }
+ return true;
+ }
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
index 239233b..b007b14 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
@@ -22,8 +22,10 @@
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
+import java.util.Set;
-public class CopyOnWriteSet<E> extends AbstractSet<E> {
+@SuppressWarnings("NullableProblems")
+public class CopyOnWriteSet<E> implements Set<E>, Cloneable {
Object[] data;
@@ -31,15 +33,14 @@
data = new Object[0];
}
- public CopyOnWriteSet(Collection<E> col) {
- if (col instanceof CopyOnWriteSet) {
- data = ((CopyOnWriteSet) col).data;
- } else {
- data = col.toArray(new Object[col.size()]);
- }
+ public CopyOnWriteSet(CopyOnWriteSet<? extends E> col) {
+ data = col.data;
}
- @Override
+ public CopyOnWriteSet(Collection<? extends E> col) {
+ data = col.toArray(new Object[col.size()]);
+ }
+
public Iterator<E> iterator() {
return new Iterator<E>() {
int idx = 0;
@@ -56,12 +57,10 @@
};
}
- @Override
public int size() {
return data.length;
}
- @Override
public boolean add(E e) {
Object[] d = data;
if (d.length == 0) {
@@ -94,12 +93,49 @@
data = a;
}
+ public Object[] toArray() {
+ return data.clone();
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ int size = data.length;
+ if (a.length < size)
+ // Make a new array of a's runtime type, but my contents:
+ return (T[]) Arrays.copyOf(data, size, a.getClass());
+ System.arraycopy(data, 0, a, 0, size);
+ if (a.length > size)
+ a[size] = null;
+ return a;
+ }
+
@Override
public boolean equals(Object o) {
- if (o instanceof CopyOnWriteSet && ((CopyOnWriteSet) o).data == data) {
+ if (!(o instanceof CopyOnWriteSet)) {
+ return false;
+ }
+ Object[] o1 = data;
+ Object[] o2 = ((CopyOnWriteSet) o).data;
+ if (o1 == o2) {
return true;
}
- return super.equals(o);
+ int l = o1.length;
+ if (l != o2.length) {
+ return false;
+ }
+ loop:
+ for (int i = l; i-- > 0;) {
+ Object v1 = o1[i];
+ for (int j = l; j-- > 0;) {
+ Object v2 = o2[j];
+ if (v1 == v2)
+ continue loop;
+ if (v1 != null && v1.equals(v2))
+ continue loop;
+ }
+ return false;
+ }
+ return true;
}
@Override
@@ -107,4 +143,92 @@
return Arrays.hashCode(data);
}
+ /**
+ * Clone this object
+ *
+ * @return a cloned object.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public CopyOnWriteSet<E> clone() {
+ try {
+ return (CopyOnWriteSet<E>) super.clone();
+ } catch (CloneNotSupportedException exc) {
+ InternalError e = new InternalError();
+ e.initCause(exc);
+ throw e; //should never happen since we are cloneable
+ }
+ }
+
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ public boolean contains(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean remove(Object o) {
+ int index;
+ if ((index = indexOf(o, data, data.length)) >= 0) {
+ remove(index);
+ return true;
+ }
+ return false;
+ }
+
+ private static int indexOf(Object o, Object[] d, int len) {
+ if (o == null) {
+ for (int i = len; i-- > 0;) {
+ if (d[i] == null)
+ return i;
+ }
+ } else {
+ for (int i = len; i-- > 0;) {
+ if (o.equals(d[i]))
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ public boolean containsAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(Collection<? extends E> c) {
+ Object[] cs = c.toArray();
+ if (cs.length == 0)
+ return false;
+ Object[] elements = data;
+ int len = elements.length;
+ int added = 0;
+ // uniquify and compact elements in cs
+ for (int i = 0; i < cs.length; ++i) {
+ Object e = cs[i];
+ if (indexOf(e, elements, len) < 0 &&
+ indexOf(e, cs, added) < 0)
+ cs[added++] = e;
+ }
+ if (added > 0) {
+ Object[] newElements = Arrays.copyOf(elements, len + added);
+ System.arraycopy(cs, 0, newElements, len, added);
+ data = newElements;
+ return true;
+ }
+ return false;
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean removeAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
index 43d0549..edd6823 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
@@ -54,10 +54,10 @@
protected final float f;
protected V defRetValue;
- protected transient volatile Iterable<Map.Entry<K, V>> fast;
- protected transient volatile OpenHashMap.MapEntrySet entries;
- protected transient volatile SortedSet<K> keys;
- protected transient volatile Collection<V> values;
+ protected transient Iterable<Map.Entry<K, V>> fast;
+ protected transient SortedSet<Map.Entry<K, V>> entries;
+ protected transient SortedSet<K> keys;
+ protected transient Collection<V> values;
public OpenHashMap(int expected, float f) {
this.first = -1;
@@ -672,23 +672,28 @@
@SuppressWarnings("unchecked")
public V get(Object k) {
if (k == null) {
- return this.containsNullKey ? (V) this.value[this.n] : this.defRetValue;
- } else {
- Object[] key = this.key;
- Object curr;
- int pos;
- if ((curr = key[pos = mix(k.hashCode()) & this.mask]) == null) {
- return this.defRetValue;
- } else if (k.equals(curr)) {
- return (V) this.value[pos];
- } else {
- while ((curr = key[pos = pos + 1 & this.mask]) != null) {
- if (k.equals(curr)) {
- return (V) this.value[pos];
- }
- }
+ return containsNullKey ? (V) value[n] : defRetValue;
+ }
- return this.defRetValue;
+ final Object[] key = this.key;
+ Object curr;
+ int pos;
+
+ // The starting point
+ if ((curr = key[pos = mix(k.hashCode()) & mask]) == null) {
+ return defRetValue;
+ }
+ if (k.equals(curr)) {
+ return (V) value[pos];
+ }
+
+ // There's always an usused entry
+ while (true) {
+ if ((curr = key[pos = (pos + 1) & mask]) == null) {
+ return defRetValue;
+ }
+ if (k.equals(curr)) {
+ return (V) value[pos];
}
}
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
index 7e87b2c..befcd77 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
@@ -28,10 +28,14 @@
super(initialCapacity);
}
+<<<<<<< HEAD
+=======
+ @SuppressWarnings("unchecked")
+>>>>>>> d6bbce6... Speed up collections a bit
public OpenHashMapList<K, V> deepClone() {
OpenHashMapList<K, V> copy = (OpenHashMapList<K, V>) super.clone();
Object[] values = copy.value;
- for (int i = 0, l = values.length; i < l; i++) {
+ for (int i = values.length; i-- > 0;) {
if (values[i] != null) {
values[i] = new CopyOnWriteList<V>((CopyOnWriteList<V>) values[i]);
}
diff --git a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
index 9e2722d..ff008a4 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
@@ -31,7 +31,7 @@
public OpenHashMapSet<K, V> deepClone() {
OpenHashMapSet<K, V> copy = (OpenHashMapSet<K, V>) super.clone();
Object[] values = copy.value;
- for (int i = 0, l = values.length; i < l; i++) {
+ for (int i = values.length; i-- > 0;) {
if (values[i] != null) {
values[i] = new CopyOnWriteSet<V>((CopyOnWriteSet<V>) values[i]);
}