LLVM API Documentation
#include <EquivalenceClasses.h>
Inheritance diagram for llvm::EquivalenceClasses< ElemTy >:
Public Types | |
typedef std::set< ECValue >::const_iterator | iterator |
iterator* - Provides a way to iterate over all values in the set. | |
Public Member Functions | |
EquivalenceClasses () | |
EquivalenceClasses (const EquivalenceClasses &RHS) | |
const EquivalenceClasses & | operator= (const EquivalenceClasses &RHS) |
iterator | begin () const |
iterator | end () const |
bool | empty () const |
member_iterator | member_begin (iterator I) const |
member_iterator | member_end () const |
iterator | findValue (const ElemTy &V) const |
const ElemTy & | getLeaderValue (const ElemTy &V) const |
const ElemTy & | getOrInsertLeaderValue (const ElemTy &V) const |
unsigned | getNumClasses () const |
iterator | insert (const ElemTy &Data) |
member_iterator | findLeader (iterator I) const |
member_iterator | findLeader (const ElemTy &V) const |
member_iterator | unionSets (const ElemTy &V1, const ElemTy &V2) |
member_iterator | unionSets (member_iterator L1, member_iterator L2) |
Classes | |
class | ECValue |
class | member_iterator |
This implementation is an efficient implementation that only stores one copy of the element being indexed per entry in the set, and allows any arbitrary type to be indexed (as long as it can be ordered with operator<).
Here is a simple example using integers:
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 EC.unionSets(5, 1); // merge the set for 1 with 5's set.
for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end(); I != E; ++I) { // Iterate over all of the equivalence 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. }
This example prints: 4 5 1 2
Definition at line 55 of file EquivalenceClasses.h.
typedef std::set<ECValue>::const_iterator llvm::EquivalenceClasses< ElemTy >::iterator |
iterator* - Provides a way to iterate over all values in the set.
Definition at line 137 of file EquivalenceClasses.h.
llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses | ( | ) | [inline] |
Definition at line 115 of file EquivalenceClasses.h.
llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses | ( | const EquivalenceClasses< ElemTy > & | RHS | ) | [inline] |
Definition at line 116 of file EquivalenceClasses.h.
iterator llvm::EquivalenceClasses< ElemTy >::begin | ( | ) | const [inline] |
Definition at line 138 of file EquivalenceClasses.h.
Referenced by llvm::EquivalenceClasses< llvm::GlobalValue * >::getNumClasses(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=().
bool llvm::EquivalenceClasses< ElemTy >::empty | ( | ) | const [inline] |
Definition at line 141 of file EquivalenceClasses.h.
iterator llvm::EquivalenceClasses< ElemTy >::end | ( | ) | const [inline] |
Definition at line 139 of file EquivalenceClasses.h.
Referenced by llvm::DSNode::addFullFunctionList(), llvm::DSNode::addFullGlobalsList(), llvm::EquivalenceClasses< llvm::GlobalValue * >::getNumClasses(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=().
member_iterator llvm::EquivalenceClasses< ElemTy >::findLeader | ( | const ElemTy & | V | ) | const [inline] |
Definition at line 206 of file EquivalenceClasses.h.
member_iterator llvm::EquivalenceClasses< ElemTy >::findLeader | ( | iterator | I | ) | const [inline] |
findLeader - Given a value in the set, return a member iterator for the equivalence class it is in. This does the path-compression part that makes union-find "union findy". This returns an end iterator if the value is not in the equivalence class.
Definition at line 202 of file EquivalenceClasses.h.
Referenced by llvm::EquivalenceClasses< llvm::GlobalValue * >::findLeader(), llvm::EquivalenceClasses< llvm::GlobalValue * >::getLeaderValue(), llvm::EquivalenceClasses< llvm::GlobalValue * >::getOrInsertLeaderValue(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::unionSets().
iterator llvm::EquivalenceClasses< ElemTy >::findValue | ( | const ElemTy & | V | ) | const [inline] |
findValue - Return an iterator to the specified value. If it does not exist, end() is returned.
Definition at line 156 of file EquivalenceClasses.h.
Referenced by llvm::DSNode::addFullFunctionList(), and llvm::DSNode::addFullGlobalsList().
const ElemTy& llvm::EquivalenceClasses< ElemTy >::getLeaderValue | ( | const ElemTy & | V | ) | const [inline] |
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).
Definition at line 163 of file EquivalenceClasses.h.
unsigned llvm::EquivalenceClasses< ElemTy >::getNumClasses | ( | ) | const [inline] |
getNumClasses - Return the number of equivalence classes in this set. Note that this is a linear time operation.
Definition at line 180 of file EquivalenceClasses.h.
const ElemTy& llvm::EquivalenceClasses< ElemTy >::getOrInsertLeaderValue | ( | const ElemTy & | V | ) | const [inline] |
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.
Definition at line 172 of file EquivalenceClasses.h.
iterator llvm::EquivalenceClasses< ElemTy >::insert | ( | const ElemTy & | Data | ) | [inline] |
insert - Insert a new value into the union/find set, ignoring the request if the value already exists.
Definition at line 193 of file EquivalenceClasses.h.
Referenced by llvm::EquivalenceClasses< llvm::GlobalValue * >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::unionSets().
member_iterator llvm::EquivalenceClasses< ElemTy >::member_begin | ( | iterator | I | ) | const [inline] |
Definition at line 146 of file EquivalenceClasses.h.
Referenced by llvm::DSNode::addFullFunctionList(), llvm::DSNode::addFullGlobalsList(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=().
member_iterator llvm::EquivalenceClasses< ElemTy >::member_end | ( | ) | const [inline] |
Definition at line 150 of file EquivalenceClasses.h.
Referenced by llvm::DSNode::addFullFunctionList(), llvm::DSNode::addFullGlobalsList(), llvm::EquivalenceClasses< llvm::GlobalValue * >::findLeader(), llvm::EquivalenceClasses< llvm::GlobalValue * >::getLeaderValue(), llvm::EquivalenceClasses< llvm::GlobalValue * >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::unionSets().
const EquivalenceClasses& llvm::EquivalenceClasses< ElemTy >::operator= | ( | const EquivalenceClasses< ElemTy > & | RHS | ) | [inline] |
Definition at line 120 of file EquivalenceClasses.h.
Referenced by llvm::EquivalenceClasses< llvm::GlobalValue * >::EquivalenceClasses().
member_iterator llvm::EquivalenceClasses< ElemTy >::unionSets | ( | member_iterator | L1, | |
member_iterator | L2 | |||
) | [inline] |
Definition at line 217 of file EquivalenceClasses.h.
member_iterator llvm::EquivalenceClasses< ElemTy >::unionSets | ( | const ElemTy & | V1, | |
const ElemTy & | V2 | |||
) | [inline] |
union - Merge the two equivalence sets for the specified values, inserting them if they do not already exist in the equivalence set.
Definition at line 213 of file EquivalenceClasses.h.
Referenced by llvm::EquivalenceClasses< llvm::GlobalValue * >::operator=(), and llvm::EquivalenceClasses< llvm::GlobalValue * >::unionSets().