libc/test/src/__support/HashTable/table_test.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-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