1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===//
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 // SmallSet unit tests.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/ADT/SmallSet.h"
15 #include "gtest/gtest.h"
16 #include <string>
17
18 using namespace llvm;
19
TEST(SmallSetTest,Insert)20 TEST(SmallSetTest, Insert) {
21
22 SmallSet<int, 4> s1;
23
24 for (int i = 0; i < 4; i++)
25 s1.insert(i);
26
27 for (int i = 0; i < 4; i++)
28 s1.insert(i);
29
30 EXPECT_EQ(4u, s1.size());
31
32 for (int i = 0; i < 4; i++)
33 EXPECT_EQ(1u, s1.count(i));
34
35 EXPECT_EQ(0u, s1.count(4));
36 }
37
TEST(SmallSetTest,Grow)38 TEST(SmallSetTest, Grow) {
39 SmallSet<int, 4> s1;
40
41 for (int i = 0; i < 8; i++)
42 s1.insert(i);
43
44 EXPECT_EQ(8u, s1.size());
45
46 for (int i = 0; i < 8; i++)
47 EXPECT_EQ(1u, s1.count(i));
48
49 EXPECT_EQ(0u, s1.count(8));
50 }
51
TEST(SmallSetTest,Erase)52 TEST(SmallSetTest, Erase) {
53 SmallSet<int, 4> s1;
54
55 for (int i = 0; i < 8; i++)
56 s1.insert(i);
57
58 EXPECT_EQ(8u, s1.size());
59
60 // Remove elements one by one and check if all other elements are still there.
61 for (int i = 0; i < 8; i++) {
62 EXPECT_EQ(1u, s1.count(i));
63 EXPECT_TRUE(s1.erase(i));
64 EXPECT_EQ(0u, s1.count(i));
65 EXPECT_EQ(8u - i - 1, s1.size());
66 for (int j = i + 1; j < 8; j++)
67 EXPECT_EQ(1u, s1.count(j));
68 }
69
70 EXPECT_EQ(0u, s1.count(8));
71 }
72
TEST(SmallSetTest,IteratorInt)73 TEST(SmallSetTest, IteratorInt) {
74 SmallSet<int, 4> s1;
75
76 // Test the 'small' case.
77 for (int i = 0; i < 3; i++)
78 s1.insert(i);
79
80 std::vector<int> V(s1.begin(), s1.end());
81 // Make sure the elements are in the expected order.
82 std::sort(V.begin(), V.end());
83 for (int i = 0; i < 3; i++)
84 EXPECT_EQ(i, V[i]);
85
86 // Test the 'big' case by adding a few more elements to switch to std::set
87 // internally.
88 for (int i = 3; i < 6; i++)
89 s1.insert(i);
90
91 V.assign(s1.begin(), s1.end());
92 // Make sure the elements are in the expected order.
93 std::sort(V.begin(), V.end());
94 for (int i = 0; i < 6; i++)
95 EXPECT_EQ(i, V[i]);
96 }
97
TEST(SmallSetTest,IteratorString)98 TEST(SmallSetTest, IteratorString) {
99 // Test SmallSetIterator for SmallSet with a type with non-trivial
100 // ctors/dtors.
101 SmallSet<std::string, 2> s1;
102
103 s1.insert("str 1");
104 s1.insert("str 2");
105 s1.insert("str 1");
106
107 std::vector<std::string> V(s1.begin(), s1.end());
108 std::sort(V.begin(), V.end());
109 EXPECT_EQ(2u, s1.size());
110 EXPECT_EQ("str 1", V[0]);
111 EXPECT_EQ("str 2", V[1]);
112
113 s1.insert("str 4");
114 s1.insert("str 0");
115 s1.insert("str 4");
116
117 V.assign(s1.begin(), s1.end());
118 // Make sure the elements are in the expected order.
119 std::sort(V.begin(), V.end());
120 EXPECT_EQ(4u, s1.size());
121 EXPECT_EQ("str 0", V[0]);
122 EXPECT_EQ("str 1", V[1]);
123 EXPECT_EQ("str 2", V[2]);
124 EXPECT_EQ("str 4", V[3]);
125 }
126
TEST(SmallSetTest,IteratorIncMoveCopy)127 TEST(SmallSetTest, IteratorIncMoveCopy) {
128 // Test SmallSetIterator for SmallSet with a type with non-trivial
129 // ctors/dtors.
130 SmallSet<std::string, 2> s1;
131
132 s1.insert("str 1");
133 s1.insert("str 2");
134
135 auto Iter = s1.begin();
136 EXPECT_EQ("str 1", *Iter);
137 ++Iter;
138 EXPECT_EQ("str 2", *Iter);
139
140 s1.insert("str 4");
141 s1.insert("str 0");
142 auto Iter2 = s1.begin();
143 Iter = std::move(Iter2);
144 EXPECT_EQ("str 0", *Iter);
145
146 auto Iter3 = s1.end();
147 Iter3 = Iter2;
148 EXPECT_EQ(Iter3, Iter2);
149 }
150