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