Home | History | Annotate | Download | only in ADT 
      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 
     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