[libc] [search] implement hcreate(_r)/hsearch(_r)/hdestroy(_r) (#73469)

This patch implements `hcreate(_r)/hsearch(_r)/hdestroy(_r)` as
specified in https://man7.org/linux/man-pages/man3/hsearch.3.html.

Notice that `neon/asimd` extension is not yet added in this patch. 

- The implementation is largely simplified from rust's
[`hashbrown`](https://github.com/rust-lang/hashbrown/blob/master/src/raw/mod.rs)
as we only consider fix-sized insertion-only hashtables. Technical
details are provided in code comments.

- This patch also contains a portable string hash function, which is
derived from [`aHash`](https://github.com/tkaitchuck/aHash)'s fallback
routine. Not using any SIMD acceleration, it has a good enough quality
(passing all SMHasher tests) and is not too bad in speed.

- Some general functionalities are added, such as `memory_size`,
`offset_to`(alignment), `next_power_of_two`, `is_power_of_two`.
`ctz/clz` are extended to support shorter integers.

4 files changed, 269 insertions, 0 deletions

diff --git a/libc/test/src/__support/HashTable/CMakeLists.txt b/libc/test/src/__support/HashTable/CMakeLists.txt
new file mode 100644
index 000000000000..ee8dde107c3f
--- /dev/null
+++ b/libc/test/src/__support/HashTable/CMakeLists.txt
@@ -0,0 +1,33 @@
+add_libc_test(
+  bitmask_test
+  SUITE
+    libc-support-tests
+  SRCS
+    bitmask_test.cpp
+  DEPENDS
+    libc.src.__support.HashTable.bitmask
+)
+
+add_libc_test(
+  table_test
+  SUITE
+    libc-support-tests
+  SRCS
+    table_test.cpp
+  DEPENDS
+    libc.src.__support.HashTable.randomness
+    libc.src.__support.HashTable.table
+    libc.src.__support.common
+  UNIT_TEST_ONLY
+)
+
+add_libc_test(
+  group_test
+  SUITE
+    libc-support-tests
+  SRCS
+    group_test.cpp
+  DEPENDS
+    libc.src.__support.HashTable.bitmask
+    libc.src.stdlib.rand
+)
diff --git a/libc/test/src/__support/HashTable/bitmask_test.cpp b/libc/test/src/__support/HashTable/bitmask_test.cpp
new file mode 100644
index 000000000000..c816c5d10638
--- /dev/null
+++ b/libc/test/src/__support/HashTable/bitmask_test.cpp
@@ -0,0 +1,69 @@
+//===-- Unittests for bitmask ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/HashTable/bitmask.h"
+#include "test/UnitTest/Test.h"
+namespace LIBC_NAMESPACE {
+namespace internal {
+
+using ShortBitMask = BitMaskAdaptor<uint16_t, 0xffff, 1>;
+using LargeBitMask = BitMaskAdaptor<uint64_t, 0x80'80'80'80'80'80'80'80, 8>;
+
+TEST(LlvmLibcHashTableBitMaskTest, SingleBitStrideLowestSetBit) {
+  uint16_t data = 0xffff;
+  for (size_t i = 0; i < 16; ++i) {
+    if (ShortBitMask{data}.any_bit_set()) {
+      ASSERT_EQ(ShortBitMask{data}.lowest_set_bit_nonzero(), i);
+      data <<= 1;
+    }
+  }
+}
+
+TEST(LlvmLibcHashTableBitMaskTest, MultiBitStrideLowestSetBit) {
+  uint64_t data = 0xffff'ffff'ffff'ffff;
+  for (size_t i = 0; i < 8; ++i) {
+    for (size_t j = 0; j < 8; ++j) {
+      if (LargeBitMask{data}.any_bit_set()) {
+        ASSERT_EQ(LargeBitMask{data}.lowest_set_bit_nonzero(), i);
+        data <<= 1;
+      }
+    }
+  }
+}
+
+TEST(LlvmLibcHashTableBitMaskTest, SingleBitStrideIteration) {
+  using Iter = IteratableBitMaskAdaptor<ShortBitMask>;
+  uint16_t data = 0xffff;
+  for (size_t i = 0; i < 16; ++i) {
+    Iter iter = {data};
+    size_t j = i;
+    for (auto x : iter) {
+      ASSERT_EQ(x, j);
+      j++;
+    }
+    ASSERT_EQ(j, size_t{16});
+    data <<= 1;
+  }
+}
+
+TEST(LlvmLibcHashTableBitMaskTest, MultiBitStrideIteration) {
+  using Iter = IteratableBitMaskAdaptor<LargeBitMask>;
+  uint64_t data = Iter::MASK;
+  for (size_t i = 0; i < 8; ++i) {
+    Iter iter = {data};
+    size_t j = i;
+    for (auto x : iter) {
+      ASSERT_EQ(x, j);
+      j++;
+    }
+    ASSERT_EQ(j, size_t{8});
+    data <<= Iter::STRIDE;
+  }
+}
+} // namespace internal
+} // namespace LIBC_NAMESPACE
diff --git a/libc/test/src/__support/HashTable/group_test.cpp b/libc/test/src/__support/HashTable/group_test.cpp
new file mode 100644
index 000000000000..907908335863
--- /dev/null
+++ b/libc/test/src/__support/HashTable/group_test.cpp
@@ -0,0 +1,90 @@
+//===-- Unittests for control group ---------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/HashTable/bitmask.h"
+
+#include "src/stdlib/rand.h"
+#include "test/UnitTest/Test.h"
+#include <stdint.h>
+
+namespace LIBC_NAMESPACE {
+namespace internal {
+
+struct ByteArray {
+  alignas(Group) uint8_t data[sizeof(Group) + 1]{};
+};
+
+TEST(LlvmLibcHashTableBitMaskTest, Match) {
+  // Any pair of targets have bit differences not only at the lowest bit.
+  // No False positive.
+  uint8_t targets[4] = {0x00, 0x11, 0xFF, 0x0F};
+  size_t count[4] = {0, 0, 0, 0};
+  size_t appearance[4][sizeof(Group)];
+  ByteArray array{};
+
+  union {
+    uintptr_t random;
+    int data[sizeof(uintptr_t) / sizeof(int)];
+  };
+
+  for (int &i : data)
+    i = rand();
+
+  for (size_t i = 0; i < sizeof(Group); ++i) {
+    size_t choice = random % 4;
+    random /= 4;
+    array.data[i] = targets[choice];
+    appearance[choice][count[choice]++] = i;
+  }
+
+  for (size_t t = 0; t < sizeof(targets); ++t) {
+    auto bitmask = Group::load(array.data).match_byte(targets[t]);
+    for (size_t i = 0; i < count[t]; ++i) {
+      size_t iterated = 0;
+      for (size_t position : bitmask) {
+        ASSERT_EQ(appearance[t][iterated], position);
+        iterated++;
+      }
+      ASSERT_EQ(count[t], iterated);
+    }
+  }
+}
+
+TEST(LlvmLibcHashTableBitMaskTest, MaskAvailable) {
+  uint8_t values[3] = {0x00, 0x0F, 0x80};
+
+  for (size_t i = 0; i < sizeof(Group); ++i) {
+    ByteArray array{};
+
+    union {
+      uintptr_t random;
+      int data[sizeof(uintptr_t) / sizeof(int)];
+    };
+
+    for (int &j : data)
+      j = rand();
+
+    ASSERT_FALSE(Group::load(array.data).mask_available().any_bit_set());
+
+    array.data[i] = 0x80;
+    for (size_t j = 0; j < sizeof(Group); ++j) {
+      if (i == j)
+        continue;
+      size_t sample_space = 2 + (j > i);
+      size_t choice = random % sample_space;
+      random /= sizeof(values);
+      array.data[j] = values[choice];
+    }
+
+    auto mask = Group::load(array.data).mask_available();
+    ASSERT_TRUE(mask.any_bit_set());
+    ASSERT_EQ(mask.lowest_set_bit_nonzero(), i);
+  }
+}
+} // namespace internal
+} // namespace LIBC_NAMESPACE
diff --git a/libc/test/src/__support/HashTable/table_test.cpp b/libc/test/src/__support/HashTable/table_test.cpp
new file mode 100644
index 000000000000..f0aa82f2d5c7
--- /dev/null
+++ b/libc/test/src/__support/HashTable/table_test.cpp
@@ -0,0 +1,77 @@
+//===-- Unittests for table -----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/HashTable/randomness.h"
+#include "src/__support/HashTable/table.h"
+#include "test/UnitTest/Test.h"
+
+namespace LIBC_NAMESPACE {
+namespace internal {
+TEST(LlvmLibcTableTest, AllocationAndDeallocation) {
+  size_t caps[] = {0, 1, 2, 3, 4, 7, 11, 37, 1024, 5261, 19999};
+  const char *keys[] = {"",         "a",         "ab",        "abc",
+                        "abcd",     "abcde",     "abcdef",    "abcdefg",
+                        "abcdefgh", "abcdefghi", "abcdefghij"};
+  for (size_t i : caps) {
+    HashTable *table = HashTable::allocate(i, 1);
+    ASSERT_NE(table, static_cast<HashTable *>(nullptr));
+    for (const char *key : keys) {
+      ASSERT_EQ(table->find(key), static_cast<ENTRY *>(nullptr));
+    }
+    HashTable::deallocate(table);
+  }
+  ASSERT_EQ(HashTable::allocate(-1, 0), static_cast<HashTable *>(nullptr));
+  HashTable::deallocate(nullptr);
+}
+
+TEST(LlvmLibcTableTest, Insertion) {
+  union key {
+    uint64_t value;
+    char bytes[8];
+  } keys[256];
+  for (size_t k = 0; k < 256; ++k) {
+    keys[k].value = LIBC_NAMESPACE::Endian::to_little_endian(k);
+  }
+  constexpr size_t CAP = next_power_of_two((sizeof(Group) + 1) * 8 / 7) / 8 * 7;
+  static_assert(CAP + 1 < 256, "CAP is too large for this test.");
+  HashTable *table =
+      HashTable::allocate(sizeof(Group) + 1, randomness::next_random_seed());
+  ASSERT_NE(table, static_cast<HashTable *>(nullptr));
+
+  // insert to full capacity.
+  for (size_t i = 0; i < CAP; ++i) {
+    ASSERT_NE(table->insert({keys[i].bytes, keys[i].bytes}),
+              static_cast<ENTRY *>(nullptr));
+  }
+
+  // one more insert should fail.
+  ASSERT_EQ(table->insert({keys[CAP + 1].bytes, keys[CAP + 1].bytes}),
+            static_cast<ENTRY *>(nullptr));
+
+  for (size_t i = 0; i < CAP; ++i) {
+    ASSERT_EQ(strcmp(table->find(keys[i].bytes)->key, keys[i].bytes), 0);
+  }
+  for (size_t i = CAP; i < 256; ++i) {
+    ASSERT_EQ(table->find(keys[i].bytes), static_cast<ENTRY *>(nullptr));
+  }
+
+  // do not replace old value
+  for (size_t i = 0; i < CAP; ++i) {
+    ASSERT_NE(table->insert({keys[i].bytes, reinterpret_cast<void *>(i)}),
+              static_cast<ENTRY *>(nullptr));
+  }
+  for (size_t i = 0; i < CAP; ++i) {
+    ASSERT_EQ(table->find(keys[i].bytes)->data,
+              reinterpret_cast<void *>(keys[i].bytes));
+  }
+
+  HashTable::deallocate(table);
+}
+
+} // namespace internal
+} // namespace LIBC_NAMESPACE