LLVM 19.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::EquivalenceClasses< ElemTy, Compare > Class Template Reference

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. More...

#include "llvm/ADT/EquivalenceClasses.h"

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

Classes

class  member_iterator
 

Public Types

using iterator = typename std::set< ECValue, ECValueComparator >::const_iterator
 iterator* - Provides a way to iterate over all values in the set.
 

Public Member Functions

 EquivalenceClasses ()=default
 
 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
 findValue - Return an iterator to the specified value.
 
const ElemTy & getLeaderValue (const ElemTy &V) const
 getLeaderValue - Return the leader for the specified value that is in the set.
 
const ElemTy & getOrInsertLeaderValue (const ElemTy &V)
 getOrInsertLeaderValue - Return the leader for the specified value that is in the set.
 
unsigned getNumClasses () const
 getNumClasses - Return the number of equivalence classes in this set.
 
iterator insert (const ElemTy &Data)
 insert - Insert a new value into the union/find set, ignoring the request if the value already exists.
 
member_iterator findLeader (iterator I) const
 findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.
 
member_iterator findLeader (const ElemTy &V) const
 
member_iterator unionSets (const ElemTy &V1, const ElemTy &V2)
 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 (member_iterator L1, member_iterator L2)
 
bool isEquivalent (const ElemTy &V1, const ElemTy &V2) const
 

Detailed Description

template<class ElemTy, class Compare = std::less<ElemTy>>
class llvm::EquivalenceClasses< ElemTy, Compare >

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< or a comparator is provided).

Here is a simple example using integers:

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.
MI != EC.member_end(); ++MI) // Loop over members in this set.
cerr << *MI << " "; // Print member.
cerr << "\n"; // Finish set.
}
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
typename std::set< ECValue, ECValueComparator >::const_iterator iterator
iterator* - Provides a way to iterate over all values in the set.

This example prints: 4 5 1 2

Definition at line 60 of file EquivalenceClasses.h.

Member Typedef Documentation

◆ iterator

template<class ElemTy , class Compare = std::less<ElemTy>>
using llvm::EquivalenceClasses< ElemTy, Compare >::iterator = typename std::set<ECValue, ECValueComparator>::const_iterator

iterator* - Provides a way to iterate over all values in the set.

Definition at line 164 of file EquivalenceClasses.h.

Constructor & Destructor Documentation

◆ EquivalenceClasses() [1/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
llvm::EquivalenceClasses< ElemTy, Compare >::EquivalenceClasses ( )
default

◆ EquivalenceClasses() [2/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
llvm::EquivalenceClasses< ElemTy, Compare >::EquivalenceClasses ( const EquivalenceClasses< ElemTy, Compare > &  RHS)
inline

Member Function Documentation

◆ begin()

template<class ElemTy , class Compare = std::less<ElemTy>>
iterator llvm::EquivalenceClasses< ElemTy, Compare >::begin ( ) const
inline

◆ empty()

template<class ElemTy , class Compare = std::less<ElemTy>>
bool llvm::EquivalenceClasses< ElemTy, Compare >::empty ( ) const
inline

Definition at line 170 of file EquivalenceClasses.h.

◆ end()

template<class ElemTy , class Compare = std::less<ElemTy>>
iterator llvm::EquivalenceClasses< ElemTy, Compare >::end ( ) const
inline

◆ findLeader() [1/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::findLeader ( const ElemTy &  V) const
inline

◆ findLeader() [2/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::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 228 of file EquivalenceClasses.h.

References I, and llvm::EquivalenceClasses< ElemTy, Compare >::member_end().

Referenced by llvm::EquivalenceClasses< ElemTy, Compare >::findLeader(), llvm::EquivalenceClasses< ElemTy, Compare >::getLeaderValue(), llvm::EquivalenceClasses< ElemTy, Compare >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< ElemTy, Compare >::isEquivalent(), and llvm::EquivalenceClasses< ElemTy, Compare >::unionSets().

◆ findValue()

template<class ElemTy , class Compare = std::less<ElemTy>>
iterator llvm::EquivalenceClasses< ElemTy, Compare >::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 184 of file EquivalenceClasses.h.

Referenced by llvm::MemoryDepChecker::areDepsSafe().

◆ getLeaderValue()

template<class ElemTy , class Compare = std::less<ElemTy>>
const ElemTy & llvm::EquivalenceClasses< ElemTy, Compare >::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 191 of file EquivalenceClasses.h.

References assert(), llvm::EquivalenceClasses< ElemTy, Compare >::findLeader(), llvm::EquivalenceClasses< ElemTy, Compare >::member_end(), and MI.

Referenced by llvm::MemoryDepChecker::areDepsSafe().

◆ getNumClasses()

template<class ElemTy , class Compare = std::less<ElemTy>>
unsigned llvm::EquivalenceClasses< ElemTy, Compare >::getNumClasses ( ) const
inline

getNumClasses - Return the number of equivalence classes in this set.

Note that this is a linear time operation.

Definition at line 208 of file EquivalenceClasses.h.

References llvm::EquivalenceClasses< ElemTy, Compare >::begin(), E, llvm::EquivalenceClasses< ElemTy, Compare >::end(), I, and NC.

◆ getOrInsertLeaderValue()

template<class ElemTy , class Compare = std::less<ElemTy>>
const ElemTy & llvm::EquivalenceClasses< ElemTy, Compare >::getOrInsertLeaderValue ( const ElemTy &  V)
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 200 of file EquivalenceClasses.h.

References assert(), llvm::EquivalenceClasses< ElemTy, Compare >::findLeader(), llvm::EquivalenceClasses< ElemTy, Compare >::insert(), llvm::EquivalenceClasses< ElemTy, Compare >::member_end(), and MI.

Referenced by llvm::computeMinimumValueSizes().

◆ insert()

template<class ElemTy , class Compare = std::less<ElemTy>>
iterator llvm::EquivalenceClasses< ElemTy, Compare >::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 220 of file EquivalenceClasses.h.

References llvm::Data.

Referenced by llvm::EquivalenceClasses< ElemTy, Compare >::getOrInsertLeaderValue(), llvm::EquivalenceClasses< ElemTy, Compare >::operator=(), and llvm::EquivalenceClasses< ElemTy, Compare >::unionSets().

◆ isEquivalent()

template<class ElemTy , class Compare = std::less<ElemTy>>
bool llvm::EquivalenceClasses< ElemTy, Compare >::isEquivalent ( const ElemTy &  V1,
const ElemTy &  V2 
) const
inline

◆ member_begin()

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::member_begin ( iterator  I) const
inline

◆ member_end()

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::member_end ( ) const
inline

◆ operator=()

template<class ElemTy , class Compare = std::less<ElemTy>>
const EquivalenceClasses & llvm::EquivalenceClasses< ElemTy, Compare >::operator= ( const EquivalenceClasses< ElemTy, Compare > &  RHS)
inline

◆ unionSets() [1/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::unionSets ( const ElemTy &  V1,
const ElemTy &  V2 
)
inline

◆ unionSets() [2/2]

template<class ElemTy , class Compare = std::less<ElemTy>>
member_iterator llvm::EquivalenceClasses< ElemTy, Compare >::unionSets ( member_iterator  L1,
member_iterator  L2 
)
inline

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