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