LLVM 20.0.0git
Public Types | Public Member Functions | List of all members
llvm::SparseSet< ValueT, KeyFunctorT, SparseT > Class Template Reference

SparseSet - Fast set implementation for objects that can be identified by small unsigned keys. More...

#include "llvm/ADT/SparseSet.h"

Inheritance diagram for llvm::SparseSet< ValueT, KeyFunctorT, SparseT >:
Inheritance graph
[legend]

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
 
SparseSetoperator= (const SparseSet &)=delete
 
 ~SparseSet ()
 
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, boolinsert (const ValueT &Val)
 insert - Attempts to insert a new element.
 
ValueToperator[] (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.
 

Detailed Description

template<typename ValueT, typename KeyFunctorT = identity<unsigned>, 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<unsigned> 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
ValueTThe type of objects in the set.
KeyFunctorTA functor that computes an unsigned index from KeyT.
SparseTAn unsigned integer type. See above.

Definition at line 124 of file SparseSet.h.

Member Typedef Documentation

◆ const_iterator

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::const_iterator = typename DenseT::const_iterator

Definition at line 172 of file SparseSet.h.

◆ const_pointer

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::const_pointer = const ValueT *

Definition at line 142 of file SparseSet.h.

◆ const_reference

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::const_reference = const ValueT &

Definition at line 140 of file SparseSet.h.

◆ iterator

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::iterator = typename DenseT::iterator

Definition at line 171 of file SparseSet.h.

◆ pointer

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::pointer = ValueT *

Definition at line 141 of file SparseSet.h.

◆ reference

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::reference = ValueT &

Definition at line 139 of file SparseSet.h.

◆ value_type

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
using llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::value_type = ValueT

Definition at line 138 of file SparseSet.h.

Constructor & Destructor Documentation

◆ SparseSet() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::SparseSet ( )
default

◆ SparseSet() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::SparseSet ( const SparseSet< ValueT, KeyFunctorT, SparseT > &  )
delete

◆ ~SparseSet()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::~SparseSet ( )
inline

Definition at line 147 of file SparseSet.h.

Member Function Documentation

◆ begin() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::begin ( )
inline

Definition at line 176 of file SparseSet.h.

References llvm::Dense.

◆ begin() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
const_iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::begin ( ) const
inline

◆ clear()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
void llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::clear ( )
inline

clear - Clears the set.

This is a very fast constant time operation.

Definition at line 194 of file SparseSet.h.

References llvm::Dense.

Referenced by llvm::LivePhysRegs::clear(), llvm::LiveRegSet::clear(), llvm::LivePhysRegs::init(), and llvm::SpillPlacement::prepare().

◆ contains()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
bool llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::contains ( const KeyT &  Key) const
inline

Check if the set contains the given Key.

Parameters
KeyA valid key to find.

Definition at line 236 of file SparseSet.h.

References llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end(), and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::find().

Referenced by llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::count().

◆ count()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
size_type llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::count ( const KeyT &  Key) const
inline

◆ empty()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
bool llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::empty ( ) const
inline

empty - Returns true if the set is empty.

This is not the same as BitVector::empty().

Definition at line 183 of file SparseSet.h.

References llvm::Dense.

Referenced by llvm::LivePhysRegs::empty(), llvm::SpillPlacement::iterate(), and llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::setUniverse().

◆ end() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end ( )
inline

Definition at line 177 of file SparseSet.h.

References llvm::Dense.

◆ end() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
const_iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::end ( ) const
inline

◆ erase() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
bool llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase ( const KeyT &  Key)
inline

erase - Erases an element identified by Key, if it exists.

Parameters
KeyThe key identifying the element to erase.
Returns
True when an element was erased, false if no element was found.

Definition at line 308 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<unsigned>, typename SparseT = uint8_t>
iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::erase ( iterator  I)
inline

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 289 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<unsigned>, typename SparseT = uint8_t>
iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::find ( const KeyT &  Key)
inline

find - Find an element by its key.

Parameters
KeyA valid key to find.
Returns
An iterator to the element identified by key, or end().

Definition at line 225 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<unsigned>, typename SparseT = uint8_t>
const_iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::find ( const KeyT &  Key) const
inline

◆ findIndex()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
iterator llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::findIndex ( unsigned  Idx)
inline

findIndex - Find an element by its index.

Parameters
IdxA valid index to find.
Returns
An iterator to the element identified by key, or end().

Definition at line 204 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<unsigned>, typename SparseT = uint8_t>
std::pair< iterator, bool > llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert ( const ValueT Val)
inline

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 253 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<unsigned>, typename SparseT = uint8_t>
SparseSet & llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::operator= ( const SparseSet< ValueT, KeyFunctorT, SparseT > &  )
delete

◆ operator[]()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
ValueT & llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::operator[] ( const KeyT &  Key)
inline

array subscript - If an element already exists with this key, return it.

Otherwise, automatically construct a new value from Key, insert it, and return the newly inserted element.

Definition at line 266 of file SparseSet.h.

References llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert().

◆ pop_back_val()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
ValueT llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::pop_back_val ( )
inline

Definition at line 270 of file SparseSet.h.

References llvm::Dense.

Referenced by llvm::SpillPlacement::iterate().

◆ setUniverse()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
void llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::setUniverse ( unsigned  U)
inline

setUniverse - Set the universe size which determines the largest key the set can hold.

The universe must be sized before any elements can be added.

Parameters
UUniverse size. All object keys must be less than U.

Definition at line 155 of file SparseSet.h.

References assert(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::empty(), and llvm::safe_calloc().

Referenced by llvm::LiveRegSet::init(), llvm::LivePhysRegs::init(), llvm::LivePhysRegs::LivePhysRegs(), llvm::SchedDFSImpl::SchedDFSImpl(), and UpdatePredRedefs().

◆ size()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
size_type llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::size ( ) const
inline

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