[libc.search] [PATCH 6/6] add `hsearch(_r)`, `hdelete(_r_)` and `hcreate(_r)` implementation

[SchrodingerZhu]

Summary

This patch adds hsearch(_r), hdelete(_r_) and hcreate(_r) to libc.
The underlying hashtable is swisstable, and the wyhash is the chosen hash function
for byte strings.

By now, the random seed of the hashtable is only utilizes limited random source.
This is because using system entropy pool can introduce other errors and
getrandom is not portable while hsearch is within the POSIX standard.

[SchrodingerZhu]

Rebase

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.fcntl.creat
     libc.src.fcntl.open
     libc.src.fcntl.openat
 
     # sched.h entrypoints
     libc.src.sched.sched_getaffinity
     libc.src.sched.sched_setaffinity
 
+    # search.h entrypoints
+    libc.src.search.hcreate
+    libc.src.search.hcreate_r
+    libc.src.search.hdestroy
+    libc.src.search.hdestroy_r
+    libc.src.search.hsearch
+    libc.src.search.hsearch_r
+
     # string.h entrypoints
     libc.src.string.bcmp
     libc.src.string.bcopy
     libc.src.string.bzero
     libc.src.string.memccpy
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy

libc/src/CMakeLists.txt

 add_subdirectory(__support)
 
 add_subdirectory(ctype)
 add_subdirectory(errno)
 add_subdirectory(fenv)
 add_subdirectory(inttypes)
 add_subdirectory(math)
 add_subdirectory(string)
 add_subdirectory(stdlib)
 add_subdirectory(stdio)
+add_subdirectory(search)
 
 if(${LIBC_TARGET_OS} STREQUAL "linux")
   add_subdirectory(dirent)
   add_subdirectory(fcntl)
   add_subdirectory(pthread)
   add_subdirectory(sched)
   add_subdirectory(sys)
   add_subdirectory(termios)

libc/src/search/CMakeLists.txt

+add_subdirectory(hashtable)
+
+add_entrypoint_object(
+  hsearch
+  SRCS
+    hsearch.cpp
+  HDRS 
+    hsearch.h
+  DEPENDS
+    .hashtable.global
+    .hashtable.search_impl
+)
+
+add_entrypoint_object(
+  hsearch_r
+  SRCS
+    hsearch_r.cpp
+  HDRS 
+    hsearch_r.h
+  DEPENDS
+    .hashtable.search_impl
+)
+
+add_entrypoint_object(
+  hcreate
+  SRCS
+    hcreate.cpp
+  HDRS 
+    hcreate.h
+  DEPENDS
+    .hashtable.global
+    .hashtable.utils
+    libc.include.errno
+)
+
+add_entrypoint_object(
+  hcreate_r
+  SRCS
+    hcreate_r.cpp
+  HDRS 
+    hcreate_r.h
+  DEPENDS
+    .hashtable.utils
+    libc.include.stdlib
+    libc.include.errno
+)
+
+add_entrypoint_object(
+  hdestroy
+  SRCS
+  hdestroy.cpp
+  HDRS 
+  hdestroy.h
+  DEPENDS
+    .hashtable.global
+    .hashtable.utils
+)
+
+add_entrypoint_object(
+  hdestroy_r
+  SRCS
+    hdestroy_r.cpp
+  HDRS 
+    hdestroy_r.h
+  DEPENDS
+    .hashtable.utils
+    libc.include.stdlib
+)

libc/src/search/hashtable/CMakeLists.txt

+add_header_library(
+  utils
+  HDRS
+    utils.h
+  DEPENDS
+    libc.src.__support.wyhash
+    libc.src.__support.swisstable
+    libc.src.string.strcmp
+    libc.src.string.strlen
+    libc.include.search
+)
+
+add_object_library(
+  global
+  SRCS
+    global.cpp 
+  HDRS
+    global.h
+  DEPENDS
+    .utils
+)
+
+add_header_library(
+  search_impl
+  HDRS
+    search_impl.h
+  DEPENDS
+    .utils
+    libc.include.errno
+)

libc/src/search/hashtable/global.h

