78 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// Equivalence classes for small integers. This is a mapping of the integers10// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.11//12// Initially each integer has its own equivalence class. Classes are joined by13// passing a representative member of each class to join().14//15// Once the classes are built, compress() will number them 0 .. M-1 and prevent16// further changes.17//18//===----------------------------------------------------------------------===//19 20#include "llvm/ADT/IntEqClasses.h"21#include <cassert>22 23using namespace llvm;24 25void 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 32unsigned 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 paths37 // incrementally. The larger leader will eventually be updated, joining the38 // 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 53unsigned 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 60void 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 67void 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 else75 Leader.push_back(EC[i] = i);76 NumClasses = 0;77}78