llvm::SmallPtrSetImpl Class Reference
SmallPtrSetImpl - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything.
More...
#include <SmallPtrSet.h>
List of all members.
Public Member Functions |
| bool | 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) |
| | 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.
|
| bool | count_imp (const void *Ptr) const |
| void | CopyFrom (const SmallPtrSetImpl &RHS) |
| | CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a different small size.
|
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 | NumElements |
| unsigned | NumTombstones |
Private Member Functions |
| bool | isSmall () const |
| unsigned | Hash (const void *Ptr) const |
| const void *const * | FindBucketFor (const void *Ptr) const |
| void | shrink_and_clear () |
| void | Grow (unsigned NewSize) |
| | Grow - Allocate a larger backing store for the buckets and move it over.
|
| void | operator= (const SmallPtrSetImpl &RHS) |
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.
Constructor & Destructor Documentation
| SmallPtrSetImpl::SmallPtrSetImpl |
( |
const void ** |
SmallStorage, |
|
|
const SmallPtrSetImpl & |
that | |
|
) |
| | [protected] |
| llvm::SmallPtrSetImpl::SmallPtrSetImpl |
( |
const void ** |
SmallStorage, |
|
|
unsigned |
SmallSize | |
|
) |
| | [inline, explicit, protected] |
| SmallPtrSetImpl::~SmallPtrSetImpl |
( |
|
) |
[protected] |
Member Function Documentation
| void llvm::SmallPtrSetImpl::clear |
( |
|
) |
[inline] |
CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a different small size.
| bool llvm::SmallPtrSetImpl::count_imp |
( |
const void * |
Ptr |
) |
const [inline, protected] |
| bool llvm::SmallPtrSetImpl::empty |
( |
|
) |
const [inline] |
| 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.
| const void *const * SmallPtrSetImpl::FindBucketFor |
( |
const void * |
Ptr |
) |
const [private] |
| static void* llvm::SmallPtrSetImpl::getEmptyMarker |
( |
|
) |
[inline, static, protected] |
| static void* llvm::SmallPtrSetImpl::getTombstoneMarker |
( |
|
) |
[inline, static, protected] |
| void SmallPtrSetImpl::Grow |
( |
unsigned |
NewSize |
) |
[private] |
Grow - Allocate a larger backing store for the buckets and move it over.
| unsigned llvm::SmallPtrSetImpl::Hash |
( |
const void * |
Ptr |
) |
const [inline, private] |
| 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.
| bool llvm::SmallPtrSetImpl::isSmall |
( |
|
) |
const [inline, private] |
| void llvm::SmallPtrSetImpl::operator= |
( |
const SmallPtrSetImpl & |
RHS |
) |
[private] |
| void SmallPtrSetImpl::shrink_and_clear |
( |
|
) |
[private] |
| unsigned llvm::SmallPtrSetImpl::size |
( |
|
) |
const [inline] |
Friends And Related Function Documentation
Member Data Documentation
CurArray - This is the current set of buckets.
If equal to SmallArray, then the set is in 'small mode'.
CurArraySize - The allocated size of CurArray, always a power of two.
Note that CurArray points to an array that has CurArraySize+1 elements in it, so that the end iterator actually points to valid memory.
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
The documentation for this class was generated from the following files:
