IntEqClasses.cpp revision 267654
1166309Srwatson//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===// 2166309Srwatson// 3166309Srwatson// The LLVM Compiler Infrastructure 4166309Srwatson// 5166365Srwatson// This file is distributed under the University of Illinois Open Source 6166309Srwatson// License. See LICENSE.TXT for details. 7166309Srwatson// 8166309Srwatson//===----------------------------------------------------------------------===// 9166309Srwatson// 10166309Srwatson// Equivalence classes for small integers. This is a mapping of the integers 11166309Srwatson// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 12166309Srwatson// 13166309Srwatson// Initially each integer has its own equivalence class. Classes are joined by 14166309Srwatson// passing a representative member of each class to join(). 15166309Srwatson// 16166309Srwatson// Once the classes are built, compress() will number them 0 .. M-1 and prevent 17166309Srwatson// further changes. 18166309Srwatson// 19166309Srwatson//===----------------------------------------------------------------------===// 20166309Srwatson 21166309Srwatson#include "llvm/ADT/IntEqClasses.h" 22166309Srwatson 23166309Srwatsonusing namespace llvm; 24166309Srwatson 25166309Srwatsonvoid IntEqClasses::grow(unsigned N) { 26166309Srwatson assert(NumClasses == 0 && "grow() called after compress()."); 27166309Srwatson EC.reserve(N); 28166309Srwatson while (EC.size() < N) 29166309Srwatson EC.push_back(EC.size()); 30166309Srwatson} 31166309Srwatson 32166309Srwatsonvoid IntEqClasses::join(unsigned a, unsigned b) { 33166309Srwatson assert(NumClasses == 0 && "join() called after compress()."); 34166309Srwatson unsigned eca = EC[a]; 35166309Srwatson unsigned ecb = EC[b]; 36166309Srwatson // Update pointers while searching for the leaders, compressing the paths 37166309Srwatson // incrementally. The larger leader will eventually be updated, joining the 38166309Srwatson // classes. 39166309Srwatson while (eca != ecb) 40166309Srwatson if (eca < ecb) 41166309Srwatson EC[b] = eca, b = ecb, ecb = EC[b]; 42166309Srwatson else 43166309Srwatson EC[a] = ecb, a = eca, eca = EC[a]; 44166309Srwatson} 45166309Srwatson 46166309Srwatsonunsigned IntEqClasses::findLeader(unsigned a) const { 47166309Srwatson assert(NumClasses == 0 && "findLeader() called after compress()."); 48166309Srwatson while (a != EC[a]) 49166309Srwatson a = EC[a]; 50166309Srwatson return a; 51166309Srwatson} 52166309Srwatson 53166309Srwatsonvoid IntEqClasses::compress() { 54166309Srwatson if (NumClasses) 55166309Srwatson return; 56166309Srwatson for (unsigned i = 0, e = EC.size(); i != e; ++i) 57166309Srwatson EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 58166309Srwatson} 59166309Srwatson 60166309Srwatsonvoid IntEqClasses::uncompress() { 61166309Srwatson if (!NumClasses) 62166309Srwatson return; 63166309Srwatson SmallVector<unsigned, 8> Leader; 64166309Srwatson for (unsigned i = 0, e = EC.size(); i != e; ++i) 65166309Srwatson if (EC[i] < Leader.size()) 66166309Srwatson EC[i] = Leader[EC[i]]; 67166309Srwatson else 68166309Srwatson Leader.push_back(EC[i] = i); 69166309Srwatson NumClasses = 0; 70166309Srwatson} 71166309Srwatson