1*0b57cec5SDimitry Andric //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
2*0b57cec5SDimitry Andric //
3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*0b57cec5SDimitry Andric //
7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
8*0b57cec5SDimitry Andric //
9*0b57cec5SDimitry Andric // Equivalence classes for small integers. This is a mapping of the integers
10*0b57cec5SDimitry Andric // 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
11*0b57cec5SDimitry Andric //
12*0b57cec5SDimitry Andric // Initially each integer has its own equivalence class. Classes are joined by
13*0b57cec5SDimitry Andric // passing a representative member of each class to join().
14*0b57cec5SDimitry Andric //
15*0b57cec5SDimitry Andric // Once the classes are built, compress() will number them 0 .. M-1 and prevent
16*0b57cec5SDimitry Andric // further changes.
17*0b57cec5SDimitry Andric //
18*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
19*0b57cec5SDimitry Andric 
20*0b57cec5SDimitry Andric #include "llvm/ADT/IntEqClasses.h"
21*0b57cec5SDimitry Andric #include <cassert>
22*0b57cec5SDimitry Andric 
23*0b57cec5SDimitry Andric using namespace llvm;
24*0b57cec5SDimitry Andric 
grow(unsigned N)25*0b57cec5SDimitry Andric void IntEqClasses::grow(unsigned N) {
26*0b57cec5SDimitry Andric   assert(NumClasses == 0 && "grow() called after compress().");
27*0b57cec5SDimitry Andric   EC.reserve(N);
28*0b57cec5SDimitry Andric   while (EC.size() < N)
29*0b57cec5SDimitry Andric     EC.push_back(EC.size());
30*0b57cec5SDimitry Andric }
31*0b57cec5SDimitry Andric 
join(unsigned a,unsigned b)32*0b57cec5SDimitry Andric unsigned IntEqClasses::join(unsigned a, unsigned b) {
33*0b57cec5SDimitry Andric   assert(NumClasses == 0 && "join() called after compress().");
34*0b57cec5SDimitry Andric   unsigned eca = EC[a];
35*0b57cec5SDimitry Andric   unsigned ecb = EC[b];
36*0b57cec5SDimitry Andric   // Update pointers while searching for the leaders, compressing the paths
37*0b57cec5SDimitry Andric   // incrementally. The larger leader will eventually be updated, joining the
38*0b57cec5SDimitry Andric   // classes.
39*0b57cec5SDimitry Andric   while (eca != ecb)
40*0b57cec5SDimitry Andric     if (eca < ecb) {
41*0b57cec5SDimitry Andric       EC[b] = eca;
42*0b57cec5SDimitry Andric       b = ecb;
43*0b57cec5SDimitry Andric       ecb = EC[b];
44*0b57cec5SDimitry Andric     } else {
45*0b57cec5SDimitry Andric       EC[a] = ecb;
46*0b57cec5SDimitry Andric       a = eca;
47*0b57cec5SDimitry Andric       eca = EC[a];
48*0b57cec5SDimitry Andric     }
49*0b57cec5SDimitry Andric 
50*0b57cec5SDimitry Andric   return eca;
51*0b57cec5SDimitry Andric }
52*0b57cec5SDimitry Andric 
findLeader(unsigned a) const53*0b57cec5SDimitry Andric unsigned IntEqClasses::findLeader(unsigned a) const {
54*0b57cec5SDimitry Andric   assert(NumClasses == 0 && "findLeader() called after compress().");
55*0b57cec5SDimitry Andric   while (a != EC[a])
56*0b57cec5SDimitry Andric     a = EC[a];
57*0b57cec5SDimitry Andric   return a;
58*0b57cec5SDimitry Andric }
59*0b57cec5SDimitry Andric 
compress()60*0b57cec5SDimitry Andric void IntEqClasses::compress() {
61*0b57cec5SDimitry Andric   if (NumClasses)
62*0b57cec5SDimitry Andric     return;
63*0b57cec5SDimitry Andric   for (unsigned i = 0, e = EC.size(); i != e; ++i)
64*0b57cec5SDimitry Andric     EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
65*0b57cec5SDimitry Andric }
66*0b57cec5SDimitry Andric 
uncompress()67*0b57cec5SDimitry Andric void IntEqClasses::uncompress() {
68*0b57cec5SDimitry Andric   if (!NumClasses)
69*0b57cec5SDimitry Andric     return;
70*0b57cec5SDimitry Andric   SmallVector<unsigned, 8> Leader;
71*0b57cec5SDimitry Andric   for (unsigned i = 0, e = EC.size(); i != e; ++i)
72*0b57cec5SDimitry Andric     if (EC[i] < Leader.size())
73*0b57cec5SDimitry Andric       EC[i] = Leader[EC[i]];
74*0b57cec5SDimitry Andric     else
75*0b57cec5SDimitry Andric       Leader.push_back(EC[i] = i);
76*0b57cec5SDimitry Andric   NumClasses = 0;
77 }
78