Fast multiset implementation for objects that can be identified by small unsigned keys. More...

#include "llvm/ADT/SparseMultiSet.h"

Inheritance diagram for llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >:

[legend]

Classes
class	iterator_base
	Our iterators are iterators over the collection of objects that share a key. More...

Public Types
using	value_type = ValueT

using	reference = ValueT &

using	const_reference = const ValueT &

using	pointer = ValueT *

using	const_pointer = const ValueT *

using	size_type = unsigned

using	iterator = iterator_base< SparseMultiSet * >

using	const_iterator = iterator_base< const SparseMultiSet * >

using	RangePair = std::pair< iterator, iterator >

Public Member Functions
	SparseMultiSet ()=default

	SparseMultiSet (const SparseMultiSet &)=delete

SparseMultiSet &	operator= (const SparseMultiSet &)=delete

	~SparseMultiSet ()

void	setUniverse (unsigned U)
	Set the universe size which determines the largest key the set can hold.

iterator	end ()
	Returns an iterator past this container.

const_iterator	end () const

bool	empty () const
	Returns true if the set is empty.

size_type	size () const
	Returns the number of elements in the set.

void	clear ()
	Clears the set.

iterator	findIndex (unsigned Idx)
	Find an element by its index.

iterator	find (const KeyT &Key)
	Find an element by its key.

const_iterator	find (const KeyT &Key) const

size_type	count (const KeyT &Key) const
	Returns the number of elements identified by Key.

bool	contains (const KeyT &Key) const
	Returns true if this set contains an element identified by Key.

iterator	getHead (const KeyT &Key)
	Return the head and tail of the subset's list, otherwise returns end().

iterator	getTail (const KeyT &Key)

RangePair	equal_range (const KeyT &K)
	The bounds of the range of items sharing Key K.

iterator	insert (const ValueT &Val)
	Insert a new element at the tail of the subset list.

iterator	erase (iterator I)
	Erases an existing element identified by a valid iterator.

void	eraseAll (const KeyT &K)
	Erase all elements with the given key.

Detailed Description

template<typename ValueT, typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>
class llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >

Fast multiset implementation for objects that can be identified by small unsigned keys.

SparseMultiSet 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, SparseMultiSet provides constant-time fast clear() 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. Iteration order is the insertion order. Iteration is only provided over elements of equivalent keys, but iterators are bidirectional.

Compared to BitVector, SparseMultiSet<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.

SparseMultiSet 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 up to 3 cache lines, but the sparse array uses 4 x Universe bytes.

