LLVM API Documentation

llvm::EquivalenceClasses< ElemTy > Class Template Reference

#include <EquivalenceClasses.h>

Inheritance diagram for llvm::EquivalenceClasses< ElemTy >:

Inheritance graph
[legend]
Collaboration diagram for llvm::EquivalenceClasses< ElemTy >:

Collaboration graph
[legend]
List of all members.

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 EquivalenceClassesoperator= (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

Detailed Description

template<class ElemTy>
class llvm::EquivalenceClasses< ElemTy >

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient operations: insert an element into a class of its own, union two classes, and find the class for a given element. In addition to these modification methods, it is possible to iterate over all of the equivalence classes and all of the elements in a class.

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.


Member Typedef Documentation

template<class ElemTy>
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.


Constructor & Destructor Documentation

template<class ElemTy>
llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses (  )  [inline]

Definition at line 115 of file EquivalenceClasses.h.

template<class ElemTy>
llvm::EquivalenceClasses< ElemTy >::EquivalenceClasses ( const EquivalenceClasses< ElemTy > &  RHS  )  [inline]

Definition at line 116 of file EquivalenceClasses.h.


Member Function Documentation

template<class ElemTy>
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().

template<class ElemTy>
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=().

template<class ElemTy>
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=().

template<class ElemTy>
bool llvm::EquivalenceClasses< ElemTy >::empty (  )  const [inline]

Definition at line 141 of file EquivalenceClasses.h.

template<class ElemTy>
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=().

template<class ElemTy>
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().

template<class ElemTy>
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().

template<class ElemTy>
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.

template<class ElemTy>
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.

template<class ElemTy>
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.

template<class ElemTy>
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().

template<class ElemTy>
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().

template<class ElemTy>
member_iterator llvm::EquivalenceClasses< ElemTy >::findLeader ( const ElemTy &  V  )  const [inline]

Definition at line 206 of file EquivalenceClasses.h.

template<class ElemTy>
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().

template<class ElemTy>
member_iterator llvm::EquivalenceClasses< ElemTy >::unionSets ( member_iterator  L1,
member_iterator  L2 
) [inline]

Definition at line 217 of file EquivalenceClasses.h.


The documentation for this class was generated from the following file: