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
-~----------~----~----~----~------~----~------~--~---
