LCOV - code coverage report
Current view: top level - include/llvm/ADT - EquivalenceClasses.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 51 56 91.1 %
Date: 2017-09-14 15:23:50 Functions: 19 19 100.0 %
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       33576 : 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       36751 :     ECValue(const ElemTy &Elt)
      79       38274 :       : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}
      80             : 
      81       27400 :     const ECValue *getLeader() const {
      82       54800 :       if (isLeader()) return this;
      83       25066 :       if (Leader->isLeader()) return Leader;
      84             :       // Path compression.
      85        2504 :       return Leader = Leader->getLeader();
      86             :     }
      87             : 
      88             :     const ECValue *getEndOfList() const {
      89             :       assert(isLeader() && "Cannot get the end of a list for a non-leader!");
      90             :       return Leader;
      91             :     }
      92             : 
      93             :     void setNext(const ECValue *NewNext) const {
      94             :       assert(getNext() == nullptr && "Already has a next pointer!");
      95        6444 :       Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
      96             :     }
      97             : 
      98             :   public:
      99       10813 :     ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
     100       10813 :                                   Data(RHS.Data) {
     101             :       // Only support copying of singleton nodes.
     102             :       assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!");
     103             :     }
     104             : 
     105      176415 :     bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
     106             : 
     107       50322 :     bool isLeader() const { return (intptr_t)Next & 1; }
     108        3477 :     const ElemTy &getData() const { return Data; }
     109             : 
     110             :     const ECValue *getNext() const {
     111       13537 :       return (ECValue*)((intptr_t)Next & ~(intptr_t)1);
     112             :     }
     113             : 
     114             :     template<typename T>
     115             :     bool operator<(const T &Val) const { return Data < Val; }
     116             :   };
     117             : 
     118             :   /// TheMapping - This implicitly provides a mapping from ElemTy values to the
     119             :   /// ECValues, it just keeps the key as part of the value.
     120             :   std::set<ECValue> TheMapping;
     121             : 
     122             : public:
     123       33412 :   EquivalenceClasses() = default;
     124         164 :   EquivalenceClasses(const EquivalenceClasses &RHS) {
     125          82 :     operator=(RHS);
     126             :   }
     127             : 
     128       11431 :   const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
     129       22862 :     TheMapping.clear();
     130       22862 :     for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
     131           0 :       if (I->isLeader()) {
     132           0 :         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             :       }
     137       11431 :     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       46392 :   iterator begin() const { return TheMapping.begin(); }
     148       46392 :   iterator end() const { return TheMapping.end(); }
     149             : 
     150         526 :   bool empty() const { return TheMapping.empty(); }
     151             : 
     152             :   /// member_* Iterate over the members of an equivalence class.
     153             :   class member_iterator;
     154             :   member_iterator member_begin(iterator I) const {
     155             :     // Only leaders provide anything to iterate over.
     156       10541 :     return member_iterator(I->isLeader() ? &*I : nullptr);
     157             :   }
     158             :   member_iterator member_end() const {
     159        1051 :     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             :   iterator findValue(const ElemTy &V) const {
     165        4569 :     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             :   const ElemTy &getLeaderValue(const ElemTy &V) const {
     172        9567 :     member_iterator MI = findLeader(V);
     173             :     assert(MI != member_end() && "Value is not in the set!");
     174        9567 :     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         776 :   const ElemTy &getOrInsertLeaderValue(const ElemTy &V) {
     181        2328 :     member_iterator MI = findLeader(insert(V));
     182             :     assert(MI != member_end() && "Value is not in the set!");
     183         776 :     return *MI;
     184             :   }
     185             : 
     186             :   /// getNumClasses - Return the number of equivalence classes in this set.
     187             :   /// Note that this is a linear time operation.
     188             :   unsigned getNumClasses() const {
     189             :     unsigned NC = 0;
     190             :     for (iterator I = begin(), E = end(); I != E; ++I)
     191             :       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             :   iterator insert(const ElemTy &Data) {
     201       81552 :     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       49792 :     if (I == TheMapping.end()) return member_end();
     210       24896 :     return member_iterator(I->getLeader());
     211             :   }
     212        9567 :   member_iterator findLeader(const ElemTy &V) const {
     213       38268 :     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        7055 :   member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
     219       19085 :     iterator V1I = insert(V1), V2I = insert(V2);
     220       21165 :     return unionSets(findLeader(V1I), findLeader(V2I));
     221             :   }
     222             :   member_iterator unionSets(member_iterator L1, member_iterator L2) {
     223             :     assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
     224        7416 :     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        6444 :     const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
     229       12888 :     L1LV.getEndOfList()->setNext(&L2LV);
     230             : 
     231             :     // Update L1LV's end of list pointer.
     232        6444 :     L1LV.Leader = L2LV.getEndOfList();
     233             : 
     234             :     // Clear L2's leader flag:
     235       12888 :     L2LV.Next = L2LV.getNext();
     236             : 
     237             :     // L2's leader is now L1.
     238        6444 :     L2LV.Leader = &L1LV;
     239             :     return L1;
     240             :   }
     241             : 
     242             :   class member_iterator : public std::iterator<std::forward_iterator_tag,
     243             :                                                const ElemTy, ptrdiff_t> {
     244             :     friend class EquivalenceClasses;
     245             : 
     246             :     using super = std::iterator<std::forward_iterator_tag,
     247             :                                 const ElemTy, ptrdiff_t>;
     248             : 
     249             :     const ECValue *Node;
     250             : 
     251             :   public:
     252             :     using size_type = size_t;
     253             :     using pointer = typename super::pointer;
     254             :     using reference = typename super::reference;
     255             : 
     256             :     explicit member_iterator() = default;
     257             :     explicit member_iterator(const ECValue *N) : Node(N) {}
     258             : 
     259             :     reference operator*() const {
     260             :       assert(Node != nullptr && "Dereferencing end()!");
     261       24810 :       return Node->getData();
     262             :     }
     263        1101 :     pointer operator->() const { return &operator*(); }
     264             : 
     265             :     member_iterator &operator++() {
     266             :       assert(Node != nullptr && "++'d off the end of the list!");
     267       14186 :       Node = Node->getNext();
     268             :       return *this;
     269             :     }
     270             : 
     271             :     member_iterator operator++(int) {    // postincrement operators.
     272        1298 :       member_iterator tmp = *this;
     273        1298 :       ++*this;
     274             :       return tmp;
     275             :     }
     276             : 
     277             :     bool operator==(const member_iterator &RHS) const {
     278             :       return Node == RHS.Node;
     279             :     }
     280             :     bool operator!=(const member_iterator &RHS) const {
     281             :       return Node != RHS.Node;
     282             :     }
     283             :   };
     284             : };
     285             : 
     286             : } // end namespace llvm
     287             : 
     288             : #endif // LLVM_ADT_EQUIVALENCECLASSES_H

Generated by: LCOV version 1.13