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