1 //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
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 // Equivalence classes for small integers. This is a mapping of the integers
10 // 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
11 //
12 // Initially each integer has its own equivalence class. Classes are joined by
13 // passing a representative member of each class to join().
14 //
15 // Once the classes are built, compress() will number them 0 .. M-1 and prevent
16 // further changes.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "llvm/ADT/IntEqClasses.h"
21 #include <cassert>
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 unsigned 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;
42       b = ecb;
43       ecb = EC[b];
44     } else {
45       EC[a] = ecb;
46       a = eca;
47       eca = EC[a];
48     }
49 
50   return eca;
51 }
52 
findLeader(unsigned a) const53 unsigned IntEqClasses::findLeader(unsigned a) const {
54   assert(NumClasses == 0 && "findLeader() called after compress().");
55   while (a != EC[a])
56     a = EC[a];
57   return a;
58 }
59 
compress()60 void IntEqClasses::compress() {
61   if (NumClasses)
62     return;
63   for (unsigned i = 0, e = EC.size(); i != e; ++i)
64     EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
65 }
66 
uncompress()67 void IntEqClasses::uncompress() {
68   if (!NumClasses)
69     return;
70   SmallVector<unsigned, 8> Leader;
71   for (unsigned i = 0, e = EC.size(); i != e; ++i)
72     if (EC[i] < Leader.size())
73       EC[i] = Leader[EC[i]];
74     else
75       Leader.push_back(EC[i] = i);
76   NumClasses = 0;
77 }
78