Author: sco...@google.com Date: Wed Apr 1 11:15:15 2009 New Revision: 5143
Modified: changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java Log: SQUASH into collections; changes based on feedback from Lex. Modified: changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java ============================================================================== --- changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java (original) +++ changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java Wed Apr 1 11:15:15 2009 @@ -35,6 +35,14 @@ */ public class HashMap<K, V> implements Map<K, V>, 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 EntryIterator implements Iterator<Entry<K, V>> { private int index = 0; private int last = -1; @@ -410,25 +418,28 @@ /** * Backing store for all the keys; transient due to custom serialization. + * Default access to avoid synthetic accessors from inner classes. */ transient Object[] keys; /** - * Number of pairs in this set; transient due to custom serialization. + * Number of pairs in this set; transient due to custom serialization. Default + * access to avoid synthetic accessors from inner classes. */ transient int size = 0; /** * Backing store for all the values; transient due to custom serialization. + * Default access to avoid synthetic accessors from inner classes. */ transient Object[] values; public HashMap() { - initTable(4); + initTable(INITIAL_TABLE_SIZE); } public HashMap(Map<? extends K, ? extends V> m) { - int newCapacity = 4; + int newCapacity = INITIAL_TABLE_SIZE; int expectedSize = m.size(); while (newCapacity * 3 < expectedSize * 4) { newCapacity <<= 1; @@ -439,7 +450,7 @@ } public void clear() { - initTable(4); + initTable(INITIAL_TABLE_SIZE); size = 0; } @@ -601,22 +612,38 @@ } } + /** + * Returns whether two keys are equal for the purposes of this set. + */ protected boolean keyEquals(Object a, Object b) { return (a == null) ? (b == null) : a.equals(b); } + /** + * Returns the hashCode for a key. + */ protected int keyHashCode(Object k) { return (k == null) ? 0 : k.hashCode(); } + /** + * Returns whether two values are equal for the purposes of this set. + */ protected boolean valueEquals(Object a, Object b) { return (a == null) ? (b == null) : a.equals(b); } + /** + * Returns the hashCode for a value. + */ protected int valueHashCode(Object v) { return (v == null) ? 0 : v.hashCode(); } + /** + * Ensures the map is large enough to contain the specified number of entries. + * Default access to avoid synthetic accessors from inner classes. + */ void ensureSizeFor(int expectedSize) { if (keys.length * 3 >= expectedSize * 4) { return; @@ -645,6 +672,11 @@ } } + /** + * Returns the index in the key table at which a particular key resides, or -1 + * if the key is not in the table. Default access to avoid synthetic accessors + * from inner classes. + */ int findKey(Object k) { int index = getKeyIndex(k); while (true) { @@ -661,6 +693,12 @@ } } + /** + * Returns the index in the key table at which a particular key resides, or + * the index of an empty slot in the table where this key should be inserted + * if it is not already in the table. Default access to avoid synthetic + * accessors from inner classes. + */ int findKeyOrEmpty(Object k) { int index = getKeyIndex(k); while (true) { @@ -677,6 +715,11 @@ } } + /** + * Removes the entry at the specified index, and performs internal management + * to make sure we don't wind up with a hole in the table. Default access to + * avoid synthetic accessors from inner classes. + */ void internalRemove(int index) { keys[index] = null; values[index] = null; @@ -685,8 +728,14 @@ } private int getKeyIndex(Object k) { + int h = keyHashCode(k); + // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions. + h += ~(h << 9); + h ^= (h >>> 14); + h += (h << 4); + h ^= (h >>> 10); // Power of two trick. - return keyHashCode(k) & (keys.length - 1); + return h & (keys.length - 1); } private void initTable(int capacity) { Modified: changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java ============================================================================== --- changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java (original) +++ changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java Wed Apr 1 11:15:15 2009 @@ -31,6 +31,14 @@ */ 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; @@ -90,20 +98,22 @@ /** * Number of objects in this set; transient due to custom serialization. + * Default access to avoid synthetic accessors from inner classes. */ transient int size = 0; /** * Backing store for all the objects; transient due to custom serialization. + * Default access to avoid synthetic accessors from inner classes. */ transient Object[] table; public HashSet() { - table = new Object[4]; + table = new Object[INITIAL_TABLE_SIZE]; } public HashSet(Collection<? extends E> c) { - int newCapacity = 4; + int newCapacity = INITIAL_TABLE_SIZE; int expectedSize = c.size(); while (newCapacity * 3 < expectedSize * 4) { newCapacity <<= 1; @@ -133,7 +143,7 @@ @Override public void clear() { - table = new Object[4]; + table = new Object[INITIAL_TABLE_SIZE]; size = 0; } @@ -189,14 +199,24 @@ } } + /** + * Returns whether two items are equal for the purposes of this set. + */ protected boolean itemEquals(Object a, Object b) { return (a == null) ? (b == null) : a.equals(b); } + /** + * Return the hashCode for an item. + */ protected int itemHashCode(Object o) { return (o == null) ? 0 : o.hashCode(); } + /** + * Works just like {...@link #addAll(Collection)}, but for arrays. Used to avoid + * having to synthesize a collection in {...@link Sets}. + */ void addAll(E[] elements) { ensureSizeFor(size + elements.length); for (E e : elements) { @@ -208,7 +228,21 @@ } } - void ensureSizeFor(int expectedSize) { + /** + * Removes the item at the specified index, and performs internal management + * to make sure we don't wind up with a hole in the table. Default access to + * avoid synthetic accessors from inner classes. + */ + void internalRemove(int index) { + table[index] = null; + --size; + plugHole(index); + } + + /** + * Ensures the set is large enough to contain the specified number of entries. + */ + private void ensureSizeFor(int expectedSize) { if (table.length * 3 >= expectedSize * 4) { return; } @@ -233,7 +267,11 @@ } } - int find(Object o) { + /** + * Returns the index in the table at which a particular item resides, or -1 if + * the item is not in the table. + */ + private int find(Object o) { int index = getIndex(o); while (true) { Object existing = table[index]; @@ -249,7 +287,12 @@ } } - int findOrEmpty(Object o) { + /** + * Returns the index in the table at which a particular item resides, or the + * index of an empty slot in the table where this item should be inserted if + * it is not already in the table. + */ + private int findOrEmpty(Object o) { int index = getIndex(o); while (true) { Object existing = table[index]; @@ -265,15 +308,15 @@ } } - void internalRemove(int index) { - table[index] = null; - --size; - plugHole(index); - } - private int getIndex(Object o) { + int h = itemHashCode(o); + // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions. + h += ~(h << 9); + h ^= (h >>> 14); + h += (h << 4); + h ^= (h >>> 10); // Power of two trick. - return itemHashCode(o) & (table.length - 1); + return h & (table.length - 1); } /** Modified: changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java ============================================================================== --- changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java (original) +++ changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java Wed Apr 1 11:15:15 2009 @@ -53,6 +53,9 @@ private static final class SingletonIterator<T> implements Iterator<T> { + /** + * Sentinel value to mark that this iterator's single item was consumed. + */ private static final Object EMPTY = new Object(); private T item; @@ -110,7 +113,7 @@ if (set.getClass() != IdentitySingletonSet.class) { return new IdentitySingletonSet<T>(set.iterator().next()); } - // intentional fall-through + return set; } default: return set; Modified: changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java ============================================================================== --- changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java (original) +++ changes/scottb/memory/dev/core/src/com/google/gwt/dev/util/collect/IdentitySingletonMap.java Wed Apr 1 11:15:15 2009 @@ -25,21 +25,18 @@ private class IdentityEntry implements Entry<K, V> { @Override - @SuppressWarnings("unchecked") public boolean equals(Object o) { if (!(o instanceof Entry)) { return false; } - Entry<K, V> entry = (Entry<K, V>) o; + Entry<?, ?> entry = (Entry<?, ?>) o; return key == entry.getKey() && value == entry.getValue(); } - @SuppressWarnings("unchecked") public K getKey() { return key; } - @SuppressWarnings("unchecked") public V getValue() { return value; } @@ -59,7 +56,16 @@ } } + /** + * The key for the single entry. Default access to avoid synthetic accessors + * from inner classes. + */ final K key; + + /** + * The value for the single entry. Default access to avoid synthetic accessors + * from inner classes. + */ final V value; public IdentitySingletonMap(K key, V value) { @@ -93,7 +99,6 @@ return entrySet().equals(other.entrySet()); } - @SuppressWarnings("unchecked") public V get(Object k) { return (key == k) ? value : null; } --~--~---------~--~----~------------~-------~--~----~ http://groups.google.com/group/Google-Web-Toolkit-Contributors -~----------~----~----~----~------~----~------~--~---