//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===//
-//
+//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
//===----------------------------------------------------------------------===//
-//
+//
// Generic implementation of equivalence classes through the use Tarjan's
// efficient union-find algorithm.
-//
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_EQUIVALENCECLASSES_H
#define LLVM_ADT_EQUIVALENCECLASSES_H
-#include "llvm/ADT/iterator"
+#include "llvm/Support/DataTypes.h"
+#include <cassert>
+#include <cstddef>
#include <set>
namespace llvm {
///
/// Here is a simple example using integers:
///
+/// \code
/// EquivalenceClasses<int> EC;
/// EC.unionSets(1, 2); // insert 1, 2 into the same set
/// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets
/// if (!I->isLeader()) continue; // Ignore non-leader sets.
/// for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
/// MI != EC.member_end(); ++MI) // Loop over members in this set.
-/// std::cerr << *MI << " "; // Print member.
-/// std::cerr << "\n"; // Finish set.
+/// cerr << *MI << " "; // Print member.
+/// cerr << "\n"; // Finish set.
/// }
+/// \endcode
///
/// This example prints:
/// 4
const ECValue *getLeader() const {
if (isLeader()) return this;
- if (Leader->isLeader() == 0) return Leader;
+ if (Leader->isLeader()) return Leader;
// Path compression.
return Leader = Leader->getLeader();
}
}
void setNext(const ECValue *NewNext) const {
- assert(getNext() == 0 && "Already has a next pointer!");
- bool isL = isLeader();
- Next = (const ECValue*)((intptr_t)NewNext | isLeader());
+ assert(getNext() == nullptr && "Already has a next pointer!");
+ Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
}
public:
ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
Data(RHS.Data) {
// Only support copying of singleton nodes.
- assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!");
+ assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!");
}
bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
std::set<ECValue> TheMapping;
public:
-
+ EquivalenceClasses() {}
+ EquivalenceClasses(const EquivalenceClasses &RHS) {
+ operator=(RHS);
+ }
+
+ const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
+ TheMapping.clear();
+ for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
+ if (I->isLeader()) {
+ member_iterator MI = RHS.member_begin(I);
+ member_iterator LeaderIt = member_begin(insert(*MI));
+ for (++MI; MI != member_end(); ++MI)
+ unionSets(LeaderIt, member_begin(insert(*MI)));
+ }
+ return *this;
+ }
+
//===--------------------------------------------------------------------===//
// Inspection methods
//
iterator begin() const { return TheMapping.begin(); }
iterator end() const { return TheMapping.end(); }
+ bool empty() const { return TheMapping.empty(); }
+
/// member_* Iterate over the members of an equivalence class.
///
class member_iterator;
member_iterator member_begin(iterator I) const {
// Only leaders provide anything to iterate over.
- return member_iterator(I->isLeader() ? &*I : 0);
+ return member_iterator(I->isLeader() ? &*I : nullptr);
}
member_iterator member_end() const {
- return member_iterator(0);
+ return member_iterator(nullptr);
}
+ /// findValue - Return an iterator to the specified value. If it does not
+ /// exist, end() is returned.
+ iterator findValue(const ElemTy &V) const {
+ return TheMapping.find(V);
+ }
+
+ /// getLeaderValue - Return the leader for the specified value that is in the
+ /// set. It is an error to call this method for a value that is not yet in
+ /// the set. For that, call getOrInsertLeaderValue(V).
+ const ElemTy &getLeaderValue(const ElemTy &V) const {
+ member_iterator MI = findLeader(V);
+ assert(MI != member_end() && "Value is not in the set!");
+ return *MI;
+ }
+
+ /// getOrInsertLeaderValue - Return the leader for the specified value that is
+ /// in the set. If the member is not in the set, it is inserted, then
+ /// returned.
+ const ElemTy &getOrInsertLeaderValue(const ElemTy &V) {
+ member_iterator MI = findLeader(insert(V));
+ assert(MI != member_end() && "Value is not in the set!");
+ return *MI;
+ }
+
+ /// getNumClasses - Return the number of equivalence classes in this set.
+ /// Note that this is a linear time operation.
+ unsigned getNumClasses() const {
+ unsigned NC = 0;
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ if (I->isLeader()) ++NC;
+ return NC;
+ }
+
+
//===--------------------------------------------------------------------===//
// Mutation methods
/// insert - Insert a new value into the union/find set, ignoring the request
/// if the value already exists.
iterator insert(const ElemTy &Data) {
- return TheMapping.insert(Data).first;
+ return TheMapping.insert(ECValue(Data)).first;
}
/// findLeader - Given a value in the set, return a member iterator for the
/// union - Merge the two equivalence sets for the specified values, inserting
/// them if they do not already exist in the equivalence set.
member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
- return unionSets(findLeader(insert(V1)), findLeader(insert(V2)));
+ iterator V1I = insert(V1), V2I = insert(V2);
+ return unionSets(findLeader(V1I), findLeader(V2I));
}
member_iterator unionSets(member_iterator L1, member_iterator L2) {
assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
// point to the L2 leader node.
const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
L1LV.getEndOfList()->setNext(&L2LV);
-
+
// Update L1LV's end of list pointer.
L1LV.Leader = L2LV.getEndOfList();
return L1;
}
- class member_iterator : public forward_iterator<ElemTy, ptrdiff_t> {
- typedef forward_iterator<const ElemTy, ptrdiff_t> super;
+ class member_iterator : public std::iterator<std::forward_iterator_tag,
+ const ElemTy, ptrdiff_t> {
+ typedef std::iterator<std::forward_iterator_tag,
+ const ElemTy, ptrdiff_t> super;
const ECValue *Node;
friend class EquivalenceClasses;
public:
explicit member_iterator() {}
explicit member_iterator(const ECValue *N) : Node(N) {}
- member_iterator(const member_iterator &I) : Node(I.Node) {}
reference operator*() const {
- assert(Node != 0 && "Dereferencing end()!");
+ assert(Node != nullptr && "Dereferencing end()!");
return Node->getData();
}
- reference operator->() const { return operator*(); }
+ pointer operator->() const { return &operator*(); }
member_iterator &operator++() {
- assert(Node != 0 && "++'d off the end of the list!");
+ assert(Node != nullptr && "++'d off the end of the list!");
Node = Node->getNext();
return *this;
}
projects / oota-llvm.git / blobdiff