src/base/circular_queue.hh

46 #include <iterator>
96      * Some parts of the code rely on getting the past the end iterator, and
99      * a before-the-beginning iterator.
138      * iterator implementation to provide the circular-ness that the
139      * standard std::vector<T>::iterator does not implement.
142      * the iterator if it is valid. 'x' denotes the element pointed to by the
143      * iterator when it is BTB or PTE.
153     struct iterator {
159         iterator(CircularQueue* cq, uint32_t idx, uint32_t round)
172          * iterator satisfies OutputIterator, therefore reference
177         iterator() : _cq(nullptr), _idx(0), _round(0) { }
179         iterator(const iterator& it)
182         iterator&
183         operator=(const iterator& it)
191         ~iterator() { _cq = nullptr; _idx = 0; _round = 0; }
194          * An iterator is dereferenceable if it is pointing to a non-null
195          * circular queue, it is not the past-the-end iterator  and the
198          * - An iterator to the first element of a full queue
200          * - The end() iterator of a full queue
202          * Sometimes, though, users will get the PTE iterator and expect it
204          * check if the iterator is still PTE.
217          * In case the clients the the PTE iterator and then grow on the back
220         bool operator==(const iterator& that) const
230         bool operator!=(const iterator& that)
262         iterator& operator++()
272         iterator
275             iterator t = *this;
287          * An iterator to a non-null circular queue is not-decrementable
289          * and we are talking about the past-the-end iterator. In that case,
290          * the iterator round equals the cq round unless the head is at the
304         iterator& operator--()
315         iterator operator--(int ) { iterator t = *this; --*this; return t; }
318         iterator& operator+=(const difference_type& t)
326         iterator& operator-=(const difference_type& t)
341         iterator operator+(const difference_type& t)
343             iterator ret(*this);
347         friend iterator operator+(const difference_type& t, iterator& it)
349             iterator ret = it;
354         iterator operator-(const difference_type& t)
356             iterator ret(*this);
360         friend iterator operator-(const difference_type& t, iterator& it)
362             iterator ret = it;
369         difference_type operator-(const iterator& that)
389         operator<(const iterator& that) const
397         operator>(const iterator& that) const
400         bool operator>=(const iterator& that) const
403         bool operator<=(const iterator& that) const
468          *            The remaining case means the the iterator is BTB:
592     iterator begin()
597             return iterator(this, _head, _round - 1);
599             return iterator(this, _head, _round);
603     iterator begin() const
608             return iterator(const_cast<CircularQueue*>(this), _head,
611             return iterator(const_cast<CircularQueue*>(this), _head,
615     iterator end()
621         return iterator(this, poi, round);
624     iterator end() const
630         return iterator(const_cast<CircularQueue*>(this), poi, round);
633     /** Return an iterator to an index in the vector.
639     iterator getIterator(size_t idx)
653         return iterator(this, idx, round);