1 //===- llvm/unittest/ADT/SmallSetTest.cpp ------------------------------===// 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 // SmallSet unit tests. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/ADT/SmallSet.h" 15 #include "gtest/gtest.h" 16 #include <string> 17 18 using namespace llvm; 19 20 TEST(SmallSetTest, Insert) { 21 22 SmallSet<int, 4> s1; 23 24 for (int i = 0; i < 4; i++) 25 s1.insert(i); 26 27 for (int i = 0; i < 4; i++) 28 s1.insert(i); 29 30 EXPECT_EQ(4u, s1.size()); 31 32 for (int i = 0; i < 4; i++) 33 EXPECT_EQ(1u, s1.count(i)); 34 35 EXPECT_EQ(0u, s1.count(4)); 36 } 37 38 TEST(SmallSetTest, Grow) { 39 SmallSet<int, 4> s1; 40 41 for (int i = 0; i < 8; i++) 42 s1.insert(i); 43 44 EXPECT_EQ(8u, s1.size()); 45 46 for (int i = 0; i < 8; i++) 47 EXPECT_EQ(1u, s1.count(i)); 48 49 EXPECT_EQ(0u, s1.count(8)); 50 } 51 52 TEST(SmallSetTest, Erase) { 53 SmallSet<int, 4> s1; 54 55 for (int i = 0; i < 8; i++) 56 s1.insert(i); 57 58 EXPECT_EQ(8u, s1.size()); 59 60 // Remove elements one by one and check if all other elements are still there. 61 for (int i = 0; i < 8; i++) { 62 EXPECT_EQ(1u, s1.count(i)); 63 EXPECT_TRUE(s1.erase(i)); 64 EXPECT_EQ(0u, s1.count(i)); 65 EXPECT_EQ(8u - i - 1, s1.size()); 66 for (int j = i + 1; j < 8; j++) 67 EXPECT_EQ(1u, s1.count(j)); 68 } 69 70 EXPECT_EQ(0u, s1.count(8)); 71 } 72 73 TEST(SmallSetTest, IteratorInt) { 74 SmallSet<int, 4> s1; 75 76 // Test the 'small' case. 77 for (int i = 0; i < 3; i++) 78 s1.insert(i); 79 80 std::vector<int> V(s1.begin(), s1.end()); 81 // Make sure the elements are in the expected order. 82 std::sort(V.begin(), V.end()); 83 for (int i = 0; i < 3; i++) 84 EXPECT_EQ(i, V[i]); 85 86 // Test the 'big' case by adding a few more elements to switch to std::set 87 // internally. 88 for (int i = 3; i < 6; i++) 89 s1.insert(i); 90 91 V.assign(s1.begin(), s1.end()); 92 // Make sure the elements are in the expected order. 93 std::sort(V.begin(), V.end()); 94 for (int i = 0; i < 6; i++) 95 EXPECT_EQ(i, V[i]); 96 } 97 98 TEST(SmallSetTest, IteratorString) { 99 // Test SmallSetIterator for SmallSet with a type with non-trivial 100 // ctors/dtors. 101 SmallSet<std::string, 2> s1; 102 103 s1.insert("str 1"); 104 s1.insert("str 2"); 105 s1.insert("str 1"); 106 107 std::vector<std::string> V(s1.begin(), s1.end()); 108 std::sort(V.begin(), V.end()); 109 EXPECT_EQ(2u, s1.size()); 110 EXPECT_EQ("str 1", V[0]); 111 EXPECT_EQ("str 2", V[1]); 112 113 s1.insert("str 4"); 114 s1.insert("str 0"); 115 s1.insert("str 4"); 116 117 V.assign(s1.begin(), s1.end()); 118 // Make sure the elements are in the expected order. 119 std::sort(V.begin(), V.end()); 120 EXPECT_EQ(4u, s1.size()); 121 EXPECT_EQ("str 0", V[0]); 122 EXPECT_EQ("str 1", V[1]); 123 EXPECT_EQ("str 2", V[2]); 124 EXPECT_EQ("str 4", V[3]); 125 } 126 127 TEST(SmallSetTest, IteratorIncMoveCopy) { 128 // Test SmallSetIterator for SmallSet with a type with non-trivial 129 // ctors/dtors. 130 SmallSet<std::string, 2> s1; 131 132 s1.insert("str 1"); 133 s1.insert("str 2"); 134 135 auto Iter = s1.begin(); 136 EXPECT_EQ("str 1", *Iter); 137 ++Iter; 138 EXPECT_EQ("str 2", *Iter); 139 140 s1.insert("str 4"); 141 s1.insert("str 0"); 142 auto Iter2 = s1.begin(); 143 Iter = std::move(Iter2); 144 EXPECT_EQ("str 0", *Iter); 145 146 auto Iter3 = s1.end(); 147 Iter3 = Iter2; 148 EXPECT_EQ(Iter3, Iter2); 149 } 150
