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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 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. 11 // 12 // Initially each integer has its own equivalence class. Classes are joined by 13 // passing a representative member of each class to join(). 14 // 15 // Once the classes are built, compress() will number them 0 .. M-1 and prevent 16 // further changes. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/ADT/IntEqClasses.h" 21 22 using namespace llvm; 23 24 void IntEqClasses::grow(unsigned N) { 25 assert(NumClasses == 0 && "grow() called after compress()."); 26 EC.reserve(N); 27 while (EC.size() < N) 28 EC.push_back(EC.size()); 29 } 30 31 unsigned IntEqClasses::join(unsigned a, unsigned b) { 32 assert(NumClasses == 0 && "join() called after compress()."); 33 unsigned eca = EC[a]; 34 unsigned ecb = EC[b]; 35 // Update pointers while searching for the leaders, compressing the paths 36 // incrementally. The larger leader will eventually be updated, joining the 37 // classes. 38 while (eca != ecb) 39 if (eca < ecb) { 40 EC[b] = eca; 41 b = ecb; 42 ecb = EC[b]; 43 } else { 44 EC[a] = ecb; 45 a = eca; 46 eca = EC[a]; 47 } 48 49 return eca; 50 } 51 52 unsigned IntEqClasses::findLeader(unsigned a) const { 53 assert(NumClasses == 0 && "findLeader() called after compress()."); 54 while (a != EC[a]) 55 a = EC[a]; 56 return a; 57 } 58 59 void IntEqClasses::compress() { 60 if (NumClasses) 61 return; 62 for (unsigned i = 0, e = EC.size(); i != e; ++i) 63 EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 64 } 65 66 void IntEqClasses::uncompress() { 67 if (!NumClasses) 68 return; 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]]; 73 else 74 Leader.push_back(EC[i] = i); 75 NumClasses = 0; 76 } 77