1e735f23018b398f45bd052b63616d7a45e29515bJeff Brown/* 2e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Copyright (C) 2011 The Android Open Source Project 3e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 4e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Licensed under the Apache License, Version 2.0 (the "License"); 5e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * you may not use this file except in compliance with the License. 6e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * You may obtain a copy of the License at 7e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 8e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * http://www.apache.org/licenses/LICENSE-2.0 9e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 10e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Unless required by applicable law or agreed to in writing, software 11e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * distributed under the License is distributed on an "AS IS" BASIS, 12e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * See the License for the specific language governing permissions and 14e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * limitations under the License. 15e735f23018b398f45bd052b63616d7a45e29515bJeff Brown */ 16e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 17e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#define LOG_TAG "BasicHashtable_test" 18e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 19e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <utils/BasicHashtable.h> 20e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <cutils/log.h> 21e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <gtest/gtest.h> 22e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <unistd.h> 23e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 24e735f23018b398f45bd052b63616d7a45e29515bJeff Brownnamespace android { 25e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 26e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef int SimpleKey; 27e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef int SimpleValue; 28e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry; 29e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable; 30e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 31e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstruct ComplexKey { 32e735f23018b398f45bd052b63616d7a45e29515bJeff Brown int k; 33e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 34e735f23018b398f45bd052b63616d7a45e29515bJeff Brown explicit ComplexKey(int k) : k(k) { 35e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount += 1; 36e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 37e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 38e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexKey(const ComplexKey& other) : k(other.k) { 39e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount += 1; 40e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 41e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 42e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ~ComplexKey() { 43e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount -= 1; 44e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 45e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 46e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bool operator ==(const ComplexKey& other) const { 47e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return k == other.k; 48e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 49e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 50e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bool operator !=(const ComplexKey& other) const { 51e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return k != other.k; 52e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 53e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 54e735f23018b398f45bd052b63616d7a45e29515bJeff Brown static ssize_t instanceCount; 55e735f23018b398f45bd052b63616d7a45e29515bJeff Brown}; 56e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 57e735f23018b398f45bd052b63616d7a45e29515bJeff Brownssize_t ComplexKey::instanceCount = 0; 58e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 59e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate<> inline hash_t hash_type(const ComplexKey& value) { 60e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return hash_type(value.k); 61e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 62e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 63e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstruct ComplexValue { 64e735f23018b398f45bd052b63616d7a45e29515bJeff Brown int v; 65e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 66e735f23018b398f45bd052b63616d7a45e29515bJeff Brown explicit ComplexValue(int v) : v(v) { 67e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount += 1; 68e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 69e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 70e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexValue(const ComplexValue& other) : v(other.v) { 71e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount += 1; 72e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 73e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 74e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ~ComplexValue() { 75e735f23018b398f45bd052b63616d7a45e29515bJeff Brown instanceCount -= 1; 76e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 77e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 78e735f23018b398f45bd052b63616d7a45e29515bJeff Brown static ssize_t instanceCount; 79e735f23018b398f45bd052b63616d7a45e29515bJeff Brown}; 80e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 81e735f23018b398f45bd052b63616d7a45e29515bJeff Brownssize_t ComplexValue::instanceCount = 0; 82e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 83e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry; 84e735f23018b398f45bd052b63616d7a45e29515bJeff Browntypedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable; 85e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 86e735f23018b398f45bd052b63616d7a45e29515bJeff Brownclass BasicHashtableTest : public testing::Test { 87e735f23018b398f45bd052b63616d7a45e29515bJeff Brownprotected: 88e735f23018b398f45bd052b63616d7a45e29515bJeff Brown virtual void SetUp() { 89e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexKey::instanceCount = 0; 90e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexValue::instanceCount = 0; 91e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 92e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 93e735f23018b398f45bd052b63616d7a45e29515bJeff Brown virtual void TearDown() { 94e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 95e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 96e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 97e735f23018b398f45bd052b63616d7a45e29515bJeff Brown void assertInstanceCount(ssize_t keys, ssize_t values) { 98e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) { 99e735f23018b398f45bd052b63616d7a45e29515bJeff Brown FAIL() << "Expected " << keys << " keys and " << values << " values " 100e735f23018b398f45bd052b63616d7a45e29515bJeff Brown "but there were actually " << ComplexKey::instanceCount << " keys and " 101e735f23018b398f45bd052b63616d7a45e29515bJeff Brown << ComplexValue::instanceCount << " values"; 102e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 103e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 104e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 105e735f23018b398f45bd052b63616d7a45e29515bJeff Brownpublic: 106e735f23018b398f45bd052b63616d7a45e29515bJeff Brown template <typename TKey, typename TEntry> 107e735f23018b398f45bd052b63616d7a45e29515bJeff Brown static void cookieAt(const BasicHashtable<TKey, TEntry>& h, size_t index, 108e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bool* collision, bool* present, hash_t* hash) { 109e735f23018b398f45bd052b63616d7a45e29515bJeff Brown uint32_t cookie = h.cookieAt(index); 110e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *collision = cookie & BasicHashtable<TKey, TEntry>::Bucket::COLLISION; 111e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *present = cookie & BasicHashtable<TKey, TEntry>::Bucket::PRESENT; 112e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *hash = cookie & BasicHashtable<TKey, TEntry>::Bucket::HASH_MASK; 113e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 114e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 115e735f23018b398f45bd052b63616d7a45e29515bJeff Brown template <typename TKey, typename TEntry> 116e735f23018b398f45bd052b63616d7a45e29515bJeff Brown static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) { 117e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return h.mBuckets; 118e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 119e735f23018b398f45bd052b63616d7a45e29515bJeff Brown}; 120e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 121e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <typename TKey, typename TValue> 122e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic size_t add(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, 123e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const TKey& key, const TValue& value) { 124e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return h.add(hash_type(key), key_value_pair_t<TKey, TValue>(key, value)); 125e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 126e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 127e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <typename TKey, typename TValue> 128e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic ssize_t find(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, 129e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index, const TKey& key) { 130e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return h.find(index, hash_type(key), key); 131e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 132e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 133e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <typename TKey, typename TValue> 134e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic bool remove(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, 135e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const TKey& key) { 136e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = find(h, -1, key); 137e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (index >= 0) { 138e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.removeAt(index); 139e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return true; 140e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 141e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return false; 142e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 143e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 144e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <typename TEntry> 145e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic void getKeyValue(const TEntry& entry, int* key, int* value); 146e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 147e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) { 148e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *key = entry.key; 149e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *value = entry.value; 150e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 151e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 152e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) { 153e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *key = entry.key.k; 154e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *value = entry.value.v; 155e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 156e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 157e735f23018b398f45bd052b63616d7a45e29515bJeff Browntemplate <typename TKey, typename TValue> 158e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic void dump(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h) { 159eb0953307ce75cec031aedbf21abff08e5a737e5Steve Block ALOGD("hashtable %p, size=%u, capacity=%u, bucketCount=%u", 160e735f23018b398f45bd052b63616d7a45e29515bJeff Brown &h, h.size(), h.capacity(), h.bucketCount()); 161e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < h.bucketCount(); i++) { 162e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bool collision, present; 163e735f23018b398f45bd052b63616d7a45e29515bJeff Brown hash_t hash; 164e735f23018b398f45bd052b63616d7a45e29515bJeff Brown BasicHashtableTest::cookieAt(h, i, &collision, &present, &hash); 165e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (present) { 166e735f23018b398f45bd052b63616d7a45e29515bJeff Brown int key, value; 167e735f23018b398f45bd052b63616d7a45e29515bJeff Brown getKeyValue(h.entryAt(i), &key, &value); 168eb0953307ce75cec031aedbf21abff08e5a737e5Steve Block ALOGD(" [%3u] = collision=%d, present=%d, hash=0x%08x, key=%3d, value=%3d, " 169e735f23018b398f45bd052b63616d7a45e29515bJeff Brown "hash_type(key)=0x%08x", 170e735f23018b398f45bd052b63616d7a45e29515bJeff Brown i, collision, present, hash, key, value, hash_type(key)); 171e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 172eb0953307ce75cec031aedbf21abff08e5a737e5Steve Block ALOGD(" [%3u] = collision=%d, present=%d", 173e735f23018b398f45bd052b63616d7a45e29515bJeff Brown i, collision, present); 174e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 175e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 176e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 177e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 178e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, DefaultConstructor_WithDefaultProperties) { 179e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 180e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 181e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 182e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 183e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 184e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 185e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 186e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 187e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Constructor_WithNonUnityLoadFactor) { 188e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h(52, 0.8f); 189e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 190e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 191e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(77U, h.capacity()); 192e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(97U, h.bucketCount()); 193e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.8f, h.loadFactor()); 194e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 195e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 196e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndExactCapacity) { 197e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h(46, 1.0f); 198e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 199e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 200e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f 201e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(47U, h.bucketCount()); 202e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(1.0f, h.loadFactor()); 203e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 204e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 205e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndInexactCapacity) { 206e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h(42, 1.0f); 207e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 208e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 209e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f 210e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(47U, h.bucketCount()); 211e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(1.0f, h.loadFactor()); 212e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 213e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 214e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, FindAddFindRemoveFind_OneEntry) { 215e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 216e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = find(h, -1, 8); 217e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 218e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 219e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = add(h, 8, 1); 220e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(1U, h.size()); 221e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 222e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(index, find(h, -1, 8)); 223e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(8, h.entryAt(index).key); 224e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(1, h.entryAt(index).value); 225e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 226e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, 8); 227e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 228e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 229e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, 8)); 230e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(0U, h.size()); 231e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 232e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, -1, 8); 233e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 234e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 235e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 236e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithUniqueKey) { 237e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const size_t N = 11; 238e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 239e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 240e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < N; i++) { 241e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = find(h, -1, int(i)); 242e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 243e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 244e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = add(h, int(i), int(i * 10)); 245e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(i + 1, h.size()); 246e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 247e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(index, find(h, -1, int(i))); 248e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(int(i), h.entryAt(index).key); 249e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(int(i * 10), h.entryAt(index).value); 250e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 251e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, int(i)); 252e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 253e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 254e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 255e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = N; --i > 0; ) { 256e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, int(i))) << "i = " << i; 257e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(i, h.size()); 258e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 259e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = find(h, -1, int(i)); 260e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 261e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 262e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 263e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 264e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithDuplicateKey) { 265e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const size_t N = 11; 266e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const int K = 1; 267e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 268e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 269e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < N; i++) { 270e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = find(h, -1, K); 271e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (i == 0) { 272e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 273e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 274e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(-1, index); 275e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 276e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 277e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, K, int(i)); 278e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(i + 1, h.size()); 279e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 280e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = -1; 281e735f23018b398f45bd052b63616d7a45e29515bJeff Brown int values = 0; 282e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t j = 0; j <= i; j++) { 283e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, K); 284e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_GE(index, 0); 285e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(K, h.entryAt(index).key); 286e735f23018b398f45bd052b63616d7a45e29515bJeff Brown values |= 1 << h.entryAt(index).value; 287e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 288e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(values, (1 << (i + 1)) - 1); 289e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 290e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, K); 291e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 292e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 293e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 294e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = N; --i > 0; ) { 295e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, K)) << "i = " << i; 296e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(i, h.size()); 297e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 298e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index = -1; 299e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t j = 0; j < i; j++) { 300e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, K); 301e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_GE(index, 0); 302e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(K, h.entryAt(index).key); 303e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 304e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 305e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = find(h, index, K); 306e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, index); 307e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 308e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 309e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 310e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Clear_WhenAlreadyEmpty_DoesNothing) { 311e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 312e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.clear(); 313e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 314e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 315e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 316e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 317e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 318e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 319e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 320e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Clear_AfterElementsAdded_RemovesThem) { 321e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 322e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, 0, 0); 323e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, 1, 0); 324e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.clear(); 325e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 326e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 327e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 328e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 329e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 330e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 331e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 332e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Clear_AfterElementsAdded_DestroysThem) { 333e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h; 334e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 335e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(1), ComplexValue(0)); 336e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 337e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 338e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.clear(); 339e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 340e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 341e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 342e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 343e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 344e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 345e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 346e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 347e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Remove_AfterElementsAdded_DestroysThem) { 348e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h; 349e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 350e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(1), ComplexValue(0)); 351e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 352e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 353e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, ComplexKey(0))); 354e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); 355e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 356e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, ComplexKey(1))); 357e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 358e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 359e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 360e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 361e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 362e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 363e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 364e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 365e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Destructor_AfterElementsAdded_DestroysThem) { 366e735f23018b398f45bd052b63616d7a45e29515bJeff Brown { 367e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h; 368e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 369e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(1), ComplexValue(0)); 370e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 371e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } // h is destroyed here 372e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 373e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 374e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 375e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 376e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) { 377e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 378e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 379e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(-1, h.next(-1)); 380e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 381e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 382e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Next_WhenNonEmpty_IteratesOverAllEntries) { 383e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const int N = 88; 384e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 385e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 386e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (int i = 0; i < N; i++) { 387e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, i, i * 10); 388e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 389e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 390e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bool set[N]; 391e735f23018b398f45bd052b63616d7a45e29515bJeff Brown memset(set, 0, sizeof(bool) * N); 392e735f23018b398f45bd052b63616d7a45e29515bJeff Brown int count = 0; 393e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (ssize_t index = -1; (index = h.next(index)) != -1; ) { 394e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_GE(index, 0); 395e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_LT(size_t(index), h.bucketCount()); 396e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 397e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const SimpleEntry& entry = h.entryAt(index); 398e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_GE(entry.key, 0); 399e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_LT(entry.key, N); 400cdc1cfb3e51f3caddc1f290b46dc789c036f22edSasha Levitskiy ASSERT_FALSE(set[entry.key]); 401e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(entry.key * 10, entry.value); 402e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 403e735f23018b398f45bd052b63616d7a45e29515bJeff Brown set[entry.key] = true; 404e735f23018b398f45bd052b63616d7a45e29515bJeff Brown count += 1; 405e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 406e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(N, count); 407e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 408e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 409e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Add_RehashesOnDemand) { 410e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SimpleHashtable h; 411e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t initialCapacity = h.capacity(); 412e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t initialBucketCount = h.bucketCount(); 413e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 414e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < initialCapacity; i++) { 415e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, int(i), 0); 416e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 417e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 418e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(initialCapacity, h.size()); 419e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(initialCapacity, h.capacity()); 420e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(initialBucketCount, h.bucketCount()); 421e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 422e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, -1, -1); 423e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 424e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(initialCapacity + 1, h.size()); 425e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_GT(h.capacity(), initialCapacity); 426e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_GT(h.bucketCount(), initialBucketCount); 427e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_GT(h.bucketCount(), h.capacity()); 428e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 429e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 430e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing) { 431e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h; 432e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 433e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const void* oldBuckets = getBuckets(h); 434e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE((void*)NULL, oldBuckets); 435e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); 436e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 437e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.rehash(h.capacity(), h.loadFactor()); 438e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 439e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(oldBuckets, getBuckets(h)); 440e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); 441e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 442e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 443e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets) { 444e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h; 445e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ((void*)NULL, getBuckets(h)); 446e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 447e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 448e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.rehash(9, 1.0f); 449e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 450e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 451e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(10U, h.capacity()); 452e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(11U, h.bucketCount()); 453e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(1.0f, h.loadFactor()); 454e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ((void*)NULL, getBuckets(h)); 455e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 456e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 457e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 458e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity) { 459e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h(10); 460e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 461e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_TRUE(remove(h, ComplexKey(0))); 462e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE((void*)NULL, getBuckets(h)); 463e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 464e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 465e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.rehash(0, 0.75f); 466e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 467e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h.size()); 468e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 469e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 470e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 471e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ((void*)NULL, getBuckets(h)); 472e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 473e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 474e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 475e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets) { 476e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h(10); 477e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(0), ComplexValue(0)); 478e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h, ComplexKey(1), ComplexValue(1)); 479e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const void* oldBuckets = getBuckets(h); 480e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 481e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 482e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h.rehash(0, 0.75f); 483e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 484e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(2U, h.size()); 485e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h.capacity()); 486e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(5U, h.bucketCount()); 487e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0.75f, h.loadFactor()); 488e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_NE(oldBuckets, getBuckets(h)); 489e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 490e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 491e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 492e735f23018b398f45bd052b63616d7a45e29515bJeff BrownTEST_F(BasicHashtableTest, CopyOnWrite) { 493e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h1; 494e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h1, ComplexKey(0), ComplexValue(0)); 495e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h1, ComplexKey(1), ComplexValue(1)); 496e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const void* originalBuckets = getBuckets(h1); 497e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 498e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ssize_t index0 = find(h1, -1, ComplexKey(0)); 499e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_GE(index0, 0); 500e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 501e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // copy constructor acquires shared reference 502e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h2(h1); 503e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 504e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(originalBuckets, getBuckets(h2)); 505e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.size(), h2.size()); 506e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.capacity(), h2.capacity()); 507e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.bucketCount(), h2.bucketCount()); 508e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.loadFactor(), h2.loadFactor()); 509e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(index0, find(h2, -1, ComplexKey(0))); 510e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 511e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // operator= acquires shared reference 512e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ComplexHashtable h3; 513e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h3 = h2; 514e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 515e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(originalBuckets, getBuckets(h3)); 516e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.size(), h3.size()); 517e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.capacity(), h3.capacity()); 518e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.bucketCount(), h3.bucketCount()); 519e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h1.loadFactor(), h3.loadFactor()); 520e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(index0, find(h3, -1, ComplexKey(0))); 521e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 522e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // editEntryAt copies shared contents 523e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1.editEntryAt(index0).value.v = 42; 524e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); 525e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(originalBuckets, getBuckets(h1)); 526e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(42, h1.entryAt(index0).value.v); 527e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0, h2.entryAt(index0).value.v); 528e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0, h3.entryAt(index0).value.v); 529e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 530e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // clear releases reference to shared contents 531e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h2.clear(); 532e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); 533e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h2.size()); 534e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(originalBuckets, getBuckets(h2)); 535e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 536e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // operator= acquires shared reference, destroys unshared contents 537e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1 = h3; 538e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 539e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(originalBuckets, getBuckets(h1)); 540e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h3.size(), h1.size()); 541e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h3.capacity(), h1.capacity()); 542e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h3.bucketCount(), h1.bucketCount()); 543e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(h3.loadFactor(), h1.loadFactor()); 544e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(index0, find(h1, -1, ComplexKey(0))); 545e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 546e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // add copies shared contents 547e735f23018b398f45bd052b63616d7a45e29515bJeff Brown add(h1, ComplexKey(2), ComplexValue(2)); 548e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(5, 5)); 549e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(originalBuckets, getBuckets(h1)); 550e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(3U, h1.size()); 551e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h2.size()); 552e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(2U, h3.size()); 553e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 554e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // remove copies shared contents 555e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1 = h3; 556e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 557e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(originalBuckets, getBuckets(h1)); 558e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1.removeAt(index0); 559e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(3, 3)); 560e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(originalBuckets, getBuckets(h1)); 561e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(1U, h1.size()); 562e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h2.size()); 563e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(2U, h3.size()); 564e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 565e735f23018b398f45bd052b63616d7a45e29515bJeff Brown // rehash copies shared contents 566e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1 = h3; 567e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); 568e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_EQ(originalBuckets, getBuckets(h1)); 569e735f23018b398f45bd052b63616d7a45e29515bJeff Brown h1.rehash(10, 1.0f); 570e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); 571e735f23018b398f45bd052b63616d7a45e29515bJeff Brown ASSERT_NE(originalBuckets, getBuckets(h1)); 572e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(2U, h1.size()); 573e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(0U, h2.size()); 574e735f23018b398f45bd052b63616d7a45e29515bJeff Brown EXPECT_EQ(2U, h3.size()); 575e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 576e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 577e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} // namespace android 578