LCOV - code coverage report
Current view: top level - include/llvm/ADT - EquivalenceClasses.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 58 144 40.3 %
Date: 2018-10-20 13:21:21 Functions: 18 140 12.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13