1 //===---- ADT/IntEqClassesTest.cpp - IntEqClasses 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/IntEqClasses.h"
11 #include "gtest/gtest.h"
12
13 using namespace llvm;
14
15 namespace {
16
TEST(IntEqClasses,Simple)17 TEST(IntEqClasses, Simple) {
18 IntEqClasses ec(10);
19
20 ec.join(0, 1);
21 ec.join(3, 2);
22 ec.join(4, 5);
23 ec.join(7, 6);
24
25 EXPECT_EQ(0u, ec.findLeader(0));
26 EXPECT_EQ(0u, ec.findLeader(1));
27 EXPECT_EQ(2u, ec.findLeader(2));
28 EXPECT_EQ(2u, ec.findLeader(3));
29 EXPECT_EQ(4u, ec.findLeader(4));
30 EXPECT_EQ(4u, ec.findLeader(5));
31 EXPECT_EQ(6u, ec.findLeader(6));
32 EXPECT_EQ(6u, ec.findLeader(7));
33 EXPECT_EQ(8u, ec.findLeader(8));
34 EXPECT_EQ(9u, ec.findLeader(9));
35
36 // join two non-leaders.
37 ec.join(1, 3);
38
39 EXPECT_EQ(0u, ec.findLeader(0));
40 EXPECT_EQ(0u, ec.findLeader(1));
41 EXPECT_EQ(0u, ec.findLeader(2));
42 EXPECT_EQ(0u, ec.findLeader(3));
43 EXPECT_EQ(4u, ec.findLeader(4));
44 EXPECT_EQ(4u, ec.findLeader(5));
45 EXPECT_EQ(6u, ec.findLeader(6));
46 EXPECT_EQ(6u, ec.findLeader(7));
47 EXPECT_EQ(8u, ec.findLeader(8));
48 EXPECT_EQ(9u, ec.findLeader(9));
49
50 // join two leaders.
51 ec.join(4, 8);
52
53 EXPECT_EQ(0u, ec.findLeader(0));
54 EXPECT_EQ(0u, ec.findLeader(1));
55 EXPECT_EQ(0u, ec.findLeader(2));
56 EXPECT_EQ(0u, ec.findLeader(3));
57 EXPECT_EQ(4u, ec.findLeader(4));
58 EXPECT_EQ(4u, ec.findLeader(5));
59 EXPECT_EQ(6u, ec.findLeader(6));
60 EXPECT_EQ(6u, ec.findLeader(7));
61 EXPECT_EQ(4u, ec.findLeader(8));
62 EXPECT_EQ(9u, ec.findLeader(9));
63
64 // join mixed.
65 ec.join(9, 1);
66
67 EXPECT_EQ(0u, ec.findLeader(0));
68 EXPECT_EQ(0u, ec.findLeader(1));
69 EXPECT_EQ(0u, ec.findLeader(2));
70 EXPECT_EQ(0u, ec.findLeader(3));
71 EXPECT_EQ(4u, ec.findLeader(4));
72 EXPECT_EQ(4u, ec.findLeader(5));
73 EXPECT_EQ(6u, ec.findLeader(6));
74 EXPECT_EQ(6u, ec.findLeader(7));
75 EXPECT_EQ(4u, ec.findLeader(8));
76 EXPECT_EQ(0u, ec.findLeader(9));
77
78 // compressed map.
79 ec.compress();
80 EXPECT_EQ(3u, ec.getNumClasses());
81
82 EXPECT_EQ(0u, ec[0]);
83 EXPECT_EQ(0u, ec[1]);
84 EXPECT_EQ(0u, ec[2]);
85 EXPECT_EQ(0u, ec[3]);
86 EXPECT_EQ(1u, ec[4]);
87 EXPECT_EQ(1u, ec[5]);
88 EXPECT_EQ(2u, ec[6]);
89 EXPECT_EQ(2u, ec[7]);
90 EXPECT_EQ(1u, ec[8]);
91 EXPECT_EQ(0u, ec[9]);
92
93 // uncompressed map.
94 ec.uncompress();
95 EXPECT_EQ(0u, ec.findLeader(0));
96 EXPECT_EQ(0u, ec.findLeader(1));
97 EXPECT_EQ(0u, ec.findLeader(2));
98 EXPECT_EQ(0u, ec.findLeader(3));
99 EXPECT_EQ(4u, ec.findLeader(4));
100 EXPECT_EQ(4u, ec.findLeader(5));
101 EXPECT_EQ(6u, ec.findLeader(6));
102 EXPECT_EQ(6u, ec.findLeader(7));
103 EXPECT_EQ(4u, ec.findLeader(8));
104 EXPECT_EQ(0u, ec.findLeader(9));
105 }
106
107 } // end anonymous namespace
108