LLVM API Documentation

EquivalenceClasses.h

Go to the documentation of this file.
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 through the use Tarjan's
00011 // efficient union-find algorithm.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_ADT_EQUIVALENCECLASSES_H
00016 #define LLVM_ADT_EQUIVALENCECLASSES_H
00017 
00018 #include "llvm/ADT/iterator"
00019 #include "llvm/Support/DataTypes.h"
00020 #include <set>
00021 
00022 namespace llvm {
00023 
00024 /// EquivalenceClasses - This represents a collection of equivalence classes and
00025 /// supports three efficient operations: insert an element into a class of its
00026 /// own, union two classes, and find the class for a given element.  In
00027 /// addition to these modification methods, it is possible to iterate over all
00028 /// of the equivalence classes and all of the elements in a class.
00029 ///
00030 /// This implementation is an efficient implementation that only stores one copy
00031 /// of the element being indexed per entry in the set, and allows any arbitrary
00032 /// type to be indexed (as long as it can be ordered with operator<).
00033 ///
00034 /// Here is a simple example using integers:
00035 ///
00036 ///  EquivalenceClasses<int> EC;
00037 ///  EC.unionSets(1, 2);                // insert 1, 2 into the same set
00038 ///  EC.insert(4); EC.insert(5);        // insert 4, 5 into own sets
00039 ///  EC.unionSets(5, 1);                // merge the set for 1 with 5's set.
00040 ///
00041 ///  for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
00042 ///       I != E; ++I) {           // Iterate over all of the equivalence sets.
00043 ///    if (!I->isLeader()) continue;   // Ignore non-leader sets.
00044 ///    for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
00045 ///         MI != EC.member_end(); ++MI)   // Loop over members in this set.
00046 ///      std::cerr << *MI << " ";  // Print member.
00047 ///    std::cerr << "\n";   // Finish set.
00048 ///  }
00049 ///
00050 /// This example prints:
00051 ///   4
00052 ///   5 1 2
00053 ///
00054 template <class ElemTy>
00055 class EquivalenceClasses {
00056   /// ECValue - The EquivalenceClasses data structure is just a set of these.
00057   /// Each of these represents a relation for a value.  First it stores the
00058   /// value itself, which provides the ordering that the set queries.  Next, it
00059   /// provides a "next pointer", which is used to enumerate all of the elements
00060   /// in the unioned set.  Finally, it defines either a "end of list pointer" or
00061   /// "leader pointer" depending on whether the value itself is a leader.  A
00062   /// "leader pointer" points to the node that is the leader for this element,
00063   /// if the node is not a leader.  A "end of list pointer" points to the last
00064   /// node in the list of members of this list.  Whether or not a node is a
00065   /// leader is determined by a bit stolen from one of the pointers.
00066   class ECValue {
00067     friend class EquivalenceClasses;
00068     mutable const ECValue *Leader, *Next;
00069     ElemTy Data;
00070     // ECValue ctor - Start out with EndOfList pointing to this node, Next is
00071     // Null, isLeader = true.
00072     ECValue(const ElemTy &Elt)
00073       : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}
00074 
00075     const ECValue *getLeader() const {
00076       if (isLeader()) return this;
00077       if (Leader->isLeader()) return Leader;
00078       // Path compression.
00079       return Leader = Leader->getLeader();
00080     }
00081     const ECValue *getEndOfList() const {
00082       assert(isLeader() && "Cannot get the end of a list for a non-leader!");
00083       return Leader;
00084     }
00085 
00086     void setNext(const ECValue *NewNext) const {
00087       assert(getNext() == 0 && "Already has a next pointer!");
00088       Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
00089     }
00090   public:
00091     ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
00092                                   Data(RHS.Data) {
00093       // Only support copying of singleton nodes.
00094       assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!");
00095     }
00096 
00097     bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
00098 
00099     bool isLeader() const { return (intptr_t)Next & 1; }
00100     const ElemTy &getData() const { return Data; }
00101 
00102     const ECValue *getNext() const {
00103       return (ECValue*)((intptr_t)Next & ~(intptr_t)1);
00104     }
00105 
00106     template<typename T>
00107     bool operator<(const T &Val) const { return Data < Val; }
00108   };
00109 
00110   /// TheMapping - This implicitly provides a mapping from ElemTy values to the
00111   /// ECValues, it just keeps the key as part of the value.
00112   std::set<ECValue> TheMapping;
00113 
00114 public:
00115   EquivalenceClasses() {}
00116   EquivalenceClasses(const EquivalenceClasses &RHS) {
00117     operator=(RHS);
00118   }
00119 
00120   const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
00121     TheMapping.clear();
00122     for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
00123       if (I->isLeader()) {
00124         member_iterator MI = RHS.member_begin(I);
00125         member_iterator LeaderIt = member_begin(insert(*MI));
00126         for (++MI; MI != member_end(); ++MI)
00127           unionSets(LeaderIt, member_begin(insert(*MI)));
00128       }
00129     return *this;
00130   }
00131 
00132   //===--------------------------------------------------------------------===//
00133   // Inspection methods
00134   //
00135 
00136   /// iterator* - Provides a way to iterate over all values in the set.
00137   typedef typename std::set<ECValue>::const_iterator iterator;
00138   iterator begin() const { return TheMapping.begin(); }
00139   iterator end() const { return TheMapping.end(); }
00140 
00141   bool empty() const { return TheMapping.empty(); }
00142 
00143   /// member_* Iterate over the members of an equivalence class.
00144   ///
00145   class member_iterator;
00146   member_iterator member_begin(iterator I) const {
00147     // Only leaders provide anything to iterate over.
00148     return member_iterator(I->isLeader() ? &*I : 0);
00149   }
00150   member_iterator member_end() const {
00151     return member_iterator(0);
00152   }
00153 
00154   /// findValue - Return an iterator to the specified value.  If it does not
00155   /// exist, end() is returned.
00156   iterator findValue(const ElemTy &V) const {
00157     return TheMapping.find(V);
00158   }
00159 
00160   /// getLeaderValue - Return the leader for the specified value that is in the
00161   /// set.  It is an error to call this method for a value that is not yet in
00162   /// the set.  For that, call getOrInsertLeaderValue(V).
00163   const ElemTy &getLeaderValue(const ElemTy &V) const {
00164     member_iterator MI = findLeader(V);
00165     assert(MI != member_end() && "Value is not in the set!");
00166     return *MI;
00167   }
00168 
00169   /// getOrInsertLeaderValue - Return the leader for the specified value that is
00170   /// in the set.  If the member is not in the set, it is inserted, then
00171   /// returned.
00172   const ElemTy &getOrInsertLeaderValue(const ElemTy &V) const {
00173     member_iterator MI = findLeader(insert(V));
00174     assert(MI != member_end() && "Value is not in the set!");
00175     return *MI;
00176   }
00177 
00178   /// getNumClasses - Return the number of equivalence classes in this set.
00179   /// Note that this is a linear time operation.
00180   unsigned getNumClasses() const {
00181     unsigned NC = 0;
00182     for (iterator I = begin(), E = end(); I != E; ++I)
00183       if (I->isLeader()) ++NC;
00184     return NC;
00185   }
00186 
00187 
00188   //===--------------------------------------------------------------------===//
00189   // Mutation methods
00190 
00191   /// insert - Insert a new value into the union/find set, ignoring the request
00192   /// if the value already exists.
00193   iterator insert(const ElemTy &Data) {
00194     return TheMapping.insert(Data).first;
00195   }
00196 
00197   /// findLeader - Given a value in the set, return a member iterator for the
00198   /// equivalence class it is in.  This does the path-compression part that
00199   /// makes union-find "union findy".  This returns an end iterator if the value
00200   /// is not in the equivalence class.
00201   ///
00202   member_iterator findLeader(iterator I) const {
00203     if (I == TheMapping.end()) return member_end();
00204     return member_iterator(I->getLeader());
00205   }
00206   member_iterator findLeader(const ElemTy &V) const {
00207     return findLeader(TheMapping.find(V));
00208   }
00209 
00210 
00211   /// union - Merge the two equivalence sets for the specified values, inserting
00212   /// them if they do not already exist in the equivalence set.
00213   member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
00214     iterator V1I = insert(V1), V2I = insert(V2);
00215     return unionSets(findLeader(V1I), findLeader(V2I));
00216   }
00217   member_iterator unionSets(member_iterator L1, member_iterator L2) {
00218     assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
00219     if (L1 == L2) return L1;   // Unifying the same two sets, noop.
00220 
00221     // Otherwise, this is a real union operation.  Set the end of the L1 list to
00222     // point to the L2 leader node.
00223     const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
00224     L1LV.getEndOfList()->setNext(&L2LV);
00225 
00226     // Update L1LV's end of list pointer.
00227     L1LV.Leader = L2LV.getEndOfList();
00228 
00229     // Clear L2's leader flag:
00230     L2LV.Next = L2LV.getNext();
00231 
00232     // L2's leader is now L1.
00233     L2LV.Leader = &L1LV;
00234     return L1;
00235   }
00236 
00237   class member_iterator : public forward_iterator<ElemTy, ptrdiff_t> {
00238     typedef forward_iterator<const ElemTy, ptrdiff_t> super;
00239     const ECValue *Node;
00240     friend class EquivalenceClasses;
00241   public:
00242     typedef size_t size_type;
00243     typedef typename super::pointer pointer;
00244     typedef typename super::reference reference;
00245 
00246     explicit member_iterator() {}
00247     explicit member_iterator(const ECValue *N) : Node(N) {}
00248     member_iterator(const member_iterator &I) : Node(I.Node) {}
00249 
00250     reference operator*() const {
00251       assert(Node != 0 && "Dereferencing end()!");
00252       return Node->getData();
00253     }
00254     reference operator->() const { return operator*(); }
00255 
00256     member_iterator &operator++() {
00257       assert(Node != 0 && "++'d off the end of the list!");
00258       Node = Node->getNext();
00259       return *this;
00260     }
00261 
00262     member_iterator operator++(int) {    // postincrement operators.
00263       member_iterator tmp = *this;
00264       ++*this;
00265       return tmp;
00266     }
00267 
00268     bool operator==(const member_iterator &RHS) const {
00269       return Node == RHS.Node;
00270     }
00271     bool operator!=(const member_iterator &RHS) const {
00272       return Node != RHS.Node;
00273     }
00274   };
00275 };
00276 
00277 } // End llvm namespace
00278 
00279 #endif