Home | History | Annotate | Download | only in ADT
      1 //===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
      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 #include "llvm/ADT/SparseSet.h"
     11 #include "gtest/gtest.h"
     12 
     13 using namespace llvm;
     14 
     15 namespace {
     16 
     17 typedef SparseSet<unsigned> USet;
     18 
     19 // Empty set tests.
     20 TEST(SparseSetTest, EmptySet) {
     21   USet Set;
     22   EXPECT_TRUE(Set.empty());
     23   EXPECT_TRUE(Set.begin() == Set.end());
     24   EXPECT_EQ(0u, Set.size());
     25 
     26   Set.setUniverse(10);
     27 
     28   // Lookups on empty set.
     29   EXPECT_TRUE(Set.find(0) == Set.end());
     30   EXPECT_TRUE(Set.find(9) == Set.end());
     31 
     32   // Same thing on a const reference.
     33   const USet &CSet = Set;
     34   EXPECT_TRUE(CSet.empty());
     35   EXPECT_TRUE(CSet.begin() == CSet.end());
     36   EXPECT_EQ(0u, CSet.size());
     37   EXPECT_TRUE(CSet.find(0) == CSet.end());
     38   USet::const_iterator I = CSet.find(5);
     39   EXPECT_TRUE(I == CSet.end());
     40 }
     41 
     42 // Single entry set tests.
     43 TEST(SparseSetTest, SingleEntrySet) {
     44   USet Set;
     45   Set.setUniverse(10);
     46   std::pair<USet::iterator, bool> IP = Set.insert(5);
     47   EXPECT_TRUE(IP.second);
     48   EXPECT_TRUE(IP.first == Set.begin());
     49 
     50   EXPECT_FALSE(Set.empty());
     51   EXPECT_FALSE(Set.begin() == Set.end());
     52   EXPECT_TRUE(Set.begin() + 1 == Set.end());
     53   EXPECT_EQ(1u, Set.size());
     54 
     55   EXPECT_TRUE(Set.find(0) == Set.end());
     56   EXPECT_TRUE(Set.find(9) == Set.end());
     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_TRUE(I == Set.end());
     76   EXPECT_TRUE(Set.empty());
     77 }
     78 
     79 // Multiple entry set tests.
     80 TEST(SparseSetTest, MultipleEntrySet) {
     81   USet Set;
     82   Set.setUniverse(10);
     83 
     84   Set.insert(5);
     85   Set.insert(3);
     86   Set.insert(2);
     87   Set.insert(1);
     88   Set.insert(4);
     89   EXPECT_EQ(5u, Set.size());
     90 
     91   // Without deletions, iteration order == insertion order.
     92   USet::const_iterator I = Set.begin();
     93   EXPECT_EQ(5u, *I);
     94   ++I;
     95   EXPECT_EQ(3u, *I);
     96   ++I;
     97   EXPECT_EQ(2u, *I);
     98   ++I;
     99   EXPECT_EQ(1u, *I);
    100   ++I;
    101   EXPECT_EQ(4u, *I);
    102   ++I;
    103   EXPECT_TRUE(I == Set.end());
    104 
    105   // Redundant insert.
    106   std::pair<USet::iterator, bool> IP = Set.insert(3);
    107   EXPECT_FALSE(IP.second);
    108   EXPECT_TRUE(IP.first == Set.begin() + 1);
    109 
    110   // Erase last element by key.
    111   EXPECT_TRUE(Set.erase(4));
    112   EXPECT_EQ(4u, Set.size());
    113   EXPECT_FALSE(Set.count(4));
    114   EXPECT_FALSE(Set.erase(4));
    115   EXPECT_EQ(4u, Set.size());
    116   EXPECT_FALSE(Set.count(4));
    117 
    118   // Erase first element by key.
    119   EXPECT_TRUE(Set.count(5));
    120   EXPECT_TRUE(Set.find(5) == Set.begin());
    121   EXPECT_TRUE(Set.erase(5));
    122   EXPECT_EQ(3u, Set.size());
    123   EXPECT_FALSE(Set.count(5));
    124   EXPECT_FALSE(Set.erase(5));
    125   EXPECT_EQ(3u, Set.size());
    126   EXPECT_FALSE(Set.count(5));
    127 
    128   Set.insert(6);
    129   Set.insert(7);
    130   EXPECT_EQ(5u, Set.size());
    131 
    132   // Erase last element by iterator.
    133   I = Set.erase(Set.end() - 1);
    134   EXPECT_TRUE(I == Set.end());
    135   EXPECT_EQ(4u, Set.size());
    136 
    137   // Erase second element by iterator.
    138   I = Set.erase(Set.begin() + 1);
    139   EXPECT_TRUE(I == Set.begin() + 1);
    140 
    141   // Clear and resize the universe.
    142   Set.clear();
    143   EXPECT_FALSE(Set.count(5));
    144   Set.setUniverse(1000);
    145 
    146   // Add more than 256 elements.
    147   for (unsigned i = 100; i != 800; ++i)
    148     Set.insert(i);
    149 
    150   for (unsigned i = 0; i != 10; ++i)
    151     Set.erase(i);
    152 
    153   for (unsigned i = 100; i != 800; ++i)
    154     EXPECT_TRUE(Set.count(i));
    155 
    156   EXPECT_FALSE(Set.count(99));
    157   EXPECT_FALSE(Set.count(800));
    158   EXPECT_EQ(700u, Set.size());
    159 }
    160 
    161 struct Alt {
    162   unsigned Value;
    163   explicit Alt(unsigned x) : Value(x) {}
    164   unsigned getSparseSetIndex() const { return Value - 1000; }
    165 };
    166 
    167 TEST(SparseSetTest, AltStructSet) {
    168   typedef SparseSet<Alt> ASet;
    169   ASet Set;
    170   Set.setUniverse(10);
    171   Set.insert(Alt(1005));
    172 
    173   ASet::iterator I = Set.find(5);
    174   ASSERT_TRUE(I == Set.begin());
    175   EXPECT_EQ(1005u, I->Value);
    176 
    177   Set.insert(Alt(1006));
    178   Set.insert(Alt(1006));
    179   I = Set.erase(Set.begin());
    180   ASSERT_TRUE(I == Set.begin());
    181   EXPECT_EQ(1006u, I->Value);
    182 
    183   EXPECT_FALSE(Set.erase(5));
    184   EXPECT_TRUE(Set.erase(6));
    185 }
    186 } // namespace
    187