class SmallPtrSetImplBase

Declaration

class SmallPtrSetImplBase : public DebugEpochBase { /* full declaration omitted */ };

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.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:50

Inherits from: DebugEpochBase

Member Variables

protected const void** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
protected const void** CurArray
CurArray - This is the current set of buckets. If equal to SmallArray, then the set is in 'small mode'.
protected unsigned int CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
protected unsigned int NumNonEmpty
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.
protected unsigned int NumTombstones
Number of tombstones in CurArray.

Method Overview

  • protected void CopyFrom(const llvm::SmallPtrSetImplBase & RHS)
  • private void CopyHelper(const llvm::SmallPtrSetImplBase & RHS)
  • protected const void ** EndPointer() const
  • private const void *const * FindBucketFor(const void * Ptr) const
  • private void Grow(unsigned int NewSize)
  • protected void MoveFrom(unsigned int SmallSize, llvm::SmallPtrSetImplBase && RHS)
  • private void MoveHelper(unsigned int SmallSize, llvm::SmallPtrSetImplBase && RHS)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, unsigned int SmallSize, llvm::SmallPtrSetImplBase && that)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, unsigned int SmallSize)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, const llvm::SmallPtrSetImplBase & that)
  • public void clear()
  • public bool empty() const
  • protected bool erase_imp(const void * Ptr)
  • protected const void *const * find_imp(const void * Ptr) const
  • protected static void * getEmptyMarker()
  • protected static void * getTombstoneMarker()
  • protected std::pair<const void *const *, bool> insert_imp(const void * Ptr)
  • private std::pair<const void *const *, bool> insert_imp_big(const void * Ptr)
  • private bool isSmall() const
  • private void shrink_and_clear()
  • public llvm::SmallPtrSetImplBase::size_type size() const
  • protected void swap(llvm::SmallPtrSetImplBase & RHS)
  • protected ~SmallPtrSetImplBase()

Inherited from DebugEpochBase:

Methods

void CopyFrom(
    const llvm::SmallPtrSetImplBase& RHS)

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:210

Parameters

const llvm::SmallPtrSetImplBase& RHS

void CopyHelper(
    const llvm::SmallPtrSetImplBase& RHS)

Description

Code shared by CopyFrom() and copy constructor.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:217

Parameters

const llvm::SmallPtrSetImplBase& RHS

const void** EndPointer() const

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:119

const void* const* FindBucketFor(
    const void* Ptr) const

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:199

Parameters

const void* Ptr

void Grow(unsigned int NewSize)

Description

Grow - Allocate a larger backing store for the buckets and move it over.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:203

Parameters

unsigned int NewSize

void MoveFrom(unsigned int SmallSize,
              llvm::SmallPtrSetImplBase&& RHS)

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:211

Parameters

unsigned int SmallSize
llvm::SmallPtrSetImplBase&& RHS

void MoveHelper(unsigned int SmallSize,
                llvm::SmallPtrSetImplBase&& RHS)

Description

Code shared by MoveFrom() and move constructor.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:215

Parameters

unsigned int SmallSize
llvm::SmallPtrSetImplBase&& RHS

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

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:72

Parameters

const void** SmallStorage
unsigned int SmallSize
llvm::SmallPtrSetImplBase&& that

SmallPtrSetImplBase(const void** SmallStorage,
                    unsigned int SmallSize)

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:75

Parameters

const void** SmallStorage
unsigned int SmallSize

SmallPtrSetImplBase(
    const void** SmallStorage,
    const llvm::SmallPtrSetImplBase& that)

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:70

Parameters

const void** SmallStorage
const llvm::SmallPtrSetImplBase& that

void clear()

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:95

bool empty() const

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:92

bool erase_imp(const void* Ptr)

Description

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.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:162

Parameters

const void* Ptr

const void* const* find_imp(const void* Ptr) const

Description

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;

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:177

Parameters

const void* Ptr

static void* getEmptyMarker()

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:113

static void* getTombstoneMarker()

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:111

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

Description

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.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:126

Parameters

const void* Ptr

std::pair<const void* const*, bool>
insert_imp_big(const void* Ptr)

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:197

Parameters

const void* Ptr

bool isSmall() const

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:195

void shrink_and_clear()

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:200

llvm::SmallPtrSetImplBase::size_type size() const

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:93

void swap(llvm::SmallPtrSetImplBase& RHS)

Description

swap - Swaps the elements of two sets. Note: This method assumes that both sets have the same small size.

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:208

Parameters

llvm::SmallPtrSetImplBase& RHS

~SmallPtrSetImplBase()

Declared at: llvm/include/llvm/ADT/SmallPtrSet.h:82