LLVM 19.0.0git
Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Friends | List of all members
llvm::SmallPtrSetImplBase Class Reference

SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything. More...

#include "llvm/ADT/SmallPtrSet.h"

Inherits llvm::DebugEpochBase.

Inherited by llvm::SmallPtrSetImpl< BasicBlock * >, llvm::SmallPtrSetImpl< const BasicBlock * >, llvm::SmallPtrSetImpl< const BasicBlockT * >, llvm::SmallPtrSetImpl< const MachineBasicBlock * >, llvm::SmallPtrSetImpl< typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * >::NodeRef >, llvm::SmallPtrSetImpl< PointeeType * >, llvm::SmallPtrSetImpl< typename GraphTraits< GraphT >::NodeRef >, llvm::SmallPtrSetImpl< typename GraphTraits< T >::NodeRef >, llvm::SmallPtrSetImpl< NodeRef >, llvm::SmallPtrSetImpl< const MDNode * >, llvm::SmallPtrSetImpl< Instruction * >, llvm::SmallPtrSetImpl< llvm::Value * >, llvm::SmallPtrSetImpl< llvm::MachineBasicBlock * >, llvm::SmallPtrSetImpl< llvm::LiveRange * >, llvm::SmallPtrSetImpl< const llvm::AllocaInst * >, llvm::SmallPtrSetImpl< CallBase * >, llvm::SmallPtrSetImpl< AssumeInst * >, llvm::SmallPtrSetImpl< const MachineInstr * >, llvm::SmallPtrSetImpl< const llvm::GlobalVariable * >, llvm::SmallPtrSetImpl< llvm::BasicBlock * >, llvm::SmallPtrSetImpl< const llvm::Value * >, llvm::SmallPtrSetImpl< const llvm::MachineBasicBlock * >, llvm::SmallPtrSetImpl< llvm::LazyCallGraph::RefSCC * >, llvm::SmallPtrSetImpl< llvm::LazyCallGraph::SCC * >, llvm::SmallPtrSetImpl< llvm::Function * >, llvm::SmallPtrSetImpl< llvm::GlobalObject * >, llvm::SmallPtrSetImpl< const llvm::MDNode * >, llvm::SmallPtrSetImpl< llvm::Instruction * >, llvm::SmallPtrSetImpl< llvm::Use * >, llvm::SmallPtrSetImpl< llvm::GlobalVariable * >, llvm::SmallPtrSetImpl< llvm::Constant * >, llvm::SmallPtrSetImpl< llvm::GlobalValue * >, llvm::SmallPtrSetImpl< const llvm::BasicBlock * >, llvm::SmallPtrSetImpl< const llvm::DbgDeclareInst * >, llvm::SmallPtrSetImpl< const llvm::DPValue * >, llvm::SmallPtrSetImpl< llvm::MachineInstr * >, llvm::SmallPtrSetImpl< const BlockT * >, llvm::SmallPtrSetImpl< const CycleT * >, llvm::SmallPtrSetImpl< const InstructionT * >, llvm::SmallPtrSetImpl< const llvm::GlobalValue * >, llvm::SmallPtrSetImpl< NodeTy * >, llvm::SmallPtrSetImpl< const Loop * >, llvm::SmallPtrSetImpl< const llvm::Function * >, llvm::SmallPtrSetImpl< llvm::InterleaveGroup< llvm::Instruction > * >, llvm::SmallPtrSetImpl< llvm::Module * >, llvm::SmallPtrSetImpl< const llvm::VNInfo * >, llvm::SmallPtrSetImpl< llvm::PHINode * >, llvm::SmallPtrSetImpl< llvm::Type * >, llvm::SmallPtrSetImpl< const PHINode * >, llvm::SmallPtrSetImpl< const llvm::Instruction * >, llvm::SmallPtrSetImpl< const llvm::MCSymbol * >, llvm::SmallPtrSetImpl< Module * >, llvm::SmallPtrSetImpl< const llvm::LazyCallGraph::Node * >, llvm::SmallPtrSetImpl< llvm::MachineRegisterInfo::Delegate * >, llvm::SmallPtrSetImpl< const Value * >, llvm::SmallPtrSetImpl< void * >, llvm::SmallPtrSetImpl< llvm::AnalysisKey * >, llvm::SmallPtrSetImpl< const llvm::SCEV * >, llvm::SmallPtrSetImpl< const llvm::Type * >, llvm::SmallPtrSetImpl< const llvm::PHINode * >, llvm::SmallPtrSetImpl< const llvm::SCEVAddRecExpr * >, llvm::SmallPtrSetImpl< const llvm::SCEVPredicate * >, llvm::SmallPtrSetImpl< llvm::cl::SubCommand * >, llvm::SmallPtrSetImpl< Value * >, and llvm::SmallPtrSetImpl< PtrType >.

