1e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===// 2e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 3e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// The LLVM Compiler Infrastructure 4e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 5e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// This file is distributed under the University of Illinois Open Source 6e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// License. See LICENSE.TXT for details. 7e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 8e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 9e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 10e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// Generic implementation of equivalence classes through the use Tarjan's 11e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// efficient union-find algorithm. 12e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 13e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 14e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 15e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#ifndef LLVM_ADT_EQUIVALENCECLASSES_H 16e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#define LLVM_ADT_EQUIVALENCECLASSES_H 17e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 181f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 197abe37e4aee38cc79d91dd069a37d7e91d5bef53Shih-wei Liao#include <cassert> 20e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <set> 21e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 22e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaonamespace llvm { 23e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 24e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// EquivalenceClasses - This represents a collection of equivalence classes and 25e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// supports three efficient operations: insert an element into a class of its 26e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// own, union two classes, and find the class for a given element. In 27e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// addition to these modification methods, it is possible to iterate over all 28e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// of the equivalence classes and all of the elements in a class. 29e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 30e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// This implementation is an efficient implementation that only stores one copy 31e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// of the element being indexed per entry in the set, and allows any arbitrary 32e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// type to be indexed (as long as it can be ordered with operator<). 33e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 34e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// Here is a simple example using integers: 35e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 36e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// EquivalenceClasses<int> EC; 37e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// EC.unionSets(1, 2); // insert 1, 2 into the same set 38e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets 39e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// EC.unionSets(5, 1); // merge the set for 1 with 5's set. 40e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 41e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end(); 42e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// I != E; ++I) { // Iterate over all of the equivalence sets. 43e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// if (!I->isLeader()) continue; // Ignore non-leader sets. 44e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I); 45e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// MI != EC.member_end(); ++MI) // Loop over members in this set. 46e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// cerr << *MI << " "; // Print member. 47e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// cerr << "\n"; // Finish set. 48e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// } 49e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 50e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// This example prints: 51e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 4 52e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 5 1 2 53e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 54e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaotemplate <class ElemTy> 55e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaoclass EquivalenceClasses { 56e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// ECValue - The EquivalenceClasses data structure is just a set of these. 57e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// Each of these represents a relation for a value. First it stores the 58e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// value itself, which provides the ordering that the set queries. Next, it 59e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// provides a "next pointer", which is used to enumerate all of the elements 60e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// in the unioned set. Finally, it defines either a "end of list pointer" or 61e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// "leader pointer" depending on whether the value itself is a leader. A 62e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// "leader pointer" points to the node that is the leader for this element, 63e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// if the node is not a leader. A "end of list pointer" points to the last 64e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// node in the list of members of this list. Whether or not a node is a 65e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// leader is determined by a bit stolen from one of the pointers. 66e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao class ECValue { 67e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao friend class EquivalenceClasses; 68e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao mutable const ECValue *Leader, *Next; 69e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao ElemTy Data; 70e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // ECValue ctor - Start out with EndOfList pointing to this node, Next is 71e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Null, isLeader = true. 72e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao ECValue(const ElemTy &Elt) 73e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {} 74e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 75e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ECValue *getLeader() const { 76e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (isLeader()) return this; 77e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (Leader->isLeader()) return Leader; 78e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Path compression. 79e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Leader = Leader->getLeader(); 80e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 81e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ECValue *getEndOfList() const { 82e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(isLeader() && "Cannot get the end of a list for a non-leader!"); 83e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Leader; 84e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 85e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 86e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao void setNext(const ECValue *NewNext) const { 87e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(getNext() == 0 && "Already has a next pointer!"); 88e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader()); 89e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 90e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao public: 91e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1), 92e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Data(RHS.Data) { 93e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Only support copying of singleton nodes. 94e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!"); 95e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 96e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 97e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool operator<(const ECValue &UFN) const { return Data < UFN.Data; } 98e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 99e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool isLeader() const { return (intptr_t)Next & 1; } 100e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ElemTy &getData() const { return Data; } 101e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 102e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ECValue *getNext() const { 103e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return (ECValue*)((intptr_t)Next & ~(intptr_t)1); 104e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 105e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 106e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao template<typename T> 107e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool operator<(const T &Val) const { return Data < Val; } 108e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao }; 109e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 110e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// TheMapping - This implicitly provides a mapping from ElemTy values to the 111e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// ECValues, it just keeps the key as part of the value. 112e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao std::set<ECValue> TheMapping; 113e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 114e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaopublic: 115e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao EquivalenceClasses() {} 116e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao EquivalenceClasses(const EquivalenceClasses &RHS) { 117e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao operator=(RHS); 118e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 119e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 120e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) { 121e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao TheMapping.clear(); 122e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 123e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (I->isLeader()) { 124e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator MI = RHS.member_begin(I); 125e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator LeaderIt = member_begin(insert(*MI)); 126e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao for (++MI; MI != member_end(); ++MI) 127e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unionSets(LeaderIt, member_begin(insert(*MI))); 128e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 129e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return *this; 130e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 131e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 132e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao //===--------------------------------------------------------------------===// 133e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Inspection methods 134e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // 135e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 136e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// iterator* - Provides a way to iterate over all values in the set. 137e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typedef typename std::set<ECValue>::const_iterator iterator; 138e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao iterator begin() const { return TheMapping.begin(); } 139e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao iterator end() const { return TheMapping.end(); } 140e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 141e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool empty() const { return TheMapping.empty(); } 142e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 143e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// member_* Iterate over the members of an equivalence class. 144e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 145e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao class member_iterator; 146e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator member_begin(iterator I) const { 147e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Only leaders provide anything to iterate over. 148e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return member_iterator(I->isLeader() ? &*I : 0); 149e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 150e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator member_end() const { 151e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return member_iterator(0); 152e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 153e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 154e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// findValue - Return an iterator to the specified value. If it does not 155e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// exist, end() is returned. 156e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao iterator findValue(const ElemTy &V) const { 157e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return TheMapping.find(V); 158e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 159e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 160e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// getLeaderValue - Return the leader for the specified value that is in the 161e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// set. It is an error to call this method for a value that is not yet in 162e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// the set. For that, call getOrInsertLeaderValue(V). 163e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ElemTy &getLeaderValue(const ElemTy &V) const { 164e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator MI = findLeader(V); 165e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(MI != member_end() && "Value is not in the set!"); 166e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return *MI; 167e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 168e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 169e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// getOrInsertLeaderValue - Return the leader for the specified value that is 170e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// in the set. If the member is not in the set, it is inserted, then 171e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// returned. 172c1eceec7637bc857cfb9cd3596a735f4d09bcc8cBill Wendling const ElemTy &getOrInsertLeaderValue(const ElemTy &V) { 173e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator MI = findLeader(insert(V)); 174e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(MI != member_end() && "Value is not in the set!"); 175e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return *MI; 176e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 177e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 178e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// getNumClasses - Return the number of equivalence classes in this set. 179e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// Note that this is a linear time operation. 180e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unsigned getNumClasses() const { 181e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao unsigned NC = 0; 182e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao for (iterator I = begin(), E = end(); I != E; ++I) 183e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (I->isLeader()) ++NC; 184e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return NC; 185e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 186e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 187e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 188e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao //===--------------------------------------------------------------------===// 189e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Mutation methods 190e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 191e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// insert - Insert a new value into the union/find set, ignoring the request 192e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// if the value already exists. 193e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao iterator insert(const ElemTy &Data) { 194491363c2ba41b17b9e3698918beaea8f5bf9d024Douglas Gregor return TheMapping.insert(ECValue(Data)).first; 195e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 196e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 197e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// findLeader - Given a value in the set, return a member iterator for the 198e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// equivalence class it is in. This does the path-compression part that 199e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// makes union-find "union findy". This returns an end iterator if the value 200e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// is not in the equivalence class. 201e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 202e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator findLeader(iterator I) const { 203e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (I == TheMapping.end()) return member_end(); 204e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return member_iterator(I->getLeader()); 205e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 206e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator findLeader(const ElemTy &V) const { 2071fd2ce185df1a76548e6d0422e567a7facf985d9Shih-wei Liao return findLeader(TheMapping.find(V)); 208e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 209e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 210e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 211e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// union - Merge the two equivalence sets for the specified values, inserting 212e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// them if they do not already exist in the equivalence set. 213e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) { 214e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao iterator V1I = insert(V1), V2I = insert(V2); 215e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return unionSets(findLeader(V1I), findLeader(V2I)); 216e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 217e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator unionSets(member_iterator L1, member_iterator L2) { 218e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!"); 219e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao if (L1 == L2) return L1; // Unifying the same two sets, noop. 220e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 221e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Otherwise, this is a real union operation. Set the end of the L1 list to 222e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // point to the L2 leader node. 223e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node; 224e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao L1LV.getEndOfList()->setNext(&L2LV); 225e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 226e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Update L1LV's end of list pointer. 227e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao L1LV.Leader = L2LV.getEndOfList(); 228e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 229e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Clear L2's leader flag: 230e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao L2LV.Next = L2LV.getNext(); 231e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 232e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // L2's leader is now L1. 233e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao L2LV.Leader = &L1LV; 234e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return L1; 235e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 236e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 237e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao class member_iterator : public std::iterator<std::forward_iterator_tag, 238e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ElemTy, ptrdiff_t> { 239e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typedef std::iterator<std::forward_iterator_tag, 240e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ElemTy, ptrdiff_t> super; 241e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const ECValue *Node; 242e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao friend class EquivalenceClasses; 243e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao public: 244e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typedef size_t size_type; 245e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typedef typename super::pointer pointer; 246e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typedef typename super::reference reference; 247e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 248e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao explicit member_iterator() {} 249e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao explicit member_iterator(const ECValue *N) : Node(N) {} 250e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator(const member_iterator &I) : Node(I.Node) {} 251e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 252e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao reference operator*() const { 253e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(Node != 0 && "Dereferencing end()!"); 254e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Node->getData(); 255e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 256e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao reference operator->() const { return operator*(); } 257e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 258e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator &operator++() { 259e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao assert(Node != 0 && "++'d off the end of the list!"); 260e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao Node = Node->getNext(); 261e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return *this; 262e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 263e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 264e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator operator++(int) { // postincrement operators. 265e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao member_iterator tmp = *this; 266e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao ++*this; 267e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return tmp; 268e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 269e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 270e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool operator==(const member_iterator &RHS) const { 271e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Node == RHS.Node; 272e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 273e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao bool operator!=(const member_iterator &RHS) const { 274e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao return Node != RHS.Node; 275e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 276e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao }; 277e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao}; 278e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 279e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao} // End llvm namespace 280e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 281e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#endif 282