FoldingSetBase - Implements the folding set functionality. More...

#include "llvm/ADT/FoldingSet.h"

Inheritance diagram for llvm::FoldingSetBase:

[legend]

Collaboration diagram for llvm::FoldingSetBase:

Classes
class	Node
	Node - This class is used to maintain the singly linked bucket list in a folding set. More...

Public Member Functions
void	clear ()
	clear - Remove all nodes from the folding set. More...

unsigned	size () const
	size - Returns the number of nodes in the folding set. More...

bool	empty () const
	empty - Returns true if there are no nodes in the folding set. More...

void	reserve (unsigned EltCount)
	reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket operation. More...

unsigned	capacity ()
	capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is performed. More...

Protected Member Functions
	FoldingSetBase (unsigned Log2InitSize=6)

	FoldingSetBase (FoldingSetBase &&Arg)

FoldingSetBase &	operator= (FoldingSetBase &&RHS)

	~FoldingSetBase ()

virtual void	GetNodeProfile (Node *N, FoldingSetNodeID &ID) const =0
	GetNodeProfile - Instantiations of the FoldingSet template implement this function to gather data bits for the given node. More...

virtual bool	NodeEquals (Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const =0
	NodeEquals - Instantiations of the FoldingSet template implement this function to compare the given node with the given ID. More...

virtual unsigned	ComputeNodeHash (Node *N, FoldingSetNodeID &TempID) const =0
	ComputeNodeHash - Instantiations of the FoldingSet template implement this function to compute a hash value for the given node. More...

bool	RemoveNode (Node *N)
	RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the node was not in the folding set. More...

Node *	GetOrInsertNode (Node *N)
	GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node, return it. More...

Node *	FindNodeOrInsertPos (const FoldingSetNodeID &ID, void *&InsertPos)
	FindNodeOrInsertPos - Look up the node specified by ID. More...

void	InsertNode (Node N, void InsertPos)
	InsertNode - Insert the specified node into the folding set, knowing that it is not already in the folding set. More...

Protected Attributes
void **	Buckets
	Buckets - Array of bucket chains. More...

unsigned	NumBuckets
	NumBuckets - Length of the Buckets array. Always a power of 2. More...

unsigned	NumNodes
	NumNodes - Number of nodes in the folding set. More...

Detailed Description

FoldingSetBase - 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 113 of file FoldingSet.h.

Constructor & Destructor Documentation

◆ FoldingSetBase() [1/2]

FoldingSetBase::FoldingSetBase ( unsigned Log2InitSize = 6 )

explicitprotected

Definition at line 229 of file FoldingSet.cpp.

References AllocateBuckets(), and assert().

◆ FoldingSetBase() [2/2]

FoldingSetBase::FoldingSetBase ( FoldingSetBase && Arg )

protected

Definition at line 237 of file FoldingSet.cpp.

References Arg.

◆ ~FoldingSetBase()

FoldingSetBase::~FoldingSetBase ( )

protected

Definition at line 255 of file FoldingSet.cpp.

References Buckets.

Member Function Documentation

◆ capacity()

unsigned llvm::FoldingSetBase::capacity ( )

inline

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

Definition at line 165 of file FoldingSet.h.

References ComputeNodeHash(), FindNodeOrInsertPos(), GetNodeProfile(), GetOrInsertNode(), InsertNode(), N, NodeEquals(), and RemoveNode().

Referenced by InsertNode(), and reserve().

◆ clear()

void FoldingSetBase::clear ( )

clear - Remove all nodes from the folding set.

Definition at line 259 of file FoldingSet.cpp.

References AllocateBuckets(), assert(), Buckets, llvm::FoldingSetNodeID::clear(), ComputeNodeHash(), GetBucketFor(), GetNextPtr(), InsertNode(), llvm::isPowerOf2_32(), llvm::Intrinsic::memset, NumBuckets, and NumNodes.

Referenced by llvm::FoldingSetVector< T, VectorT >::clear(), and llvm::FoldingSetBase::Node::SetNextInBucket().

◆ ComputeNodeHash()

virtual unsigned llvm::FoldingSetBase::ComputeNodeHash	(	Node *	N,
		FoldingSetNodeID &	TempID
	)		const

protectedpure virtual

ComputeNodeHash - Instantiations of the FoldingSet template implement this function to compute a hash value for the given node.

Referenced by capacity(), clear(), and InsertNode().

◆ empty()

bool llvm::FoldingSetBase::empty ( ) const

inline

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

Definition at line 156 of file FoldingSet.h.

References reserve().

Referenced by llvm::FoldingSetVector< T, VectorT >::empty().

◆ FindNodeOrInsertPos()

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

protected

FindNodeOrInsertPos - 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 322 of file FoldingSet.cpp.

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

Referenced by capacity(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::FindNodeOrInsertPos(), and GetOrInsertNode().

◆ GetNodeProfile()

virtual void llvm::FoldingSetBase::GetNodeProfile	(	Node *	N,
		FoldingSetNodeID &	ID
	)		const

protectedpure virtual

GetNodeProfile - Instantiations of the FoldingSet template implement this function to gather data bits for the given node.

Referenced by capacity(), and GetOrInsertNode().

◆ GetOrInsertNode()

FoldingSetBase::Node * FoldingSetBase::GetOrInsertNode ( FoldingSetBase::Node * N )

protected

GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node, return it.

Otherwise, insert 'N' and return it instead.

Otherwise, insert 'N' and it instead.

Definition at line 417 of file FoldingSet.cpp.

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

Referenced by capacity(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::GetOrInsertNode(), and llvm::FoldingSetImpl< llvm::DIEAbbrev >::InsertNode().

◆ InsertNode()

void FoldingSetBase::InsertNode	(	Node *	N,
		void *	InsertPos
	)

protected

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

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

InsertPos must be obtained from FindNodeOrInsertPos.

The insert position is actually a bucket pointer.

Definition at line 347 of file FoldingSet.cpp.

References assert(), Buckets, capacity(), ComputeNodeHash(), GetBucketFor(), llvm::FoldingSetBase::Node::getNextInBucket(), N, NumBuckets, NumNodes, and llvm::FoldingSetBase::Node::SetNextInBucket().

Referenced by capacity(), clear(), GetOrInsertNode(), and llvm::FoldingSetImpl< llvm::DIEAbbrev >::InsertNode().

◆ NodeEquals()

virtual bool llvm::FoldingSetBase::NodeEquals	(	Node *	N,
		const FoldingSetNodeID &	ID,
		unsigned	IDHash,
		FoldingSetNodeID &	TempID
	)		const

protectedpure virtual

NodeEquals - Instantiations of the FoldingSet template implement this function to compare the given node with the given ID.

Referenced by capacity(), and FindNodeOrInsertPos().

◆ operator=()

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

protected

Definition at line 244 of file FoldingSet.cpp.

References Buckets, NumBuckets, and NumNodes.

Referenced by llvm::FoldingSet< llvm::DIEAbbrev >::FoldingSet(), and llvm::FoldingSetImpl< llvm::DIEAbbrev >::FoldingSetImpl().

◆ RemoveNode()

bool FoldingSetBase::RemoveNode ( Node * N )

protected

RemoveNode - 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 376 of file FoldingSet.cpp.

References GetBucketPtr(), llvm::FoldingSetBase::Node::getNextInBucket(), GetNextPtr(), NumNodes, and llvm::FoldingSetBase::Node::SetNextInBucket().

Referenced by capacity(), and llvm::FoldingSetImpl< llvm::DIEAbbrev >::RemoveNode().

◆ reserve()

void FoldingSetBase::reserve ( unsigned EltCount )

reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket operation.

reserve is permitted to allocate more space than requested by EltCount.

Definition at line 309 of file FoldingSet.cpp.

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

Referenced by empty().

◆ size()

unsigned llvm::FoldingSetBase::size ( ) const

inline

size - Returns the number of nodes in the folding set.

Definition at line 153 of file FoldingSet.h.

References NumNodes.

Referenced by llvm::FoldingSetVector< T, VectorT >::size().

Member Data Documentation

◆ Buckets

void** llvm::FoldingSetBase::Buckets

protected

Buckets - Array of bucket chains.

Definition at line 118 of file FoldingSet.h.

Referenced by llvm::FoldingSetImpl< llvm::DIEAbbrev >::begin(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::bucket_begin(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::bucket_end(), clear(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::end(), FindNodeOrInsertPos(), InsertNode(), operator=(), and ~FoldingSetBase().

◆ NumBuckets

unsigned llvm::FoldingSetBase::NumBuckets

protected

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

Definition at line 121 of file FoldingSet.h.

Referenced by llvm::FoldingSetImpl< llvm::DIEAbbrev >::bucket_begin(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::bucket_end(), clear(), llvm::FoldingSetImpl< llvm::DIEAbbrev >::end(), FindNodeOrInsertPos(), InsertNode(), and operator=().

◆ NumNodes

unsigned llvm::FoldingSetBase::NumNodes

protected

NumNodes - Number of nodes in the folding set.

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

Definition at line 125 of file FoldingSet.h.

Referenced by clear(), 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()

◆ ComputeNodeHash()

◆ empty()

◆ FindNodeOrInsertPos()

◆ GetNodeProfile()

◆ GetOrInsertNode()

◆ InsertNode()

◆ NodeEquals()

◆ operator=()

◆ RemoveNode()

◆ reserve()

◆ size()

Member Data Documentation

◆ Buckets

◆ NumBuckets

◆ NumNodes