135 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "src/__support/CPP/bit.h" // bit_ceil10#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 15namespace LIBC_NAMESPACE_DECL {16namespace internal {17TEST(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 34TEST(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] = static_cast<uint8_t>(i % 256);47 keys[i].bytes[2] = 0;48 } else {49 keys[i].bytes[0] = 1;50 keys[i].bytes[1] = static_cast<uint8_t>(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.73TEST(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 84TEST(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 value105 // here because the grow finishes with a fastpath insertion that is different106 // 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 auto comp = [](char l, char r) -> int { return l - r; };112 ASSERT_EQ(113 inline_strcmp(table->find(keys[i].bytes)->key, keys[i].bytes, comp), 0);114 }115 for (size_t i = CAP + 1; i < 256; ++i) {116 ASSERT_EQ(table->find(keys[i].bytes), static_cast<ENTRY *>(nullptr));117 }118 119 // do not replace old value120 for (size_t i = 0; i <= CAP; ++i) {121 ASSERT_NE(122 HashTable::insert(table, {keys[i].bytes, reinterpret_cast<void *>(i)}),123 static_cast<ENTRY *>(nullptr));124 }125 for (size_t i = 0; i <= CAP; ++i) {126 ASSERT_EQ(table->find(keys[i].bytes)->data,127 reinterpret_cast<void *>(keys[i].bytes));128 }129 130 HashTable::deallocate(table);131}132 133} // namespace internal134} // namespace LIBC_NAMESPACE_DECL135