1 //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
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 // Equivalence classes for small integers. This is a mapping of the integers
11 // 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
12 //
13 // Initially each integer has its own equivalence class. Classes are joined by
14 // passing a representative member of each class to join().
15 //
16 // Once the classes are built, compress() will number them 0 .. M-1 and prevent
17 // further changes.
18 //
19 //===----------------------------------------------------------------------===//
20
21 #include "llvm/ADT/IntEqClasses.h"
22
23 using namespace llvm;
24
grow(unsigned N)25 void IntEqClasses::grow(unsigned N) {
26 assert(NumClasses == 0 && "grow() called after compress().");
27 EC.reserve(N);
28 while (EC.size() < N)
29 EC.push_back(EC.size());
30 }
31
join(unsigned a,unsigned b)32 void IntEqClasses::join(unsigned a, unsigned b) {
33 assert(NumClasses == 0 && "join() called after compress().");
34 unsigned eca = EC[a];
35 unsigned ecb = EC[b];
36 // Update pointers while searching for the leaders, compressing the paths
37 // incrementally. The larger leader will eventually be updated, joining the
38 // classes.
39 while (eca != ecb)
40 if (eca < ecb)
41 EC[b] = eca, b = ecb, ecb = EC[b];
42 else
43 EC[a] = ecb, a = eca, eca = EC[a];
44 }
45
findLeader(unsigned a) const46 unsigned IntEqClasses::findLeader(unsigned a) const {
47 assert(NumClasses == 0 && "findLeader() called after compress().");
48 while (a != EC[a])
49 a = EC[a];
50 return a;
51 }
52
compress()53 void IntEqClasses::compress() {
54 if (NumClasses)
55 return;
56 for (unsigned i = 0, e = EC.size(); i != e; ++i)
57 EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
58 }
59
uncompress()60 void IntEqClasses::uncompress() {
61 if (!NumClasses)
62 return;
63 SmallVector<unsigned, 8> Leader;
64 for (unsigned i = 0, e = EC.size(); i != e; ++i)
65 if (EC[i] < Leader.size())
66 EC[i] = Leader[EC[i]];
67 else
68 Leader.push_back(EC[i] = i);
69 NumClasses = 0;
70 }
71