class SparseMultiSet

Declaration

template <typename ValueT,
          typename KeyFunctorT = identity<unsigned int>,
          typename SparseT = uint8_t>
class SparseMultiSet { /* full declaration omitted */ };

Description

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.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:86

Templates

ValueT

The type of objects in the set.

KeyFunctorT = identity<unsigned int>

A functor that computes an unsigned index from KeyT.

SparseT = uint8_t

An unsigned integer type. See above.

Member Variables

private llvm::SparseMultiSet::DenseT Dense

private SparseT* Sparse = nullptr

private unsigned int Universe = 0

private KeyFunctorT KeyIndexOf

private SparseSetValFunctor<llvm::SparseMultiSet::KeyT, ValueT, KeyFunctorT> ValIndexOf

private unsigned int FreelistIdx = SMSNode::INVALID

We have a built-in recycler for reusing tombstone slots. This recycler puts a singly-linked free list into tombstone slots, allowing us quick erasure, iterator preservation, and dense size.

private unsigned int NumFree = 0

Method Overview

• public SparseMultiSet<ValueT, KeyFunctorT, SparseT>()
• public SparseMultiSet<ValueT, KeyFunctorT, SparseT>(const SparseMultiSet<ValueT, KeyFunctorT, SparseT> &)
• private unsigned int addValue(const ValueT & V, unsigned int Prev, unsigned int Next)
• public void clear()
• public bool contains(const llvm::SparseMultiSet::KeyT & Key) const
• public llvm::SparseMultiSet::size_type count(const llvm::SparseMultiSet::KeyT & Key) const
• public bool empty() const
• public llvm::SparseMultiSet::iterator end()
• public llvm::SparseMultiSet::const_iterator end() const
• public llvm::SparseMultiSet::RangePair equal_range(const llvm::SparseMultiSet::KeyT & K)
• public llvm::SparseMultiSet::iterator erase(llvm::SparseMultiSet::iterator I)
• public void eraseAll(const llvm::SparseMultiSet::KeyT & K)
• public llvm::SparseMultiSet::iterator find(const llvm::SparseMultiSet::KeyT & Key)
• public llvm::SparseMultiSet::const_iterator find(const llvm::SparseMultiSet::KeyT & Key) const
• public llvm::SparseMultiSet::iterator findIndex(unsigned int Idx)
• public llvm::SparseMultiSet::iterator getHead(const llvm::SparseMultiSet::KeyT & Key)
• public llvm::SparseMultiSet::iterator getTail(const llvm::SparseMultiSet::KeyT & Key)
• public llvm::SparseMultiSet::iterator insert(const ValueT & Val)
• private bool isHead(const llvm::SparseMultiSet::SMSNode & D) const
• private bool isSingleton(const llvm::SparseMultiSet::SMSNode & N) const
• private void makeTombstone(unsigned int Idx)
• public void setUniverse(unsigned int U)
• public llvm::SparseMultiSet::size_type size() const
• private unsigned int sparseIndex(const llvm::SparseMultiSet::SMSNode & N) const
• private unsigned int sparseIndex(const ValueT & Val) const
• private llvm::SparseMultiSet::iterator unlink(const llvm::SparseMultiSet::SMSNode & N)
• public ~SparseMultiSet<ValueT, KeyFunctorT, SparseT>()

Methods

¶SparseMultiSet<ValueT, KeyFunctorT, SparseT>()

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:193

¶SparseMultiSet<ValueT, KeyFunctorT, SparseT>(
    const SparseMultiSet<ValueT,
                         KeyFunctorT,
                         SparseT>&)

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:194

Parameters

const SparseMultiSet<ValueT, KeyFunctorT, SparseT>&

¶unsigned int addValue(const ValueT& V,
                      unsigned int Prev,
                      unsigned int Next)

Description

Add in the given SMSNode. Uses a free entry in our freelist if available. Returns the index of the added node.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:160

Parameters

const ValueT& V

unsigned int Prev

unsigned int Next

¶void clear()

Description

Clears the set. This is a very fast constant time operation.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:343

¶bool contains(
    const llvm::SparseMultiSet::KeyT& Key) const

Description

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

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:396

Parameters

const llvm::SparseMultiSet::KeyT& Key

