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