1//===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "gtest/gtest.h"
11#include "llvm/ADT/DenseMap.h"
12
13using namespace llvm;
14
15namespace {
16
17// Test fixture
18class DenseMapTest : public testing::Test {
19protected:
20  DenseMap<uint32_t, uint32_t> uintMap;
21  DenseMap<uint32_t *, uint32_t *> uintPtrMap;
22  uint32_t dummyInt;
23};
24
25// Empty map tests
26TEST_F(DenseMapTest, EmptyIntMapTest) {
27  // Size tests
28  EXPECT_EQ(0u, uintMap.size());
29  EXPECT_TRUE(uintMap.empty());
30
31  // Iterator tests
32  EXPECT_TRUE(uintMap.begin() == uintMap.end());
33
34  // Lookup tests
35  EXPECT_FALSE(uintMap.count(0u));
36  EXPECT_TRUE(uintMap.find(0u) == uintMap.end());
37  EXPECT_EQ(0u, uintMap.lookup(0u));
38}
39
40// Empty map tests for pointer map
41TEST_F(DenseMapTest, EmptyPtrMapTest) {
42  // Size tests
43  EXPECT_EQ(0u, uintPtrMap.size());
44  EXPECT_TRUE(uintPtrMap.empty());
45
46  // Iterator tests
47  EXPECT_TRUE(uintPtrMap.begin() == uintPtrMap.end());
48
49  // Lookup tests
50  EXPECT_FALSE(uintPtrMap.count(&dummyInt));
51  EXPECT_TRUE(uintPtrMap.find(&dummyInt) == uintPtrMap.begin());
52  EXPECT_EQ(0, uintPtrMap.lookup(&dummyInt));
53}
54
55// Constant map tests
56TEST_F(DenseMapTest, ConstEmptyMapTest) {
57  const DenseMap<uint32_t, uint32_t> & constUintMap = uintMap;
58  const DenseMap<uint32_t *, uint32_t *> & constUintPtrMap = uintPtrMap;
59  EXPECT_EQ(0u, constUintMap.size());
60  EXPECT_EQ(0u, constUintPtrMap.size());
61  EXPECT_TRUE(constUintMap.empty());
62  EXPECT_TRUE(constUintPtrMap.empty());
63  EXPECT_TRUE(constUintMap.begin() == constUintMap.end());
64  EXPECT_TRUE(constUintPtrMap.begin() == constUintPtrMap.end());
65}
66
67// A map with a single entry
68TEST_F(DenseMapTest, SingleEntryMapTest) {
69  uintMap[0] = 1;
70
71  // Size tests
72  EXPECT_EQ(1u, uintMap.size());
73  EXPECT_FALSE(uintMap.begin() == uintMap.end());
74  EXPECT_FALSE(uintMap.empty());
75
76  // Iterator tests
77  DenseMap<uint32_t, uint32_t>::iterator it = uintMap.begin();
78  EXPECT_EQ(0u, it->first);
79  EXPECT_EQ(1u, it->second);
80  ++it;
81  EXPECT_TRUE(it == uintMap.end());
82
83  // Lookup tests
84  EXPECT_TRUE(uintMap.count(0u));
85  EXPECT_TRUE(uintMap.find(0u) == uintMap.begin());
86  EXPECT_EQ(1u, uintMap.lookup(0u));
87  EXPECT_EQ(1u, uintMap[0]);
88}
89
90// Test clear() method
91TEST_F(DenseMapTest, ClearTest) {
92  uintMap[0] = 1;
93  uintMap.clear();
94
95  EXPECT_EQ(0u, uintMap.size());
96  EXPECT_TRUE(uintMap.empty());
97  EXPECT_TRUE(uintMap.begin() == uintMap.end());
98}
99
100// Test erase(iterator) method
101TEST_F(DenseMapTest, EraseTest) {
102  uintMap[0] = 1;
103  uintMap.erase(uintMap.begin());
104
105  EXPECT_EQ(0u, uintMap.size());
106  EXPECT_TRUE(uintMap.empty());
107  EXPECT_TRUE(uintMap.begin() == uintMap.end());
108}
109
110// Test erase(value) method
111TEST_F(DenseMapTest, EraseTest2) {
112  uintMap[0] = 1;
113  uintMap.erase(0);
114
115  EXPECT_EQ(0u, uintMap.size());
116  EXPECT_TRUE(uintMap.empty());
117  EXPECT_TRUE(uintMap.begin() == uintMap.end());
118}
119
120// Test insert() method
121TEST_F(DenseMapTest, InsertTest) {
122  uintMap.insert(std::make_pair(0u, 1u));
123  EXPECT_EQ(1u, uintMap.size());
124  EXPECT_EQ(1u, uintMap[0]);
125}
126
127// Test copy constructor method
128TEST_F(DenseMapTest, CopyConstructorTest) {
129  uintMap[0] = 1;
130  DenseMap<uint32_t, uint32_t> copyMap(uintMap);
131
132  EXPECT_EQ(1u, copyMap.size());
133  EXPECT_EQ(1u, copyMap[0]);
134}
135
136// Test assignment operator method
137TEST_F(DenseMapTest, AssignmentTest) {
138  uintMap[0] = 1;
139  DenseMap<uint32_t, uint32_t> copyMap = uintMap;
140
141  EXPECT_EQ(1u, copyMap.size());
142  EXPECT_EQ(1u, copyMap[0]);
143}
144
145// A more complex iteration test
146TEST_F(DenseMapTest, IterationTest) {
147  bool visited[100];
148
149  // Insert 100 numbers into the map
150  for (int i = 0; i < 100; ++i) {
151    visited[i] = false;
152    uintMap[i] = 3;
153  }
154
155  // Iterate over all numbers and mark each one found.
156  for (DenseMap<uint32_t, uint32_t>::iterator it = uintMap.begin();
157      it != uintMap.end(); ++it) {
158    visited[it->first] = true;
159  }
160
161  // Ensure every number was visited.
162  for (int i = 0; i < 100; ++i) {
163    ASSERT_TRUE(visited[i]) << "Entry #" << i << " was never visited";
164  }
165}
166
167// const_iterator test
168TEST_F(DenseMapTest, ConstIteratorTest) {
169  // Check conversion from iterator to const_iterator.
170  DenseMap<uint32_t, uint32_t>::iterator it = uintMap.begin();
171  DenseMap<uint32_t, uint32_t>::const_iterator cit(it);
172  EXPECT_TRUE(it == cit);
173
174  // Check copying of const_iterators.
175  DenseMap<uint32_t, uint32_t>::const_iterator cit2(cit);
176  EXPECT_TRUE(cit == cit2);
177}
178
179// Key traits that allows lookup with either an unsigned or char* key;
180// In the latter case, "a" == 0, "b" == 1 and so on.
181struct TestDenseMapInfo {
182  static inline unsigned getEmptyKey() { return ~0; }
183  static inline unsigned getTombstoneKey() { return ~0U - 1; }
184  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
185  static unsigned getHashValue(const char* Val) {
186    return (unsigned)(Val[0] - 'a') * 37U;
187  }
188  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
189    return LHS == RHS;
190  }
191  static bool isEqual(const char* LHS, const unsigned& RHS) {
192    return (unsigned)(LHS[0] - 'a') == RHS;
193  }
194};
195
196// find_as() tests
197TEST_F(DenseMapTest, FindAsTest) {
198  DenseMap<unsigned, unsigned, TestDenseMapInfo> map;
199  map[0] = 1;
200  map[1] = 2;
201  map[2] = 3;
202
203  // Size tests
204  EXPECT_EQ(3u, map.size());
205
206  // Normal lookup tests
207  EXPECT_EQ(1, map.count(1));
208  EXPECT_EQ(1u, map.find(0)->second);
209  EXPECT_EQ(2u, map.find(1)->second);
210  EXPECT_EQ(3u, map.find(2)->second);
211  EXPECT_TRUE(map.find(3) == map.end());
212
213  // find_as() tests
214  EXPECT_EQ(1u, map.find_as("a")->second);
215  EXPECT_EQ(2u, map.find_as("b")->second);
216  EXPECT_EQ(3u, map.find_as("c")->second);
217  EXPECT_TRUE(map.find_as("d") == map.end());
218}
219
220}
221