Author: gnodet
Date: Mon Jul 13 15:19:30 2015
New Revision: 1690730
URL: http://svn.apache.org/r1690730
Log:
[FELIX-4942] Speed up collections a bit
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/ArrayMap.java
Mon Jul 13 15:19:30 2015
@@ -21,11 +21,12 @@ package org.apache.felix.resolver.util;
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 @@ public class ArrayMap<K, V> extends Abst
return index < size;
}
+ @SuppressWarnings("unchecked")
public V next() {
if (index >= size) {
throw new NoSuchElementException();
@@ -152,7 +154,7 @@ public class ArrayMap<K, V> extends Abst
return index < size;
}
- public Entry<K, V> next() {
+ public FastEntry next() {
if (index >= size) {
throw new NoSuchElementException();
}
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteList.java
Mon Jul 13 15:19:30 2015
@@ -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 @@ public class CopyOnWriteList<T> extends
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;
+ }
+
+ public CopyOnWriteList(Collection<? extends E> col) {
+ data = col.toArray(new Object[col.size()]);
}
- @Override
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 @@ public class CopyOnWriteList<T> extends
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 @@ public class CopyOnWriteList<T> extends
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;
+ }
}
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/CopyOnWriteSet.java
Mon Jul 13 15:19:30 2015
@@ -22,8 +22,10 @@ import java.util.AbstractSet;
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 @@ public class CopyOnWriteSet<E> extends A
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;
+ }
+
+ public CopyOnWriteSet(Collection<? extends E> col) {
+ data = col.toArray(new Object[col.size()]);
}
- @Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int idx = 0;
@@ -56,12 +57,10 @@ public class CopyOnWriteSet<E> extends A
};
}
- @Override
public int size() {
return data.length;
}
- @Override
public boolean add(E e) {
Object[] d = data;
if (d.length == 0) {
@@ -94,12 +93,49 @@ public class CopyOnWriteSet<E> extends A
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 @@ public class CopyOnWriteSet<E> extends A
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();
+ }
+
}
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMap.java
Mon Jul 13 15:19:30 2015
@@ -54,10 +54,10 @@ public class OpenHashMap<K, V> implement
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 @@ public class OpenHashMap<K, V> implement
@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];
}
}
}
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapList.java
Mon Jul 13 15:19:30 2015
@@ -28,10 +28,14 @@ public class OpenHashMapList<K, V> exten
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]);
}
Modified:
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
URL:
http://svn.apache.org/viewvc/felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java?rev=1690730&r1=1690729&r2=1690730&view=diff
==============================================================================
---
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
(original)
+++
felix/trunk/resolver/src/main/java/org/apache/felix/resolver/util/OpenHashMapSet.java
Mon Jul 13 15:19:30 2015
@@ -31,7 +31,7 @@ public class OpenHashMapSet<K, V> extend
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]);
}
