LLVM: llvm::SparseSet< ValueT, KeyFunctorT, SparseT (original) (raw)
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys. More...
#include "[llvm/ADT/SparseSet.h](SparseSet%5F8h%5Fsource.html)"
| Public Types | |
|---|---|
| using | value_type = ValueT |
| using | reference = ValueT & |
| using | const_reference = const ValueT & |
| using | pointer = ValueT * |
| using | const_pointer = const ValueT * |
| using | iterator = typename DenseT::iterator |
| using | const_iterator = typename DenseT::const_iterator |
| Public Member Functions | |
|---|---|
| SparseSet ()=default | |
| SparseSet (const SparseSet &)=delete | |
| SparseSet & | operator= (const SparseSet &)=delete |
| SparseSet (SparseSet &&)=default | |
| void | setUniverse (unsigned U) |
| setUniverse - Set the universe size which determines the largest key the set can hold. | |
| const_iterator | begin () const |
| const_iterator | end () const |
| iterator | begin () |
| iterator | end () |
| bool | empty () const |
| empty - Returns true if the set is empty. | |
| size_type | size () const |
| size - Returns the number of elements in the set. | |
| void | clear () |
| clear - Clears the set. | |
| iterator | findIndex (unsigned Idx) |
| findIndex - Find an element by its index. | |
| iterator | find (const KeyT &Key) |
| find - Find an element by its key. | |
| const_iterator | find (const KeyT &Key) const |
| bool | contains (const KeyT &Key) const |
| Check if the set contains the given Key. | |
| size_type | count (const KeyT &Key) const |
| count - Returns 1 if this set contains an element identified by Key, 0 otherwise. | |
| std::pair< iterator, bool > | insert (const ValueT &Val) |
| insert - Attempts to insert a new element. | |
| ValueT & | operator[] (const KeyT &Key) |
| array subscript - If an element already exists with this key, return it. | |
| ValueT | pop_back_val () |
| iterator | erase (iterator I) |
| erase - Erases an existing element identified by a valid iterator. | |
| bool | erase (const KeyT &Key) |
| erase - Erases an element identified by Key, if it exists. | |
template<typename ValueT, typename KeyFunctorT = identity, typename SparseT = uint8_t>
class llvm::SparseSet< ValueT, KeyFunctorT, SparseT >
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
SparseSet allocates memory proportional to the size of the key universe, so it is not recommended for building composite data structures. It is useful for algorithms that require a single set with fast operations.
Compared to DenseSet and DenseMap, SparseSet provides constant-time fast clear() and iteration as fast as a vector. The find(), insert(), and erase() operations are all constant time, and typically faster than a hash table. The iteration order doesn't depend on numerical key values, it only depends on the order of insert() and erase() operations. When no elements have been erased, the iteration order is the insertion order.
Compared to BitVector, SparseSet uses 8x-40x more memory, but offers constant-time clear() and size() operations as well as fast iteration independent on the size of the universe.
SparseSet contains a dense vector holding all the objects and a sparse array holding indexes into the dense vector. Most of the memory is used by the sparse array which is the size of the key universe. The SparseT template parameter provides a space/speed tradeoff for sets holding many elements.
When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse array uses 4 x Universe bytes.
When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache lines, but the sparse array is 4x smaller. N is the number of elements in the set.
For sets that may grow to thousands of elements, SparseT should be set to uint16_t or uint32_t.
Template Parameters
| ValueT | The type of objects in the set. |
|---|---|
| KeyFunctorT | A functor that computes an unsigned index from KeyT. |
| SparseT | An unsigned integer type. See above. |
Definition at line 124 of file SparseSet.h.
◆ const_iterator
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ const_pointer
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ const_reference
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ iterator
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ pointer
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ reference
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ value_type
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ SparseSet() [2/3]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ SparseSet() [3/3]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ begin() [1/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ begin() [2/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ clear()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ contains()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ count()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ empty()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ end() [1/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ end() [2/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
Definition at line 179 of file SparseSet.h.
References llvm::Dense.
Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::contains(), llvm::LiveRegSet::contains(), llvm::LivePhysRegs::end(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase(), llvm::LiveRegSet::erase(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::findIndex(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert(), insertDeleteInstructions(), llvm::LivePhysRegs::removeRegsInMask(), updatePhysDepsDownwards(), and updatePhysDepsUpwards().
◆ erase() [1/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
erase - Erases an element identified by Key, if it exists.
Parameters
| Key | The key identifying the element to erase. |
|---|
Returns
True when an element was erased, false if no element was found.
Definition at line 312 of file SparseSet.h.
References llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::find(), and I.
◆ erase() [2/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
erase - Erases an existing element identified by a valid iterator.
This invalidates all iterators, but erase() returns an iterator pointing to the next element. This makes it possible to erase selected elements while iterating over the set:
for (SparseSet::iterator I = Set.begin(); I != Set.end();) if (test(*I)) I = Set.erase(I); else ++I;
Note that end() changes when elements are erased, unlike std::list.
Definition at line 293 of file SparseSet.h.
References assert(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::begin(), llvm::Dense, llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end(), I, and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::size().
Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase(), insertDeleteInstructions(), llvm::LivePhysRegs::removeReg(), llvm::LivePhysRegs::removeRegsInMask(), updatePhysDepsDownwards(), updatePhysDepsUpwards(), and llvm::SchedDFSImpl::visitPostorderNode().
◆ find() [1/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
find - Find an element by its key.
Parameters
Returns
An iterator to the element identified by key, or end().
Definition at line 229 of file SparseSet.h.
References llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::findIndex().
Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::contains(), llvm::LiveRegSet::contains(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase(), llvm::LiveRegSet::erase(), updatePhysDepsDownwards(), and updatePhysDepsUpwards().
◆ find() [2/2]
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ findIndex()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
findIndex - Find an element by its index.
Parameters
| Idx | A valid index to find. |
|---|
Returns
An iterator to the element identified by key, or end().
Definition at line 208 of file SparseSet.h.
References assert(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::begin(), llvm::Dense, llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end(), Idx, and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::size().
Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::find(), and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert().
◆ insert()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
insert - Attempts to insert a new element.
If Val is successfully inserted, return (I, true), where I is an iterator pointing to the newly inserted element.
If the set already contains an element with the same key as Val, return (I, false), where I is an iterator pointing to the existing element.
Insertion invalidates all iterators.
Definition at line 257 of file SparseSet.h.
References llvm::Dense, llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::findIndex(), I, Idx, and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::size().
Referenced by llvm::LivePhysRegs::addReg(), llvm::LiveRegSet::insert(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::operator, and UpdatePredRedefs().
◆ operator=()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ operator[]()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ pop_back_val()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ setUniverse()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
◆ size()
template<typename ValueT , typename KeyFunctorT = identity, typename SparseT = uint8_t>
size - Returns the number of elements in the set.
This is not the same as BitVector::size() which returns the size of the universe.
Definition at line 194 of file SparseSet.h.
References llvm::Dense.
Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase(), llvm::SchedDFSImpl::finalize(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::findIndex(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert(), and llvm::LiveRegSet::size().
The documentation for this class was generated from the following file:
- include/llvm/ADT/SparseSet.h