+//===-- Implementation Header of Global Hashtable -------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HASHTABLE_GLOBAL_H
+#define LLVM_LIBC_SRC_SEARCH_HASHTABLE_GLOBAL_H
+
+#include "src/search/hashtable/utils.h"
+
+namespace __llvm_libc::search::hashtable {
+extern SeededTable global_raw_table;
+} // namespace __llvm_libc::search::hashtable
+
+#endif // LLVM_LIBC_SRC_SEARCH_HASHTABLE_GLOBAL_H

libc/src/search/hashtable/global.cpp

+//===-- Implementation of Global Hashtable --------------------------------===//
+//
+// 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/search/hashtable/global.h"
+
+namespace __llvm_libc::search::hashtable {
+SeededTable global_raw_table;
+}

libc/src/search/hashtable/search_impl.h

+//===-- Implementation Header of Hashtable Search  -------------------  ---===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_LIBC_SRC_SEARCH_HASHTABLE_SEARCH_IMPL_H
+#define LLVM_LIBC_SRC_SEARCH_HASHTABLE_SEARCH_IMPL_H
+
+#include "src/search/hashtable/utils.h"
+#include <errno.h>
+namespace __llvm_libc::search::hashtable {
+
+static inline int search_impl(ENTRY item, ACTION action, ENTRY **retval,
+                              SeededTable *table) {
+  using namespace search;
+  Hash hasher{table->seed};
+  switch (action) {
+  case ENTER: {
+    auto bucket = table->raw.find_or_insert(item, hasher, equal);
+    if (!bucket) {
+      *retval = nullptr;
+      errno = ENOMEM;
+      return 0;
+    }
+    *retval = bucket.ptr - 1;
+    return 1;
+  }
+  case FIND: {
+    auto bucket = table->raw.find(item, hasher, equal);
+    if (!bucket) {
+      *retval = nullptr;
+      errno = ESRCH;
+      return 0;
+    }
+    *retval = bucket.ptr - 1;
+    return 1;
+  }
+  }
+
+  return 0;
+}
+} // namespace __llvm_libc::search::hashtable
+#endif // LLVM_LIBC_SRC_SEARCH_HASHTABLE_SEARCH_IMPL_H

libc/src/search/hashtable/utils.h

+//===-- Utilities of hashtable --------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HASHTABLE_UTILS_H
+#define LLVM_LIBC_SRC_SEARCH_HASHTABLE_UTILS_H
+
+#ifndef LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_RESIZE
+#define LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_RESIZE 0
+#endif
+
+#ifndef LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_DELETION
+#define LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_DELETION 0
+#endif
+
+#include "src/__support/swisstable.h"
+#include "src/__support/wyhash.h"
+#include "src/string/strcmp.h"
+#include "src/string/strlen.h"
+#include <search.h>
+
+namespace __llvm_libc::search::hashtable {
+
+static inline bool equal(const ENTRY &a, const ENTRY &b) {
+  return strcmp(a.key, b.key) == 0;
+}
+
+using RawTable =
+    internal::swisstable::RawTable<ENTRY,
+                                   LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_RESIZE,
+                                   LLVM_LIBC_SEARCH_ENABLE_HASHTABLE_DELETION>;
+
+struct SeededTable {
+  RawTable raw;
+  uint64_t seed;
+};
+
+using Bucket = internal::swisstable::Bucket<ENTRY>;
+
+struct TableHeader {
+  SeededTable *table;
+};
+
+static inline SeededTable *get_table(hsearch_data *hdata) {
+  return reinterpret_cast<TableHeader *>(hdata)->table;
+}
+
+static inline void set_table(hsearch_data *hdata, SeededTable *table) {
+  reinterpret_cast<TableHeader *>(hdata)->table = table;
+}
+
+struct Hash {
+  uint64_t seed;
+  uint64_t operator()(const ENTRY &entry) const {
+    size_t length = __llvm_libc::strlen(entry.key);
+    return internal::wyhash::DefaultHash::hash(entry.key, length, seed);
+  }
+};
+
+// For now, we use only for seed to initialize the table.
+// The number comes from Kunth's PRNG.
+static constexpr inline uint64_t DEFAULT_SEED = 6364136223846793005;
+
+} // namespace __llvm_libc::search::hashtable
+#endif // LLVM_LIBC_SRC_SEARCH_HASHTABLE_UTILS_H

