1218885Sdim//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// Equivalence classes for small integers. This is a mapping of the integers 11218885Sdim// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 12218885Sdim// 13218885Sdim// Initially each integer has its own equivalence class. Classes are joined by 14218885Sdim// passing a representative member of each class to join(). 15218885Sdim// 16218885Sdim// Once the classes are built, compress() will number them 0 .. M-1 and prevent 17218885Sdim// further changes. 18218885Sdim// 19218885Sdim//===----------------------------------------------------------------------===// 20218885Sdim 21218885Sdim#include "llvm/ADT/IntEqClasses.h" 22218885Sdim 23218885Sdimusing namespace llvm; 24218885Sdim 25218885Sdimvoid IntEqClasses::grow(unsigned N) { 26218885Sdim assert(NumClasses == 0 && "grow() called after compress()."); 27218885Sdim EC.reserve(N); 28218885Sdim while (EC.size() < N) 29218885Sdim EC.push_back(EC.size()); 30218885Sdim} 31218885Sdim 32218885Sdimvoid IntEqClasses::join(unsigned a, unsigned b) { 33218885Sdim assert(NumClasses == 0 && "join() called after compress()."); 34218885Sdim unsigned eca = EC[a]; 35218885Sdim unsigned ecb = EC[b]; 36218885Sdim // Update pointers while searching for the leaders, compressing the paths 37218885Sdim // incrementally. The larger leader will eventually be updated, joining the 38218885Sdim // classes. 39218885Sdim while (eca != ecb) 40218885Sdim if (eca < ecb) 41218885Sdim EC[b] = eca, b = ecb, ecb = EC[b]; 42218885Sdim else 43218885Sdim EC[a] = ecb, a = eca, eca = EC[a]; 44218885Sdim} 45218885Sdim 46218885Sdimunsigned IntEqClasses::findLeader(unsigned a) const { 47218885Sdim assert(NumClasses == 0 && "findLeader() called after compress()."); 48218885Sdim while (a != EC[a]) 49218885Sdim a = EC[a]; 50218885Sdim return a; 51218885Sdim} 52218885Sdim 53218885Sdimvoid IntEqClasses::compress() { 54218885Sdim if (NumClasses) 55218885Sdim return; 56218885Sdim for (unsigned i = 0, e = EC.size(); i != e; ++i) 57218885Sdim EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 58218885Sdim} 59218885Sdim 60218885Sdimvoid IntEqClasses::uncompress() { 61218885Sdim if (!NumClasses) 62218885Sdim return; 63218885Sdim SmallVector<unsigned, 8> Leader; 64218885Sdim for (unsigned i = 0, e = EC.size(); i != e; ++i) 65218885Sdim if (EC[i] < Leader.size()) 66218885Sdim EC[i] = Leader[EC[i]]; 67218885Sdim else 68218885Sdim Leader.push_back(EC[i] = i); 69218885Sdim NumClasses = 0; 70218885Sdim} 71