1//===-- Unittests for hsearch ---------------------------------------------===//
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/table.h"
11#include "src/search/hcreate.h"
12#include "src/search/hcreate_r.h"
13#include "src/search/hdestroy.h"
14#include "src/search/hdestroy_r.h"
15#include "src/search/hsearch.h"
16#include "test/UnitTest/ErrnoSetterMatcher.h"
17#include "test/UnitTest/Test.h"
18
19TEST(LlvmLibcHsearchTest, CreateTooLarge) {
20 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
21 struct hsearch_data hdata;
22 ASSERT_THAT(LIBC_NAMESPACE::hcreate(-1), Fails(ENOMEM, 0));
23 ASSERT_THAT(LIBC_NAMESPACE::hcreate_r(-1, &hdata), Fails(ENOMEM, 0));
24}
25
26TEST(LlvmLibcHSearchTest, CreateInvalid) {
27 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
28 ASSERT_THAT(LIBC_NAMESPACE::hcreate_r(16, nullptr), Fails(EINVAL, 0));
29}
30
31TEST(LlvmLibcHSearchTest, CreateValid) {
32 struct hsearch_data hdata;
33 ASSERT_GT(LIBC_NAMESPACE::hcreate_r(1, &hdata), 0);
34 LIBC_NAMESPACE::hdestroy_r(&hdata);
35
36 ASSERT_GT(LIBC_NAMESPACE::hcreate(1), 0);
37 LIBC_NAMESPACE::hdestroy();
38}
39
40char search_data[] = "1234567890abcdefghijklmnopqrstuvwxyz"
41 "1234567890abcdefghijklmnopqrstuvwxyz"
42 "1234567890abcdefghijklmnopqrstuvwxyz"
43 "1234567890abcdefghijklmnopqrstuvwxyz"
44 "1234567890abcdefghijklmnopqrstuvwxyz";
45char search_data2[] =
46 "@@@@@@@@@@@@@@!!!!!!!!!!!!!!!!!###########$$$$$$$$$$^^^^^^&&&&&&&&";
47
48constexpr size_t GROUP_SIZE = sizeof(LIBC_NAMESPACE::internal::Group);
49constexpr size_t CAP =
50 LIBC_NAMESPACE::cpp::bit_ceil((GROUP_SIZE + 1) * 8 / 7) / 8 * 7;
51static_assert(CAP < sizeof(search_data), "CAP too large");
52
53TEST(LlvmLibcHSearchTest, GrowFromZero) {
54 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
55 ASSERT_GT(LIBC_NAMESPACE::hcreate(0), 0);
56 for (size_t i = 0; i < sizeof(search_data) - 1; ++i) {
57 ENTRY *inserted = LIBC_NAMESPACE::hsearch(
58 {&search_data[i], reinterpret_cast<void *>(i)}, ENTER);
59 ASSERT_NE(inserted, static_cast<ENTRY *>(nullptr));
60 ASSERT_EQ(inserted->key, &search_data[i]);
61 }
62 for (size_t i = sizeof(search_data) - 1; i != 0; --i) {
63 ASSERT_EQ(
64 LIBC_NAMESPACE::hsearch({&search_data[i - 1], nullptr}, FIND)->data,
65 reinterpret_cast<void *>(i - 1));
66 }
67
68 LIBC_NAMESPACE::hdestroy();
69}
70
71TEST(LlvmLibcHSearchTest, NotFound) {
72 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
73 ASSERT_GT(LIBC_NAMESPACE::hcreate(GROUP_SIZE + 1), 0);
74 ASSERT_THAT(static_cast<void *>(
75 LIBC_NAMESPACE::hsearch({search_data2, nullptr}, FIND)),
76 Fails(ESRCH, static_cast<void *>(nullptr)));
77 for (size_t i = 0; i < CAP; ++i) {
78 ASSERT_EQ(LIBC_NAMESPACE::hsearch({&search_data[i], nullptr}, ENTER)->key,
79 &search_data[i]);
80 }
81 ASSERT_THAT(static_cast<void *>(
82 LIBC_NAMESPACE::hsearch({search_data2, nullptr}, FIND)),
83 Fails(ESRCH, static_cast<void *>(nullptr)));
84 LIBC_NAMESPACE::hdestroy();
85}
86
87TEST(LlvmLibcHSearchTest, Found) {
88 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
89 ASSERT_GT(LIBC_NAMESPACE::hcreate(GROUP_SIZE + 1), 0);
90 for (size_t i = 0; i < CAP; ++i) {
91 ENTRY *inserted = LIBC_NAMESPACE::hsearch(
92 {&search_data[i], reinterpret_cast<void *>(i)}, ENTER);
93 ASSERT_NE(inserted, static_cast<ENTRY *>(nullptr));
94 ASSERT_EQ(inserted->key, &search_data[i]);
95 }
96 for (size_t i = 0; i < CAP; ++i) {
97 ASSERT_EQ(LIBC_NAMESPACE::hsearch({&search_data[i], nullptr}, FIND)->data,
98 reinterpret_cast<void *>(i));
99 }
100 LIBC_NAMESPACE::hdestroy();
101}
102
103TEST(LlvmLibcHSearchTest, OnlyInsertWhenNotFound) {
104 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
105 ASSERT_GT(LIBC_NAMESPACE::hcreate(GROUP_SIZE + 1), 0);
106 for (size_t i = 0; i < CAP / 7 * 5; ++i) {
107 ASSERT_EQ(LIBC_NAMESPACE::hsearch(
108 {&search_data[i], reinterpret_cast<void *>(i)}, ENTER)
109 ->key,
110 &search_data[i]);
111 }
112 for (size_t i = 0; i < CAP; ++i) {
113 ASSERT_EQ(LIBC_NAMESPACE::hsearch(
114 {&search_data[i], reinterpret_cast<void *>(1000 + i)}, ENTER)
115 ->key,
116 &search_data[i]);
117 }
118 for (size_t i = 0; i < CAP / 7 * 5; ++i) {
119 ASSERT_EQ(LIBC_NAMESPACE::hsearch({&search_data[i], nullptr}, FIND)->data,
120 reinterpret_cast<void *>(i));
121 }
122 for (size_t i = CAP / 7 * 5; i < CAP; ++i) {
123 ASSERT_EQ(LIBC_NAMESPACE::hsearch({&search_data[i], nullptr}, FIND)->data,
124 reinterpret_cast<void *>(1000 + i));
125 }
126 LIBC_NAMESPACE::hdestroy();
127}
128

source code of libc/test/src/search/hsearch_test.cpp