18fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman//===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===// 28fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// 38fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// The LLVM Compiler Infrastructure 48fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// 58fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// This file is distributed under the University of Illinois Open Source 68fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// License. See LICENSE.TXT for details. 78fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// 88fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman//===----------------------------------------------------------------------===// 98fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 108fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman#include "gtest/gtest.h" 118fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman#include "llvm/ADT/DenseMap.h" 12e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth#include <map> 136446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth#include <set> 148fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 158fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukmanusing namespace llvm; 168fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 178fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukmannamespace { 188fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 19dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthuint32_t getTestKey(int i, uint32_t *) { return i; } 20dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthuint32_t getTestValue(int i, uint32_t *) { return 42 + i; } 21e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth 22dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthuint32_t *getTestKey(int i, uint32_t **) { 23dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static uint32_t dummy_arr1[8192]; 24dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(i < 8192 && "Only support 8192 dummy keys."); 25dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return &dummy_arr1[i]; 26e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth} 27dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthuint32_t *getTestValue(int i, uint32_t **) { 28e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth static uint32_t dummy_arr1[8192]; 29e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth assert(i < 8192 && "Only support 8192 dummy keys."); 30e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth return &dummy_arr1[i]; 318fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 328fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 336446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth/// \brief A test class that tries to check that construction and destruction 346446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth/// occur correctly. 356446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthclass CtorTester { 366446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth static std::set<CtorTester *> Constructed; 376446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth int Value; 386446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 396446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthpublic: 406446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth explicit CtorTester(int Value = 0) : Value(Value) { 416446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth EXPECT_TRUE(Constructed.insert(this).second); 426446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 436446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth CtorTester(uint32_t Value) : Value(Value) { 446446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth EXPECT_TRUE(Constructed.insert(this).second); 456446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 466446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth CtorTester(const CtorTester &Arg) : Value(Arg.Value) { 476446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth EXPECT_TRUE(Constructed.insert(this).second); 486446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 496446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth ~CtorTester() { 506446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth EXPECT_EQ(1u, Constructed.erase(this)); 516446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 526446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth operator uint32_t() const { return Value; } 536446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 546446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth int getValue() const { return Value; } 556446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; } 566446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth}; 576446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 586446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthstd::set<CtorTester *> CtorTester::Constructed; 596446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 606446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthstruct CtorTesterMapInfo { 616446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth static inline CtorTester getEmptyKey() { return CtorTester(-1); } 626446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth static inline CtorTester getTombstoneKey() { return CtorTester(-2); } 636446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth static unsigned getHashValue(const CtorTester &Val) { 646446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth return Val.getValue() * 37u; 656446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 666446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) { 676446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth return LHS == RHS; 686446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 696446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth}; 706446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 716446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler CarruthCtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } 726446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler CarruthCtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } 736446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 74dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth// Test fixture, with helper functions implemented by forwarding to global 75dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth// function overloads selected by component types of the type parameter. This 76dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth// allows all of the map implementations to be tested with shared 77dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth// implementations of helper routines. 78dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate <typename T> 79dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthclass DenseMapTest : public ::testing::Test { 80dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthprotected: 81dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth T Map; 82dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 83dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static typename T::key_type *const dummy_key_ptr; 84dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static typename T::mapped_type *const dummy_value_ptr; 85dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 86dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename T::key_type getKey(int i = 0) { 87dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return getTestKey(i, dummy_key_ptr); 88dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 89dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename T::mapped_type getValue(int i = 0) { 90dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return getTestValue(i, dummy_value_ptr); 91dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 92dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth}; 93dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 94dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate <typename T> 95dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtypename T::key_type *const DenseMapTest<T>::dummy_key_ptr = 0; 96dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate <typename T> 97dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtypename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = 0; 98e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth 99e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth// Register these types for testing. 100e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruthtypedef ::testing::Types<DenseMap<uint32_t, uint32_t>, 101dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth DenseMap<uint32_t *, uint32_t *>, 1026446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>, 103dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap<uint32_t, uint32_t>, 1046446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth SmallDenseMap<uint32_t *, uint32_t *>, 1056446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth SmallDenseMap<CtorTester, CtorTester, 4, 1066446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth CtorTesterMapInfo> 107dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth > DenseMapTestTypes; 108e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); 109e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth 110e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth// Empty map tests 111e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, EmptyIntMapTest) { 1128fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Size tests 113e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(0u, this->Map.size()); 114e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.empty()); 1158fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1168fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Iterator tests 117e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.begin() == this->Map.end()); 1188fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1198fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Lookup tests 120e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_FALSE(this->Map.count(this->getKey())); 121e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); 1227027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth#ifndef _MSC_VER 123e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(typename TypeParam::mapped_type(), 124e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map.lookup(this->getKey())); 1257027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth#else 1267027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth // MSVC, at least old versions, cannot parse the typename to disambiguate 1277027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth // TypeParam::mapped_type as a type. However, because MSVC doesn't implement 1287027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth // two-phase name lookup, it also doesn't require the typename. Deal with 1297027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth // this mutual incompatibility through specialized code. 1307027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth EXPECT_EQ(TypeParam::mapped_type(), 1317027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth this->Map.lookup(this->getKey())); 1327027ba92dd7381188d3014d2ae1d9bedef9a218eChandler Carruth#endif 1338fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1348fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1358fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Constant map tests 136e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, ConstEmptyMapTest) { 137e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth const TypeParam &ConstMap = this->Map; 138e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(0u, ConstMap.size()); 139e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(ConstMap.empty()); 140e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); 1418fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1428fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1438fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// A map with a single entry 144e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, SingleEntryMapTest) { 145e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 1468fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1478fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Size tests 148e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(1u, this->Map.size()); 149e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_FALSE(this->Map.begin() == this->Map.end()); 150e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_FALSE(this->Map.empty()); 1518fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1528fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Iterator tests 153e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth typename TypeParam::iterator it = this->Map.begin(); 154e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getKey(), it->first); 155e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), it->second); 1568fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman ++it; 157e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(it == this->Map.end()); 1588fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1598fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Lookup tests 160e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.count(this->getKey())); 161e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); 162e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); 163e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 1648fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1658fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1668fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test clear() method 167e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, ClearTest) { 168e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 169e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map.clear(); 1708fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 171e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(0u, this->Map.size()); 172e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.empty()); 173e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.begin() == this->Map.end()); 1748fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1758fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1768fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test erase(iterator) method 177e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, EraseTest) { 178e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 179e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map.erase(this->Map.begin()); 1808fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 181e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(0u, this->Map.size()); 182e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.empty()); 183e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.begin() == this->Map.end()); 1848fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1858fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1868fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test erase(value) method 187e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, EraseTest2) { 188e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 189e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map.erase(this->getKey()); 1908fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 191e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(0u, this->Map.size()); 192e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.empty()); 193e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_TRUE(this->Map.begin() == this->Map.end()); 1948fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 1958fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 1968fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test insert() method 197e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, InsertTest) { 198e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map.insert(std::make_pair(this->getKey(), this->getValue())); 199e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(1u, this->Map.size()); 200e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 2018fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 2028fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2038fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test copy constructor method 204e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, CopyConstructorTest) { 205e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 206e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth TypeParam copyMap(this->Map); 2078fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2088fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman EXPECT_EQ(1u, copyMap.size()); 209e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 2108fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 2118fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2128fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// Test assignment operator method 213e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, AssignmentTest) { 214e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey()] = this->getValue(); 215e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth TypeParam copyMap = this->Map; 2168fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2178fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman EXPECT_EQ(1u, copyMap.size()); 218e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); 2198fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 2208fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2218dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth// Test swap method 2228dffa4a106b52d893388c94c24e365e14c468b7cChandler CarruthTYPED_TEST(DenseMapTest, SwapTest) { 2238dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map[this->getKey()] = this->getValue(); 2248dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth TypeParam otherMap; 2258dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2268dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map.swap(otherMap); 2278dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(0u, this->Map.size()); 2288dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_TRUE(this->Map.empty()); 2298dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(1u, otherMap.size()); 2308dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); 2318dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2328dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map.swap(otherMap); 2338dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(0u, otherMap.size()); 2348dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_TRUE(otherMap.empty()); 2358dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(1u, this->Map.size()); 2368dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); 2378dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2388dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Make this more interesting by inserting 100 numbers into the map. 2398dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (int i = 0; i < 100; ++i) 2408dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map[this->getKey(i)] = this->getValue(i); 2418dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2428dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map.swap(otherMap); 2438dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(0u, this->Map.size()); 2448dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_TRUE(this->Map.empty()); 2458dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(100u, otherMap.size()); 2468dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (int i = 0; i < 100; ++i) 2478dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); 2488dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2498dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth this->Map.swap(otherMap); 2508dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(0u, otherMap.size()); 2518dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_TRUE(otherMap.empty()); 2528dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(100u, this->Map.size()); 2538dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (int i = 0; i < 100; ++i) 2548dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); 2558dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth} 2568dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 2578fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman// A more complex iteration test 258e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, IterationTest) { 2598fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman bool visited[100]; 260e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth std::map<typename TypeParam::key_type, unsigned> visitedIndex; 2618fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2628fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Insert 100 numbers into the map 2638fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman for (int i = 0; i < 100; ++i) { 2648fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman visited[i] = false; 265e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth visitedIndex[this->getKey(i)] = i; 266e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth 267e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth this->Map[this->getKey(i)] = this->getValue(i); 2688fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman } 2698fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2708fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Iterate over all numbers and mark each one found. 271e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth for (typename TypeParam::iterator it = this->Map.begin(); 272e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth it != this->Map.end(); ++it) 273e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth visited[visitedIndex[it->first]] = true; 2748fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 2758fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman // Ensure every number was visited. 276e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth for (int i = 0; i < 100; ++i) 277c870bb5c96c14da387770685dc6f200442a7549dMisha Brukman ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited"; 2788fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 2798fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman 28081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin// const_iterator test 281e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTYPED_TEST(DenseMapTest, ConstIteratorTest) { 28281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Check conversion from iterator to const_iterator. 283e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth typename TypeParam::iterator it = this->Map.begin(); 284e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth typename TypeParam::const_iterator cit(it); 28581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin EXPECT_TRUE(it == cit); 28681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 28781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Check copying of const_iterators. 288e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler Carruth typename TypeParam::const_iterator cit2(cit); 28981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin EXPECT_TRUE(cit == cit2); 29081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin} 29181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 292babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin// Key traits that allows lookup with either an unsigned or char* key; 293babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin// In the latter case, "a" == 0, "b" == 1 and so on. 294babd5980d8a8b4aad9814212a269f6197ebf1f2eTalinstruct TestDenseMapInfo { 295babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static inline unsigned getEmptyKey() { return ~0; } 296babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static inline unsigned getTombstoneKey() { return ~0U - 1; } 297babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 298babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static unsigned getHashValue(const char* Val) { 299babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return (unsigned)(Val[0] - 'a') * 37U; 300babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 301babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 302babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return LHS == RHS; 303babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 304babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static bool isEqual(const char* LHS, const unsigned& RHS) { 305babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return (unsigned)(LHS[0] - 'a') == RHS; 306babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 307babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin}; 308babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 309babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin// find_as() tests 310e5c7bc65c30feabed5f05eecee1ff1433e35d381Chandler CarruthTEST(DenseMapCustomTest, FindAsTest) { 311babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin DenseMap<unsigned, unsigned, TestDenseMapInfo> map; 312babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin map[0] = 1; 313babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin map[1] = 2; 314babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin map[2] = 3; 315babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 316babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin // Size tests 317babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(3u, map.size()); 318babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 319babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin // Normal lookup tests 320babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(1, map.count(1)); 321babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(1u, map.find(0)->second); 322babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(2u, map.find(1)->second); 323babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(3u, map.find(2)->second); 324babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_TRUE(map.find(3) == map.end()); 325babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 326babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin // find_as() tests 327babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(1u, map.find_as("a")->second); 328babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(2u, map.find_as("b")->second); 329babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_EQ(3u, map.find_as("c")->second); 330babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin EXPECT_TRUE(map.find_as("d") == map.end()); 331babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin} 332babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 333fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooperstruct ContiguousDenseMapInfo { 334fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper static inline unsigned getEmptyKey() { return ~0; } 335fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper static inline unsigned getTombstoneKey() { return ~0U - 1; } 336fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper static unsigned getHashValue(const unsigned& Val) { return Val; } 337fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 338fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper return LHS == RHS; 339fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper } 340fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper}; 341fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper 342fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper// Test that filling a small dense map with exactly the number of elements in 343fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper// the map grows to have enough space for an empty bucket. 344fbaf206f470b5a6a54811547641ee41368a2cccdPete CooperTEST(DenseMapCustomTest, SmallDenseMapGrowTest) { 345fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper SmallDenseMap<unsigned, unsigned, 32, ContiguousDenseMapInfo> map; 346fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // Add some number of elements, then delete a few to leave us some tombstones. 347fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // If we just filled the map with 32 elements we'd grow because of not enough 348fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // tombstones which masks the issue here. 349fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper for (unsigned i = 0; i < 20; ++i) 350fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper map[i] = i + 1; 351fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper for (unsigned i = 0; i < 10; ++i) 352fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper map.erase(i); 353fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper for (unsigned i = 20; i < 32; ++i) 354fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper map[i] = i + 1; 355fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper 356fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // Size tests 357fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper EXPECT_EQ(22u, map.size()); 358fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper 359fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // Try to find an element which doesn't exist. There was a bug in 360fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // SmallDenseMap which led to a map with num elements == small capacity not 361fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // having an empty bucket any more. Finding an element not in the map would 362fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper // therefore never terminate. 363fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper EXPECT_TRUE(map.find(32) == map.end()); 364fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper} 365fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper 3668fb520eb4f06d4ef771abe9c22d85b2a275988eeMisha Brukman} 367