libc/src/search/hcreate.h

+//===-- Implementation header for hcreate -----------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HCREATE_H
+#define LLVM_LIBC_SRC_SEARCH_HCREATE_H
+
+#include <search.h>
+
+namespace __llvm_libc {
+int hcreate(size_t);
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HCREATE_H

libc/src/search/hcreate.cpp

+//===-- Implementation of hcreate -------------------------------*- C++ -*-===//
+//
+// 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/search/hcreate.h"
+#include "src/search/hashtable/global.h"
+#include "src/search/hashtable/utils.h"
+#include <errno.h>
+
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(int, hcreate, (size_t nel)) {
+  using namespace search::hashtable;
+  global_raw_table.raw = RawTable::with_capacity(nel);
+  global_raw_table.seed = DEFAULT_SEED ^ reinterpret_cast<uintptr_t>(&nel);
+  if (!global_raw_table.raw.is_valid()) {
+    errno = ENOMEM;
+    return 0;
+  }
+  return 1;
+}
+
+} // namespace __llvm_libc

libc/src/search/hcreate_r.h

+//===-- Implementation header for hcreate_r ---------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HCREATE_R_H
+#define LLVM_LIBC_SRC_SEARCH_HCREATE_R_H
+
+#include <search.h> // ENTRY, ACTION, hsearch_data
+
+namespace __llvm_libc {
+int hcreate_r(size_t, hsearch_data *);
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HCREATE_R_H

libc/src/search/hcreate_r.cpp

+//===-- Implementation of hcreate_r -----------------------------*- C++ -*-===//
+//
+// 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/search/hcreate_r.h"
+#include "src/search/hashtable/utils.h"
+#include <asm-generic/errno-base.h>
+#include <errno.h>
+#include <stdlib.h>
+
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(int, hcreate_r, (size_t nel, hsearch_data *hdata)) {
+  using namespace search::hashtable;
+
+  if (hdata == nullptr) {
+    errno = EINVAL;
+    return 0;
+  }
+
+  SeededTable *table = static_cast<SeededTable *>(
+      aligned_alloc(alignof(SeededTable), sizeof(SeededTable)));
+
+  if (table == nullptr) {
+    errno = ENOMEM;
+    return 0;
+  }
+
+  table->raw = RawTable::with_capacity(nel);
+
+  if (!table->raw.is_valid()) {
+    free(table);
+    errno = ENOMEM;
+    return 0;
+  }
+
+  set_table(hdata, table);
+  table->seed = DEFAULT_SEED ^ reinterpret_cast<uintptr_t>(table);
+  return 1;
+}
+
+} // namespace __llvm_libc

libc/src/search/hdestroy.h

+//===-- Implementation header for hdestroy ----------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HDESTROY_H
+#define LLVM_LIBC_SRC_SEARCH_HDESTROY_H
+
+namespace __llvm_libc {
+void hdestroy();
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HDESTROY_H

libc/src/search/hdestroy.cpp

+//===-- Implementation of hdestroy ------------------------------*- C++ -*-===//
+//
+// 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/search/hdestroy.h"
+#include "src/search/hashtable/global.h"
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(void, hdestroy, ()) {
+  using namespace search::hashtable;
+  global_raw_table.raw.release();
+  global_raw_table.seed = 0;
+}
+
+} // namespace __llvm_libc

libc/src/search/hdestroy_r.h

+//===-- Implementation header for hdestroy_r --------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HDESTROY_R_H
+#define LLVM_LIBC_SRC_SEARCH_HDESTROY_R_H
+
+#include <search.h>
+
+namespace __llvm_libc {
+void hdestroy_r(hsearch_data *);
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HDESTROY_R_H

libc/src/search/hdestroy_r.cpp

+//===-- Implementation of hdestroy_r ----------------------------*- C++ -*-===//
+//
+// 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/search/hdestroy_r.h"
+#include "src/search/hashtable/utils.h"
+#include <search.h>
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(void, hdestroy_r, (hsearch_data * hdata)) {
+  using namespace search::hashtable;
+  SeededTable *table = get_table(hdata);
+  table->raw.release();
+  table->seed = 0;
+  free(table);
+}
+
+} // namespace __llvm_libc

