1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===//
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // SmallSet unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ADT/SmallSet.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "gtest/gtest.h"
16 #include <string>
17 
18 using namespace llvm;
19 
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 
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 
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 
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   llvm::sort(V);
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   llvm::sort(V);
94   for (int i = 0; i < 6; i++)
95     EXPECT_EQ(i, V[i]);
96 }
97 
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   llvm::sort(V);
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   llvm::sort(V);
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 
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 
147 TEST(SmallSetTest, EqualityComparisonTest) {
148   SmallSet<int, 8> s1small;
149   SmallSet<int, 10> s2small;
150   SmallSet<int, 3> s3large;
151   SmallSet<int, 8> s4large;
152 
153   for (int i = 1; i < 5; i++) {
154     s1small.insert(i);
155     s2small.insert(5 - i);
156     s3large.insert(i);
157   }
158   for (int i = 1; i < 11; i++)
159     s4large.insert(i);
160 
161   EXPECT_EQ(s1small, s1small);
162   EXPECT_EQ(s3large, s3large);
163 
164   EXPECT_EQ(s1small, s2small);
165   EXPECT_EQ(s1small, s3large);
166   EXPECT_EQ(s2small, s3large);
167 
168   EXPECT_NE(s1small, s4large);
169   EXPECT_NE(s4large, s3large);
170 }
171 
172 TEST(SmallSetTest, Contains) {
173   SmallSet<int, 2> Set;
174   EXPECT_FALSE(Set.contains(0));
175   EXPECT_FALSE(Set.contains(1));
176 
177   Set.insert(0);
178   Set.insert(1);
179   EXPECT_TRUE(Set.contains(0));
180   EXPECT_TRUE(Set.contains(1));
181 
182   Set.insert(1);
183   EXPECT_TRUE(Set.contains(0));
184   EXPECT_TRUE(Set.contains(1));
185 
186   Set.erase(1);
187   EXPECT_TRUE(Set.contains(0));
188   EXPECT_FALSE(Set.contains(1));
189 
190   Set.insert(1);
191   Set.insert(2);
192   EXPECT_TRUE(Set.contains(0));
193   EXPECT_TRUE(Set.contains(1));
194   EXPECT_TRUE(Set.contains(2));
195 }
196