Public Types

using size_type = unsigned
 

Public Member Functions

SmallPtrSetImplBaseoperator= (const SmallPtrSetImplBase &)=delete
 
bool empty () const
 
size_type size () const
 
void clear ()
 
- Public Member Functions inherited from llvm::DebugEpochBase
void incrementEpoch ()
 

Protected Member Functions

 SmallPtrSetImplBase (const void **SmallStorage, const SmallPtrSetImplBase &that)
 
 SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that)
 
 SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize)
 
 ~SmallPtrSetImplBase ()
 
const void ** EndPointer () const
 
std::pair< const void *const *, boolinsert_imp (const void *Ptr)
 insert_imp - This returns true if the pointer was new to the set, false if it was already in the set.
 
bool erase_imp (const void *Ptr)
 erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false.
 
const void *constfind_imp (const void *Ptr) const
 Returns the raw pointer needed to construct an iterator.
 
void swap (SmallPtrSetImplBase &RHS)
 swap - Swaps the elements of two sets.
 
void CopyFrom (const SmallPtrSetImplBase &RHS)
 
void MoveFrom (unsigned SmallSize, SmallPtrSetImplBase &&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'.
 
const void ** CurArray
 CurArray - This is the current set of buckets.
 
unsigned CurArraySize
 CurArraySize - The allocated size of CurArray, always a power of two.
 
unsigned NumNonEmpty
 Number of elements in CurArray that contain a value or are a tombstone.
 
unsigned NumTombstones
 Number of tombstones in CurArray.
 

Friends

class SmallPtrSetIteratorImpl
 

Detailed Description

SmallPtrSetImplBase - 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 51 of file SmallPtrSet.h.

Member Typedef Documentation

◆ size_type

Definition at line 89 of file SmallPtrSet.h.

Constructor & Destructor Documentation

◆ SmallPtrSetImplBase() [1/3]

SmallPtrSetImplBase::SmallPtrSetImplBase ( const void **  SmallStorage,
const SmallPtrSetImplBase that 
)
protected

Definition at line 121 of file SmallPtrSet.cpp.

References CurArray, CurArraySize, llvm::safe_malloc(), and SmallArray.

◆ SmallPtrSetImplBase() [2/3]

SmallPtrSetImplBase::SmallPtrSetImplBase ( const void **  SmallStorage,
unsigned  SmallSize,
SmallPtrSetImplBase &&  that 
)
protected

Definition at line 137 of file SmallPtrSet.cpp.

References SmallArray.

◆ SmallPtrSetImplBase() [3/3]

llvm::SmallPtrSetImplBase::SmallPtrSetImplBase ( const void **  SmallStorage,
unsigned  SmallSize 
)
inlineexplicitprotected

Definition at line 76 of file SmallPtrSet.h.

References assert().

◆ ~SmallPtrSetImplBase()

llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase ( )
inlineprotected

Definition at line 83 of file SmallPtrSet.h.

References CurArray.

Member Function Documentation

◆ clear()

void llvm::SmallPtrSetImplBase::clear ( )
inline

◆ CopyFrom()

void SmallPtrSetImplBase::CopyFrom ( const SmallPtrSetImplBase RHS)
protected

◆ empty()

bool llvm::SmallPtrSetImplBase::empty ( ) const
inline

◆ EndPointer()

const void ** llvm::SmallPtrSetImplBase::EndPointer ( ) const
inlineprotected

◆ erase_imp()

bool llvm::SmallPtrSetImplBase::erase_imp ( const void *  Ptr)
inlineprotected

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 163 of file SmallPtrSet.h.

References assert(), EndPointer(), find_imp(), getTombstoneMarker(), NumTombstones, P, and Ptr.

Referenced by llvm::SmallPtrSetImpl< PtrType >::erase().

◆ find_imp()

const void *const * llvm::SmallPtrSetImplBase::find_imp ( const void *  Ptr) const
inlineprotected

Returns the raw pointer needed to construct an iterator.

If element not found, this will be EndPointer. Otherwise, it will be a pointer to the slot which stores Ptr;

Definition at line 178 of file SmallPtrSet.h.

References E, EndPointer(), NumNonEmpty, Ptr, and SmallArray.

Referenced by llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), erase_imp(), and llvm::SmallPtrSetImpl< PtrType >::find().