libc/src/search/hsearch.h

+//===-- Implementation header for hsearch -----------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HSEARCH_H
+#define LLVM_LIBC_SRC_SEARCH_HSEARCH_H
+
+#include <search.h> // ENTRY, ACTION, hsearch_data
+
+namespace __llvm_libc {
+ENTRY *hsearch(ENTRY item, ACTION action);
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HSEARCH_H

libc/src/search/hsearch.cpp

+//===-- Implementation of hsearch -------------------------------*- C++ -*-===//
+//
+// 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/search/hsearch.h"
+#include "src/search/hashtable/global.h"
+#include "src/search/hashtable/search_impl.h"
+
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(ENTRY *, hsearch, (ENTRY item, ACTION action)) {
+  using namespace search::hashtable;
+  ENTRY *e;
+  search_impl(item, action, &e, &global_raw_table);
+  return e;
+}
+
+} // namespace __llvm_libc

libc/src/search/hsearch_r.h

+//===-- Implementation header for hsearch_r ---------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_SEARCH_HSEARCH_R_H
+#define LLVM_LIBC_SRC_SEARCH_HSEARCH_R_H
+
+#include <search.h> // ENTRY, ACTION, hsearch_data
+
+namespace __llvm_libc {
+int hsearch_r(ENTRY item, ACTION action, ENTRY **retval, hsearch_data *);
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SEARCH_HSEARCH_R_H

libc/src/search/hsearch_r.cpp

+//===-- Implementation of hsearch_r -----------------------------*- C++ -*-===//
+//
+// 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/search/hsearch_r.h"
+#include "src/search/hashtable/search_impl.h"
+
+namespace __llvm_libc {
+LLVM_LIBC_FUNCTION(int, hsearch_r,
+                   (ENTRY item, ACTION action, ENTRY **retval,
+                    hsearch_data *hdata)) {
+  using namespace search::hashtable;
+  return search_impl(item, action, retval, get_table(hdata));
+}
+
+} // namespace __llvm_libc

libc/test/src/CMakeLists.txt

 endfunction(add_fp_unittest)
 
 add_subdirectory(__support)
 add_subdirectory(ctype)
 add_subdirectory(errno)
 add_subdirectory(fenv)
 add_subdirectory(inttypes)
 add_subdirectory(math)
+add_subdirectory(search)
 add_subdirectory(string)
 add_subdirectory(stdlib)
 add_subdirectory(stdio)
 
 if(${LIBC_TARGET_OS} STREQUAL "linux")
   add_subdirectory(fcntl)
   add_subdirectory(sched)
   add_subdirectory(sys)

libc/test/src/search/CMakeLists.txt

+add_libc_testsuite(libc_search_unittests)
+add_libc_unittest(
+  hsearch_test
+  SUITE
+    libc_search_unittests
+  SRCS
+    hsearch_test.cpp
+  DEPENDS
+    libc.src.search.hsearch_r
+    libc.src.search.hcreate_r
+    libc.src.search.hdestroy_r
+    libc.src.search.hsearch
+    libc.src.search.hcreate
+    libc.src.search.hdestroy
+    libc.src.errno.errno
+)
 No newline at end of file

libc/test/src/search/hsearch_test.cpp

+//===-- Unittests for hsearch ---------------------------------------------===//
+//
+// 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/search/hcreate.h"
+#include "src/search/hcreate_r.h"
+#include "src/search/hdestroy.h"
+#include "src/search/hsearch.h"
+#include "test/ErrnoSetterMatcher.h"
+#include "utils/UnitTest/LibcTest.h"
+#include <asm-generic/errno-base.h>
+
+TEST(LlvmLibcHsearchTest, CreateTooLarge) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  struct hsearch_data hdata;
+  ASSERT_THAT(__llvm_libc::hcreate(-1), Fails(ENOMEM, 0));
+  ASSERT_THAT(__llvm_libc::hcreate_r(-1, &hdata), Fails(ENOMEM, 0));
+}
+
+TEST(LlvmLibcHSearchTest, CreateInvalid) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  ASSERT_THAT(__llvm_libc::hcreate_r(16, nullptr), Fails(EINVAL, 0));
+}
+
+TEST(LlvmLibcHSearchTest, CreateValid) {
+  struct hsearch_data hdata;
+  ASSERT_GT(__llvm_libc::hcreate_r(16, &hdata), 0);
+  hdestroy_r(&hdata);
+
+  ASSERT_GT(__llvm_libc::hcreate(16), 0);
+  hdestroy();
+}
+
+char search_data[] = "1234567890abcdefghijklmnopqrstuvwxyz"
+                     "1234567890abcdefghijklmnopqrstuvwxyz"
+                     "1234567890abcdefghijklmnopqrstuvwxyz"
+                     "1234567890abcdefghijklmnopqrstuvwxyz"
+                     "1234567890abcdefghijklmnopqrstuvwxyz";
+char search_data2[] =
+    "@@@@@@@@@@@@@@!!!!!!!!!!!!!!!!!###########$$$$$$$$$$^^^^^^&&&&&&&&";
+
+TEST(LlvmLibcHSearchTest, InsertTooMany) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  ASSERT_GT(__llvm_libc::hcreate(16), 0);
+  for (size_t i = 0; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch({&search_data[i], nullptr}, ENTER)->key,
+              &search_data[i]);
+  }
+  ASSERT_THAT(
+      static_cast<void *>(__llvm_libc::hsearch({search_data2, nullptr}, ENTER)),
+      Fails(ENOMEM, static_cast<void *>(nullptr)));
+  hdestroy();
+}
+
+TEST(LlvmLibcHSearchTest, NotFound) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  ASSERT_GT(__llvm_libc::hcreate(16), 0);
+  ASSERT_THAT(
+      static_cast<void *>(__llvm_libc::hsearch({search_data2, nullptr}, FIND)),
+      Fails(ESRCH, static_cast<void *>(nullptr)));
+  for (size_t i = 0; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch({&search_data[i], nullptr}, ENTER)->key,
+              &search_data[i]);
+  }
+  ASSERT_THAT(
+      static_cast<void *>(__llvm_libc::hsearch({search_data2, nullptr}, FIND)),
+      Fails(ESRCH, static_cast<void *>(nullptr)));
+  hdestroy();
+}
+
+TEST(LlvmLibcHSearchTest, Found) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  ASSERT_GT(__llvm_libc::hcreate(16), 0);
+  for (size_t i = 0; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch(
+                  {&search_data[i], reinterpret_cast<void *>(i)}, ENTER)
+                  ->key,
+              &search_data[i]);
+  }
+  for (size_t i = 0; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch({&search_data[i], nullptr}, FIND)->data,
+              reinterpret_cast<void *>(i));
+  }
+  hdestroy();
+}
+
+TEST(LlvmLibcHSearchTest, OnlyInsertWhenNotFound) {
+  using __llvm_libc::testing::ErrnoSetterMatcher::Fails;
+  ASSERT_GT(__llvm_libc::hcreate(16), 0);
+  for (size_t i = 0; i < 16 * 5; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch(
+                  {&search_data[i], reinterpret_cast<void *>(i)}, ENTER)
+                  ->key,
+              &search_data[i]);
+  }
+  for (size_t i = 0; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch(
+                  {&search_data[i], reinterpret_cast<void *>(1000 + i)}, ENTER)
+                  ->key,
+              &search_data[i]);
+  }
+  for (size_t i = 0; i < 16 * 5; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch({&search_data[i], nullptr}, FIND)->data,
+              reinterpret_cast<void *>(i));
+  }
+  for (size_t i = 16 * 5; i < 16 * 7; ++i) {
+    ASSERT_EQ(__llvm_libc::hsearch({&search_data[i], nullptr}, FIND)->data,
+              reinterpret_cast<void *>(1000 + i));
+  }
+  hdestroy();
+}