21 #ifndef LLVM_ADT_SPARSEMULTISET_H
22 #define LLVM_ADT_SPARSEMULTISET_H
75 template<
typename ValueT,
77 typename SparseT = uint8_t>
86 static const unsigned INVALID = ~0U;
92 SMSNode(ValueT D,
unsigned P,
unsigned N) : Data(D), Prev(P), Next(N) { }
96 return Next == INVALID;
100 bool isTombstone()
const {
101 return Prev == INVALID;
106 bool isValid()
const {
return Prev != INVALID; }
109 typedef typename KeyFunctorT::argument_type KeyT;
114 KeyFunctorT KeyIndexOf;
120 unsigned FreelistIdx;
123 unsigned sparseIndex(
const ValueT &Val)
const {
124 assert(ValIndexOf(Val) < Universe &&
125 "Invalid key in set. Did object mutate?");
126 return ValIndexOf(Val);
128 unsigned sparseIndex(
const SMSNode &
N)
const {
return sparseIndex(N.Data); }
138 bool isHead(
const SMSNode &D)
const {
139 assert(D.isValid() &&
"Invalid node for head");
140 return Dense[D.Prev].isTail();
145 bool isSingleton(
const SMSNode &N)
const {
146 assert(N.isValid() &&
"Invalid node for singleton");
148 return &Dense[N.Prev] == &
N;
153 unsigned addValue(
const ValueT& V,
unsigned Prev,
unsigned Next) {
156 return Dense.
size() - 1;
160 unsigned Idx = FreelistIdx;
161 unsigned NextFree = Dense[Idx].Next;
162 assert(Dense[Idx].isTombstone() &&
"Non-tombstone free?");
164 Dense[Idx] = SMSNode(V, Prev, Next);
165 FreelistIdx = NextFree;
171 void makeTombstone(
unsigned Idx) {
172 Dense[Idx].Prev = SMSNode::INVALID;
173 Dense[Idx].Next = FreelistIdx;
186 : Sparse(0), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) { }
198 assert(
empty() &&
"Can only resize universe on an empty map");
200 if (U >= Universe/4 && U <= Universe)
206 Sparse =
reinterpret_cast<SparseT*
>(
calloc(U,
sizeof(SparseT)));
212 template<
typename SMSPtrTy>
221 : SMS(P), Idx(I), SparseIdx(SI) { }
225 if (Idx == SMSNode::INVALID)
228 assert(Idx < SMS->Dense.size() &&
"Out of range, non-INVALID Idx?");
233 bool isKeyed()
const {
return SparseIdx < SMS->Universe; }
235 unsigned Prev()
const {
return SMS->Dense[Idx].Prev; }
236 unsigned Next()
const {
return SMS->Dense[Idx].Next; }
238 void setPrev(
unsigned P) { SMS->Dense[Idx].Prev =
P; }
239 void setNext(
unsigned N) { SMS->Dense[Idx].Next =
N; }
242 typedef std::iterator<std::bidirectional_iterator_tag, ValueT>
super;
249 : SMS(RHS.SMS), Idx(RHS.Idx), SparseIdx(RHS.SparseIdx) { }
254 SparseIdx = RHS.SparseIdx;
259 assert(isKeyed() && SMS->sparseIndex(SMS->Dense[Idx].Data) == SparseIdx &&
260 "Dereferencing iterator of invalid key or index");
262 return SMS->Dense[Idx].Data;
269 if (SMS == RHS.SMS && Idx == RHS.Idx) {
270 assert((isEnd() || SparseIdx == RHS.SparseIdx) &&
271 "Same dense entry, but different keys?");
284 assert(isKeyed() &&
"Decrementing an invalid iterator");
285 assert((isEnd() || !SMS->isHead(SMS->Dense[Idx])) &&
286 "Decrementing head of list");
290 Idx = SMS->findIndex(SparseIdx).Prev();
297 assert(!isEnd() && isKeyed() &&
"Incrementing an invalid/end iterator");
337 assert(NumFree <= Dense.
size() &&
"Out-of-bounds free entries");
338 return Dense.
size() - NumFree;
347 FreelistIdx = SMSNode::INVALID;
356 assert(Idx < Universe &&
"Key out of range");
357 assert(std::numeric_limits<SparseT>::is_integer &&
358 !std::numeric_limits<SparseT>::is_signed &&
359 "SparseT must be an unsigned integer type");
360 const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u;
361 for (
unsigned i = Sparse[Idx], e = Dense.
size(); i < e; i += Stride) {
362 const unsigned FoundIdx = sparseIndex(Dense[i]);
365 if (Idx == FoundIdx && Dense[i].isValid() && isHead(Dense[i]))
390 unsigned count(
const KeyT &Key)
const {
408 I =
iterator(
this, I.Prev(), KeyIndexOf(Key));
418 return make_pair(B, E);
424 unsigned Idx = sparseIndex(Val);
427 unsigned NodeIdx = addValue(Val, SMSNode::INVALID, SMSNode::INVALID);
431 Sparse[Idx] = NodeIdx;
432 Dense[NodeIdx].Prev = NodeIdx;
433 return iterator(
this, NodeIdx, Idx);
437 unsigned HeadIdx = I.Idx;
438 unsigned TailIdx = I.Prev();
439 Dense[TailIdx].Next = NodeIdx;
440 Dense[HeadIdx].Prev = NodeIdx;
441 Dense[NodeIdx].Prev = TailIdx;
443 return iterator(
this, NodeIdx, Idx);
471 assert(I.isKeyed() && !I.isEnd() && !Dense[I.Idx].isTombstone() &&
472 "erasing invalid/end/tombstone iterator");
479 makeTombstone(I.Idx);
494 if (isSingleton(N)) {
496 assert(N.Next == SMSNode::INVALID &&
"Singleton has next?");
497 return iterator(
this, SMSNode::INVALID, ValIndexOf(N.Data));
502 Sparse[sparseIndex(N)] = N.Next;
503 Dense[N.Next].Prev = N.Prev;
504 return iterator(
this, N.Next, ValIndexOf(N.Data));
509 findIndex(sparseIndex(N)).setPrev(N.Prev);
510 Dense[N.Prev].Next = N.Next;
513 iterator I(
this, N.Prev, ValIndexOf(N.Data));
518 Dense[N.Next].Prev = N.Prev;
519 Dense[N.Prev].Next = N.Next;
520 return iterator(
this, N.Next, ValIndexOf(N.Data));
void push_back(const T &Elt)
super::reference reference
const iterator_base & operator=(const iterator_base &RHS)
iterator insert(const ValueT &Val)
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
iterator_base & operator--()
Increment and decrement operators.
const_iterator find(const KeyT &Key) const
RangePair equal_range(const KeyT &K)
iterator_base< SparseMultiSet * > iterator
iterator getHead(const KeyT &Key)
Return the head and tail of the subset's list, otherwise returns end().
const ValueT * const_pointer
iterator getTail(const KeyT &Key)
iterator_base & operator++()
iterator_base operator++(int)
iterator_base< const SparseMultiSet * > const_iterator
super::value_type value_type
void setUniverse(unsigned U)
pointer operator->() const
int unlink(const char *path);
iterator find(const KeyT &Key)
const_iterator end() const
reference operator*() const
iterator_base operator--(int)
super::difference_type difference_type
void eraseAll(const KeyT &K)
iterator findIndex(unsigned Idx)
unsigned count(const KeyT &Key) const
#define LLVM_DELETED_FUNCTION
**iterator erase(iterator I)
iterator_base(const iterator_base &RHS)
std::iterator< std::bidirectional_iterator_tag, ValueT > super
bool operator!=(const iterator_base &RHS) const
const ValueT & const_reference
bool operator==(const iterator_base &RHS) const
Comparison operators.
std::pair< iterator, iterator > RangePair
void *calloc(size_t count, size_t size);