llvm/unittests/ADT/SparseMultiSetTest.cpp

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