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