1193323Sed//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Generic implementation of equivalence classes through the use Tarjan's 11193323Sed// efficient union-find algorithm. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_ADT_EQUIVALENCECLASSES_H 16193323Sed#define LLVM_ADT_EQUIVALENCECLASSES_H 17193323Sed 18218893Sdim#include "llvm/Support/DataTypes.h" 19205407Srdivacky#include <cassert> 20193323Sed#include <set> 21193323Sed 22193323Sednamespace llvm { 23193323Sed 24193323Sed/// EquivalenceClasses - This represents a collection of equivalence classes and 25193323Sed/// supports three efficient operations: insert an element into a class of its 26193323Sed/// own, union two classes, and find the class for a given element. In 27193323Sed/// addition to these modification methods, it is possible to iterate over all 28193323Sed/// of the equivalence classes and all of the elements in a class. 29193323Sed/// 30193323Sed/// This implementation is an efficient implementation that only stores one copy 31193323Sed/// of the element being indexed per entry in the set, and allows any arbitrary 32193323Sed/// type to be indexed (as long as it can be ordered with operator<). 33193323Sed/// 34193323Sed/// Here is a simple example using integers: 35193323Sed/// 36243830Sdim/// \code 37193323Sed/// EquivalenceClasses<int> EC; 38193323Sed/// EC.unionSets(1, 2); // insert 1, 2 into the same set 39193323Sed/// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets 40193323Sed/// EC.unionSets(5, 1); // merge the set for 1 with 5's set. 41193323Sed/// 42193323Sed/// for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end(); 43193323Sed/// I != E; ++I) { // Iterate over all of the equivalence sets. 44193323Sed/// if (!I->isLeader()) continue; // Ignore non-leader sets. 45193323Sed/// for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I); 46193323Sed/// MI != EC.member_end(); ++MI) // Loop over members in this set. 47193323Sed/// cerr << *MI << " "; // Print member. 48193323Sed/// cerr << "\n"; // Finish set. 49193323Sed/// } 50243830Sdim/// \endcode 51193323Sed/// 52193323Sed/// This example prints: 53193323Sed/// 4 54193323Sed/// 5 1 2 55193323Sed/// 56193323Sedtemplate <class ElemTy> 57193323Sedclass EquivalenceClasses { 58193323Sed /// ECValue - The EquivalenceClasses data structure is just a set of these. 59193323Sed /// Each of these represents a relation for a value. First it stores the 60193323Sed /// value itself, which provides the ordering that the set queries. Next, it 61193323Sed /// provides a "next pointer", which is used to enumerate all of the elements 62193323Sed /// in the unioned set. Finally, it defines either a "end of list pointer" or 63193323Sed /// "leader pointer" depending on whether the value itself is a leader. A 64193323Sed /// "leader pointer" points to the node that is the leader for this element, 65193323Sed /// if the node is not a leader. A "end of list pointer" points to the last 66193323Sed /// node in the list of members of this list. Whether or not a node is a 67193323Sed /// leader is determined by a bit stolen from one of the pointers. 68193323Sed class ECValue { 69193323Sed friend class EquivalenceClasses; 70193323Sed mutable const ECValue *Leader, *Next; 71193323Sed ElemTy Data; 72193323Sed // ECValue ctor - Start out with EndOfList pointing to this node, Next is 73193323Sed // Null, isLeader = true. 74193323Sed ECValue(const ElemTy &Elt) 75193323Sed : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {} 76193323Sed 77193323Sed const ECValue *getLeader() const { 78193323Sed if (isLeader()) return this; 79193323Sed if (Leader->isLeader()) return Leader; 80193323Sed // Path compression. 81193323Sed return Leader = Leader->getLeader(); 82193323Sed } 83193323Sed const ECValue *getEndOfList() const { 84193323Sed assert(isLeader() && "Cannot get the end of a list for a non-leader!"); 85193323Sed return Leader; 86193323Sed } 87193323Sed 88193323Sed void setNext(const ECValue *NewNext) const { 89193323Sed assert(getNext() == 0 && "Already has a next pointer!"); 90193323Sed Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader()); 91193323Sed } 92193323Sed public: 93193323Sed ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1), 94193323Sed Data(RHS.Data) { 95193323Sed // Only support copying of singleton nodes. 96193323Sed assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!"); 97193323Sed } 98193323Sed 99193323Sed bool operator<(const ECValue &UFN) const { return Data < UFN.Data; } 100193323Sed 101193323Sed bool isLeader() const { return (intptr_t)Next & 1; } 102193323Sed const ElemTy &getData() const { return Data; } 103193323Sed 104193323Sed const ECValue *getNext() const { 105193323Sed return (ECValue*)((intptr_t)Next & ~(intptr_t)1); 106193323Sed } 107193323Sed 108193323Sed template<typename T> 109193323Sed bool operator<(const T &Val) const { return Data < Val; } 110193323Sed }; 111193323Sed 112193323Sed /// TheMapping - This implicitly provides a mapping from ElemTy values to the 113193323Sed /// ECValues, it just keeps the key as part of the value. 114193323Sed std::set<ECValue> TheMapping; 115193323Sed 116193323Sedpublic: 117193323Sed EquivalenceClasses() {} 118193323Sed EquivalenceClasses(const EquivalenceClasses &RHS) { 119193323Sed operator=(RHS); 120193323Sed } 121193323Sed 122193323Sed const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) { 123193323Sed TheMapping.clear(); 124193323Sed for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 125193323Sed if (I->isLeader()) { 126193323Sed member_iterator MI = RHS.member_begin(I); 127193323Sed member_iterator LeaderIt = member_begin(insert(*MI)); 128193323Sed for (++MI; MI != member_end(); ++MI) 129193323Sed unionSets(LeaderIt, member_begin(insert(*MI))); 130193323Sed } 131193323Sed return *this; 132193323Sed } 133193323Sed 134193323Sed //===--------------------------------------------------------------------===// 135193323Sed // Inspection methods 136193323Sed // 137193323Sed 138193323Sed /// iterator* - Provides a way to iterate over all values in the set. 139193323Sed typedef typename std::set<ECValue>::const_iterator iterator; 140193323Sed iterator begin() const { return TheMapping.begin(); } 141193323Sed iterator end() const { return TheMapping.end(); } 142193323Sed 143193323Sed bool empty() const { return TheMapping.empty(); } 144193323Sed 145193323Sed /// member_* Iterate over the members of an equivalence class. 146193323Sed /// 147193323Sed class member_iterator; 148193323Sed member_iterator member_begin(iterator I) const { 149193323Sed // Only leaders provide anything to iterate over. 150193323Sed return member_iterator(I->isLeader() ? &*I : 0); 151193323Sed } 152193323Sed member_iterator member_end() const { 153193323Sed return member_iterator(0); 154193323Sed } 155193323Sed 156193323Sed /// findValue - Return an iterator to the specified value. If it does not 157193323Sed /// exist, end() is returned. 158193323Sed iterator findValue(const ElemTy &V) const { 159193323Sed return TheMapping.find(V); 160193323Sed } 161193323Sed 162193323Sed /// getLeaderValue - Return the leader for the specified value that is in the 163193323Sed /// set. It is an error to call this method for a value that is not yet in 164193323Sed /// the set. For that, call getOrInsertLeaderValue(V). 165193323Sed const ElemTy &getLeaderValue(const ElemTy &V) const { 166193323Sed member_iterator MI = findLeader(V); 167193323Sed assert(MI != member_end() && "Value is not in the set!"); 168193323Sed return *MI; 169193323Sed } 170193323Sed 171193323Sed /// getOrInsertLeaderValue - Return the leader for the specified value that is 172193323Sed /// in the set. If the member is not in the set, it is inserted, then 173193323Sed /// returned. 174210299Sed const ElemTy &getOrInsertLeaderValue(const ElemTy &V) { 175193323Sed member_iterator MI = findLeader(insert(V)); 176193323Sed assert(MI != member_end() && "Value is not in the set!"); 177193323Sed return *MI; 178193323Sed } 179193323Sed 180193323Sed /// getNumClasses - Return the number of equivalence classes in this set. 181193323Sed /// Note that this is a linear time operation. 182193323Sed unsigned getNumClasses() const { 183193323Sed unsigned NC = 0; 184193323Sed for (iterator I = begin(), E = end(); I != E; ++I) 185193323Sed if (I->isLeader()) ++NC; 186193323Sed return NC; 187193323Sed } 188193323Sed 189193323Sed 190193323Sed //===--------------------------------------------------------------------===// 191193323Sed // Mutation methods 192193323Sed 193193323Sed /// insert - Insert a new value into the union/find set, ignoring the request 194193323Sed /// if the value already exists. 195193323Sed iterator insert(const ElemTy &Data) { 196208599Srdivacky return TheMapping.insert(ECValue(Data)).first; 197193323Sed } 198193323Sed 199193323Sed /// findLeader - Given a value in the set, return a member iterator for the 200193323Sed /// equivalence class it is in. This does the path-compression part that 201193323Sed /// makes union-find "union findy". This returns an end iterator if the value 202193323Sed /// is not in the equivalence class. 203193323Sed /// 204193323Sed member_iterator findLeader(iterator I) const { 205193323Sed if (I == TheMapping.end()) return member_end(); 206193323Sed return member_iterator(I->getLeader()); 207193323Sed } 208193323Sed member_iterator findLeader(const ElemTy &V) const { 209193323Sed return findLeader(TheMapping.find(V)); 210193323Sed } 211193323Sed 212193323Sed 213193323Sed /// union - Merge the two equivalence sets for the specified values, inserting 214193323Sed /// them if they do not already exist in the equivalence set. 215193323Sed member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) { 216193323Sed iterator V1I = insert(V1), V2I = insert(V2); 217193323Sed return unionSets(findLeader(V1I), findLeader(V2I)); 218193323Sed } 219193323Sed member_iterator unionSets(member_iterator L1, member_iterator L2) { 220193323Sed assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!"); 221193323Sed if (L1 == L2) return L1; // Unifying the same two sets, noop. 222193323Sed 223193323Sed // Otherwise, this is a real union operation. Set the end of the L1 list to 224193323Sed // point to the L2 leader node. 225193323Sed const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node; 226193323Sed L1LV.getEndOfList()->setNext(&L2LV); 227193323Sed 228193323Sed // Update L1LV's end of list pointer. 229193323Sed L1LV.Leader = L2LV.getEndOfList(); 230193323Sed 231193323Sed // Clear L2's leader flag: 232193323Sed L2LV.Next = L2LV.getNext(); 233193323Sed 234193323Sed // L2's leader is now L1. 235193323Sed L2LV.Leader = &L1LV; 236193323Sed return L1; 237193323Sed } 238193323Sed 239198090Srdivacky class member_iterator : public std::iterator<std::forward_iterator_tag, 240198090Srdivacky const ElemTy, ptrdiff_t> { 241198090Srdivacky typedef std::iterator<std::forward_iterator_tag, 242198090Srdivacky const ElemTy, ptrdiff_t> super; 243193323Sed const ECValue *Node; 244193323Sed friend class EquivalenceClasses; 245193323Sed public: 246193323Sed typedef size_t size_type; 247193323Sed typedef typename super::pointer pointer; 248193323Sed typedef typename super::reference reference; 249193323Sed 250193323Sed explicit member_iterator() {} 251193323Sed explicit member_iterator(const ECValue *N) : Node(N) {} 252193323Sed member_iterator(const member_iterator &I) : Node(I.Node) {} 253193323Sed 254193323Sed reference operator*() const { 255193323Sed assert(Node != 0 && "Dereferencing end()!"); 256193323Sed return Node->getData(); 257193323Sed } 258193323Sed reference operator->() const { return operator*(); } 259193323Sed 260193323Sed member_iterator &operator++() { 261193323Sed assert(Node != 0 && "++'d off the end of the list!"); 262193323Sed Node = Node->getNext(); 263193323Sed return *this; 264193323Sed } 265193323Sed 266193323Sed member_iterator operator++(int) { // postincrement operators. 267193323Sed member_iterator tmp = *this; 268193323Sed ++*this; 269193323Sed return tmp; 270193323Sed } 271193323Sed 272193323Sed bool operator==(const member_iterator &RHS) const { 273193323Sed return Node == RHS.Node; 274193323Sed } 275193323Sed bool operator!=(const member_iterator &RHS) const { 276193323Sed return Node != RHS.Node; 277193323Sed } 278193323Sed }; 279193323Sed}; 280193323Sed 281193323Sed} // End llvm namespace 282193323Sed 283193323Sed#endif 284