1 //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Equivalence classes for small integers. This is a mapping of the integers 11 // 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 12 // 13 // Initially each integer has its own equivalence class. Classes are joined by 14 // passing a representative member of each class to join(). 15 // 16 // Once the classes are built, compress() will number them 0 .. M-1 and prevent 17 // further changes. 18 // 19 //===----------------------------------------------------------------------===// 20 21 #include "llvm/ADT/IntEqClasses.h" 22 23 using namespace llvm; 24 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 32 void 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, b = ecb, ecb = EC[b]; 42 else 43 EC[a] = ecb, a = eca, eca = EC[a]; 44 } 45 46 unsigned IntEqClasses::findLeader(unsigned a) const { 47 assert(NumClasses == 0 && "findLeader() called after compress()."); 48 while (a != EC[a]) 49 a = EC[a]; 50 return a; 51 } 52 53 void IntEqClasses::compress() { 54 if (NumClasses) 55 return; 56 for (unsigned i = 0, e = EC.size(); i != e; ++i) 57 EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 58 } 59 60 void IntEqClasses::uncompress() { 61 if (!NumClasses) 62 return; 63 SmallVector<unsigned, 8> Leader; 64 for (unsigned i = 0, e = EC.size(); i != e; ++i) 65 if (EC[i] < Leader.size()) 66 EC[i] = Leader[EC[i]]; 67 else 68 Leader.push_back(EC[i] = i); 69 NumClasses = 0; 70 } 71
