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
20TEST(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
27TEST(LlvmLibcHSearchTest, CreateInvalid) {
28 using LIBC_NAMESPACE::testing::ErrnoSetterMatcher::Fails;
29 ASSERT_THAT(LIBC_NAMESPACE::hcreate_r(16, nullptr), Fails(EINVAL, 0));
30}
31
32TEST(LlvmLibcHSearchTest, CreateValid) {
33 struct hsearch_data hdata;
34 ASSERT_GT(LIBC_NAMESPACE::hcreate_r(1, &hdata), 0);
35 LIBC_NAMESPACE::hdestroy_r(htab: &hdata);
36
37 ASSERT_GT(LIBC_NAMESPACE::hcreate(1), 0);
38 LIBC_NAMESPACE::hdestroy();
39}
40
41char search_data[] = "1234567890abcdefghijklmnopqrstuvwxyz"
42 "1234567890abcdefghijklmnopqrstuvwxyz"
43 "1234567890abcdefghijklmnopqrstuvwxyz"
44 "1234567890abcdefghijklmnopqrstuvwxyz"
45 "1234567890abcdefghijklmnopqrstuvwxyz";
46char search_data2[] =
47 "@@@@@@@@@@@@@@!!!!!!!!!!!!!!!!!###########$$$$$$$$$$^^^^^^&&&&&&&&";
48
49constexpr size_t GROUP_SIZE = sizeof(LIBC_NAMESPACE::internal::Group);
50constexpr size_t CAP =
51 LIBC_NAMESPACE::cpp::bit_ceil(value: (GROUP_SIZE + 1) * 8 / 7) / 8 * 7;
52static_assert(CAP < sizeof(search_data), "CAP too large");
53
54TEST(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 item: {.key: &search_data[i], .data: reinterpret_cast<void *>(i)}, action: 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
72TEST(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
88TEST(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 item: {.key: &search_data[i], .data: reinterpret_cast<void *>(i)}, action: 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
104TEST(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

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