ADT/SparseMultiSetTest.cpp: Try to appease cygwin-clang on stage2, take two. [-Wsign...
[oota-llvm.git] / unittests / ADT / SparseMultiSetTest.cpp
1 //===------ ADT/SparseSetTest.cpp - SparseSet 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 "llvm/ADT/SparseMultiSet.h"
11 #include "gtest/gtest.h"
12
13 using namespace llvm;
14
15 namespace {
16
17 typedef SparseMultiSet<unsigned> USet;
18
19 // Empty set tests.
20 TEST(SparseMultiSetTest, EmptySet) {
21   USet Set;
22   EXPECT_TRUE(Set.empty());
23   EXPECT_EQ(0u, Set.size());
24
25   Set.setUniverse(10);
26
27   // Lookups on empty set.
28   EXPECT_TRUE(Set.find(0) == Set.end());
29   EXPECT_TRUE(Set.find(9) == Set.end());
30
31   // Same thing on a const reference.
32   const USet &CSet = Set;
33   EXPECT_TRUE(CSet.empty());
34   EXPECT_EQ(0u, CSet.size());
35   EXPECT_TRUE(CSet.find(0) == CSet.end());
36   USet::const_iterator I = CSet.find(5);
37   EXPECT_TRUE(I == CSet.end());
38 }
39
40 // Single entry set tests.
41 TEST(SparseMultiSetTest, SingleEntrySet) {
42   USet Set;
43   Set.setUniverse(10);
44   USet::iterator I = Set.insert(5);
45   EXPECT_TRUE(I != Set.end());
46   EXPECT_TRUE(*I == 5);
47
48   EXPECT_FALSE(Set.empty());
49   EXPECT_EQ(1u, Set.size());
50
51   EXPECT_TRUE(Set.find(0) == Set.end());
52   EXPECT_TRUE(Set.find(9) == Set.end());
53
54   EXPECT_FALSE(Set.contains(0));
55   EXPECT_TRUE(Set.contains(5));
56
57   // Extra insert.
58   I = Set.insert(5);
59   EXPECT_TRUE(I != Set.end());
60   EXPECT_TRUE(I == ++Set.find(5));
61   I--;
62   EXPECT_TRUE(I == Set.find(5));
63
64   // Erase non-existent element.
65   I = Set.find(1);
66   EXPECT_TRUE(I == Set.end());
67   EXPECT_EQ(2u, Set.size());
68   EXPECT_EQ(5u, *Set.find(5));
69
70   // Erase iterator.
71   I = Set.find(5);
72   EXPECT_TRUE(I != Set.end());
73   I = Set.erase(I);
74   EXPECT_TRUE(I != Set.end());
75   I = Set.erase(I);
76   EXPECT_TRUE(I == Set.end());
77   EXPECT_TRUE(Set.empty());
78 }
79
80 // Multiple entry set tests.
81 TEST(SparseMultiSetTest, MultipleEntrySet) {
82   USet Set;
83   Set.setUniverse(10);
84
85   Set.insert(5);
86   Set.insert(5);
87   Set.insert(5);
88   Set.insert(3);
89   Set.insert(2);
90   Set.insert(1);
91   Set.insert(4);
92   EXPECT_EQ(7u, Set.size());
93
94   // Erase last element by key.
95   EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end());
96   EXPECT_EQ(6u, Set.size());
97   EXPECT_FALSE(Set.contains(4));
98   EXPECT_TRUE(Set.find(4) == Set.end());
99
100   // Erase first element by key.
101   EXPECT_EQ(3u, Set.count(5));
102   EXPECT_TRUE(Set.find(5) != Set.end());
103   EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end());
104   EXPECT_EQ(5u, Set.size());
105   EXPECT_EQ(2u, Set.count(5));
106
107   Set.insert(6);
108   Set.insert(7);
109   EXPECT_EQ(7u, Set.size());
110
111   // Erase tail by iterator.
112   EXPECT_TRUE(Set.getTail(6) == Set.getHead(6));
113   USet::iterator I = Set.erase(Set.find(6));
114   EXPECT_TRUE(I == Set.end());
115   EXPECT_EQ(6u, Set.size());
116
117   // Erase tails by iterator.
118   EXPECT_EQ(2u, Set.count(5));
119   I = Set.getTail(5);
120   I = Set.erase(I);
121   EXPECT_TRUE(I == Set.end());
122   --I;
123   EXPECT_EQ(1u, Set.count(5));
124   EXPECT_EQ(5u, *I);
125   I = Set.erase(I);
126   EXPECT_TRUE(I == Set.end());
127   EXPECT_EQ(0u, Set.count(5));
128
129   Set.insert(8);
130   Set.insert(8);
131   Set.insert(8);
132   Set.insert(8);
133   Set.insert(8);
134
135   // Erase all the 8s
136   EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end()));
137   Set.eraseAll(8);
138   EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end()));
139
140   // Clear and resize the universe.
141   Set.clear();
142   EXPECT_EQ(0u, Set.size());
143   EXPECT_FALSE(Set.contains(3));
144   Set.setUniverse(1000);
145
146   // Add more than 256 elements.
147   for (unsigned i = 100; i != 800; ++i)
148     Set.insert(i);
149
150   for (unsigned i = 0; i != 10; ++i)
151     Set.eraseAll(i);
152
153   for (unsigned i = 100; i != 800; ++i)
154     EXPECT_EQ(1u, Set.count(i));
155
156   EXPECT_FALSE(Set.contains(99));
157   EXPECT_FALSE(Set.contains(800));
158   EXPECT_EQ(700u, Set.size());
159 }
160
161 // Test out iterators
162 TEST(SparseMultiSetTest, Iterators) {
163   USet Set;
164   Set.setUniverse(100);
165
166   Set.insert(0);
167   Set.insert(1);
168   Set.insert(2);
169   Set.insert(0);
170   Set.insert(1);
171   Set.insert(0);
172
173   USet::RangePair RangePair = Set.equal_range(0);
174   USet::iterator B = RangePair.first;
175   USet::iterator E = RangePair.second;
176
177   // Move the iterators around, going to end and coming back.
178   EXPECT_EQ(3, std::distance(B, E));
179   EXPECT_EQ(B, --(--(--E)));
180   EXPECT_EQ(++(++(++E)), Set.end());
181   EXPECT_EQ(B, --(--(--E)));
182   EXPECT_EQ(++(++(++E)), Set.end());
183
184   // Insert into the tail, and move around again
185   Set.insert(0);
186   EXPECT_EQ(B, --(--(--(--E))));
187   EXPECT_EQ(++(++(++(++E))), Set.end());
188   EXPECT_EQ(B, --(--(--(--E))));
189   EXPECT_EQ(++(++(++(++E))), Set.end());
190
191   // Erase a tail, and move around again
192   USet::iterator Erased = Set.erase(Set.getTail(0));
193   EXPECT_EQ(Erased, E);
194   EXPECT_EQ(B, --(--(--E)));
195
196   USet Set2;
197   Set2.setUniverse(11);
198   Set2.insert(3);
199   EXPECT_TRUE(!Set2.contains(0));
200   EXPECT_TRUE(!Set.contains(3));
201
202   EXPECT_EQ(Set2.getHead(3), Set2.getTail(3));
203   EXPECT_EQ(Set2.getHead(0), Set2.getTail(0));
204   B = Set2.find(3);
205   EXPECT_EQ(Set2.find(3), --(++B));
206 }
207
208 struct Alt {
209   unsigned Value;
210   explicit Alt(unsigned x) : Value(x) {}
211   unsigned getSparseSetIndex() const { return Value - 1000; }
212 };
213
214 TEST(SparseMultiSetTest, AltStructSet) {
215   typedef SparseMultiSet<Alt> ASet;
216   ASet Set;
217   Set.setUniverse(10);
218   Set.insert(Alt(1005));
219
220   ASet::iterator I = Set.find(5);
221   ASSERT_TRUE(I != Set.end());
222   EXPECT_EQ(1005u, I->Value);
223
224   Set.insert(Alt(1006));
225   Set.insert(Alt(1006));
226   I = Set.erase(Set.find(6));
227   ASSERT_TRUE(I != Set.end());
228   EXPECT_EQ(1006u, I->Value);
229   I = Set.erase(Set.find(6));
230   ASSERT_TRUE(I == Set.end());
231
232   EXPECT_TRUE(Set.contains(5));
233   EXPECT_FALSE(Set.contains(6));
234 }
235 } // namespace