199 lines · cpp
1//===----------- ImmutableSetTest.cpp - ImmutableSet unit tests ------------===//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/ImmutableSet.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15class ImmutableSetTest : public testing::Test {16protected:17 // for callback tests18 static char buffer[10];19 20 struct MyIter {21 int counter;22 char *ptr;23 24 MyIter() : counter(0), ptr(buffer) {25 for (unsigned i=0; i<sizeof(buffer);++i) buffer[i]='\0';26 }27 void operator()(char c) {28 *ptr++ = c;29 ++counter;30 }31 };32};33char ImmutableSetTest::buffer[10];34 35 36TEST_F(ImmutableSetTest, EmptyIntSetTest) {37 ImmutableSet<int>::Factory f;38 39 EXPECT_TRUE(f.getEmptySet() == f.getEmptySet());40 EXPECT_FALSE(f.getEmptySet() != f.getEmptySet());41 EXPECT_TRUE(f.getEmptySet().isEmpty());42 43 ImmutableSet<int> S = f.getEmptySet();44 EXPECT_EQ(0u, S.getHeight());45 EXPECT_TRUE(S.begin() == S.end());46 EXPECT_FALSE(S.begin() != S.end());47}48 49 50TEST_F(ImmutableSetTest, OneElemIntSetTest) {51 ImmutableSet<int>::Factory f;52 ImmutableSet<int> S = f.getEmptySet();53 54 ImmutableSet<int> S2 = f.add(S, 3);55 EXPECT_TRUE(S.isEmpty());56 EXPECT_FALSE(S2.isEmpty());57 EXPECT_FALSE(S == S2);58 EXPECT_TRUE(S != S2);59 EXPECT_FALSE(S.contains(3));60 EXPECT_TRUE(S2.contains(3));61 EXPECT_FALSE(S2.begin() == S2.end());62 EXPECT_TRUE(S2.begin() != S2.end());63 64 ImmutableSet<int> S3 = f.add(S, 2);65 EXPECT_TRUE(S.isEmpty());66 EXPECT_FALSE(S3.isEmpty());67 EXPECT_FALSE(S == S3);68 EXPECT_TRUE(S != S3);69 EXPECT_FALSE(S.contains(2));70 EXPECT_TRUE(S3.contains(2));71 72 EXPECT_FALSE(S2 == S3);73 EXPECT_TRUE(S2 != S3);74 EXPECT_FALSE(S2.contains(2));75 EXPECT_FALSE(S3.contains(3));76}77 78TEST_F(ImmutableSetTest, MultiElemIntSetTest) {79 ImmutableSet<int>::Factory f;80 ImmutableSet<int> S = f.getEmptySet();81 82 ImmutableSet<int> S2 = f.add(f.add(f.add(S, 3), 4), 5);83 ImmutableSet<int> S3 = f.add(f.add(f.add(S2, 9), 20), 43);84 ImmutableSet<int> S4 = f.add(S2, 9);85 86 EXPECT_TRUE(S.isEmpty());87 EXPECT_FALSE(S2.isEmpty());88 EXPECT_FALSE(S3.isEmpty());89 EXPECT_FALSE(S4.isEmpty());90 91 EXPECT_FALSE(S.contains(3));92 EXPECT_FALSE(S.contains(9));93 94 EXPECT_TRUE(S2.contains(3));95 EXPECT_TRUE(S2.contains(4));96 EXPECT_TRUE(S2.contains(5));97 EXPECT_FALSE(S2.contains(9));98 EXPECT_FALSE(S2.contains(0));99 100 EXPECT_TRUE(S3.contains(43));101 EXPECT_TRUE(S3.contains(20));102 EXPECT_TRUE(S3.contains(9));103 EXPECT_TRUE(S3.contains(3));104 EXPECT_TRUE(S3.contains(4));105 EXPECT_TRUE(S3.contains(5));106 EXPECT_FALSE(S3.contains(0));107 108 EXPECT_TRUE(S4.contains(9));109 EXPECT_TRUE(S4.contains(3));110 EXPECT_TRUE(S4.contains(4));111 EXPECT_TRUE(S4.contains(5));112 EXPECT_FALSE(S4.contains(20));113 EXPECT_FALSE(S4.contains(43));114}115 116TEST_F(ImmutableSetTest, RemoveIntSetTest) {117 ImmutableSet<int>::Factory f;118 ImmutableSet<int> S = f.getEmptySet();119 120 ImmutableSet<int> S2 = f.add(f.add(S, 4), 5);121 ImmutableSet<int> S3 = f.add(S2, 3);122 ImmutableSet<int> S4 = f.remove(S3, 3);123 124 EXPECT_TRUE(S3.contains(3));125 EXPECT_FALSE(S2.contains(3));126 EXPECT_FALSE(S4.contains(3));127 128 EXPECT_TRUE(S2 == S4);129 EXPECT_TRUE(S3 != S2);130 EXPECT_TRUE(S3 != S4);131 132 EXPECT_TRUE(S3.contains(4));133 EXPECT_TRUE(S3.contains(5));134 135 EXPECT_TRUE(S4.contains(4));136 EXPECT_TRUE(S4.contains(5));137}138 139TEST_F(ImmutableSetTest, IterLongSetTest) {140 ImmutableSet<long>::Factory f;141 ImmutableSet<long> S = f.getEmptySet();142 143 ImmutableSet<long> S2 = f.add(f.add(f.add(S, 0), 1), 2);144 ImmutableSet<long> S3 = f.add(f.add(f.add(S2, 3), 4), 5);145 146 int i = 0;147 for (ImmutableSet<long>::iterator I = S.begin(), E = S.end(); I != E; ++I) {148 i++;149 }150 ASSERT_EQ(0, i);151 152 i = 0;153 for (ImmutableSet<long>::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {154 ASSERT_EQ(i, *I);155 i++;156 }157 ASSERT_EQ(3, i);158 159 i = 0;160 for (ImmutableSet<long>::iterator I = S3.begin(), E = S3.end(); I != E; I++) {161 ASSERT_EQ(i, *I);162 i++;163 }164 ASSERT_EQ(6, i);165}166 167TEST_F(ImmutableSetTest, AddIfNotFoundTest) {168 ImmutableSet<long>::Factory f(/*canonicalize=*/false);169 ImmutableSet<long> S = f.getEmptySet();170 S = f.add(S, 1);171 S = f.add(S, 2);172 S = f.add(S, 3);173 174 ImmutableSet<long> T1 = f.add(S, 1);175 ImmutableSet<long> T2 = f.add(S, 2);176 ImmutableSet<long> T3 = f.add(S, 3);177 EXPECT_EQ(S.getRoot(), T1.getRoot());178 EXPECT_EQ(S.getRoot(), T2.getRoot());179 EXPECT_EQ(S.getRoot(), T3.getRoot());180 181 ImmutableSet<long> U = f.add(S, 4);182 EXPECT_NE(S.getRoot(), U.getRoot());183}184 185TEST_F(ImmutableSetTest, RemoveIfNotFoundTest) {186 ImmutableSet<long>::Factory f(/*canonicalize=*/false);187 ImmutableSet<long> S = f.getEmptySet();188 S = f.add(S, 1);189 S = f.add(S, 2);190 S = f.add(S, 3);191 192 ImmutableSet<long> T = f.remove(S, 4);193 EXPECT_EQ(S.getRoot(), T.getRoot());194 195 ImmutableSet<long> U = f.remove(S, 3);196 EXPECT_NE(S.getRoot(), U.getRoot());197}198} // namespace199