#include <SparseMultiSet.h>
Classes | |
| class | iterator_base |
| struct | SMSNode |
Public Types | |
| typedef ValueT | value_type |
| typedef ValueT & | reference |
| typedef const ValueT & | const_reference |
| typedef ValueT * | pointer |
| typedef const ValueT * | const_pointer |
| typedef unsigned | size_type |
| typedef iterator_base < SparseMultiSet * > | iterator |
| typedef iterator_base< const SparseMultiSet * > | const_iterator |
| typedef std::pair< iterator, iterator > | RangePair |
Public Member Functions | |
| SparseMultiSet () | |
| ~SparseMultiSet () | |
| void | setUniverse (unsigned U) |
| iterator | end () |
| const_iterator | end () const |
| bool | empty () const |
| size_type | size () const |
| void | clear () |
| iterator | findIndex (unsigned Idx) |
| iterator | find (const KeyT &Key) |
| const_iterator | find (const KeyT &Key) const |
| size_type | count (const KeyT &Key) const |
| 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) |
| iterator | insert (const ValueT &Val) |
Detailed Description
template<typename ValueT, typename KeyFunctorT = llvm::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 78 of file SparseMultiSet.h.
Member Typedef Documentation
| typedef iterator_base<const SparseMultiSet *> llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_iterator |
Definition at line 308 of file SparseMultiSet.h.
| typedef const ValueT* llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_pointer |
Definition at line 187 of file SparseMultiSet.h.
| typedef const ValueT& llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::const_reference |
Definition at line 185 of file SparseMultiSet.h.
| typedef iterator_base<SparseMultiSet *> llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::iterator |
Definition at line 307 of file SparseMultiSet.h.
| typedef ValueT* llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::pointer |
Definition at line 186 of file SparseMultiSet.h.
| typedef std::pair<iterator, iterator> llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::RangePair |
Definition at line 311 of file SparseMultiSet.h.
| typedef ValueT& llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::reference |
Definition at line 184 of file SparseMultiSet.h.
| typedef unsigned llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::size_type |
Definition at line 188 of file SparseMultiSet.h.
| typedef ValueT llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::value_type |
Definition at line 183 of file SparseMultiSet.h.
Constructor & Destructor Documentation
| llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::SparseMultiSet | ( | ) | [inline] |
Definition at line 190 of file SparseMultiSet.h.
| llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::~SparseMultiSet | ( | ) | [inline] |
Definition at line 193 of file SparseMultiSet.h.
Member Function Documentation
| void llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::clear | ( | ) | [inline] |
Clears the set. This is a very fast constant time operation.
Definition at line 338 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().
| 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 391 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addPhysRegDataDeps(), llvm::ScheduleDAGInstrs::addPhysRegDeps(), and llvm::ScheduleDAGInstrs::addSchedBarrierDeps().
| 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 382 of file SparseMultiSet.h.
| 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 324 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addSchedBarrierDeps(), llvm::ScheduleDAGInstrs::buildSchedGraph(), and llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::setUniverse().
| 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 315 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addPhysRegDataDeps(), llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addVRegUseDeps(), llvm::ScheduleDAGMILive::computeCyclicCriticalPath(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::contains(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::count(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::findIndex(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::getTail(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::insert(), and llvm::ScheduleDAGMILive::updatePressureDiffs().
| const_iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::end | ( | ) | const [inline] |
Definition at line 316 of file SparseMultiSet.h.
| 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 407 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps().
| 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 371 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addPhysRegDataDeps(), llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addVRegUseDeps(), llvm::ScheduleDAGMILive::computeCyclicCriticalPath(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::contains(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::count(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::equal_range(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::getHead(), llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::getTail(), and llvm::ScheduleDAGMILive::updatePressureDiffs().
| const_iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::find | ( | const KeyT & | Key | ) | const [inline] |
Definition at line 375 of file SparseMultiSet.h.
| 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 350 of file SparseMultiSet.h.
Referenced by llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::find(), and llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::insert().
| 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 396 of file SparseMultiSet.h.
| iterator llvm::SparseMultiSet< ValueT, KeyFunctorT, SparseT >::getTail | ( | const KeyT & | Key | ) | [inline] |
Definition at line 397 of file SparseMultiSet.h.
| 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 415 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::addPhysRegDeps(), llvm::ScheduleDAGInstrs::addSchedBarrierDeps(), and llvm::ScheduleDAGInstrs::addVRegUseDeps().
| 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 200 of file SparseMultiSet.h.
Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().
| 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 331 of file SparseMultiSet.h.
Referenced by llvm::SparseMultiSet< VReg2SUnit, VirtReg2IndexFunctor >::empty().
The documentation for this class was generated from the following file:
1.7.6.1