1//===- llvm/unittest/ADT/FoldingSetTest.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// FoldingSet unit tests.
11//
12//===----------------------------------------------------------------------===//
13
14#include "gtest/gtest.h"
15#include "llvm/ADT/FoldingSet.h"
16#include <string>
17
18using namespace llvm;
19
20namespace {
21
22// Unaligned string test.
23TEST(FoldingSetTest, UnalignedStringTest) {
24  SCOPED_TRACE("UnalignedStringTest");
25
26  FoldingSetNodeID a, b;
27  // An aligned string.
28  std::string str1= "a test string";
29  a.AddString(str1);
30
31  // An unaligned string.
32  std::string str2 = ">" + str1;
33  b.AddString(str2.c_str() + 1);
34
35  EXPECT_EQ(a.ComputeHash(), b.ComputeHash());
36}
37
38struct TrivialPair : public FoldingSetNode {
39  unsigned Key = 0;
40  unsigned Value = 0;
41  TrivialPair(unsigned K, unsigned V) : FoldingSetNode(), Key(K), Value(V) {}
42
43  void Profile(FoldingSetNodeID &ID) const {
44    ID.AddInteger(Key);
45    ID.AddInteger(Value);
46  }
47};
48
49TEST(FoldingSetTest, IDComparison) {
50  FoldingSet<TrivialPair> Trivial;
51
52  TrivialPair T(99, 42);
53  Trivial.InsertNode(&T);
54
55  void *InsertPos = nullptr;
56  FoldingSetNodeID ID;
57  T.Profile(ID);
58  TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
59  EXPECT_EQ(&T, N);
60  EXPECT_EQ(nullptr, InsertPos);
61}
62
63TEST(FoldingSetTest, MissedIDComparison) {
64  FoldingSet<TrivialPair> Trivial;
65
66  TrivialPair S(100, 42);
67  TrivialPair T(99, 42);
68  Trivial.InsertNode(&T);
69
70  void *InsertPos = nullptr;
71  FoldingSetNodeID ID;
72  S.Profile(ID);
73  TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
74  EXPECT_EQ(nullptr, N);
75  EXPECT_NE(nullptr, InsertPos);
76}
77
78TEST(FoldingSetTest, RemoveNodeThatIsPresent) {
79  FoldingSet<TrivialPair> Trivial;
80
81  TrivialPair T(99, 42);
82  Trivial.InsertNode(&T);
83  EXPECT_EQ(Trivial.size(), 1U);
84
85  bool WasThere = Trivial.RemoveNode(&T);
86  EXPECT_TRUE(WasThere);
87  EXPECT_EQ(0U, Trivial.size());
88}
89
90TEST(FoldingSetTest, RemoveNodeThatIsAbsent) {
91  FoldingSet<TrivialPair> Trivial;
92
93  TrivialPair T(99, 42);
94  bool WasThere = Trivial.RemoveNode(&T);
95  EXPECT_FALSE(WasThere);
96  EXPECT_EQ(0U, Trivial.size());
97}
98
99TEST(FoldingSetTest, GetOrInsertInserting) {
100  FoldingSet<TrivialPair> Trivial;
101
102  TrivialPair T(99, 42);
103  TrivialPair *N = Trivial.GetOrInsertNode(&T);
104  EXPECT_EQ(&T, N);
105}
106
107TEST(FoldingSetTest, GetOrInsertGetting) {
108  FoldingSet<TrivialPair> Trivial;
109
110  TrivialPair T(99, 42);
111  TrivialPair T2(99, 42);
112  Trivial.InsertNode(&T);
113  TrivialPair *N = Trivial.GetOrInsertNode(&T2);
114  EXPECT_EQ(&T, N);
115}
116
117TEST(FoldingSetTest, InsertAtPos) {
118  FoldingSet<TrivialPair> Trivial;
119
120  void *InsertPos = nullptr;
121  TrivialPair Finder(99, 42);
122  FoldingSetNodeID ID;
123  Finder.Profile(ID);
124  Trivial.FindNodeOrInsertPos(ID, InsertPos);
125
126  TrivialPair T(99, 42);
127  Trivial.InsertNode(&T, InsertPos);
128  EXPECT_EQ(1U, Trivial.size());
129}
130
131TEST(FoldingSetTest, EmptyIsTrue) {
132  FoldingSet<TrivialPair> Trivial;
133  EXPECT_TRUE(Trivial.empty());
134}
135
136TEST(FoldingSetTest, EmptyIsFalse) {
137  FoldingSet<TrivialPair> Trivial;
138  TrivialPair T(99, 42);
139  Trivial.InsertNode(&T);
140  EXPECT_FALSE(Trivial.empty());
141}
142
143TEST(FoldingSetTest, ClearOnEmpty) {
144  FoldingSet<TrivialPair> Trivial;
145  Trivial.clear();
146  EXPECT_TRUE(Trivial.empty());
147}
148
149TEST(FoldingSetTest, ClearOnNonEmpty) {
150  FoldingSet<TrivialPair> Trivial;
151  TrivialPair T(99, 42);
152  Trivial.InsertNode(&T);
153  Trivial.clear();
154  EXPECT_TRUE(Trivial.empty());
155}
156
157TEST(FoldingSetTest, CapacityLargerThanReserve) {
158  FoldingSet<TrivialPair> Trivial;
159  auto OldCapacity = Trivial.capacity();
160  Trivial.reserve(OldCapacity + 1);
161  EXPECT_GE(Trivial.capacity(), OldCapacity + 1);
162}
163
164TEST(FoldingSetTest, SmallReserveChangesNothing) {
165  FoldingSet<TrivialPair> Trivial;
166  auto OldCapacity = Trivial.capacity();
167  Trivial.reserve(OldCapacity - 1);
168  EXPECT_EQ(Trivial.capacity(), OldCapacity);
169}
170
171}
172
173