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 "gtest/gtest.h"
15 #include <string>
16 
17 using namespace llvm;
18 
19 TEST(SmallSetTest, Insert) {
20 
21   SmallSet<int, 4> s1;
22 
23   for (int i = 0; i < 4; i++)
24     s1.insert(i);
25 
26   for (int i = 0; i < 4; i++)
27     s1.insert(i);
28 
29   EXPECT_EQ(4u, s1.size());
30 
31   for (int i = 0; i < 4; i++)
32     EXPECT_EQ(1u, s1.count(i));
33 
34   EXPECT_EQ(0u, s1.count(4));
35 }
36 
37 TEST(SmallSetTest, Grow) {
38   SmallSet<int, 4> s1;
39 
40   for (int i = 0; i < 8; i++)
41     s1.insert(i);
42 
43   EXPECT_EQ(8u, s1.size());
44 
45   for (int i = 0; i < 8; i++)
46     EXPECT_EQ(1u, s1.count(i));
47 
48   EXPECT_EQ(0u, s1.count(8));
49 }
50 
51 TEST(SmallSetTest, Erase) {
52   SmallSet<int, 4> s1;
53 
54   for (int i = 0; i < 8; i++)
55     s1.insert(i);
56 
57   EXPECT_EQ(8u, s1.size());
58 
59   // Remove elements one by one and check if all other elements are still there.
60   for (int i = 0; i < 8; i++) {
61     EXPECT_EQ(1u, s1.count(i));
62     EXPECT_TRUE(s1.erase(i));
63     EXPECT_EQ(0u, s1.count(i));
64     EXPECT_EQ(8u - i - 1, s1.size());
65     for (int j = i + 1; j < 8; j++)
66       EXPECT_EQ(1u, s1.count(j));
67   }
68 
69   EXPECT_EQ(0u, s1.count(8));
70 }
71 
72 TEST(SmallSetTest, IteratorInt) {
73   SmallSet<int, 4> s1;
74 
75   // Test the 'small' case.
76   for (int i = 0; i < 3; i++)
77     s1.insert(i);
78 
79   std::vector<int> V(s1.begin(), s1.end());
80   // Make sure the elements are in the expected order.
81   std::sort(V.begin(), V.end());
82   for (int i = 0; i < 3; i++)
83     EXPECT_EQ(i, V[i]);
84 
85   // Test the 'big' case by adding a few more elements to switch to std::set
86   // internally.
87   for (int i = 3; i < 6; i++)
88     s1.insert(i);
89 
90   V.assign(s1.begin(), s1.end());
91   // Make sure the elements are in the expected order.
92   std::sort(V.begin(), V.end());
93   for (int i = 0; i < 6; i++)
94     EXPECT_EQ(i, V[i]);
95 }
96 
97 TEST(SmallSetTest, IteratorString) {
98   // Test SmallSetIterator for SmallSet with a type with non-trivial
99   // ctors/dtors.
100   SmallSet<std::string, 2> s1;
101 
102   s1.insert("str 1");
103   s1.insert("str 2");
104   s1.insert("str 1");
105 
106   std::vector<std::string> V(s1.begin(), s1.end());
107   std::sort(V.begin(), V.end());
108   EXPECT_EQ(2u, s1.size());
109   EXPECT_EQ("str 1", V[0]);
110   EXPECT_EQ("str 2", V[1]);
111 
112   s1.insert("str 4");
113   s1.insert("str 0");
114   s1.insert("str 4");
115 
116   V.assign(s1.begin(), s1.end());
117   // Make sure the elements are in the expected order.
118   std::sort(V.begin(), V.end());
119   EXPECT_EQ(4u, s1.size());
120   EXPECT_EQ("str 0", V[0]);
121   EXPECT_EQ("str 1", V[1]);
122   EXPECT_EQ("str 2", V[2]);
123   EXPECT_EQ("str 4", V[3]);
124 }
125 
126 TEST(SmallSetTest, IteratorIncMoveCopy) {
127   // Test SmallSetIterator for SmallSet with a type with non-trivial
128   // ctors/dtors.
129   SmallSet<std::string, 2> s1;
130 
131   s1.insert("str 1");
132   s1.insert("str 2");
133 
134   auto Iter = s1.begin();
135   EXPECT_EQ("str 1", *Iter);
136   ++Iter;
137   EXPECT_EQ("str 2", *Iter);
138 
139   s1.insert("str 4");
140   s1.insert("str 0");
141   auto Iter2 = s1.begin();
142   Iter = std::move(Iter2);
143   EXPECT_EQ("str 0", *Iter);
144 }
145 
146 TEST(SmallSetTest, EqualityComparisonTest) {
147   SmallSet<int, 8> s1small;
148   SmallSet<int, 10> s2small;
149   SmallSet<int, 3> s3large;
150   SmallSet<int, 8> s4large;
151 
152   for (int i = 1; i < 5; i++) {
153     s1small.insert(i);
154     s2small.insert(5 - i);
155     s3large.insert(i);
156   }
157   for (int i = 1; i < 11; i++)
158     s4large.insert(i);
159 
160   EXPECT_EQ(s1small, s1small);
161   EXPECT_EQ(s3large, s3large);
162 
163   EXPECT_EQ(s1small, s2small);
164   EXPECT_EQ(s1small, s3large);
165   EXPECT_EQ(s2small, s3large);
166 
167   EXPECT_NE(s1small, s4large);
168   EXPECT_NE(s4large, s3large);
169 }
170 
171 TEST(SmallSetTest, Contains) {
172   SmallSet<int, 2> Set;
173   EXPECT_FALSE(Set.contains(0));
174   EXPECT_FALSE(Set.contains(1));
175 
176   Set.insert(0);
177   Set.insert(1);
178   EXPECT_TRUE(Set.contains(0));
179   EXPECT_TRUE(Set.contains(1));
180 
181   Set.insert(1);
182   EXPECT_TRUE(Set.contains(0));
183   EXPECT_TRUE(Set.contains(1));
184 
185   Set.erase(1);
186   EXPECT_TRUE(Set.contains(0));
187   EXPECT_FALSE(Set.contains(1));
188 
189   Set.insert(1);
190   Set.insert(2);
191   EXPECT_TRUE(Set.contains(0));
192   EXPECT_TRUE(Set.contains(1));
193   EXPECT_TRUE(Set.contains(2));
194 }
195