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
TEST(LlvmLibcHsearchTest,CreateTooLarge)19 TEST(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
TEST(LlvmLibcHSearchTest,CreateInvalid)26 TEST(LlvmLibcHSearchTest, CreateInvalid) {
27 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
28 ASSERT_THAT(LIBC_NAMESPACE::hcreate_r(16, nullptr), Fails(EINVAL, 0));
29 }
30
TEST(LlvmLibcHSearchTest,CreateValid)31 TEST(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
40 char search_data[] = "1234567890abcdefghijklmnopqrstuvwxyz"
41 "1234567890abcdefghijklmnopqrstuvwxyz"
42 "1234567890abcdefghijklmnopqrstuvwxyz"
43 "1234567890abcdefghijklmnopqrstuvwxyz"
44 "1234567890abcdefghijklmnopqrstuvwxyz";
45 char search_data2[] =
46 "@@@@@@@@@@@@@@!!!!!!!!!!!!!!!!!###########$$$$$$$$$$^^^^^^&&&&&&&&";
47
48 constexpr size_t GROUP_SIZE = sizeof(LIBC_NAMESPACE::internal::Group);
49 constexpr size_t CAP =
50 LIBC_NAMESPACE::cpp::bit_ceil((GROUP_SIZE + 1) * 8 / 7) / 8 * 7;
51 static_assert(CAP < sizeof(search_data), "CAP too large");
52
TEST(LlvmLibcHSearchTest,GrowFromZero)53 TEST(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
TEST(LlvmLibcHSearchTest,NotFound)71 TEST(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
TEST(LlvmLibcHSearchTest,Found)87 TEST(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
TEST(LlvmLibcHSearchTest,OnlyInsertWhenNotFound)103 TEST(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