1 //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
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
7 //===----------------------------------------------------------------------===//
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.
12 // Initially each integer has its own equivalence class. Classes are joined by
13 // passing a representative member of each class to join().
15 // Once the classes are built, compress() will number them 0 .. M-1 and prevent
18 //===----------------------------------------------------------------------===//
20 #include "llvm/ADT/IntEqClasses.h"
24 void IntEqClasses::grow(unsigned N) {
25 assert(NumClasses == 0 && "grow() called after compress().");
28 EC.push_back(EC.size());
31 unsigned IntEqClasses::join(unsigned a, unsigned b) {
32 assert(NumClasses == 0 && "join() called after compress().");
35 // Update pointers while searching for the leaders, compressing the paths
36 // incrementally. The larger leader will eventually be updated, joining the
52 unsigned IntEqClasses::findLeader(unsigned a) const {
53 assert(NumClasses == 0 && "findLeader() called after compress().");
59 void IntEqClasses::compress() {
62 for (unsigned i = 0, e = EC.size(); i != e; ++i)
63 EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
66 void IntEqClasses::uncompress() {
69 SmallVector<unsigned, 8> Leader;
70 for (unsigned i = 0, e = EC.size(); i != e; ++i)
71 if (EC[i] < Leader.size())
72 EC[i] = Leader[EC[i]];
74 Leader.push_back(EC[i] = i);