Implements the folding set functionality. More...

#include "llvm/ADT/FoldingSet.h"

Inheritance diagram for llvm::FoldingSetBase:

Classes
struct	FoldingSetInfo
	Functions provided by the derived class to compute folding properties. More...
class	Node
	This class is used to maintain the singly linked bucket list in a folding set. More...

Public Member Functions
LLVM_ABI void	clear ()
	Remove all nodes from the folding set.
unsigned	size () const
	Returns the number of nodes in the folding set.
bool	empty () const
	Returns true if there are no nodes in the folding set.
unsigned	capacity () const
	Returns the number of nodes permitted in the folding set before a rebucket operation is performed.
Public Member Functions inherited from llvm::DebugEpochBase
void	incrementEpoch ()

Protected Member Functions
LLVM_ABI	FoldingSetBase (unsigned Log2InitSize)
LLVM_ABI	FoldingSetBase (FoldingSetBase &&Arg)
LLVM_ABI FoldingSetBase &	operator= (FoldingSetBase &&RHS)
LLVM_ABI	~FoldingSetBase ()
LLVM_ABI void	reserve (unsigned EltCount, const FoldingSetInfo &Info)
	Grow the number of buckets so that we can hold at least `EltCount` nodes before rebucketing.
LLVM_ABI bool	RemoveNode (Node *N)
	Remove a node from the folding set, returning true if one was removed or false if the node was not in the folding set.
LLVM_ABI Node *	GetOrInsertNode (Node *N, const FoldingSetInfo &Info)
	If there is an existing node exactly equal to the node `N`, return it.
LLVM_ABI Node *	FindNodeOrInsertPos (const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info)
	Look up the node specified by ID.
LLVM_ABI void	InsertNode (Node N, void InsertPos, const FoldingSetInfo &Info)
	Insert the specified node into the folding set, knowing that it is not already in the folding set.

Protected Attributes
void **	Buckets
	Array of bucket chains.
unsigned	NumBuckets
	Length of the Buckets array. Always a power of 2.
unsigned	NumNodes
	Number of nodes in the folding set.

Detailed Description

Implements the folding set functionality.

The main structure is an array of buckets. Each bucket is indexed by the hash of the nodes it contains. The bucket itself points to the nodes contained in the bucket via a singly linked list. The last node in the list points back to the bucket to facilitate node removal.

Definition at line 299 of file FoldingSet.h.

Constructor & Destructor Documentation

◆ FoldingSetBase() [1/2]

FoldingSetBase::FoldingSetBase ( unsigned Log2InitSize )

explicitprotected

Definition at line 178 of file FoldingSet.cpp.

References AllocateBuckets(), assert(), Buckets, NumBuckets, and NumNodes.

Referenced by FoldingSetBase(), and operator=().

◆ FoldingSetBase() [2/2]

FoldingSetBase::FoldingSetBase ( FoldingSetBase && Arg )

protected

Definition at line 186 of file FoldingSet.cpp.

References Buckets, FoldingSetBase(), NumBuckets, and NumNodes.

◆ ~FoldingSetBase()

FoldingSetBase::~FoldingSetBase ( )

protected

Definition at line 207 of file FoldingSet.cpp.

References Buckets.

Member Function Documentation

◆ capacity()

unsigned llvm::FoldingSetBase::capacity ( ) const

inline

Returns the number of nodes permitted in the folding set before a rebucket operation is performed.

Definition at line 344 of file FoldingSet.h.

References NumBuckets.

Referenced by InsertNode(), and reserve().

◆ clear()

void FoldingSetBase::clear ( )

Remove all nodes from the folding set.

Definition at line 209 of file FoldingSet.cpp.

References Buckets, llvm::DebugEpochBase::incrementEpoch(), NumBuckets, and NumNodes.

◆ empty()

bool llvm::FoldingSetBase::empty ( ) const

inlinenodiscard

Returns true if there are no nodes in the folding set.

Definition at line 340 of file FoldingSet.h.

References NumNodes.

◆ FindNodeOrInsertPos()

FoldingSetBase::Node * FoldingSetBase::FindNodeOrInsertPos	(	const FoldingSetNodeID &	ID,
		void *&	InsertPos,
		const FoldingSetInfo &	Info )

protected

Look up the node specified by ID.

If it exists, return it. If not, return the insertion token that will make insertion faster.

Definition at line 260 of file FoldingSet.cpp.

References Buckets, llvm::FoldingSetNodeID::clear(), GetBucketFor(), GetNextPtr(), and NumBuckets.

Referenced by llvm::FoldingSetImpl< T, Trait >< ListTy >::FindNodeOrInsertPos(), and GetOrInsertNode().

◆ GetOrInsertNode()

