235 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/SparseMultiSet.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16using USet = SparseMultiSet<unsigned>;17 18// Empty set tests.19TEST(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.40TEST(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.80TEST(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 8s135 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 iterators161TEST(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 again184 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 again191 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 207struct Alt {208 unsigned Value;209 explicit Alt(unsigned x) : Value(x) {}210 unsigned getSparseSetIndex() const { return Value - 1000; }211};212 213TEST(SparseMultiSetTest, AltStructSet) {214 using ASet = SparseMultiSet<Alt>;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} // namespace235