◆ getEmptyMarker()

static void * llvm::SmallPtrSetImplBase::getEmptyMarker ( )
inlinestaticprotected

◆ getTombstoneMarker()

static void * llvm::SmallPtrSetImplBase::getTombstoneMarker ( )
inlinestaticprotected

◆ insert_imp()

std::pair< const void *const *, bool > llvm::SmallPtrSetImplBase::insert_imp ( const void *  Ptr)
inlineprotected

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 127 of file SmallPtrSet.h.

References CurArraySize, E, getTombstoneMarker(), llvm::DebugEpochBase::incrementEpoch(), NumNonEmpty, NumTombstones, Ptr, and SmallArray.

Referenced by llvm::SmallPtrSetImpl< PtrType >::insert().

◆ MoveFrom()

void SmallPtrSetImplBase::MoveFrom ( unsigned  SmallSize,
SmallPtrSetImplBase &&  RHS 
)
protected

Definition at line 181 of file SmallPtrSet.cpp.

References CurArray, and RHS.

Referenced by llvm::SmallPtrSet< PtrType, SmallSize >::operator=().

◆ operator=()

SmallPtrSetImplBase & llvm::SmallPtrSetImplBase::operator= ( const SmallPtrSetImplBase )
delete

◆ size()

size_type llvm::SmallPtrSetImplBase::size ( ) const
inline

◆ swap()

void SmallPtrSetImplBase::swap ( SmallPtrSetImplBase RHS)
protected

swap - Swaps the elements of two sets.

Note: This method assumes that both sets have the same small size.

Definition at line 213 of file SmallPtrSet.cpp.

References assert(), CurArray, CurArraySize, NumTombstones, RHS, SmallArray, and std::swap().

Referenced by llvm::SmallPtrSet< PtrType, SmallSize >::swap().

Friends And Related Function Documentation

◆ SmallPtrSetIteratorImpl

friend class SmallPtrSetIteratorImpl
friend

Definition at line 52 of file SmallPtrSet.h.

Member Data Documentation

◆ CurArray

const void** llvm::SmallPtrSetImplBase::CurArray
protected

CurArray - This is the current set of buckets.

If equal to SmallArray, then the set is in 'small mode'.

Definition at line 59 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetImpl< PtrType >::begin(), clear(), CopyFrom(), EndPointer(), MoveFrom(), SmallPtrSetImplBase(), swap(), and ~SmallPtrSetImplBase().

◆ CurArraySize

unsigned llvm::SmallPtrSetImplBase::CurArraySize
protected

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

Definition at line 61 of file SmallPtrSet.h.

Referenced by clear(), CopyFrom(), EndPointer(), insert_imp(), SmallPtrSetImplBase(), and swap().

◆ NumNonEmpty

unsigned llvm::SmallPtrSetImplBase::NumNonEmpty
protected

Number of elements in CurArray that contain a value or are a tombstone.

If small, all these elements are at the beginning of CurArray and the rest is uninitialized.

Definition at line 66 of file SmallPtrSet.h.

Referenced by clear(), EndPointer(), find_imp(), insert_imp(), and size().

◆ NumTombstones

unsigned llvm::SmallPtrSetImplBase::NumTombstones
protected

Number of tombstones in CurArray.

Definition at line 68 of file SmallPtrSet.h.

Referenced by clear(), erase_imp(), insert_imp(), size(), and swap().

◆ SmallArray

const void** llvm::SmallPtrSetImplBase::SmallArray
protected

SmallArray - Points to a fixed size set of buckets, used in 'small mode'.

Definition at line 56 of file SmallPtrSet.h.

Referenced by CopyFrom(), find_imp(), insert_imp(), SmallPtrSetImplBase(), and swap().


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