269 lines · cpp
1//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//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 "llvm/ADT/DenseSet.h"10#include "gmock/gmock.h"11#include "gtest/gtest.h"12#include <type_traits>13 14using namespace llvm;15 16namespace {17 18static_assert(19 std::is_const_v<20 std::remove_pointer_t<DenseSet<int>::const_iterator::pointer>>,21 "Iterator pointer type should be const");22static_assert(23 std::is_const_v<24 std::remove_reference_t<DenseSet<int>::const_iterator::reference>>,25 "Iterator reference type should be const");26 27// Test hashing with a set of only two entries.28TEST(DenseSetTest, DoubleEntrySetTest) {29 llvm::DenseSet<unsigned> set(2);30 set.insert(0);31 set.insert(1);32 // Original failure was an infinite loop in this call:33 EXPECT_EQ(0u, set.count(2));34}35 36TEST(DenseSetTest, CtorRange) {37 constexpr unsigned Args[] = {3, 1, 2};38 llvm::DenseSet<unsigned> set(llvm::from_range, Args);39 EXPECT_THAT(set, ::testing::UnorderedElementsAre(1, 2, 3));40}41 42TEST(DenseSetTest, CtorRangeImplicitConversion) {43 constexpr char Args[] = {3, 1, 2};44 llvm::DenseSet<unsigned> set(llvm::from_range, Args);45 EXPECT_THAT(set, ::testing::UnorderedElementsAre(1, 2, 3));46}47 48TEST(SmallDenseSetTest, CtorRange) {49 constexpr unsigned Args[] = {9, 7, 8};50 llvm::SmallDenseSet<unsigned> set(llvm::from_range, Args);51 EXPECT_THAT(set, ::testing::UnorderedElementsAre(7, 8, 9));52}53 54TEST(DenseSetTest, InsertRange) {55 llvm::DenseSet<unsigned> set;56 constexpr unsigned Args[] = {3, 1, 2};57 set.insert_range(Args);58 EXPECT_THAT(set, ::testing::UnorderedElementsAre(1, 2, 3));59}60 61TEST(SmallDenseSetTest, InsertRange) {62 llvm::SmallDenseSet<unsigned> set;63 constexpr unsigned Args[] = {9, 7, 8};64 set.insert_range(Args);65 EXPECT_THAT(set, ::testing::UnorderedElementsAre(7, 8, 9));66}67 68struct TestDenseSetInfo {69 static inline unsigned getEmptyKey() { return ~0; }70 static inline unsigned getTombstoneKey() { return ~0U - 1; }71 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }72 static unsigned getHashValue(const char* Val) {73 return (unsigned)(Val[0] - 'a') * 37U;74 }75 static bool isEqual(const unsigned& LHS, const unsigned& RHS) {76 return LHS == RHS;77 }78 static bool isEqual(const char* LHS, const unsigned& RHS) {79 return (unsigned)(LHS[0] - 'a') == RHS;80 }81};82 83// Test fixture84template <typename T> class DenseSetTest : public testing::Test {85protected:86 T Set = GetTestSet();87 88private:89 static T GetTestSet() {90 std::remove_const_t<T> Set;91 Set.insert(0);92 Set.insert(1);93 Set.insert(2);94 return Set;95 }96};97 98// Register these types for testing.99using DenseSetTestTypes =100 ::testing::Types<DenseSet<unsigned, TestDenseSetInfo>,101 const DenseSet<unsigned, TestDenseSetInfo>,102 SmallDenseSet<unsigned, 1, TestDenseSetInfo>,103 SmallDenseSet<unsigned, 4, TestDenseSetInfo>,104 const SmallDenseSet<unsigned, 4, TestDenseSetInfo>,105 SmallDenseSet<unsigned, 64, TestDenseSetInfo>>;106TYPED_TEST_SUITE(DenseSetTest, DenseSetTestTypes, );107 108TYPED_TEST(DenseSetTest, Constructor) {109 constexpr unsigned a[] = {1, 2, 4};110 TypeParam set(std::begin(a), std::end(a));111 EXPECT_EQ(3u, set.size());112 EXPECT_EQ(1u, set.count(1));113 EXPECT_EQ(1u, set.count(2));114 EXPECT_EQ(1u, set.count(4));115}116 117TYPED_TEST(DenseSetTest, InitializerList) {118 TypeParam set({1, 2, 1, 4});119 EXPECT_EQ(3u, set.size());120 EXPECT_EQ(1u, set.count(1));121 EXPECT_EQ(1u, set.count(2));122 EXPECT_EQ(1u, set.count(4));123 EXPECT_EQ(0u, set.count(3));124}125 126TYPED_TEST(DenseSetTest, InitializerListWithNonPowerOfTwoLength) {127 TypeParam set({1, 2, 3});128 EXPECT_EQ(3u, set.size());129 EXPECT_EQ(1u, set.count(1));130 EXPECT_EQ(1u, set.count(2));131 EXPECT_EQ(1u, set.count(3));132}133 134TYPED_TEST(DenseSetTest, ConstIteratorComparison) {135 TypeParam set({1});136 const TypeParam &cset = set;137 EXPECT_EQ(set.begin(), cset.begin());138 EXPECT_EQ(set.end(), cset.end());139 EXPECT_NE(set.end(), cset.begin());140 EXPECT_NE(set.begin(), cset.end());141}142 143TYPED_TEST(DenseSetTest, DefaultConstruction) {144 typename TypeParam::iterator I, J;145 typename TypeParam::const_iterator CI, CJ;146 EXPECT_EQ(I, J);147 EXPECT_EQ(CI, CJ);148}149 150TYPED_TEST(DenseSetTest, EmptyInitializerList) {151 TypeParam set({});152 EXPECT_EQ(0u, set.size());153 EXPECT_EQ(0u, set.count(0));154}155 156TYPED_TEST(DenseSetTest, FindAsTest) {157 auto &set = this->Set;158 // Size tests159 EXPECT_EQ(3u, set.size());160 161 // Normal lookup tests162 EXPECT_EQ(1u, set.count(1));163 EXPECT_EQ(0u, *set.find(0));164 EXPECT_EQ(1u, *set.find(1));165 EXPECT_EQ(2u, *set.find(2));166 EXPECT_TRUE(set.find(3) == set.end());167 168 // find_as() tests169 EXPECT_EQ(0u, *set.find_as("a"));170 EXPECT_EQ(1u, *set.find_as("b"));171 EXPECT_EQ(2u, *set.find_as("c"));172 EXPECT_TRUE(set.find_as("d") == set.end());173}174 175TYPED_TEST(DenseSetTest, EqualityComparisonTest) {176 TypeParam set1({1, 2, 3, 4});177 TypeParam set2({4, 3, 2, 1});178 TypeParam set3({2, 3, 4, 5});179 180 EXPECT_EQ(set1, set2);181 EXPECT_NE(set1, set3);182}183 184// Simple class that counts how many moves and copy happens when growing a map185struct CountCopyAndMove {186 static int Move;187 static int Copy;188 int Value;189 CountCopyAndMove(int Value) : Value(Value) {}190 191 CountCopyAndMove(const CountCopyAndMove &RHS) {192 Value = RHS.Value;193 Copy++;194 }195 CountCopyAndMove &operator=(const CountCopyAndMove &RHS) {196 Value = RHS.Value;197 Copy++;198 return *this;199 }200 CountCopyAndMove(CountCopyAndMove &&RHS) {201 Value = RHS.Value;202 Move++;203 }204 CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) {205 Value = RHS.Value;206 Move++;207 return *this;208 }209};210int CountCopyAndMove::Copy = 0;211int CountCopyAndMove::Move = 0;212} // anonymous namespace213 214namespace llvm {215// Specialization required to insert a CountCopyAndMove into a DenseSet.216template <> struct DenseMapInfo<CountCopyAndMove> {217 static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); };218 static inline CountCopyAndMove getTombstoneKey() {219 return CountCopyAndMove(-2);220 };221 static unsigned getHashValue(const CountCopyAndMove &Val) {222 return Val.Value;223 }224 static bool isEqual(const CountCopyAndMove &LHS,225 const CountCopyAndMove &RHS) {226 return LHS.Value == RHS.Value;227 }228};229}230 231namespace {232// Make sure reserve actually gives us enough buckets to insert N items233// without increasing allocation size.234TEST(DenseSetCustomTest, ReserveTest) {235 // Test a few different size, 48 is *not* a random choice: we need a value236 // that is 2/3 of a power of two to stress the grow() condition, and the power237 // of two has to be at least 64 because of minimum size allocation in the238 // DenseMa. 66 is a value just above the 64 default init.239 for (auto Size : {1, 2, 48, 66}) {240 DenseSet<CountCopyAndMove> Set;241 Set.reserve(Size);242 unsigned MemorySize = Set.getMemorySize();243 CountCopyAndMove::Copy = 0;244 CountCopyAndMove::Move = 0;245 for (int i = 0; i < Size; ++i)246 Set.insert(CountCopyAndMove(i));247 // Check that we didn't grow248 EXPECT_EQ(MemorySize, Set.getMemorySize());249 // Check that move was called the expected number of times250 EXPECT_EQ(Size, CountCopyAndMove::Move);251 // Check that no copy occurred252 EXPECT_EQ(0, CountCopyAndMove::Copy);253 }254}255TEST(DenseSetCustomTest, ConstTest) {256 // Test that const pointers work okay for count and find, even when the257 // underlying map is a non-const pointer.258 DenseSet<int *> Map;259 int A;260 int *B = &A;261 const int *C = &A;262 Map.insert(B);263 EXPECT_EQ(Map.count(B), 1u);264 EXPECT_EQ(Map.count(C), 1u);265 EXPECT_TRUE(Map.contains(B));266 EXPECT_TRUE(Map.contains(C));267}268}269