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
13 using namespace llvm;
14
15 namespace {
16
17 // Test fixture
18 class DenseMapTest : public testing::Test {
19 protected:
20 DenseMap<uint32_t, uint32_t> uintMap;
21 DenseMap<uint32_t *, uint32_t *> uintPtrMap;
22 uint32_t dummyInt;
23 };
24
25 // Empty map tests
TEST_F(DenseMapTest,EmptyIntMapTest)26 TEST_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
TEST_F(DenseMapTest,EmptyPtrMapTest)41 TEST_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
TEST_F(DenseMapTest,ConstEmptyMapTest)56 TEST_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
TEST_F(DenseMapTest,SingleEntryMapTest)68 TEST_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
TEST_F(DenseMapTest,ClearTest)91 TEST_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
TEST_F(DenseMapTest,EraseTest)101 TEST_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
TEST_F(DenseMapTest,EraseTest2)111 TEST_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
TEST_F(DenseMapTest,InsertTest)121 TEST_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
TEST_F(DenseMapTest,CopyConstructorTest)128 TEST_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
TEST_F(DenseMapTest,AssignmentTest)137 TEST_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
TEST_F(DenseMapTest,IterationTest)146 TEST_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
TEST_F(DenseMapTest,ConstIteratorTest)168 TEST_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 }
180