FoldingSetBase::Node * FoldingSetBase::GetOrInsertNode	(	Node *	N,
		const FoldingSetInfo &	Info )

protected

If there is an existing node exactly equal to the node N, return it.

Otherwise, insert N and return it instead.

Definition at line 353 of file FoldingSet.cpp.

References FindNodeOrInsertPos(), InsertNode(), and N.

Referenced by llvm::FoldingSetImpl< T, Trait >< ListTy >::GetOrInsertNode().

◆ InsertNode()

void FoldingSetBase::InsertNode	(	Node *	N,
		void *	InsertPos,
		const FoldingSetInfo &	Info )

protected

Insert the specified node into the folding set, knowing that it is not already in the folding set.

InsertPos must be obtained from FindNodeOrInsertPos.

The insert position is actually a bucket pointer.

Definition at line 282 of file FoldingSet.cpp.

References assert(), Buckets, capacity(), GetBucketFor(), llvm::DebugEpochBase::incrementEpoch(), N, llvm::Next, NumBuckets, and NumNodes.

Referenced by GetOrInsertNode(), and llvm::FoldingSetImpl< T, Trait >< ListTy >::InsertNode().

◆ operator=()

FoldingSetBase & FoldingSetBase::operator= ( FoldingSetBase && RHS )

protected

Definition at line 194 of file FoldingSet.cpp.

References Buckets, FoldingSetBase(), llvm::DebugEpochBase::incrementEpoch(), NumBuckets, and NumNodes.

◆ RemoveNode()

bool FoldingSetBase::RemoveNode ( Node * N )

protected

Remove a node from the folding set, returning true if one was removed or false if the node was not in the folding set.

Definition at line 312 of file FoldingSet.cpp.

References GetBucketPtr(), GetNextPtr(), llvm::DebugEpochBase::incrementEpoch(), N, and NumNodes.

Referenced by llvm::FoldingSetImpl< T, Trait >< ListTy >::RemoveNode().

◆ reserve()

void FoldingSetBase::reserve	(	unsigned	EltCount,
		const FoldingSetInfo &	Info )

protected

Grow the number of buckets so that we can hold at least EltCount nodes before rebucketing.

May allocate more space than requested.

Definition at line 251 of file FoldingSet.cpp.

References llvm::bit_floor(), and capacity().

Referenced by llvm::FoldingSetImpl< T, Trait >< ListTy >::reserve().

◆ size()

unsigned llvm::FoldingSetBase::size ( ) const

inline

Returns the number of nodes in the folding set.

Definition at line 337 of file FoldingSet.h.

References NumNodes.

Member Data Documentation

◆ Buckets

void** llvm::FoldingSetBase::Buckets

protected

Array of bucket chains.

Definition at line 302 of file FoldingSet.h.

Referenced by llvm::FoldingSetImpl< T, Trait >< ListTy >::begin(), llvm::FoldingSetImpl< T, Trait >< ListTy >::begin(), clear(), llvm::FoldingSetImpl< T, Trait >< ListTy >::end(), llvm::FoldingSetImpl< T, Trait >< ListTy >::end(), FindNodeOrInsertPos(), FoldingSetBase(), FoldingSetBase(), InsertNode(), operator=(), and ~FoldingSetBase().

◆ NumBuckets

unsigned llvm::FoldingSetBase::NumBuckets

protected

Length of the Buckets array. Always a power of 2.

Definition at line 305 of file FoldingSet.h.

Referenced by capacity(), clear(), llvm::FoldingSetImpl< T, Trait >< ListTy >::end(), llvm::FoldingSetImpl< T, Trait >< ListTy >::end(), FindNodeOrInsertPos(), FoldingSetBase(), FoldingSetBase(), InsertNode(), and operator=().

◆ NumNodes

unsigned llvm::FoldingSetBase::NumNodes

protected

Number of nodes in the folding set.

Growth occurs when NumNodes is greater than twice the number of buckets.

Definition at line 309 of file FoldingSet.h.

Referenced by clear(), empty(), FoldingSetBase(), FoldingSetBase(), InsertNode(), operator=(), RemoveNode(), and size().

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

include/llvm/ADT/FoldingSet.h
lib/Support/FoldingSet.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ FoldingSetBase() [1/2]

◆ FoldingSetBase() [2/2]

◆ ~FoldingSetBase()

Member Function Documentation

◆ capacity()

◆ clear()

◆ empty()

◆ FindNodeOrInsertPos()

◆ GetOrInsertNode()

◆ InsertNode()

◆ operator=()

◆ RemoveNode()

◆ reserve()

◆ size()

Member Data Documentation

◆ Buckets

◆ NumBuckets

◆ NumNodes