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