llvm/unittests/ADT/FoldingSet.cpp

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