LLVM API Documentation
#include <SmallPtrSet.h>
Public Member Functions | |
| bool | empty () const |
| unsigned | size () const |
| void | clear () |
Protected Member Functions | |
| SmallPtrSetImpl (const SmallPtrSetImpl &that) | |
| SmallPtrSetImpl (unsigned SmallSize) | |
| ~SmallPtrSetImpl () | |
| bool | insert_imp (const void *Ptr) |
| bool | erase_imp (const void *Ptr) |
| bool | count_imp (const void *Ptr) const |
| void | CopyFrom (const SmallPtrSetImpl &RHS) |
Static Protected Member Functions | |
| static void * | getTombstoneMarker () |
| static void * | getEmptyMarker () |
Protected Attributes | |
| const void ** | CurArray |
| unsigned | CurArraySize |
| unsigned | NumElements |
| unsigned | NumTombstones |
| const void * | SmallArray [1] |
Friends | |
| class | SmallPtrSetIteratorImpl |
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 46 of file SmallPtrSet.h.
| SmallPtrSetImpl::SmallPtrSetImpl | ( | const SmallPtrSetImpl & | that | ) | [protected] |
Definition at line 169 of file SmallPtrSet.cpp.
References CurArray, CurArraySize, isSmall(), llvm::Intrinsic::memcpy, NumElements, NumTombstones, and SmallArray.
| llvm::SmallPtrSetImpl::SmallPtrSetImpl | ( | unsigned | SmallSize | ) | [inline, explicit, protected] |
Definition at line 64 of file SmallPtrSet.h.
References clear(), CurArray, CurArraySize, and SmallArray.
| SmallPtrSetImpl::~SmallPtrSetImpl | ( | ) | [protected] |
| bool llvm::SmallPtrSetImpl::empty | ( | ) | const [inline] |
Definition at line 77 of file SmallPtrSet.h.
References size().
Referenced by LeakDetectorImpl< llvm::Value >::hasGarbage(), isLiveInButUnusedBefore(), and llvm::MemoryDependenceAnalysis::removeInstruction().
| unsigned llvm::SmallPtrSetImpl::size | ( | ) | const [inline] |
Definition at line 78 of file SmallPtrSet.h.
References NumElements.
Referenced by DeadPHICycle(), empty(), llvm::LiveIntervals::intervalIsInOneMBB(), PHIsEqualValue(), and RemoveUnreachableBlocksFromFn().
| void llvm::SmallPtrSetImpl::clear | ( | ) | [inline] |
Definition at line 80 of file SmallPtrSet.h.
References CurArray, CurArraySize, llvm::Intrinsic::memset, NumElements, and NumTombstones.
Referenced by AllGlobalLoadUsesSimpleEnoughForHeapSRA(), LeakDetectorImpl< llvm::Value >::clear(), and SmallPtrSetImpl().
| static void* llvm::SmallPtrSetImpl::getTombstoneMarker | ( | ) | [inline, static, protected] |
Definition at line 93 of file SmallPtrSet.h.
Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), erase_imp(), and insert_imp().
| static void* llvm::SmallPtrSetImpl::getEmptyMarker | ( | ) | [inline, static, protected] |
Definition at line 94 of file SmallPtrSet.h.
Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), and erase_imp().
| 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.
Definition at line 39 of file SmallPtrSet.cpp.
References CurArraySize, E, getTombstoneMarker(), NumTombstones, and SmallArray.
Referenced by llvm::SmallPtrSet< const T *, 8 >::insert().
| 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.
Definition at line 72 of file SmallPtrSet.cpp.
References E, getEmptyMarker(), getTombstoneMarker(), NumTombstones, and SmallArray.
Referenced by llvm::SmallPtrSet< const T *, 8 >::erase().
| bool llvm::SmallPtrSetImpl::count_imp | ( | const void * | Ptr | ) | const [inline, protected] |
Definition at line 111 of file SmallPtrSet.h.
References E, NumElements, and SmallArray.
Referenced by llvm::SmallPtrSet< const T *, 8 >::count().
| void SmallPtrSetImpl::CopyFrom | ( | const SmallPtrSetImpl & | RHS | ) | [protected] |
CopyFrom - implement operator= from a smallptrset that has the same pointer type, but may have a different small size.
Definition at line 191 of file SmallPtrSet.cpp.
References CurArray, CurArraySize, isSmall(), llvm::Intrinsic::memcpy, NumElements, NumTombstones, and SmallArray.
Referenced by llvm::SmallPtrSet< const T *, 8 >::operator=().
friend class SmallPtrSetIteratorImpl [friend] |
Definition at line 47 of file SmallPtrSet.h.
const void** llvm::SmallPtrSetImpl::CurArray [protected] |
CurArray - This is the current set of buckets. If it points to SmallArray, then the set is in 'small mode'.
Definition at line 51 of file SmallPtrSet.h.
Referenced by llvm::SmallPtrSet< const T *, 8 >::begin(), clear(), CopyFrom(), llvm::SmallPtrSet< const T *, 8 >::end(), SmallPtrSetImpl(), and ~SmallPtrSetImpl().
unsigned llvm::SmallPtrSetImpl::CurArraySize [protected] |
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.
Definition at line 55 of file SmallPtrSet.h.
Referenced by clear(), CopyFrom(), llvm::SmallPtrSet< const T *, 8 >::end(), insert_imp(), and SmallPtrSetImpl().
unsigned llvm::SmallPtrSetImpl::NumElements [protected] |
Definition at line 58 of file SmallPtrSet.h.
Referenced by clear(), CopyFrom(), count_imp(), size(), and SmallPtrSetImpl().
unsigned llvm::SmallPtrSetImpl::NumTombstones [protected] |
Definition at line 59 of file SmallPtrSet.h.
Referenced by clear(), CopyFrom(), erase_imp(), insert_imp(), and SmallPtrSetImpl().
const void* llvm::SmallPtrSetImpl::SmallArray[1] [protected] |
Definition at line 60 of file SmallPtrSet.h.
Referenced by CopyFrom(), count_imp(), erase_imp(), insert_imp(), and SmallPtrSetImpl().