From 62d708f4dd8e2a8554df4967837df9896efeff7c Mon Sep 17 00:00:00 2001
From: Dianne Hackborn
Date: Thu, 25 Jul 2013 16:42:59 -0700
Subject: [PATCH] Okay, I give in, add null key support to ArrayMap and
ArraySet.
Change-Id: Iac5035f9c5884a9f9d5acb38132bb128d7a55249
---
core/java/android/util/ArrayMap.java | 76 +++++++++++++++++-----
core/java/android/util/ArraySet.java | 70 ++++++++++++++++----
.../android/test/activity/ArrayMapTests.java | 28 +++++---
3 files changed, 133 insertions(+), 41 deletions(-)
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index 22f62d70980a..fa534cc8f502 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -36,9 +36,6 @@ import java.util.Set;
* and deleting entries in the array. For containers holding up to hundreds of items,
* the performance difference is not significant, less than 50%.
*
- * Note: unlike {@link java.util.HashMap}, this container does not support
- * null keys.
- *
* Because this container is intended to better balance memory use, unlike most other
* standard Java containers it will shrink its array as items are removed from it. Currently
* you have no control over this shrinking -- if you set a capacity and then remove an
@@ -86,7 +83,7 @@ public final class ArrayMap implements Map {
int mSize;
MapCollections mCollections;
- private int indexOf(Object key, int hash) {
+ int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
@@ -102,19 +99,57 @@ public final class ArrayMap implements Map {
}
// If the key at the returned index matches, that's what we want.
- if (mArray[index<<1].equals(key)) {
+ if (key.equals(mArray[index<<1])) {
return index;
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
- if (mArray[end << 1].equals(key)) return end;
+ if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
- if (mArray[i << 1].equals(key)) return i;
+ if (key.equals(mArray[i << 1])) return i;
+ }
+
+ // Key not found -- return negative value indicating where a
+ // new entry for this key should go. We use the end of the
+ // hash chain to reduce the number of array entries that will
+ // need to be copied when inserting.
+ return ~end;
+ }
+
+ int indexOfNull() {
+ final int N = mSize;
+
+ // Important fast case: if nothing is in here, nothing to look for.
+ if (N == 0) {
+ return ~0;
+ }
+
+ int index = ContainerHelpers.binarySearch(mHashes, N, 0);
+
+ // If the hash code wasn't found, then we have no entry for this key.
+ if (index < 0) {
+ return index;
+ }
+
+ // If the key at the returned index matches, that's what we want.
+ if (null == mArray[index<<1]) {
+ return index;
+ }
+
+ // Search for a matching key after the index.
+ int end;
+ for (end = index + 1; end < N && mHashes[end] == 0; end++) {
+ if (null == mArray[end << 1]) return end;
+ }
+
+ // Search for a matching key before the index.
+ for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
+ if (null == mArray[i << 1]) return i;
}
// Key not found -- return negative value indicating where a
@@ -285,10 +320,10 @@ public final class ArrayMap implements Map {
*/
@Override
public boolean containsKey(Object key) {
- return indexOf(key, key.hashCode()) >= 0;
+ return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0);
}
- private int indexOfValue(Object value) {
+ int indexOfValue(Object value) {
final int N = mSize*2;
final Object[] array = mArray;
if (value == null) {
@@ -327,7 +362,7 @@ public final class ArrayMap implements Map {
*/
@Override
public V get(Object key) {
- final int index = indexOf(key, key.hashCode());
+ final int index = key == null ? indexOfNull() : indexOf(key, key.hashCode());
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
@@ -380,8 +415,15 @@ public final class ArrayMap implements Map {
*/
@Override
public V put(K key, V value) {
- final int hash = key.hashCode();
- int index = indexOf(key, hash);
+ final int hash;
+ int index;
+ if (key == null) {
+ hash = 0;
+ index = indexOfNull();
+ } else {
+ hash = key.hashCode();
+ index = indexOf(key, hash);
+ }
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
@@ -430,7 +472,7 @@ public final class ArrayMap implements Map {
*/
public void append(K key, V value) {
int index = mSize;
- final int hash = key.hashCode();
+ final int hash = key == null ? 0 : key.hashCode();
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
@@ -478,7 +520,7 @@ public final class ArrayMap implements Map {
*/
@Override
public V remove(Object key) {
- int index = indexOf(key, key.hashCode());
+ int index = key == null ? indexOfNull() : indexOf(key, key.hashCode());
if (index >= 0) {
return removeAt(index);
}
@@ -492,7 +534,7 @@ public final class ArrayMap implements Map {
* @return Returns the value that was stored at this index.
*/
public V removeAt(int index) {
- final V old = (V)mArray[(index << 1) + 1];
+ final Object old = mArray[(index << 1) + 1];
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
@@ -539,7 +581,7 @@ public final class ArrayMap implements Map {
mArray[(mSize << 1) + 1] = null;
}
}
- return old;
+ return (V)old;
}
/**
@@ -664,7 +706,7 @@ public final class ArrayMap implements Map {
@Override
protected int colIndexOfKey(Object key) {
- return indexOf(key, key.hashCode());
+ return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}
@Override
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index 1648ec925c62..3c695e906647 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -35,9 +35,6 @@ import java.util.Set;
* and deleting entries in the array. For containers holding up to hundreds of items,
* the performance difference is not significant, less than 50%.
*
- * Note: unlike {@link java.util.HashSet}, this container does not support
- * null values.
- *
* Because this container is intended to better balance memory use, unlike most other
* standard Java containers it will shrink its array as items are removed from it. Currently
* you have no control over this shrinking -- if you set a capacity and then remove an
@@ -93,19 +90,57 @@ public final class ArraySet implements Collection, Set {
}
// If the key at the returned index matches, that's what we want.
- if (mArray[index].equals(key)) {
+ if (key.equals(mArray[index])) {
return index;
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
- if (mArray[end].equals(key)) return end;
+ if (key.equals(mArray[end])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
- if (mArray[i].equals(key)) return i;
+ if (key.equals(mArray[i])) return i;
+ }
+
+ // Key not found -- return negative value indicating where a
+ // new entry for this key should go. We use the end of the
+ // hash chain to reduce the number of array entries that will
+ // need to be copied when inserting.
+ return ~end;
+ }
+
+ private int indexOfNull() {
+ final int N = mSize;
+
+ // Important fast case: if nothing is in here, nothing to look for.
+ if (N == 0) {
+ return ~0;
+ }
+
+ int index = ContainerHelpers.binarySearch(mHashes, N, 0);
+
+ // If the hash code wasn't found, then we have no entry for this key.
+ if (index < 0) {
+ return index;
+ }
+
+ // If the key at the returned index matches, that's what we want.
+ if (null == mArray[index]) {
+ return index;
+ }
+
+ // Search for a matching key after the index.
+ int end;
+ for (end = index + 1; end < N && mHashes[end] == 0; end++) {
+ if (null == mArray[end]) return end;
+ }
+
+ // Search for a matching key before the index.
+ for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
+ if (null == mArray[i]) return i;
}
// Key not found -- return negative value indicating where a
@@ -254,7 +289,7 @@ public final class ArraySet implements Collection, Set {
*/
@Override
public boolean contains(Object key) {
- return indexOf(key, key.hashCode()) >= 0;
+ return key == null ? (indexOfNull() >= 0) : (indexOf(key, key.hashCode()) >= 0);
}
/**
@@ -285,8 +320,15 @@ public final class ArraySet implements Collection, Set {
*/
@Override
public boolean add(E value) {
- final int hash = value.hashCode();
- int index = indexOf(value, hash);
+ final int hash;
+ int index;
+ if (value == null) {
+ hash = 0;
+ index = indexOfNull();
+ } else {
+ hash = value.hashCode();
+ index = indexOf(value, hash);
+ }
if (index >= 0) {
return false;
}
@@ -352,7 +394,7 @@ public final class ArraySet implements Collection, Set {
*/
@Override
public boolean remove(Object object) {
- int index = indexOf(object, object.hashCode());
+ int index = object == null ? indexOfNull() : indexOf(object, object.hashCode());
if (index >= 0) {
removeAt(index);
return true;
@@ -366,7 +408,7 @@ public final class ArraySet implements Collection, Set {
* @return Returns the value that was stored at this index.
*/
public E removeAt(int index) {
- final E old = (E)mArray[index];
+ final Object old = mArray[index];
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
@@ -410,7 +452,7 @@ public final class ArraySet implements Collection, Set {
mArray[mSize] = null;
}
}
- return old;
+ return (E)old;
}
/**
@@ -542,12 +584,12 @@ public final class ArraySet implements Collection, Set {
@Override
protected int colIndexOfKey(Object key) {
- return indexOf(key, key.hashCode());
+ return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}
@Override
protected int colIndexOfValue(Object value) {
- return indexOf(value, value.hashCode());
+ return value == null ? indexOfNull() : indexOf(value, value.hashCode());
}
@Override
diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
index 9b54927a357a..28e86bf502a0 100644
--- a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
+++ b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
@@ -48,15 +48,17 @@ public class ArrayMapTests {
OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+ OP_ADD, OP_ADD, OP_ADD,
OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+ OP_REM, OP_REM, OP_REM,
OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
};
static int[] KEYS = new int[] {
// General adding and removing.
- 100, 1900, 600, 200, 1200, 1500, 1800, 100, 1900,
+ -1, 1900, 600, 200, 1200, 1500, 1800, 100, 1900,
2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400,
- 600, 100, 1900, 600, 300, 2100, 200, 800, 800,
+ 600, -1, 1900, 600, 300, 2100, 200, 800, 800,
1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900,
// Shrink when removing item from end.
@@ -74,7 +76,9 @@ public class ArrayMapTests {
// Test hash collisions.
105, 106, 108, 104, 102, 102, 107, 5, 205,
4, 202, 203, 3, 5, 101, 109, 200, 201,
+ 0, -1, 100,
106, 108, 104, 102, 103, 105, 107, 101, 109,
+ -1, 100, 0,
4, 5, 3, 5, 200, 203, 202, 201, 205,
};
@@ -87,6 +91,9 @@ public class ArrayMapTests {
@Override
public final boolean equals(Object o) {
+ if (o == null) {
+ return false;
+ }
return mValue == ((ControlledHash)o).mValue;
}
@@ -277,20 +284,21 @@ public class ArrayMapTests {
Integer oldArray;
boolean hashChanged;
boolean arrayChanged;
+ ControlledHash key = KEYS[i] < 0 ? null : new ControlledHash(KEYS[i]);
switch (OPS[i]) {
case OP_ADD:
Log.i("test", "Adding key: " + KEYS[i]);
- oldHash = hashMap.put(new ControlledHash(KEYS[i]), i);
- oldArray = arrayMap.put(new ControlledHash(KEYS[i]), i);
- hashChanged = hashSet.add(new ControlledHash(KEYS[i]));
- arrayChanged = arraySet.add(new ControlledHash(KEYS[i]));
+ oldHash = hashMap.put(key, i);
+ oldArray = arrayMap.put(key, i);
+ hashChanged = hashSet.add(key);
+ arrayChanged = arraySet.add(key);
break;
case OP_REM:
Log.i("test", "Removing key: " + KEYS[i]);
- oldHash = hashMap.remove(new ControlledHash(KEYS[i]));
- oldArray = arrayMap.remove(new ControlledHash(KEYS[i]));
- hashChanged = hashSet.remove(new ControlledHash(KEYS[i]));
- arrayChanged = arraySet.remove(new ControlledHash(KEYS[i]));
+ oldHash = hashMap.remove(key);
+ oldArray = arrayMap.remove(key);
+ hashChanged = hashSet.remove(key);
+ arrayChanged = arraySet.remove(key);
break;
default:
Log.e("test", "Bad operation " + OPS[i] + " @ " + i);
--
2.11.0