1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 3b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// The LLVM Compiler Infrastructure 4b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 8b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell//===----------------------------------------------------------------------===// 99769ab22265b313171d201b5928688524a01bd87Misha Brukman// 1072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner// Generic implementation of equivalence classes through the use Tarjan's 1172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner// efficient union-find algorithm. 129769ab22265b313171d201b5928688524a01bd87Misha Brukman// 1348486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===----------------------------------------------------------------------===// 1487a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 15551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_EQUIVALENCECLASSES_H 16551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_EQUIVALENCECLASSES_H 1787a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 181f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 197e1b037edd0d5ad2b54f530f1ba0d2f64c9ca686Andrew Lenharth#include <cassert> 208bba4dd9bcaf8ba63be24dbcbbed6ff35504e9e5Andrew Lenharth#include <set> 2187a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 22d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 23d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// EquivalenceClasses - This represents a collection of equivalence classes and 2572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// supports three efficient operations: insert an element into a class of its 2672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// own, union two classes, and find the class for a given element. In 2772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// addition to these modification methods, it is possible to iterate over all 2872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// of the equivalence classes and all of the elements in a class. 2972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 3072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// This implementation is an efficient implementation that only stores one copy 3172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// of the element being indexed per entry in the set, and allows any arbitrary 3272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// type to be indexed (as long as it can be ordered with operator<). 3372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 3472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// Here is a simple example using integers: 3572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 364e0ae44b3a1b5f7157351764fd125c7c85959797Dmitri Gribenko/// \code 3772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// EquivalenceClasses<int> EC; 3872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// EC.unionSets(1, 2); // insert 1, 2 into the same set 3972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets 4072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// EC.unionSets(5, 1); // merge the set for 1 with 5's set. 4172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 4272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end(); 4372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// I != E; ++I) { // Iterate over all of the equivalence sets. 4472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// if (!I->isLeader()) continue; // Ignore non-leader sets. 4572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I); 4672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// MI != EC.member_end(); ++MI) // Loop over members in this set. 47e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling/// cerr << *MI << " "; // Print member. 48e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling/// cerr << "\n"; // Finish set. 4972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// } 504e0ae44b3a1b5f7157351764fd125c7c85959797Dmitri Gribenko/// \endcode 5172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 5272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// This example prints: 5372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 4 5472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 5 1 2 5572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner/// 5687a991eea38197c9e5abc763d83321799649b25bSumant Kowshiktemplate <class ElemTy> 5787a991eea38197c9e5abc763d83321799649b25bSumant Kowshikclass EquivalenceClasses { 5872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// ECValue - The EquivalenceClasses data structure is just a set of these. 5972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// Each of these represents a relation for a value. First it stores the 6072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// value itself, which provides the ordering that the set queries. Next, it 6172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// provides a "next pointer", which is used to enumerate all of the elements 6272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// in the unioned set. Finally, it defines either a "end of list pointer" or 6372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// "leader pointer" depending on whether the value itself is a leader. A 6472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// "leader pointer" points to the node that is the leader for this element, 6572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// if the node is not a leader. A "end of list pointer" points to the last 6672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// node in the list of members of this list. Whether or not a node is a 6772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// leader is determined by a bit stolen from one of the pointers. 6872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner class ECValue { 6972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner friend class EquivalenceClasses; 7072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner mutable const ECValue *Leader, *Next; 7172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner ElemTy Data; 7272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // ECValue ctor - Start out with EndOfList pointing to this node, Next is 7372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Null, isLeader = true. 7472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner ECValue(const ElemTy &Elt) 7572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {} 7672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 7772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ECValue *getLeader() const { 7872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner if (isLeader()) return this; 7967823970461ba101fbb3704b016182e19bc5e2dfChris Lattner if (Leader->isLeader()) return Leader; 8072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Path compression. 8172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return Leader = Leader->getLeader(); 8272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 8372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ECValue *getEndOfList() const { 8472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner assert(isLeader() && "Cannot get the end of a list for a non-leader!"); 8572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return Leader; 8687a991eea38197c9e5abc763d83321799649b25bSumant Kowshik } 8787a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 8872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner void setNext(const ECValue *NewNext) const { 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(getNext() == nullptr && "Already has a next pointer!"); 9037884fc79e9a55e92ec26574c710c8d3609aa839Misha Brukman Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader()); 916ffd14dd54b0b1a63f7cc9726a18bdaa6d8008d0Vikram S. Adve } 9272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner public: 9372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1), 9472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner Data(RHS.Data) { 9572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Only support copying of singleton nodes. 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!"); 9772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 9872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 9972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner bool operator<(const ECValue &UFN) const { return Data < UFN.Data; } 10072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 10172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner bool isLeader() const { return (intptr_t)Next & 1; } 10272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ElemTy &getData() const { return Data; } 10372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 10472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ECValue *getNext() const { 10572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return (ECValue*)((intptr_t)Next & ~(intptr_t)1); 10672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 10772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 10872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner template<typename T> 10972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner bool operator<(const T &Val) const { return Data < Val; } 11072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner }; 11172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 11272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// TheMapping - This implicitly provides a mapping from ElemTy values to the 11372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// ECValues, it just keeps the key as part of the value. 11472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner std::set<ECValue> TheMapping; 11572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 11672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattnerpublic: 1174a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner EquivalenceClasses() {} 1184a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner EquivalenceClasses(const EquivalenceClasses &RHS) { 1194a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner operator=(RHS); 1204a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner } 1214a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner 1224a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) { 1231f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner TheMapping.clear(); 1244a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 1251f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner if (I->isLeader()) { 1261f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner member_iterator MI = RHS.member_begin(I); 1271f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner member_iterator LeaderIt = member_begin(insert(*MI)); 1281f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner for (++MI; MI != member_end(); ++MI) 1291f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner unionSets(LeaderIt, member_begin(insert(*MI))); 1301f377fefb745002a7aacb1ec87a4beb7bd87856eChris Lattner } 1314a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner return *this; 1324a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner } 1339769ab22265b313171d201b5928688524a01bd87Misha Brukman 13472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner //===--------------------------------------------------------------------===// 13572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Inspection methods 13672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // 13772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 13872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// iterator* - Provides a way to iterate over all values in the set. 13972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner typedef typename std::set<ECValue>::const_iterator iterator; 14072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner iterator begin() const { return TheMapping.begin(); } 14172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner iterator end() const { return TheMapping.end(); } 14272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 143ef35ba4f646457728a57f73f93e816b77bd9c8a7Chris Lattner bool empty() const { return TheMapping.empty(); } 144ef35ba4f646457728a57f73f93e816b77bd9c8a7Chris Lattner 14572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// member_* Iterate over the members of an equivalence class. 14672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// 14772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner class member_iterator; 14872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator member_begin(iterator I) const { 14972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Only leaders provide anything to iterate over. 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return member_iterator(I->isLeader() ? &*I : nullptr); 15172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 15272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator member_end() const { 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return member_iterator(nullptr); 15487a991eea38197c9e5abc763d83321799649b25bSumant Kowshik } 15587a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 15667823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// findValue - Return an iterator to the specified value. If it does not 15767823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// exist, end() is returned. 15867823970461ba101fbb3704b016182e19bc5e2dfChris Lattner iterator findValue(const ElemTy &V) const { 15967823970461ba101fbb3704b016182e19bc5e2dfChris Lattner return TheMapping.find(V); 16067823970461ba101fbb3704b016182e19bc5e2dfChris Lattner } 16167823970461ba101fbb3704b016182e19bc5e2dfChris Lattner 16267823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// getLeaderValue - Return the leader for the specified value that is in the 16367823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// set. It is an error to call this method for a value that is not yet in 16467823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// the set. For that, call getOrInsertLeaderValue(V). 16567823970461ba101fbb3704b016182e19bc5e2dfChris Lattner const ElemTy &getLeaderValue(const ElemTy &V) const { 16667823970461ba101fbb3704b016182e19bc5e2dfChris Lattner member_iterator MI = findLeader(V); 16767823970461ba101fbb3704b016182e19bc5e2dfChris Lattner assert(MI != member_end() && "Value is not in the set!"); 16867823970461ba101fbb3704b016182e19bc5e2dfChris Lattner return *MI; 16967823970461ba101fbb3704b016182e19bc5e2dfChris Lattner } 17067823970461ba101fbb3704b016182e19bc5e2dfChris Lattner 17167823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// getOrInsertLeaderValue - Return the leader for the specified value that is 17267823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// in the set. If the member is not in the set, it is inserted, then 17367823970461ba101fbb3704b016182e19bc5e2dfChris Lattner /// returned. 17418f82a9a5d81c1214714be1b25f3e548030b7e1cBill Wendling const ElemTy &getOrInsertLeaderValue(const ElemTy &V) { 17567823970461ba101fbb3704b016182e19bc5e2dfChris Lattner member_iterator MI = findLeader(insert(V)); 17667823970461ba101fbb3704b016182e19bc5e2dfChris Lattner assert(MI != member_end() && "Value is not in the set!"); 17767823970461ba101fbb3704b016182e19bc5e2dfChris Lattner return *MI; 17867823970461ba101fbb3704b016182e19bc5e2dfChris Lattner } 17967823970461ba101fbb3704b016182e19bc5e2dfChris Lattner 1804a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner /// getNumClasses - Return the number of equivalence classes in this set. 1814a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner /// Note that this is a linear time operation. 1824a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner unsigned getNumClasses() const { 1834a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner unsigned NC = 0; 1844a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner for (iterator I = begin(), E = end(); I != E; ++I) 1854a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner if (I->isLeader()) ++NC; 1864a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner return NC; 1874a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner } 1884a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner 1894a6d9cf122fa2cd83669f1a284c86949852f0ac3Chris Lattner 19072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner //===--------------------------------------------------------------------===// 19172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Mutation methods 19272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 19372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// insert - Insert a new value into the union/find set, ignoring the request 19472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// if the value already exists. 19572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner iterator insert(const ElemTy &Data) { 1967d9663c70b3300070298d716dba6e6f6ce2d1e3eDouglas Gregor return TheMapping.insert(ECValue(Data)).first; 19787a991eea38197c9e5abc763d83321799649b25bSumant Kowshik } 19872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 19972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// findLeader - Given a value in the set, return a member iterator for the 20072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// equivalence class it is in. This does the path-compression part that 20172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// makes union-find "union findy". This returns an end iterator if the value 20272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// is not in the equivalence class. 20372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// 20472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator findLeader(iterator I) const { 20572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner if (I == TheMapping.end()) return member_end(); 20672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return member_iterator(I->getLeader()); 20772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 20872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator findLeader(const ElemTy &V) const { 20972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return findLeader(TheMapping.find(V)); 21072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 21172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 21272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 21372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// union - Merge the two equivalence sets for the specified values, inserting 21472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner /// them if they do not already exist in the equivalence set. 21572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) { 21667823970461ba101fbb3704b016182e19bc5e2dfChris Lattner iterator V1I = insert(V1), V2I = insert(V2); 21767823970461ba101fbb3704b016182e19bc5e2dfChris Lattner return unionSets(findLeader(V1I), findLeader(V2I)); 21872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 21972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator unionSets(member_iterator L1, member_iterator L2) { 22072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!"); 22172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner if (L1 == L2) return L1; // Unifying the same two sets, noop. 22272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 22372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Otherwise, this is a real union operation. Set the end of the L1 list to 22472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // point to the L2 leader node. 22572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node; 22672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner L1LV.getEndOfList()->setNext(&L2LV); 2279769ab22265b313171d201b5928688524a01bd87Misha Brukman 22872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Update L1LV's end of list pointer. 22972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner L1LV.Leader = L2LV.getEndOfList(); 23072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 23172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // Clear L2's leader flag: 23272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner L2LV.Next = L2LV.getNext(); 23372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 23472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner // L2's leader is now L1. 23572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner L2LV.Leader = &L1LV; 23672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return L1; 23787a991eea38197c9e5abc763d83321799649b25bSumant Kowshik } 23887a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 2397362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif class member_iterator : public std::iterator<std::forward_iterator_tag, 240b97cb9cbe120c50cd78c4d2c0b86d4dd8047b055Gabor Greif const ElemTy, ptrdiff_t> { 241b97cb9cbe120c50cd78c4d2c0b86d4dd8047b055Gabor Greif typedef std::iterator<std::forward_iterator_tag, 242b97cb9cbe120c50cd78c4d2c0b86d4dd8047b055Gabor Greif const ElemTy, ptrdiff_t> super; 24372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner const ECValue *Node; 24472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner friend class EquivalenceClasses; 24572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner public: 24672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner typedef size_t size_type; 24772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner typedef typename super::pointer pointer; 24872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner typedef typename super::reference reference; 24972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 25072af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner explicit member_iterator() {} 25172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner explicit member_iterator(const ECValue *N) : Node(N) {} 25272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 25372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner reference operator*() const { 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Node != nullptr && "Dereferencing end()!"); 255b97cb9cbe120c50cd78c4d2c0b86d4dd8047b055Gabor Greif return Node->getData(); 25672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 25772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner reference operator->() const { return operator*(); } 25872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 25972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator &operator++() { 260dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Node != nullptr && "++'d off the end of the list!"); 26172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner Node = Node->getNext(); 26272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return *this; 26372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 26472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner 26572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator operator++(int) { // postincrement operators. 26672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner member_iterator tmp = *this; 26772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner ++*this; 26872af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return tmp; 26972af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 2706ffd14dd54b0b1a63f7cc9726a18bdaa6d8008d0Vikram S. Adve 27172af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner bool operator==(const member_iterator &RHS) const { 27272af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return Node == RHS.Node; 27372af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 27472af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner bool operator!=(const member_iterator &RHS) const { 27572af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner return Node != RHS.Node; 27672af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner } 27772af57f26c27176f3ed4858e59eb4017f819afe1Chris Lattner }; 27887a991eea38197c9e5abc763d83321799649b25bSumant Kowshik}; 27987a991eea38197c9e5abc763d83321799649b25bSumant Kowshik 280d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 281d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 28287a991eea38197c9e5abc763d83321799649b25bSumant Kowshik#endif 283