1 //===-- Unittests for table -----------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "src/__support/CPP/bit.h" // bit_ceil 10 #include "src/__support/HashTable/randomness.h" 11 #include "src/__support/HashTable/table.h" 12 #include "src/__support/macros/config.h" 13 #include "test/UnitTest/Test.h" 14 15 namespace LIBC_NAMESPACE_DECL { 16 namespace internal { 17 TEST(LlvmLibcTableTest, AllocationAndDeallocation) { 18 size_t caps[] = {0, 1, 2, 3, 4, 7, 11, 37, 1024, 5261, 19999}; 19 const char *keys[] = {"", "a", "ab", "abc", 20 "abcd", "abcde", "abcdef", "abcdefg", 21 "abcdefgh", "abcdefghi", "abcdefghij"}; 22 for (size_t i : caps) { 23 HashTable *table = HashTable::allocate(i, 1); 24 ASSERT_NE(table, static_cast<HashTable *>(nullptr)); 25 for (const char *key : keys) { 26 ASSERT_EQ(table->find(key), static_cast<ENTRY *>(nullptr)); 27 } 28 HashTable::deallocate(table); 29 } 30 ASSERT_EQ(HashTable::allocate(-1, 0), static_cast<HashTable *>(nullptr)); 31 HashTable::deallocate(nullptr); 32 } 33 34 TEST(LlvmLibcTableTest, Iteration) { 35 constexpr size_t TEST_SIZE = 512; 36 size_t counter[TEST_SIZE]; 37 struct key { 38 uint8_t bytes[3]; 39 } keys[TEST_SIZE]; 40 HashTable *table = HashTable::allocate(0, 0x7f7f7f7f7f7f7f7f); 41 ASSERT_NE(table, static_cast<HashTable *>(nullptr)); 42 for (size_t i = 0; i < TEST_SIZE; ++i) { 43 counter[i] = 0; 44 if (i >= 256) { 45 keys[i].bytes[0] = 2; 46 keys[i].bytes[1] = i % 256; 47 keys[i].bytes[2] = 0; 48 } else { 49 keys[i].bytes[0] = 1; 50 keys[i].bytes[1] = i; 51 keys[i].bytes[2] = 0; 52 } 53 HashTable::insert(table, {reinterpret_cast<char *>(keys[i].bytes), 54 reinterpret_cast<void *>((size_t)i)}); 55 } 56 57 size_t count = 0; 58 for (const ENTRY &e : *table) { 59 size_t data = reinterpret_cast<size_t>(e.data); 60 ++counter[data]; 61 ++count; 62 } 63 ASSERT_EQ(count, TEST_SIZE); 64 for (size_t i = 0; i < TEST_SIZE; ++i) { 65 ASSERT_EQ(counter[i], static_cast<size_t>(1)); 66 } 67 HashTable::deallocate(table); 68 } 69 70 // Check if resize works correctly. This test actually covers two things: 71 // - The sizes are indeed growing. 72 // - The sizes are growing rapidly enough to reach the upper bound. 73 TEST(LlvmLibcTableTest, GrowthSequence) { 74 size_t cap = capacity_to_entries(0); 75 // right shift 4 to avoid overflow ssize_t. 76 while (cap < static_cast<size_t>(-1) >> 4u) { 77 size_t hint = cap / 8 * 7 + 1; 78 size_t new_cap = capacity_to_entries(hint); 79 ASSERT_GT(new_cap, cap); 80 cap = new_cap; 81 } 82 } 83 84 TEST(LlvmLibcTableTest, Insertion) { 85 struct key { 86 char bytes[2]; 87 } keys[256]; 88 for (size_t k = 0; k < 256; ++k) { 89 keys[k].bytes[0] = static_cast<char>(k); 90 keys[k].bytes[1] = 0; 91 } 92 constexpr size_t CAP = cpp::bit_ceil((sizeof(Group) + 1) * 8 / 7) / 8 * 7; 93 static_assert(CAP + 1 < 256, "CAP is too large for this test."); 94 HashTable *table = 95 HashTable::allocate(sizeof(Group) + 1, randomness::next_random_seed()); 96 ASSERT_NE(table, static_cast<HashTable *>(nullptr)); 97 98 // insert to full capacity. 99 for (size_t i = 0; i < CAP; ++i) { 100 ASSERT_NE(HashTable::insert(table, {keys[i].bytes, keys[i].bytes}), 101 static_cast<ENTRY *>(nullptr)); 102 } 103 104 // One more insert should grow the table successfully. We test the value 105 // here because the grow finishes with a fastpath insertion that is different 106 // from the normal insertion. 107 ASSERT_EQ(HashTable::insert(table, {keys[CAP].bytes, keys[CAP].bytes})->data, 108 static_cast<void *>(keys[CAP].bytes)); 109 110 for (size_t i = 0; i <= CAP; ++i) { 111 ASSERT_EQ(strcmp(table->find(keys[i].bytes)->key, keys[i].bytes), 0); 112 } 113 for (size_t i = CAP + 1; i < 256; ++i) { 114 ASSERT_EQ(table->find(keys[i].bytes), static_cast<ENTRY *>(nullptr)); 115 } 116 117 // do not replace old value 118 for (size_t i = 0; i <= CAP; ++i) { 119 ASSERT_NE( 120 HashTable::insert(table, {keys[i].bytes, reinterpret_cast<void *>(i)}), 121 static_cast<ENTRY *>(nullptr)); 122 } 123 for (size_t i = 0; i <= CAP; ++i) { 124 ASSERT_EQ(table->find(keys[i].bytes)->data, 125 reinterpret_cast<void *>(keys[i].bytes)); 126 } 127 128 HashTable::deallocate(table); 129 } 130 131 } // namespace internal 132 } // namespace LIBC_NAMESPACE_DECL 133