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(0, 1);
20   ec.join(3, 2);
21   ec.join(4, 5);
22   ec.join(7, 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(1, 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(4, 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(9, 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