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 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 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 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 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 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 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 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