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:49

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)
  • protected const void ** EndPointer() const
  • protected void MoveFrom(unsigned int SmallSize, llvm::SmallPtrSetImplBase && RHS)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, const llvm::SmallPtrSetImplBase & that)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, unsigned int SmallSize, llvm::SmallPtrSetImplBase && that)
  • protected SmallPtrSetImplBase(const void ** SmallStorage, unsigned int SmallSize)
  • 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)
  • 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:209

Parameters

const llvm::SmallPtrSetImplBase& RHS

const void** EndPointer() const

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

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

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

Parameters

unsigned int SmallSize
llvm::SmallPtrSetImplBase&& RHS

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

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

Parameters

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

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

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

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:74

Parameters

const void** SmallStorage
unsigned int SmallSize

void clear()

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

bool empty() const

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

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:161

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:176

Parameters

const void* Ptr

static void* getEmptyMarker()

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

static void* getTombstoneMarker()

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

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:125

Parameters

const void* Ptr

llvm::SmallPtrSetImplBase::size_type size() const

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

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:207

Parameters

llvm::SmallPtrSetImplBase& RHS

~SmallPtrSetImplBase()

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