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