220 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/SparseSet.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16using USet = SparseSet<unsigned>;17 18// Empty set tests.19TEST(SparseSetTest, EmptySet) {20 USet Set;21 EXPECT_TRUE(Set.empty());22 EXPECT_TRUE(Set.begin() == Set.end());23 EXPECT_EQ(0u, Set.size());24 25 Set.setUniverse(10);26 27 // Lookups on empty set.28 EXPECT_FALSE(Set.contains(0));29 EXPECT_FALSE(Set.contains(9));30 31 // Same thing on a const reference.32 const USet &CSet = Set;33 EXPECT_TRUE(CSet.empty());34 EXPECT_TRUE(CSet.begin() == CSet.end());35 EXPECT_EQ(0u, CSet.size());36 EXPECT_FALSE(CSet.contains(0));37 USet::const_iterator I = CSet.find(5);38 EXPECT_TRUE(I == CSet.end());39}40 41// Single entry set tests.42TEST(SparseSetTest, SingleEntrySet) {43 USet Set;44 Set.setUniverse(10);45 std::pair<USet::iterator, bool> IP = Set.insert(5);46 EXPECT_TRUE(IP.second);47 EXPECT_TRUE(IP.first == Set.begin());48 49 EXPECT_FALSE(Set.empty());50 EXPECT_FALSE(Set.begin() == Set.end());51 EXPECT_TRUE(Set.begin() + 1 == Set.end());52 EXPECT_EQ(1u, Set.size());53 54 EXPECT_FALSE(Set.contains(0));55 EXPECT_FALSE(Set.contains(9));56 EXPECT_TRUE(Set.contains(5));57 58 EXPECT_FALSE(Set.count(0));59 EXPECT_TRUE(Set.count(5));60 61 // Redundant insert.62 IP = Set.insert(5);63 EXPECT_FALSE(IP.second);64 EXPECT_TRUE(IP.first == Set.begin());65 66 // Erase non-existent element.67 EXPECT_FALSE(Set.erase(1));68 EXPECT_EQ(1u, Set.size());69 EXPECT_EQ(5u, *Set.begin());70 71 // Erase iterator.72 USet::iterator I = Set.find(5);73 EXPECT_TRUE(I == Set.begin());74 I = Set.erase(I);75 EXPECT_FALSE(Set.contains(5));76 EXPECT_TRUE(I == Set.end());77 EXPECT_TRUE(Set.empty());78}79 80// Multiple entry set tests.81TEST(SparseSetTest, MultipleEntrySet) {82 USet Set;83 Set.setUniverse(10);84 85 Set.insert(5);86 Set.insert(3);87 Set.insert(2);88 Set.insert(1);89 Set.insert(4);90 EXPECT_EQ(5u, Set.size());91 92 // Without deletions, iteration order == insertion order.93 USet::const_iterator I = Set.begin();94 EXPECT_EQ(5u, *I);95 ++I;96 EXPECT_EQ(3u, *I);97 ++I;98 EXPECT_EQ(2u, *I);99 ++I;100 EXPECT_EQ(1u, *I);101 ++I;102 EXPECT_EQ(4u, *I);103 ++I;104 EXPECT_TRUE(I == Set.end());105 106 // Redundant insert.107 std::pair<USet::iterator, bool> IP = Set.insert(3);108 EXPECT_FALSE(IP.second);109 EXPECT_TRUE(IP.first == Set.begin() + 1);110 111 // Erase last element by key.112 EXPECT_TRUE(Set.erase(4));113 EXPECT_EQ(4u, Set.size());114 EXPECT_FALSE(Set.count(4));115 EXPECT_FALSE(Set.erase(4));116 EXPECT_EQ(4u, Set.size());117 EXPECT_FALSE(Set.count(4));118 119 // Erase first element by key.120 EXPECT_TRUE(Set.count(5));121 EXPECT_TRUE(Set.find(5) == Set.begin());122 EXPECT_TRUE(Set.erase(5));123 EXPECT_EQ(3u, Set.size());124 EXPECT_FALSE(Set.count(5));125 EXPECT_FALSE(Set.erase(5));126 EXPECT_EQ(3u, Set.size());127 EXPECT_FALSE(Set.count(5));128 129 Set.insert(6);130 Set.insert(7);131 EXPECT_EQ(5u, Set.size());132 133 // Erase last element by iterator.134 I = Set.erase(Set.end() - 1);135 EXPECT_TRUE(I == Set.end());136 EXPECT_EQ(4u, Set.size());137 138 // Erase second element by iterator.139 I = Set.erase(Set.begin() + 1);140 EXPECT_TRUE(I == Set.begin() + 1);141 142 // Clear and resize the universe.143 Set.clear();144 EXPECT_FALSE(Set.count(5));145 Set.setUniverse(1000);146 147 // Add more than 256 elements.148 for (unsigned i = 100; i != 800; ++i)149 Set.insert(i);150 151 for (unsigned i = 0; i != 10; ++i)152 Set.erase(i);153 154 for (unsigned i = 100; i != 800; ++i)155 EXPECT_TRUE(Set.count(i));156 157 EXPECT_FALSE(Set.count(99));158 EXPECT_FALSE(Set.count(800));159 EXPECT_EQ(700u, Set.size());160}161 162struct Alt {163 unsigned Value;164 explicit Alt(unsigned x) : Value(x) {}165 unsigned getSparseSetIndex() const { return Value - 1000; }166};167 168TEST(SparseSetTest, AltStructSet) {169 using ASet = SparseSet<Alt>;170 ASet Set;171 Set.setUniverse(10);172 Set.insert(Alt(1005));173 174 ASet::iterator I = Set.find(5);175 ASSERT_TRUE(I == Set.begin());176 EXPECT_EQ(1005u, I->Value);177 178 Set.insert(Alt(1006));179 Set.insert(Alt(1006));180 I = Set.erase(Set.begin());181 ASSERT_TRUE(I == Set.begin());182 EXPECT_EQ(1006u, I->Value);183 184 EXPECT_FALSE(Set.erase(5));185 EXPECT_TRUE(Set.erase(6));186}187 188TEST(SparseSetTest, PopBack) {189 USet Set;190 const unsigned UpperBound = 300;191 Set.setUniverse(UpperBound);192 for (unsigned i = 0; i < UpperBound; ++i)193 Set.insert(i);194 195 // Make sure pop back returns the values in the reverse order we196 // inserted them.197 unsigned Expected = UpperBound;198 while (!Set.empty())199 ASSERT_TRUE(--Expected == Set.pop_back_val());200 201 // Insert again the same elements in the sparse set and make sure202 // each insertion actually inserts the elements. I.e., check203 // that the underlying data structure are properly cleared.204 for (unsigned i = 0; i < UpperBound; ++i)205 ASSERT_TRUE(Set.insert(i).second);206}207 208TEST(SparseSetTest, MoveConstructor) {209 USet Set;210 Set.setUniverse(2);211 Set.insert(1);212 EXPECT_FALSE(Set.empty());213 // Move and check original is empty.214 USet OtherSet(std::move(Set));215 EXPECT_TRUE(Set.empty());216 EXPECT_TRUE(OtherSet.contains(1));217}218 219} // namespace220