1//===- llvm/unittest/ADT/SmallPtrSetTest.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// SmallPtrSet unit tests.
11//
12//===----------------------------------------------------------------------===//
13
14#include "gtest/gtest.h"
15#include "llvm/ADT/SmallPtrSet.h"
16
17using namespace llvm;
18
19TEST(SmallPtrSetTest, Assignment) {
20  int buf[8];
21  for (int i = 0; i < 8; ++i)
22    buf[i] = 0;
23
24  SmallPtrSet<int *, 4> s1;
25  s1.insert(&buf[0]);
26  s1.insert(&buf[1]);
27
28  SmallPtrSet<int *, 4> s2;
29  (s2 = s1).insert(&buf[2]);
30
31  // Self assign as well.
32  (s2 = s2).insert(&buf[3]);
33
34  s1 = s2;
35  EXPECT_EQ(4U, s1.size());
36  for (int i = 0; i < 8; ++i)
37    if (i < 4)
38      EXPECT_TRUE(s1.count(&buf[i]));
39    else
40      EXPECT_FALSE(s1.count(&buf[i]));
41}
42
43TEST(SmallPtrSetTest, GrowthTest) {
44  int i;
45  int buf[8];
46  for(i=0; i<8; ++i) buf[i]=0;
47
48
49  SmallPtrSet<int *, 4> s;
50  typedef SmallPtrSet<int *, 4>::iterator iter;
51
52  s.insert(&buf[0]);
53  s.insert(&buf[1]);
54  s.insert(&buf[2]);
55  s.insert(&buf[3]);
56  EXPECT_EQ(4U, s.size());
57
58  i = 0;
59  for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
60      (**I)++;
61  EXPECT_EQ(4, i);
62  for(i=0; i<8; ++i)
63      EXPECT_EQ(i<4?1:0,buf[i]);
64
65  s.insert(&buf[4]);
66  s.insert(&buf[5]);
67  s.insert(&buf[6]);
68  s.insert(&buf[7]);
69
70  i = 0;
71  for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
72      (**I)++;
73  EXPECT_EQ(8, i);
74  s.erase(&buf[4]);
75  s.erase(&buf[5]);
76  s.erase(&buf[6]);
77  s.erase(&buf[7]);
78  EXPECT_EQ(4U, s.size());
79
80  i = 0;
81  for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
82      (**I)++;
83  EXPECT_EQ(4, i);
84  for(i=0; i<8; ++i)
85      EXPECT_EQ(i<4?3:1,buf[i]);
86
87  s.clear();
88  for(i=0; i<8; ++i) buf[i]=0;
89  for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires
90  EXPECT_EQ(8U, s.size());
91  for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
92      (**I)++;
93  for(i=0; i<8; ++i)
94      EXPECT_EQ(1,buf[i]);
95}
96
97TEST(SmallPtrSetTest, CopyAndMoveTest) {
98  int buf[8];
99  for (int i = 0; i < 8; ++i)
100    buf[i] = 0;
101
102  SmallPtrSet<int *, 4> s1;
103  s1.insert(&buf[0]);
104  s1.insert(&buf[1]);
105  s1.insert(&buf[2]);
106  s1.insert(&buf[3]);
107  EXPECT_EQ(4U, s1.size());
108  for (int i = 0; i < 8; ++i)
109    if (i < 4)
110      EXPECT_TRUE(s1.count(&buf[i]));
111    else
112      EXPECT_FALSE(s1.count(&buf[i]));
113
114  SmallPtrSet<int *, 4> s2(s1);
115  EXPECT_EQ(4U, s2.size());
116  for (int i = 0; i < 8; ++i)
117    if (i < 4)
118      EXPECT_TRUE(s2.count(&buf[i]));
119    else
120      EXPECT_FALSE(s2.count(&buf[i]));
121
122  s1 = s2;
123  EXPECT_EQ(4U, s1.size());
124  EXPECT_EQ(4U, s2.size());
125  for (int i = 0; i < 8; ++i)
126    if (i < 4)
127      EXPECT_TRUE(s1.count(&buf[i]));
128    else
129      EXPECT_FALSE(s1.count(&buf[i]));
130
131  SmallPtrSet<int *, 4> s3(std::move(s1));
132  EXPECT_EQ(4U, s3.size());
133  EXPECT_TRUE(s1.empty());
134  for (int i = 0; i < 8; ++i)
135    if (i < 4)
136      EXPECT_TRUE(s3.count(&buf[i]));
137    else
138      EXPECT_FALSE(s3.count(&buf[i]));
139
140  // Move assign into the moved-from object. Also test move of a non-small
141  // container.
142  s3.insert(&buf[4]);
143  s3.insert(&buf[5]);
144  s3.insert(&buf[6]);
145  s3.insert(&buf[7]);
146  s1 = std::move(s3);
147  EXPECT_EQ(8U, s1.size());
148  EXPECT_TRUE(s3.empty());
149  for (int i = 0; i < 8; ++i)
150    EXPECT_TRUE(s1.count(&buf[i]));
151
152  // Copy assign into a moved-from object.
153  s3 = s1;
154  EXPECT_EQ(8U, s3.size());
155  EXPECT_EQ(8U, s1.size());
156  for (int i = 0; i < 8; ++i)
157    EXPECT_TRUE(s3.count(&buf[i]));
158}
159
160TEST(SmallPtrSetTest, SwapTest) {
161  int buf[10];
162
163  SmallPtrSet<int *, 2> a;
164  SmallPtrSet<int *, 2> b;
165
166  a.insert(&buf[0]);
167  a.insert(&buf[1]);
168  b.insert(&buf[2]);
169
170  std::swap(a, b);
171
172  EXPECT_EQ(1U, a.size());
173  EXPECT_EQ(2U, b.size());
174  EXPECT_TRUE(a.count(&buf[2]));
175  EXPECT_TRUE(b.count(&buf[0]));
176  EXPECT_TRUE(b.count(&buf[1]));
177
178  b.insert(&buf[3]);
179  std::swap(a, b);
180
181  EXPECT_EQ(3U, a.size());
182  EXPECT_EQ(1U, b.size());
183  EXPECT_TRUE(a.count(&buf[0]));
184  EXPECT_TRUE(a.count(&buf[1]));
185  EXPECT_TRUE(a.count(&buf[3]));
186  EXPECT_TRUE(b.count(&buf[2]));
187
188  std::swap(a, b);
189
190  EXPECT_EQ(1U, a.size());
191  EXPECT_EQ(3U, b.size());
192  EXPECT_TRUE(a.count(&buf[2]));
193  EXPECT_TRUE(b.count(&buf[0]));
194  EXPECT_TRUE(b.count(&buf[1]));
195  EXPECT_TRUE(b.count(&buf[3]));
196
197  a.insert(&buf[4]);
198  a.insert(&buf[5]);
199  a.insert(&buf[6]);
200
201  std::swap(b, a);
202
203  EXPECT_EQ(3U, a.size());
204  EXPECT_EQ(4U, b.size());
205  EXPECT_TRUE(b.count(&buf[2]));
206  EXPECT_TRUE(b.count(&buf[4]));
207  EXPECT_TRUE(b.count(&buf[5]));
208  EXPECT_TRUE(b.count(&buf[6]));
209  EXPECT_TRUE(a.count(&buf[0]));
210  EXPECT_TRUE(a.count(&buf[1]));
211  EXPECT_TRUE(a.count(&buf[3]));
212}
213