#include <SmallPtrSet.h>

Inheritance diagram for llvm::SmallPtrSetImpl:

Collaboration diagram for llvm::SmallPtrSetImpl:

Public Member Functions
bool LLVM_ATTRIBUTE_UNUSED_RESULT	empty () const

unsigned	size () const

void	clear ()

Protected Member Functions
	SmallPtrSetImpl (const void **SmallStorage, const SmallPtrSetImpl &that)

	SmallPtrSetImpl (const void **SmallStorage, unsigned SmallSize)

	~SmallPtrSetImpl ()

bool	insert_imp (const void *Ptr)

bool	erase_imp (const void *Ptr)

bool	count_imp (const void *Ptr) const

void	swap (SmallPtrSetImpl &RHS)

void	CopyFrom (const SmallPtrSetImpl &RHS)

Static Protected Member Functions
static void *	getTombstoneMarker ()

static void *	getEmptyMarker ()

Protected Attributes
const void **	SmallArray
	SmallArray - Points to a fixed size set of buckets, used in 'small mode'. More...

const void **	CurArray

unsigned	CurArraySize
	CurArraySize - The allocated size of CurArray, always a power of two. More...

unsigned	NumElements

unsigned	NumTombstones

Friends
class	SmallPtrSetIteratorImpl

Detailed Description

SmallPtrSetImpl - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one for small and one for large sets.

Small sets use an array of pointers allocated in the SmallPtrSet object, which is treated as a simple array of pointers. When a pointer is added to the set, the array is scanned to see if the element already exists, if not the element is 'pushed back' onto the array. If we run out of space in the array, we grow into the 'large set' case. SmallSet should be used when the sets are often small. In this case, no memory allocation is used, and only light-weight and cache-efficient scanning is used.

Large sets use a classic exponentially-probed hash table. Empty buckets are represented with an illegal pointer value (-1) to allow null pointers to be inserted. Tombstones are represented with another illegal pointer value (-2), to allow deletion. The hash table is resized when the table is 3/4 or more. When this happens, the table is doubled in size.

Definition at line 48 of file SmallPtrSet.h.

Constructor & Destructor Documentation

SmallPtrSetImpl::SmallPtrSetImpl	(	const void **	SmallStorage,
		const SmallPtrSetImpl &	that
	)

protected

Definition at line 166 of file SmallPtrSet.cpp.

References CurArray, CurArraySize, llvm::LibFunc::malloc, llvm::Intrinsic::memcpy, NumElements, NumTombstones, and SmallArray.

llvm::SmallPtrSetImpl::SmallPtrSetImpl	(	const void **	SmallStorage,
		unsigned	SmallSize
	)

inlineexplicitprotected

Definition at line 65 of file SmallPtrSet.h.

References clear().

SmallPtrSetImpl::~SmallPtrSetImpl ( )

protected

Definition at line 275 of file SmallPtrSet.cpp.

References CurArray, and llvm::LibFunc::free.

Member Function Documentation

void llvm::SmallPtrSetImpl::clear ( )

inline

Definition at line 77 of file SmallPtrSet.h.

References CurArray, CurArraySize, llvm::Intrinsic::memset, NumElements, and NumTombstones.

Referenced by AllGlobalLoadUsesSimpleEnoughForHeapSRA(), llvm::LeakDetectorImpl< llvm::Value >::clear(), llvm::SCEVExpander::clearPostInc(), llvm::ObjectSizeOffsetEvaluator::compute(), ComputePostOrders(), llvm::LexicalScopes::getMachineBasicBlocks(), and SmallPtrSetImpl().

void SmallPtrSetImpl::CopyFrom ( const SmallPtrSetImpl & RHS )

protected

CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a different small size.

Definition at line 191 of file SmallPtrSet.cpp.

References CurArray, CurArraySize, llvm::LibFunc::free, llvm::LibFunc::malloc, llvm::Intrinsic::memcpy, NumElements, NumTombstones, llvm::LibFunc::realloc, SmallArray, and T.

Referenced by llvm::SmallPtrSet< const T *, 8 >::operator=().

bool llvm::SmallPtrSetImpl::count_imp ( const void * Ptr ) const

inlineprotected

Definition at line 108 of file SmallPtrSet.h.

References NumElements, and SmallArray.

Referenced by llvm::SmallPtrSet< const T *, 8 >::count().

bool LLVM_ATTRIBUTE_UNUSED_RESULT llvm::SmallPtrSetImpl::empty ( ) const

inline

Definition at line 74 of file SmallPtrSet.h.

References size().

Referenced by llvm::findPHICopyInsertPoint(), llvm::FoldBranchToCommonDest(), llvm::LeakDetectorImpl< llvm::Value >::hasGarbage(), llvm::SDNode::hasPredecessorHelper(), isProfitableChain(), llvm::SelectionDAG::MorphNodeTo(), llvm::MemoryDependenceAnalysis::removeInstruction(), and setUsedInitializer().

bool SmallPtrSetImpl::erase_imp ( const void * Ptr )

protected

erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false. This is hidden from the client so that the derived class can check that the right type of pointer is passed in.

Definition at line 74 of file SmallPtrSet.cpp.

References getEmptyMarker(), getTombstoneMarker(), NumElements, NumTombstones, and SmallArray.

Referenced by llvm::SmallPtrSet< const T *, 8 >::erase().

static void* llvm::SmallPtrSetImpl::getEmptyMarker ( )

inlinestaticprotected

Definition at line 91 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), and erase_imp().

static void* llvm::SmallPtrSetImpl::getTombstoneMarker ( )

inlinestaticprotected

Definition at line 90 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), erase_imp(), and insert_imp().

bool SmallPtrSetImpl::insert_imp ( const void * Ptr )

protected

insert_imp - This returns true if the pointer was new to the set, false if it was already in the set. This is hidden from the client so that the derived class can check that the right type of pointer is passed in.

Definition at line 37 of file SmallPtrSet.cpp.

References CurArraySize, getTombstoneMarker(), NumElements, NumTombstones, and SmallArray.

Referenced by llvm::SmallPtrSet< const T *, 8 >::insert().

unsigned llvm::SmallPtrSetImpl::size ( ) const

inline

Definition at line 75 of file SmallPtrSet.h.

References NumElements.

Referenced by DeadPHICycle(), empty(), llvm::CodeExtractor::extractCodeRegion(), llvm::findPHICopyInsertPoint(), FindPredecessorAutoreleaseWithSafePath(), FindPredecessorRetainWithSafePath(), llvm::MemoryDependenceAnalysis::getNonLocalCallDependency(), PHIsEqualValue(), and llvm::removeUnreachableBlocks().