LLVM API Documentation
00001 //===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Generic implementation of equivalence classes and implementation of 00011 // union-find algorithms A not-so-fancy implementation: 2 level tree i.e root 00012 // and one more level Overhead of a union = size of the equivalence class being 00013 // attached Overhead of a find = 1. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #ifndef LLVM_ADT_EQUIVALENCECLASSES_H 00018 #define LLVM_ADT_EQUIVALENCECLASSES_H 00019 00020 #include <map> 00021 #include <set> 00022 #include <vector> 00023 00024 namespace llvm { 00025 00026 template <class ElemTy> 00027 class EquivalenceClasses { 00028 // Maps each element to the element that is the leader of its 00029 // equivalence class. 00030 std::map<ElemTy, ElemTy> Elem2LeaderMap; 00031 00032 // Maintains the set of leaders 00033 std::set<ElemTy> LeaderSet; 00034 00035 // Caches the equivalence class for each leader 00036 std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap; 00037 00038 // Make Element2 the leader of the union of classes Element1 and Element2 00039 // Element1 and Element2 are presumed to be leaders of their respective 00040 // equivalence classes. 00041 void attach(ElemTy Element1, ElemTy Element2) { 00042 for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 00043 Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 00044 ElemI != ElemE; ++ElemI) { 00045 if (ElemI->second == Element1) 00046 Elem2LeaderMap[ElemI->first] = Element2; 00047 } 00048 } 00049 00050 public: 00051 // If an element has not yet in any class, make it a separate new class. 00052 // Return the leader of the class containing the element. 00053 ElemTy addElement (ElemTy NewElement) { 00054 typename std::map<ElemTy, ElemTy>::iterator ElemI = 00055 Elem2LeaderMap.find(NewElement); 00056 if (ElemI == Elem2LeaderMap.end()) { 00057 Elem2LeaderMap[NewElement] = NewElement; 00058 LeaderSet.insert(NewElement); 00059 return NewElement; 00060 } 00061 else 00062 return ElemI->second; 00063 } 00064 00065 ElemTy findClass(ElemTy Element) const { 00066 typename std::map<ElemTy, ElemTy>::const_iterator I = 00067 Elem2LeaderMap.find(Element); 00068 return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second; 00069 } 00070 00071 /// Attach the set with Element1 to the set with Element2 adding Element1 and 00072 /// Element2 to the set of equivalence classes if they are not there already. 00073 /// Implication: Make Element1 the element in the smaller set. 00074 /// Take Leader[Element1] out of the set of leaders. 00075 void unionSetsWith(ElemTy Element1, ElemTy Element2) { 00076 // If either Element1 or Element2 does not already exist, include it 00077 const ElemTy& leader1 = addElement(Element1); 00078 const ElemTy& leader2 = addElement(Element2); 00079 assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0); 00080 if (leader1 != leader2) { 00081 attach(leader1, leader2); 00082 LeaderSet.erase(leader1); 00083 } 00084 } 00085 00086 // Returns a vector containing all the elements in the equivalence class 00087 // including Element1 00088 const std::set<ElemTy> & getEqClass(ElemTy Element1) { 00089 assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end()); 00090 const ElemTy classLeader = Elem2LeaderMap[Element1]; 00091 00092 std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader]; 00093 00094 // If the EqClass vector is empty, it has not been computed yet: do it now 00095 if (EqClass.empty()) { 00096 for (typename std::map<ElemTy, ElemTy>::iterator 00097 ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 00098 ElemI != ElemE; ++ElemI) 00099 if (ElemI->second == classLeader) 00100 EqClass.insert(ElemI->first); 00101 assert(! EqClass.empty()); // must at least include the leader 00102 } 00103 00104 return EqClass; 00105 } 00106 00107 std::set<ElemTy>& getLeaderSet() { return LeaderSet; } 00108 const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; } 00109 00110 std::map<ElemTy, ElemTy>& getLeaderMap() { return Elem2LeaderMap;} 00111 const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;} 00112 }; 00113 00114 } // End llvm namespace 00115 00116 #endif