Author: sco...@google.com Date: Mon May 11 17:08:49 2009 New Revision: 5341
Modified: trunk/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java Log: Speed up JRealClassType.getSubTypes() by implementing an optimized toArray() in our set classes. Review by: spoon (desk) Modified: trunk/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java ============================================================================== --- trunk/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java (original) +++ trunk/dev/core/src/com/google/gwt/core/ext/typeinfo/JRealClassType.java Mon May 11 17:08:49 2009 @@ -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); Modified: trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java ============================================================================== --- trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java (original) +++ trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java Mon May 11 17:08:49 2009 @@ -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; } Modified: trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java ============================================================================== --- trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java (original) +++ trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java Mon May 11 17:08:49 2009 @@ -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; } @@ -170,6 +171,30 @@ @Override public int size() { 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; } /** Modified: trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java ============================================================================== --- trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java (original) +++ trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java Mon May 11 17:08:49 2009 @@ -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; } } Modified: trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java ============================================================================== --- trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java (original) +++ trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java Mon May 11 17:08:49 2009 @@ -119,7 +119,7 @@ } return set; default: - // ArrayList + // HashSet set.remove(toRemove); return set; } --~--~---------~--~----~------------~-------~--~----~ http://groups.google.com/group/Google-Web-Toolkit-Contributors -~----------~----~----~----~------~----~------~--~---