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