When SparseT is uint8_t (the default), find() touches up to 3+[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.

Multiset behavior is provided by providing doubly linked lists for values that are inlined in the dense vector. SparseMultiSet is a good choice when one desires a growable number of entries per key, as it will retain the SparseSet algorithmic properties despite being growable. Thus, it is often a better choice than a SparseSet of growable containers or a vector of vectors. SparseMultiSet also keeps iterators valid after erasure (provided the iterators don't point to the element erased), allowing for more intuitive and fast removal.

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 86 of file SparseMultiSet.h.

Member Typedef Documentation

◆ const_iterator

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_iterator = iterator_base<const SparseMultiSet *>

Definition at line 312 of file SparseMultiSet.h.

◆ const_pointer

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_pointer = const ValueT *

Definition at line 189 of file SparseMultiSet.h.

◆ const_reference

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_reference = const ValueT &

Definition at line 187 of file SparseMultiSet.h.

◆ iterator

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::iterator = iterator_base<SparseMultiSet *>

Definition at line 311 of file SparseMultiSet.h.

◆ pointer

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::pointer = ValueT *

Definition at line 188 of file SparseMultiSet.h.

◆ RangePair

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::RangePair = std::pair<iterator, iterator>

Definition at line 315 of file SparseMultiSet.h.

◆ reference

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::reference = ValueT &

Definition at line 186 of file SparseMultiSet.h.

◆ size_type

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::size_type = unsigned

Definition at line 190 of file SparseMultiSet.h.

◆ value_type

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

using llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::value_type = ValueT

Definition at line 185 of file SparseMultiSet.h.

Constructor & Destructor Documentation

◆ SparseMultiSet() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::SparseMultiSet ( )

default

◆ SparseMultiSet() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::SparseMultiSet ( const SparseMultiSet< ValueT, KeyFunctorT, SparseT > & )

delete

◆ ~SparseMultiSet()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::~SparseMultiSet ( )

inline

Definition at line 195 of file SparseMultiSet.h.

Member Function Documentation

◆ clear()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

void llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::clear ( )

inline

Clears the set.

This is a very fast constant time operation.

Definition at line 342 of file SparseMultiSet.h.

References llvm::Dense.

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph(), and llvm::ScheduleDAGMILive::initRegPressure().

◆ contains()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

bool llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::contains ( const KeyT & Key ) const

inline

Returns true if this set contains an element identified by Key.

Definition at line 395 of file SparseMultiSet.h.

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

Referenced by llvm::ScheduleDAGInstrs::addSchedBarrierDeps().

◆ count()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

size_type llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::count ( const KeyT & Key ) const

inline

Returns the number of elements identified by Key.

This will be linear in the number of elements of that key.

Definition at line 386 of file SparseMultiSet.h.

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

◆ empty()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

bool llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::empty ( ) const

inline

Returns true if the set is empty.

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

Definition at line 328 of file SparseMultiSet.h.

References llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::size().

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph(), and llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::setUniverse().

◆ end() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end ( )

inline

Returns an iterator past this container.

Note that such an iterator cannot be decremented, but will compare equal to other end iterators.

Definition at line 319 of file SparseMultiSet.h.

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDataDeps(), llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addVRegDefDeps(), llvm::ScheduleDAGInstrs::addVRegUseDeps(), llvm::ScheduleDAGMILive::collectVRegUses(), llvm::ScheduleDAGMILive::computeCyclicCriticalPath(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::contains(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::count(), llvm::ScheduleDAGInstrs::deadDefHasNoUse(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::eraseAll(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::findIndex(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getTail(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::insert(), and llvm::ScheduleDAGMILive::updatePressureDiffs().

◆ end() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

const_iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end ( ) const

inline

Definition at line 320 of file SparseMultiSet.h.

◆ equal_range()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

RangePair llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::equal_range ( const KeyT & K )

inline

The bounds of the range of items sharing Key K.

First member is the head of the list, and the second member is a decrementable end iterator for that key.

Definition at line 411 of file SparseMultiSet.h.

References B, E, and llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find().

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps().

◆ erase()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::erase ( iterator I )

inline

Erases an existing element identified by a valid iterator.

This invalidates iterators pointing at the same entry, but erase() returns an iterator pointing to the next element in the subset's list. This makes it possible to erase selected elements while iterating over the subset:

tie(I, E) = Set.equal_range(Key); while (I != E) if (test(*I)) I = Set.erase(I); else ++I;

Note that if the last element in the subset list is erased, this will return an end iterator which can be decremented to get the new tail (if it exists):

tie(B, I) = Set.equal_range(Key); for (bool isBegin = B == I; !isBegin; /* empty *‍/) { isBegin = (–I) == B; if (test(I)) break; I = erase(I); }

Definition at line 466 of file SparseMultiSet.h.

References assert(), llvm::Dense, and I.

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addVRegDefDeps(), and llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::eraseAll().

◆ eraseAll()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

void llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::eraseAll ( const KeyT & K )

inline

Erase all elements with the given key.

This invalidates all iterators of that key.

Definition at line 482 of file SparseMultiSet.h.

References llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::erase(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find(), and I.

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps().

◆ find() [1/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find ( const KeyT & Key )

inline

Find an element by its key.

Parameters

Key	A valid key to find.

Returns: An iterator to the element identified by key, or end().

Definition at line 375 of file SparseMultiSet.h.

References llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::findIndex().

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDataDeps(), llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addVRegDefDeps(), llvm::ScheduleDAGInstrs::addVRegUseDeps(), llvm::ScheduleDAGMILive::collectVRegUses(), llvm::ScheduleDAGMILive::computeCyclicCriticalPath(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::contains(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::count(), llvm::ScheduleDAGInstrs::deadDefHasNoUse(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::equal_range(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::eraseAll(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getHead(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getTail(), and llvm::ScheduleDAGMILive::updatePressureDiffs().

◆ find() [2/2]

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

const_iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find ( const KeyT & Key ) const

inline

Definition at line 379 of file SparseMultiSet.h.

References llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::findIndex(), and I.

◆ findIndex()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::findIndex ( unsigned Idx )

inline

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 354 of file SparseMultiSet.h.

References assert(), llvm::Dense, llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end(), Idx, and isValid().

Referenced by llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find(), and llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::insert().

◆ getHead()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getHead ( const KeyT & Key )

inline

Return the head and tail of the subset's list, otherwise returns end().

Definition at line 400 of file SparseMultiSet.h.

References llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find().

◆ getTail()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getTail ( const KeyT & Key )

inline

Definition at line 401 of file SparseMultiSet.h.

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

◆ insert()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::insert ( const ValueT & Val )

inline

Insert a new element at the tail of the subset list.

Returns an iterator to the newly added entry.

Definition at line 419 of file SparseMultiSet.h.

References llvm::Dense, llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end(), llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::findIndex(), I, and Idx.

Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addSchedBarrierDeps(), llvm::ScheduleDAGInstrs::addVRegDefDeps(), llvm::ScheduleDAGInstrs::addVRegUseDeps(), and llvm::ScheduleDAGMILive::collectVRegUses().

◆ operator=()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

SparseMultiSet & llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::operator= ( const SparseMultiSet< ValueT, KeyFunctorT, SparseT > & )

delete

◆ setUniverse()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

void llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::setUniverse ( unsigned U )

inline

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

U	Universe size. All object keys must be less than U.

Definition at line 202 of file SparseMultiSet.h.

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

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph(), and llvm::ScheduleDAGMILive::initRegPressure().

◆ size()

template<typename ValueT , typename KeyFunctorT = identity<unsigned>, typename SparseT = uint8_t>

size_type llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::size ( ) const

inline

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 335 of file SparseMultiSet.h.

References assert(), and llvm::Dense.

Referenced by llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::empty().

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

include/llvm/ADT/SparseMultiSet.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ iterator

◆ pointer

◆ RangePair

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ SparseMultiSet() [1/2]

◆ SparseMultiSet() [2/2]

◆ ~SparseMultiSet()

Member Function Documentation

◆ clear()

◆ contains()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range()

◆ erase()

◆ eraseAll()

◆ find() [1/2]

◆ find() [2/2]

◆ findIndex()

◆ getHead()

◆ getTail()

◆ insert()

◆ operator=()

◆ setUniverse()

◆ size()