1 //===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// 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 #ifndef LLVM_ADT_INTEQCLASSES_H 21 #define LLVM_ADT_INTEQCLASSES_H 22 23 #include "llvm/ADT/SmallVector.h" 24 25 namespace llvm { 26 27 class IntEqClasses { 28 /// EC - When uncompressed, map each integer to a smaller member of its 29 /// equivalence class. The class leader is the smallest member and maps to 30 /// itself. 31 /// 32 /// When compressed, EC[i] is the equivalence class of i. 33 SmallVector<unsigned, 8> EC; 34 35 /// NumClasses - The number of equivalence classes when compressed, or 0 when 36 /// uncompressed. 37 unsigned NumClasses; 38 39 public: 40 /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. 41 IntEqClasses(unsigned N = 0) : NumClasses(0) { grow(N); } 42 43 /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique 44 /// equivalence classes. 45 /// This requires an uncompressed map. 46 void grow(unsigned N); 47 48 /// clear - Clear all classes so that grow() will assign a unique class to 49 /// every integer. 50 void clear() { 51 EC.clear(); 52 NumClasses = 0; 53 } 54 55 /// Join the equivalence classes of a and b. After joining classes, 56 /// findLeader(a) == findLeader(b). This requires an uncompressed map. 57 /// Returns the new leader. 58 unsigned join(unsigned a, unsigned b); 59 60 /// findLeader - Compute the leader of a's equivalence class. This is the 61 /// smallest member of the class. 62 /// This requires an uncompressed map. 63 unsigned findLeader(unsigned a) const; 64 65 /// compress - Compress equivalence classes by numbering them 0 .. M. 66 /// This makes the equivalence class map immutable. 67 void compress(); 68 69 /// getNumClasses - Return the number of equivalence classes after compress() 70 /// was called. 71 unsigned getNumClasses() const { return NumClasses; } 72 73 /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. 74 /// This requires a compressed map. 75 unsigned operator[](unsigned a) const { 76 assert(NumClasses && "operator[] called before compress()"); 77 return EC[a]; 78 } 79 80 /// uncompress - Change back to the uncompressed representation that allows 81 /// editing. 82 void uncompress(); 83 }; 84 85 } // End llvm namespace 86 87 #endif 88