WPILibC++  unspecified
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Pages
llvm::SmallPtrSetImplBase Class Reference

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

#include <SmallPtrSet.h>

Inheritance diagram for llvm::SmallPtrSetImplBase:
llvm::SmallPtrSetImpl< PtrType > llvm::SmallPtrSet< PtrType, SmallSize >

Public Types

typedef unsigned size_type
 

Public Member Functions

bool LLVM_ATTRIBUTE_UNUSED_RESULT empty () const
 
size_type size () const
 
void clear ()
 

Protected Member Functions

 SmallPtrSetImplBase (const void **SmallStorage, const SmallPtrSetImplBase &that)
 
 SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that)
 
 SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize)
 
std::pair< const void *const
*, bool > 
insert_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. More...
 
bool erase_imp (const void *Ptr)
 erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false. More...
 
bool count_imp (const void *Ptr) const
 
void swap (SmallPtrSetImplBase &RHS)
 swap - Swaps the elements of two sets. More...
 
void CopyFrom (const SmallPtrSetImplBase &RHS)
 CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a different small size. More...
 
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. More...
 
unsigned CurArraySize
 CurArraySize - The allocated size of CurArray, always a power of two.
 
unsigned NumElements
 
unsigned NumTombstones
 

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.

Member Function Documentation

void SmallPtrSetImplBase::CopyFrom ( const SmallPtrSetImplBase RHS)
protected

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

bool SmallPtrSetImplBase::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.

std::pair< const void *const *, bool > SmallPtrSetImplBase::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.

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.

Member Data Documentation

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'.


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