summaryrefslogtreecommitdiff
path: root/libutils
diff options
context:
space:
mode:
authorSergio Giro <sgiro@google.com>2015-10-01 18:59:59 +0000
committerAndroid Git Automerger <android-git-automerger@android.com>2015-10-01 18:59:59 +0000
commit075f690dae125375a67eddce577fa6d8f6028711 (patch)
tree654dfb85cc538d75e3d860bb6e4f402ab5b120c6 /libutils
parent9625980058e2a2a3153a0311f2b98f20eec4f62d (diff)
parentbdae9bf2ec3bbf8e33a34caa412bd8fd7bc2d434 (diff)
am bdae9bf2: resolved conflicts for 70808827 to stage-aosp-master
* commit 'bdae9bf2ec3bbf8e33a34caa412bd8fd7bc2d434': system/core: remove BasicHashtable
Diffstat (limited to 'libutils')
-rw-r--r--libutils/Android.mk1
-rw-r--r--libutils/BasicHashtable.cpp350
-rw-r--r--libutils/tests/Android.mk1
-rw-r--r--libutils/tests/BasicHashtable_test.cpp582
4 files changed, 0 insertions, 934 deletions
diff --git a/libutils/Android.mk b/libutils/Android.mk
index 13c2964a5..631b5a3b4 100644
--- a/libutils/Android.mk
+++ b/libutils/Android.mk
@@ -15,7 +15,6 @@
LOCAL_PATH:= $(call my-dir)
commonSources:= \
- BasicHashtable.cpp \
CallStack.cpp \
FileMap.cpp \
JenkinsHash.cpp \
diff --git a/libutils/BasicHashtable.cpp b/libutils/BasicHashtable.cpp
deleted file mode 100644
index 1e9f05333..000000000
--- a/libutils/BasicHashtable.cpp
+++ /dev/null
@@ -1,350 +0,0 @@
-/*
- * Copyright (C) 2011 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#define LOG_TAG "BasicHashtable"
-
-#include <math.h>
-
-#include <utils/Log.h>
-#include <utils/BasicHashtable.h>
-#include <utils/misc.h>
-
-#include "SharedBuffer.h"
-
-namespace android {
-
-BasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor,
- size_t minimumInitialCapacity, float loadFactor) :
- mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor),
- mLoadFactor(loadFactor), mSize(0),
- mFilledBuckets(0), mBuckets(NULL) {
- determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity);
-}
-
-BasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) :
- mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor),
- mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor),
- mSize(other.mSize), mFilledBuckets(other.mFilledBuckets),
- mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) {
- if (mBuckets) {
- SharedBuffer::bufferFromData(mBuckets)->acquire();
- }
-}
-
-BasicHashtableImpl::~BasicHashtableImpl()
-{
-}
-
-void BasicHashtableImpl::edit() {
- if (mBuckets && !SharedBuffer::bufferFromData(mBuckets)->onlyOwner()) {
- clone();
- }
-}
-
-void BasicHashtableImpl::dispose() {
- if (mBuckets) {
- releaseBuckets(mBuckets, mBucketCount);
- }
-}
-
-void BasicHashtableImpl::clone() {
- if (mBuckets) {
- void* newBuckets = allocateBuckets(mBucketCount);
- copyBuckets(mBuckets, newBuckets, mBucketCount);
- releaseBuckets(mBuckets, mBucketCount);
- mBuckets = newBuckets;
- }
-}
-
-void BasicHashtableImpl::setTo(const BasicHashtableImpl& other) {
- if (mBuckets) {
- releaseBuckets(mBuckets, mBucketCount);
- }
-
- mCapacity = other.mCapacity;
- mLoadFactor = other.mLoadFactor;
- mSize = other.mSize;
- mFilledBuckets = other.mFilledBuckets;
- mBucketCount = other.mBucketCount;
- mBuckets = other.mBuckets;
-
- if (mBuckets) {
- SharedBuffer::bufferFromData(mBuckets)->acquire();
- }
-}
-
-void BasicHashtableImpl::clear() {
- if (mBuckets) {
- if (mFilledBuckets) {
- SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets);
- if (sb->onlyOwner()) {
- destroyBuckets(mBuckets, mBucketCount);
- for (size_t i = 0; i < mBucketCount; i++) {
- Bucket& bucket = bucketAt(mBuckets, i);
- bucket.cookie = 0;
- }
- } else {
- releaseBuckets(mBuckets, mBucketCount);
- mBuckets = NULL;
- }
- mFilledBuckets = 0;
- }
- mSize = 0;
- }
-}
-
-ssize_t BasicHashtableImpl::next(ssize_t index) const {
- if (mSize) {
- while (size_t(++index) < mBucketCount) {
- const Bucket& bucket = bucketAt(mBuckets, index);
- if (bucket.cookie & Bucket::PRESENT) {
- return index;
- }
- }
- }
- return -1;
-}
-
-ssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash,
- const void* __restrict__ key) const {
- if (!mSize) {
- return -1;
- }
-
- hash = trimHash(hash);
- if (index < 0) {
- index = chainStart(hash, mBucketCount);
-
- const Bucket& bucket = bucketAt(mBuckets, size_t(index));
- if (bucket.cookie & Bucket::PRESENT) {
- if (compareBucketKey(bucket, key)) {
- return index;
- }
- } else {
- if (!(bucket.cookie & Bucket::COLLISION)) {
- return -1;
- }
- }
- }
-
- size_t inc = chainIncrement(hash, mBucketCount);
- for (;;) {
- index = chainSeek(index, inc, mBucketCount);
-
- const Bucket& bucket = bucketAt(mBuckets, size_t(index));
- if (bucket.cookie & Bucket::PRESENT) {
- if ((bucket.cookie & Bucket::HASH_MASK) == hash
- && compareBucketKey(bucket, key)) {
- return index;
- }
- }
- if (!(bucket.cookie & Bucket::COLLISION)) {
- return -1;
- }
- }
-}
-
-size_t BasicHashtableImpl::add(hash_t hash, const void* entry) {
- if (!mBuckets) {
- mBuckets = allocateBuckets(mBucketCount);
- } else {
- edit();
- }
-
- hash = trimHash(hash);
- for (;;) {
- size_t index = chainStart(hash, mBucketCount);
- Bucket* bucket = &bucketAt(mBuckets, size_t(index));
- if (bucket->cookie & Bucket::PRESENT) {
- size_t inc = chainIncrement(hash, mBucketCount);
- do {
- bucket->cookie |= Bucket::COLLISION;
- index = chainSeek(index, inc, mBucketCount);
- bucket = &bucketAt(mBuckets, size_t(index));
- } while (bucket->cookie & Bucket::PRESENT);
- }
-
- uint32_t collision = bucket->cookie & Bucket::COLLISION;
- if (!collision) {
- if (mFilledBuckets >= mCapacity) {
- rehash(mCapacity * 2, mLoadFactor);
- continue;
- }
- mFilledBuckets += 1;
- }
-
- bucket->cookie = collision | Bucket::PRESENT | hash;
- mSize += 1;
- initializeBucketEntry(*bucket, entry);
- return index;
- }
-}
-
-void BasicHashtableImpl::removeAt(size_t index) {
- edit();
-
- Bucket& bucket = bucketAt(mBuckets, index);
- bucket.cookie &= ~Bucket::PRESENT;
- if (!(bucket.cookie & Bucket::COLLISION)) {
- mFilledBuckets -= 1;
- }
- mSize -= 1;
- if (!mHasTrivialDestructor) {
- destroyBucketEntry(bucket);
- }
-}
-
-void BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) {
- if (minimumCapacity < mSize) {
- minimumCapacity = mSize;
- }
- size_t newBucketCount, newCapacity;
- determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity);
-
- if (newBucketCount != mBucketCount || newCapacity != mCapacity) {
- if (mBuckets) {
- void* newBuckets;
- if (mSize) {
- newBuckets = allocateBuckets(newBucketCount);
- for (size_t i = 0; i < mBucketCount; i++) {
- const Bucket& fromBucket = bucketAt(mBuckets, i);
- if (fromBucket.cookie & Bucket::PRESENT) {
- hash_t hash = fromBucket.cookie & Bucket::HASH_MASK;
- size_t index = chainStart(hash, newBucketCount);
- Bucket* toBucket = &bucketAt(newBuckets, size_t(index));
- if (toBucket->cookie & Bucket::PRESENT) {
- size_t inc = chainIncrement(hash, newBucketCount);
- do {
- toBucket->cookie |= Bucket::COLLISION;
- index = chainSeek(index, inc, newBucketCount);
- toBucket = &bucketAt(newBuckets, size_t(index));
- } while (toBucket->cookie & Bucket::PRESENT);
- }
- toBucket->cookie = Bucket::PRESENT | hash;
- initializeBucketEntry(*toBucket, fromBucket.entry);
- }
- }
- } else {
- newBuckets = NULL;
- }
- releaseBuckets(mBuckets, mBucketCount);
- mBuckets = newBuckets;
- mFilledBuckets = mSize;
- }
- mBucketCount = newBucketCount;
- mCapacity = newCapacity;
- }
- mLoadFactor = loadFactor;
-}
-
-void* BasicHashtableImpl::allocateBuckets(size_t count) const {
- size_t bytes = count * mBucketSize;
- SharedBuffer* sb = SharedBuffer::alloc(bytes);
- LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.",
- uint32_t(bytes), uint32_t(count));
- void* buckets = sb->data();
- for (size_t i = 0; i < count; i++) {
- Bucket& bucket = bucketAt(buckets, i);
- bucket.cookie = 0;
- }
- return buckets;
-}
-
-void BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const {
- SharedBuffer* sb = SharedBuffer::bufferFromData(buckets);
- if (sb->release(SharedBuffer::eKeepStorage) == 1) {
- destroyBuckets(buckets, count);
- SharedBuffer::dealloc(sb);
- }
-}
-
-void BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const {
- if (!mHasTrivialDestructor) {
- for (size_t i = 0; i < count; i++) {
- Bucket& bucket = bucketAt(buckets, i);
- if (bucket.cookie & Bucket::PRESENT) {
- destroyBucketEntry(bucket);
- }
- }
- }
-}
-
-void BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets,
- void* __restrict__ toBuckets, size_t count) const {
- for (size_t i = 0; i < count; i++) {
- const Bucket& fromBucket = bucketAt(fromBuckets, i);
- Bucket& toBucket = bucketAt(toBuckets, i);
- toBucket.cookie = fromBucket.cookie;
- if (fromBucket.cookie & Bucket::PRESENT) {
- initializeBucketEntry(toBucket, fromBucket.entry);
- }
- }
-}
-
-// Table of 31-bit primes where each prime is no less than twice as large
-// as the previous one. Generated by "primes.py".
-static size_t PRIMES[] = {
- 5,
- 11,
- 23,
- 47,
- 97,
- 197,
- 397,
- 797,
- 1597,
- 3203,
- 6421,
- 12853,
- 25717,
- 51437,
- 102877,
- 205759,
- 411527,
- 823117,
- 1646237,
- 3292489,
- 6584983,
- 13169977,
- 26339969,
- 52679969,
- 105359939,
- 210719881,
- 421439783,
- 842879579,
- 1685759167,
- 0,
-};
-
-void BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor,
- size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) {
- LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f,
- "Invalid load factor %0.3f. Must be in the range (0, 1].", loadFactor);
-
- size_t count = ceilf(minimumCapacity / loadFactor) + 1;
- size_t i = 0;
- while (count > PRIMES[i] && i < NELEM(PRIMES)) {
- i++;
- }
- count = PRIMES[i];
- LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for "
- "hashtable with minimum capacity %u and load factor %0.3f.",
- uint32_t(minimumCapacity), loadFactor);
- *outBucketCount = count;
- *outCapacity = ceilf((count - 1) * loadFactor);
-}
-
-}; // namespace android
diff --git a/libutils/tests/Android.mk b/libutils/tests/Android.mk
index d4a45fd72..47415ab05 100644
--- a/libutils/tests/Android.mk
+++ b/libutils/tests/Android.mk
@@ -22,7 +22,6 @@ include $(CLEAR_VARS)
LOCAL_MODULE := libutils_tests
LOCAL_SRC_FILES := \
- BasicHashtable_test.cpp \
BlobCache_test.cpp \
BitSet_test.cpp \
Looper_test.cpp \
diff --git a/libutils/tests/BasicHashtable_test.cpp b/libutils/tests/BasicHashtable_test.cpp
deleted file mode 100644
index 4b3a71728..000000000
--- a/libutils/tests/BasicHashtable_test.cpp
+++ /dev/null
@@ -1,582 +0,0 @@
-/*
- * Copyright (C) 2011 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#define LOG_TAG "BasicHashtable_test"
-
-#include <utils/BasicHashtable.h>
-#include <cutils/log.h>
-#include <gtest/gtest.h>
-#include <unistd.h>
-
-namespace {
-
-typedef int SimpleKey;
-typedef int SimpleValue;
-typedef android::key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry;
-typedef android::BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable;
-
-struct ComplexKey {
- int k;
-
- explicit ComplexKey(int k) : k(k) {
- instanceCount += 1;
- }
-
- ComplexKey(const ComplexKey& other) : k(other.k) {
- instanceCount += 1;
- }
-
- ~ComplexKey() {
- instanceCount -= 1;
- }
-
- bool operator ==(const ComplexKey& other) const {
- return k == other.k;
- }
-
- bool operator !=(const ComplexKey& other) const {
- return k != other.k;
- }
-
- static ssize_t instanceCount;
-};
-
-ssize_t ComplexKey::instanceCount = 0;
-
-struct ComplexValue {
- int v;
-
- explicit ComplexValue(int v) : v(v) {
- instanceCount += 1;
- }
-
- ComplexValue(const ComplexValue& other) : v(other.v) {
- instanceCount += 1;
- }
-
- ~ComplexValue() {
- instanceCount -= 1;
- }
-
- static ssize_t instanceCount;
-};
-
-ssize_t ComplexValue::instanceCount = 0;
-
-} // namespace
-
-
-namespace android {
-
-typedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry;
-typedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable;
-
-template<> inline hash_t hash_type(const ComplexKey& value) {
- return hash_type(value.k);
-}
-
-class BasicHashtableTest : public testing::Test {
-protected:
- virtual void SetUp() {
- ComplexKey::instanceCount = 0;
- ComplexValue::instanceCount = 0;
- }
-
- virtual void TearDown() {
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
- }
-
- void assertInstanceCount(ssize_t keys, ssize_t values) {
- if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
- FAIL() << "Expected " << keys << " keys and " << values << " values "
- "but there were actually " << ComplexKey::instanceCount << " keys and "
- << ComplexValue::instanceCount << " values";
- }
- }
-
-public:
- template <typename TKey, typename TEntry>
- static void cookieAt(const BasicHashtable<TKey, TEntry>& h, size_t index,
- bool* collision, bool* present, hash_t* hash) {
- uint32_t cookie = h.cookieAt(index);
- *collision = cookie & BasicHashtable<TKey, TEntry>::Bucket::COLLISION;
- *present = cookie & BasicHashtable<TKey, TEntry>::Bucket::PRESENT;
- *hash = cookie & BasicHashtable<TKey, TEntry>::Bucket::HASH_MASK;
- }
-
- template <typename TKey, typename TEntry>
- static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) {
- return h.mBuckets;
- }
-};
-
-template <typename TKey, typename TValue>
-static size_t add(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
- const TKey& key, const TValue& value) {
- return h.add(hash_type(key), key_value_pair_t<TKey, TValue>(key, value));
-}
-
-template <typename TKey, typename TValue>
-static ssize_t find(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
- ssize_t index, const TKey& key) {
- return h.find(index, hash_type(key), key);
-}
-
-template <typename TKey, typename TValue>
-static bool remove(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
- const TKey& key) {
- ssize_t index = find(h, -1, key);
- if (index >= 0) {
- h.removeAt(index);
- return true;
- }
- return false;
-}
-
-template <typename TEntry>
-static void getKeyValue(const TEntry& entry, int* key, int* value);
-
-template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) {
- *key = entry.key;
- *value = entry.value;
-}
-
-template <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) {
- *key = entry.key.k;
- *value = entry.value.v;
-}
-
-template <typename TKey, typename TValue>
-static void dump(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h) {
- ALOGD("hashtable %p, size=%u, capacity=%u, bucketCount=%u",
- &h, h.size(), h.capacity(), h.bucketCount());
- for (size_t i = 0; i < h.bucketCount(); i++) {
- bool collision, present;
- hash_t hash;
- BasicHashtableTest::cookieAt(h, i, &collision, &present, &hash);
- if (present) {
- int key, value;
- getKeyValue(h.entryAt(i), &key, &value);
- ALOGD(" [%3u] = collision=%d, present=%d, hash=0x%08x, key=%3d, value=%3d, "
- "hash_type(key)=0x%08x",
- i, collision, present, hash, key, value, hash_type(key));
- } else {
- ALOGD(" [%3u] = collision=%d, present=%d",
- i, collision, present);
- }
- }
-}
-
-TEST_F(BasicHashtableTest, DefaultConstructor_WithDefaultProperties) {
- SimpleHashtable h;
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Constructor_WithNonUnityLoadFactor) {
- SimpleHashtable h(52, 0.8f);
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(77U, h.capacity());
- EXPECT_EQ(97U, h.bucketCount());
- EXPECT_EQ(0.8f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndExactCapacity) {
- SimpleHashtable h(46, 1.0f);
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
- EXPECT_EQ(47U, h.bucketCount());
- EXPECT_EQ(1.0f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndInexactCapacity) {
- SimpleHashtable h(42, 1.0f);
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
- EXPECT_EQ(47U, h.bucketCount());
- EXPECT_EQ(1.0f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, FindAddFindRemoveFind_OneEntry) {
- SimpleHashtable h;
- ssize_t index = find(h, -1, 8);
- ASSERT_EQ(-1, index);
-
- index = add(h, 8, 1);
- ASSERT_EQ(1U, h.size());
-
- ASSERT_EQ(index, find(h, -1, 8));
- ASSERT_EQ(8, h.entryAt(index).key);
- ASSERT_EQ(1, h.entryAt(index).value);
-
- index = find(h, index, 8);
- ASSERT_EQ(-1, index);
-
- ASSERT_TRUE(remove(h, 8));
- ASSERT_EQ(0U, h.size());
-
- index = find(h, -1, 8);
- ASSERT_EQ(-1, index);
-}
-
-TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithUniqueKey) {
- const size_t N = 11;
-
- SimpleHashtable h;
- for (size_t i = 0; i < N; i++) {
- ssize_t index = find(h, -1, int(i));
- ASSERT_EQ(-1, index);
-
- index = add(h, int(i), int(i * 10));
- ASSERT_EQ(i + 1, h.size());
-
- ASSERT_EQ(index, find(h, -1, int(i)));
- ASSERT_EQ(int(i), h.entryAt(index).key);
- ASSERT_EQ(int(i * 10), h.entryAt(index).value);
-
- index = find(h, index, int(i));
- ASSERT_EQ(-1, index);
- }
-
- for (size_t i = N; --i > 0; ) {
- ASSERT_TRUE(remove(h, int(i))) << "i = " << i;
- ASSERT_EQ(i, h.size());
-
- ssize_t index = find(h, -1, int(i));
- ASSERT_EQ(-1, index);
- }
-}
-
-TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithDuplicateKey) {
- const size_t N = 11;
- const int K = 1;
-
- SimpleHashtable h;
- for (size_t i = 0; i < N; i++) {
- ssize_t index = find(h, -1, K);
- if (i == 0) {
- ASSERT_EQ(-1, index);
- } else {
- ASSERT_NE(-1, index);
- }
-
- add(h, K, int(i));
- ASSERT_EQ(i + 1, h.size());
-
- index = -1;
- int values = 0;
- for (size_t j = 0; j <= i; j++) {
- index = find(h, index, K);
- ASSERT_GE(index, 0);
- ASSERT_EQ(K, h.entryAt(index).key);
- values |= 1 << h.entryAt(index).value;
- }
- ASSERT_EQ(values, (1 << (i + 1)) - 1);
-
- index = find(h, index, K);
- ASSERT_EQ(-1, index);
- }
-
- for (size_t i = N; --i > 0; ) {
- ASSERT_TRUE(remove(h, K)) << "i = " << i;
- ASSERT_EQ(i, h.size());
-
- ssize_t index = -1;
- for (size_t j = 0; j < i; j++) {
- index = find(h, index, K);
- ASSERT_GE(index, 0);
- ASSERT_EQ(K, h.entryAt(index).key);
- }
-
- index = find(h, index, K);
- ASSERT_EQ(-1, index);
- }
-}
-
-TEST_F(BasicHashtableTest, Clear_WhenAlreadyEmpty_DoesNothing) {
- SimpleHashtable h;
- h.clear();
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_RemovesThem) {
- SimpleHashtable h;
- add(h, 0, 0);
- add(h, 1, 0);
- h.clear();
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_DestroysThem) {
- ComplexHashtable h;
- add(h, ComplexKey(0), ComplexValue(0));
- add(h, ComplexKey(1), ComplexValue(0));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
-
- h.clear();
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Remove_AfterElementsAdded_DestroysThem) {
- ComplexHashtable h;
- add(h, ComplexKey(0), ComplexValue(0));
- add(h, ComplexKey(1), ComplexValue(0));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
-
- ASSERT_TRUE(remove(h, ComplexKey(0)));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
-
- ASSERT_TRUE(remove(h, ComplexKey(1)));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
-}
-
-TEST_F(BasicHashtableTest, Destructor_AfterElementsAdded_DestroysThem) {
- {
- ComplexHashtable h;
- add(h, ComplexKey(0), ComplexValue(0));
- add(h, ComplexKey(1), ComplexValue(0));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- } // h is destroyed here
-
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-}
-
-TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) {
- SimpleHashtable h;
-
- ASSERT_EQ(-1, h.next(-1));
-}
-
-TEST_F(BasicHashtableTest, Next_WhenNonEmpty_IteratesOverAllEntries) {
- const int N = 88;
-
- SimpleHashtable h;
- for (int i = 0; i < N; i++) {
- add(h, i, i * 10);
- }
-
- bool set[N];
- memset(set, 0, sizeof(bool) * N);
- int count = 0;
- for (ssize_t index = -1; (index = h.next(index)) != -1; ) {
- ASSERT_GE(index, 0);
- ASSERT_LT(size_t(index), h.bucketCount());
-
- const SimpleEntry& entry = h.entryAt(index);
- ASSERT_GE(entry.key, 0);
- ASSERT_LT(entry.key, N);
- ASSERT_FALSE(set[entry.key]);
- ASSERT_EQ(entry.key * 10, entry.value);
-
- set[entry.key] = true;
- count += 1;
- }
- ASSERT_EQ(N, count);
-}
-
-TEST_F(BasicHashtableTest, Add_RehashesOnDemand) {
- SimpleHashtable h;
- size_t initialCapacity = h.capacity();
- size_t initialBucketCount = h.bucketCount();
-
- for (size_t i = 0; i < initialCapacity; i++) {
- add(h, int(i), 0);
- }
-
- EXPECT_EQ(initialCapacity, h.size());
- EXPECT_EQ(initialCapacity, h.capacity());
- EXPECT_EQ(initialBucketCount, h.bucketCount());
-
- add(h, -1, -1);
-
- EXPECT_EQ(initialCapacity + 1, h.size());
- EXPECT_GT(h.capacity(), initialCapacity);
- EXPECT_GT(h.bucketCount(), initialBucketCount);
- EXPECT_GT(h.bucketCount(), h.capacity());
-}
-
-TEST_F(BasicHashtableTest, Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing) {
- ComplexHashtable h;
- add(h, ComplexKey(0), ComplexValue(0));
- const void* oldBuckets = getBuckets(h);
- ASSERT_NE((void*)NULL, oldBuckets);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
-
- h.rehash(h.capacity(), h.loadFactor());
-
- ASSERT_EQ(oldBuckets, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
-}
-
-TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets) {
- ComplexHashtable h;
- ASSERT_EQ((void*)NULL, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-
- h.rehash(9, 1.0f);
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(10U, h.capacity());
- EXPECT_EQ(11U, h.bucketCount());
- EXPECT_EQ(1.0f, h.loadFactor());
- EXPECT_EQ((void*)NULL, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-}
-
-TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity) {
- ComplexHashtable h(10);
- add(h, ComplexKey(0), ComplexValue(0));
- ASSERT_TRUE(remove(h, ComplexKey(0)));
- ASSERT_NE((void*)NULL, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-
- h.rehash(0, 0.75f);
-
- EXPECT_EQ(0U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
- EXPECT_EQ((void*)NULL, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
-}
-
-TEST_F(BasicHashtableTest, Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets) {
- ComplexHashtable h(10);
- add(h, ComplexKey(0), ComplexValue(0));
- add(h, ComplexKey(1), ComplexValue(1));
- const void* oldBuckets = getBuckets(h);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
-
- h.rehash(0, 0.75f);
-
- EXPECT_EQ(2U, h.size());
- EXPECT_EQ(3U, h.capacity());
- EXPECT_EQ(5U, h.bucketCount());
- EXPECT_EQ(0.75f, h.loadFactor());
- EXPECT_NE(oldBuckets, getBuckets(h));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
-}
-
-TEST_F(BasicHashtableTest, CopyOnWrite) {
- ComplexHashtable h1;
- add(h1, ComplexKey(0), ComplexValue(0));
- add(h1, ComplexKey(1), ComplexValue(1));
- const void* originalBuckets = getBuckets(h1);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ssize_t index0 = find(h1, -1, ComplexKey(0));
- EXPECT_GE(index0, 0);
-
- // copy constructor acquires shared reference
- ComplexHashtable h2(h1);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ASSERT_EQ(originalBuckets, getBuckets(h2));
- EXPECT_EQ(h1.size(), h2.size());
- EXPECT_EQ(h1.capacity(), h2.capacity());
- EXPECT_EQ(h1.bucketCount(), h2.bucketCount());
- EXPECT_EQ(h1.loadFactor(), h2.loadFactor());
- EXPECT_EQ(index0, find(h2, -1, ComplexKey(0)));
-
- // operator= acquires shared reference
- ComplexHashtable h3;
- h3 = h2;
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ASSERT_EQ(originalBuckets, getBuckets(h3));
- EXPECT_EQ(h1.size(), h3.size());
- EXPECT_EQ(h1.capacity(), h3.capacity());
- EXPECT_EQ(h1.bucketCount(), h3.bucketCount());
- EXPECT_EQ(h1.loadFactor(), h3.loadFactor());
- EXPECT_EQ(index0, find(h3, -1, ComplexKey(0)));
-
- // editEntryAt copies shared contents
- h1.editEntryAt(index0).value.v = 42;
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
- ASSERT_NE(originalBuckets, getBuckets(h1));
- EXPECT_EQ(42, h1.entryAt(index0).value.v);
- EXPECT_EQ(0, h2.entryAt(index0).value.v);
- EXPECT_EQ(0, h3.entryAt(index0).value.v);
-
- // clear releases reference to shared contents
- h2.clear();
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
- EXPECT_EQ(0U, h2.size());
- ASSERT_NE(originalBuckets, getBuckets(h2));
-
- // operator= acquires shared reference, destroys unshared contents
- h1 = h3;
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ASSERT_EQ(originalBuckets, getBuckets(h1));
- EXPECT_EQ(h3.size(), h1.size());
- EXPECT_EQ(h3.capacity(), h1.capacity());
- EXPECT_EQ(h3.bucketCount(), h1.bucketCount());
- EXPECT_EQ(h3.loadFactor(), h1.loadFactor());
- EXPECT_EQ(index0, find(h1, -1, ComplexKey(0)));
-
- // add copies shared contents
- add(h1, ComplexKey(2), ComplexValue(2));
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(5, 5));
- ASSERT_NE(originalBuckets, getBuckets(h1));
- EXPECT_EQ(3U, h1.size());
- EXPECT_EQ(0U, h2.size());
- EXPECT_EQ(2U, h3.size());
-
- // remove copies shared contents
- h1 = h3;
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ASSERT_EQ(originalBuckets, getBuckets(h1));
- h1.removeAt(index0);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(3, 3));
- ASSERT_NE(originalBuckets, getBuckets(h1));
- EXPECT_EQ(1U, h1.size());
- EXPECT_EQ(0U, h2.size());
- EXPECT_EQ(2U, h3.size());
-
- // rehash copies shared contents
- h1 = h3;
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
- ASSERT_EQ(originalBuckets, getBuckets(h1));
- h1.rehash(10, 1.0f);
- ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
- ASSERT_NE(originalBuckets, getBuckets(h1));
- EXPECT_EQ(2U, h1.size());
- EXPECT_EQ(0U, h2.size());
- EXPECT_EQ(2U, h3.size());
-}
-
-} // namespace android