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
13using namespace llvm;
14
15namespace {
16
17TEST(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