¶llvm::SparseMultiSet::size_type count(
    const llvm::SparseMultiSet::KeyT& Key) const

Description

Returns the number of elements identified by Key. This will be linear in the number of elements of that key.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:387

Parameters

const llvm::SparseMultiSet::KeyT& Key

¶bool empty() const

Description

Returns true if the set is empty. This is not the same as BitVector::empty().

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:329

¶llvm::SparseMultiSet::iterator end()

Description

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

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:320

¶llvm::SparseMultiSet::const_iterator end() const

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:321

¶llvm::SparseMultiSet::RangePair equal_range(
    const llvm::SparseMultiSet::KeyT& K)

Description

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.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:412

Parameters

const llvm::SparseMultiSet::KeyT& K

¶llvm::SparseMultiSet::iterator erase(
    llvm::SparseMultiSet::iterator I)

Description

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); }

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:467

Parameters

llvm::SparseMultiSet::iterator I

¶void eraseAll(const llvm::SparseMultiSet::KeyT& K)

Description

Erase all elements with the given key. This invalidates all iterators of that key.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:483

Parameters

const llvm::SparseMultiSet::KeyT& K

¶llvm::SparseMultiSet::iterator find(
    const llvm::SparseMultiSet::KeyT& Key)

Description

Find an element by its key.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:376

Parameters

const llvm::SparseMultiSet::KeyT& Key

A valid key to find.

Returns

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

¶llvm::SparseMultiSet::const_iterator find(
    const llvm::SparseMultiSet::KeyT& Key) const

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:380

Parameters

const llvm::SparseMultiSet::KeyT& Key

¶llvm::SparseMultiSet::iterator findIndex(
    unsigned int Idx)

Description

Find an element by its index.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:355

Parameters

unsigned int Idx

A valid index to find.

Returns

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

¶llvm::SparseMultiSet::iterator getHead(
    const llvm::SparseMultiSet::KeyT& Key)

Description

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

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:401

Parameters

const llvm::SparseMultiSet::KeyT& Key

¶llvm::SparseMultiSet::iterator getTail(
    const llvm::SparseMultiSet::KeyT& Key)

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:402

Parameters

const llvm::SparseMultiSet::KeyT& Key

¶llvm::SparseMultiSet::iterator insert(
    const ValueT& Val)

Description

Insert a new element at the tail of the subset list. Returns an iterator to the newly added entry.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:420

Parameters

const ValueT& Val

¶bool isHead(
    const llvm::SparseMultiSet::SMSNode& D) const

Description

Whether the given entry is the head of the list. List heads's previous pointers are to the tail of the list, allowing for efficient access to the list tail. D must be a valid entry node.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:145

Parameters

const llvm::SparseMultiSet::SMSNode& D

¶bool isSingleton(
    const llvm::SparseMultiSet::SMSNode& N) const

Description

Whether the given entry is a singleton entry, i.e. the only entry with that key.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:152

Parameters

const llvm::SparseMultiSet::SMSNode& N

¶void makeTombstone(unsigned int Idx)

Description

Make the current index a new tombstone. Pushes it onto the freelist.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:178

Parameters

unsigned int Idx

¶void setUniverse(unsigned int U)

Description

Set the universe size which determines the largest key the set can hold. The universe must be sized before any elements can be added.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:203

Parameters

unsigned int U

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

¶llvm::SparseMultiSet::size_type size() const

Description

Returns the number of elements in the set. This is not the same as BitVector::size() which returns the size of the universe.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:336

¶unsigned int sparseIndex(
    const llvm::SparseMultiSet::SMSNode& N) const

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:140

Parameters

const llvm::SparseMultiSet::SMSNode& N

¶unsigned int sparseIndex(const ValueT& Val) const

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:135

Parameters

const ValueT& Val

¶llvm::SparseMultiSet::iterator unlink(
    const llvm::SparseMultiSet::SMSNode& N)

Description

Unlink the node from its list. Returns the next node in the list.

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:490

Parameters

const llvm::SparseMultiSet::SMSNode& N

¶~SparseMultiSet<ValueT, KeyFunctorT, SparseT>()

Declared at: llvm/include/llvm/ADT/SparseMultiSet.h:196