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