Speed up JRealClassType.getSubTypes() by implementing an optimized toArray() in our set classes.
Review by: spoon (desk)
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@5341 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java b/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java
index 8430ccd..baec501 100644
--- a/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java
+++ b/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java
@@ -15,8 +15,8 @@
*/
package com.google.gwt.core.ext.typeinfo;
+import com.google.gwt.dev.util.collect.IdentitySets;
import com.google.gwt.dev.util.collect.Lists;
-import com.google.gwt.dev.util.collect.Sets;
import java.lang.annotation.Annotation;
import java.util.List;
@@ -28,7 +28,7 @@
*/
public class JRealClassType extends JClassType {
- private Set<JClassType> allSubtypes = Sets.create();
+ private Set<JClassType> allSubtypes = IdentitySets.create();
private final Annotations annotations = new Annotations();
@@ -410,8 +410,7 @@
}
protected void acceptSubtype(JClassType me) {
- // TODO(scottb): revisit
- allSubtypes = Sets.add(allSubtypes, me);
+ allSubtypes = IdentitySets.add(allSubtypes, me);
notifySuperTypesOf(me);
}
@@ -477,8 +476,7 @@
}
protected void removeSubtype(JClassType me) {
- // TODO(scottb): revisit
- allSubtypes = Sets.remove(allSubtypes, me);
+ allSubtypes = IdentitySets.remove(allSubtypes, me);
if (superclass != null) {
superclass.removeSubtype(me);
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java b/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
index c643d9f..0e7845d 100644
--- a/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
+++ b/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
@@ -408,11 +408,11 @@
}
};
- private static Object maskNullKey(Object k) {
+ static Object maskNullKey(Object k) {
return (k == null) ? NULL_KEY : k;
}
- private static Object unmaskNullKey(Object k) {
+ static Object unmaskNullKey(Object k) {
return (k == NULL_KEY) ? null : k;
}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java b/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
index 58dcc29..8387a35 100644
--- a/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
+++ b/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
@@ -19,6 +19,7 @@
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
+import java.lang.reflect.Array;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
@@ -31,14 +32,6 @@
*/
public class HashSet<E> extends AbstractSet<E> implements Serializable {
- /**
- * In the interest of memory-savings, we start with the smallest feasible
- * power-of-two table size that can hold three items without rehashing. If we
- * started with a size of 2, we'd have to expand as soon as the second item
- * was added.
- */
- private static final int INITIAL_TABLE_SIZE = 4;
-
private class SetIterator implements Iterator<E> {
private int index = 0;
private int last = -1;
@@ -82,17 +75,25 @@
}
}
+ /**
+ * In the interest of memory-savings, we start with the smallest feasible
+ * power-of-two table size that can hold three items without rehashing. If we
+ * started with a size of 2, we'd have to expand as soon as the second item
+ * was added.
+ */
+ private static final int INITIAL_TABLE_SIZE = 4;
+
private static final Object NULL_ITEM = new Serializable() {
Object readResolve() {
return NULL_ITEM;
}
};
- private static Object maskNull(Object o) {
+ static Object maskNull(Object o) {
return (o == null) ? NULL_ITEM : o;
}
- private static Object unmaskNull(Object o) {
+ static Object unmaskNull(Object o) {
return (o == NULL_ITEM) ? null : o;
}
@@ -172,6 +173,30 @@
return size;
}
+ @Override
+ public Object[] toArray() {
+ return toArray(new Object[size]);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public <T> T[] toArray(T[] a) {
+ if (a.length < size) {
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+ }
+ int index = 0;
+ for (int i = 0; i < table.length; ++i) {
+ Object e = table[i];
+ if (e != null) {
+ a[index++] = (T) unmaskNull(e);
+ }
+ }
+ while (index < a.length) {
+ a[index++] = null;
+ }
+ return a;
+ }
+
/**
* Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
*/
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
index 6c1f989..8791f28 100644
--- a/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
+++ b/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
@@ -16,6 +16,7 @@
package com.google.gwt.dev.util.collect;
import java.io.Serializable;
+import java.lang.reflect.Array;
import java.util.AbstractSet;
import java.util.Collections;
import java.util.Iterator;
@@ -29,12 +30,12 @@
*/
public class IdentitySets {
- private static class IdentitySingletonSet<T> extends AbstractSet<T> implements
+ private static class IdentitySingletonSet<E> extends AbstractSet<E> implements
Serializable {
- private final T item;
+ private final E item;
- IdentitySingletonSet(T item) {
+ IdentitySingletonSet(E item) {
this.item = item;
}
@@ -42,15 +43,33 @@
return o == item;
}
- public Iterator<T> iterator() {
- return new SingletonIterator<T>(item);
+ public Iterator<E> iterator() {
+ return new SingletonIterator<E>(item);
}
public int size() {
return 1;
}
- }
+ @Override
+ public Object[] toArray() {
+ return toArray(new Object[1]);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public <T> T[] toArray(T[] a) {
+ if (a.length < 1) {
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), 1);
+ }
+ a[0] = (T) item;
+ int i = 1;
+ while (i < a.length) {
+ a[i++] = null;
+ }
+ return a;
+ }
+ }
private static final class SingletonIterator<T> implements Iterator<T> {
/**
@@ -83,6 +102,10 @@
}
}
+ private static final Class<?> MULTI_SET_CLASS = IdentityHashSet.class;
+
+ private static final Class<?> SINGLETON_SET_CLASS = IdentitySingletonSet.class;
+
public static <T> Set<T> add(Set<T> set, T toAdd) {
switch (set.size()) {
case 0:
@@ -105,17 +128,76 @@
}
}
+ public static <T> Set<T> create() {
+ return Collections.emptySet();
+ }
+
+ public static <T> Set<T> create(T item) {
+ return new IdentitySingletonSet<T>(item);
+ }
+
+ public static <T> Set<T> create(T... items) {
+ switch (items.length) {
+ case 0:
+ return create();
+ case 1:
+ return create(items[0]);
+ default:
+ IdentityHashSet<T> result = new IdentityHashSet<T>();
+ result.addAll(items);
+ return result;
+ }
+ }
+
public static <T> Set<T> normalize(Set<T> set) {
switch (set.size()) {
case 0:
- return Collections.emptySet();
+ return create();
case 1: {
- if (set.getClass() != IdentitySingletonSet.class) {
- return new IdentitySingletonSet<T>(set.iterator().next());
+ if (set.getClass() == SINGLETON_SET_CLASS) {
+ return set;
}
- return set;
+ return create(set.iterator().next());
}
default:
+ if (set.getClass() == MULTI_SET_CLASS) {
+ return set;
+ }
+ IdentityHashSet<T> result = new IdentityHashSet<T>();
+ result.addAll(set);
+ return result;
+ }
+ }
+
+ public static <T> Set<T> normalizeUnmodifiable(Set<T> set) {
+ if (set.size() < 2) {
+ return normalize(set);
+ } else {
+ // TODO: implement an UnmodifiableIdentityHashSet?
+ return Collections.unmodifiableSet(normalize(set));
+ }
+ }
+
+ public static <T> Set<T> remove(Set<T> set, T toRemove) {
+ switch (set.size()) {
+ case 0:
+ // Empty
+ return set;
+ case 1:
+ // Singleton -> Empty
+ if (set.contains(toRemove)) {
+ return create();
+ }
+ return set;
+ case 2:
+ // IdentityHashSet -> Singleton
+ if (set.remove(toRemove)) {
+ return create(set.iterator().next());
+ }
+ return set;
+ default:
+ // IdentityHashSet
+ set.remove(toRemove);
return set;
}
}
diff --git a/dev/core/src/com/google/gwt/dev/util/collect/Sets.java b/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
index be9006c..b98d3d8 100644
--- a/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
+++ b/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
@@ -119,7 +119,7 @@
}
return set;
default:
- // ArrayList
+ // HashSet
set.remove(toRemove);
return set;
}
