From 2ea459e6cdae27e2d071593becf98ef86556fc92 Mon Sep 17 00:00:00 2001 From: Hoa Nguyen Date: Thu, 20 Aug 2020 00:08:07 -0700 Subject: [PATCH] base: Tag API methods and variables to circular_queue.hh Change-Id: I0e6a89a3e3d14a6d269277e1ffeea1ed49d8e1e4 Signed-off-by: Hoa Nguyen Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/32962 Reviewed-by: Daniel Carvalho Maintainer: Bobby R. Bruce Tested-by: kokoro --- src/base/circular_queue.hh | 229 ++++++++++++++++++++++++++++++++----- 1 file changed, 202 insertions(+), 27 deletions(-) diff --git a/src/base/circular_queue.hh b/src/base/circular_queue.hh index b2d4cb59a..e7c8f62a1 100644 --- a/src/base/circular_queue.hh +++ b/src/base/circular_queue.hh @@ -77,6 +77,10 @@ * * The Round number is only relevant for checking validity of indices, * therefore it will be omitted or shown as '_' + * + * @tparam T Type of the elements in the queue + * + * @ingroup api_base_utils */ template class CircularQueue : private std::vector @@ -154,10 +158,18 @@ class CircularQueue : private std::vector uint32_t _round; public: + /** + * @ingroup api_base_utils + */ iterator(CircularQueue* cq, uint32_t idx, uint32_t round) : _cq(cq), _idx(idx), _round(round) {} - /** Iterator Traits */ + /** + * Iterator Traits + * + * @ingroup api_base_utils + * @{ + */ using value_type = T; using difference_type = std::ptrdiff_t; using reference = value_type&; @@ -165,6 +177,7 @@ class CircularQueue : private std::vector using pointer = value_type*; using const_pointer = const value_type*; using iterator_category = std::random_access_iterator_tag; + /** @} */ // end of api_base_utils /** Trait reference type * iterator satisfies OutputIterator, therefore reference @@ -172,11 +185,20 @@ class CircularQueue : private std::vector static_assert(std::is_same::value, "reference type is not assignable as required"); + /** + * @ingroup api_base_utils + */ iterator() : _cq(nullptr), _idx(0), _round(0) { } + /** + * @ingroup api_base_utils + */ iterator(const iterator& it) : _cq(it._cq), _idx(it._idx), _round(it._round) {} + /** + * @ingroup api_base_utils + */ iterator& operator=(const iterator& it) { @@ -186,9 +208,13 @@ class CircularQueue : private std::vector return *this; } + /** + * @ingroup api_base_utils + */ ~iterator() { _cq = nullptr; _idx = 0; _round = 0; } - /** Test dereferenceability. + /** + * Test dereferenceability. * An iterator is dereferenceable if it is pointing to a non-null * circular queue, it is not the past-the-end iterator and the * index is a valid index to that queue. PTE test is required to @@ -200,6 +226,8 @@ class CircularQueue : private std::vector * Sometimes, though, users will get the PTE iterator and expect it * to work after growing the buffer on the tail, so we have to * check if the iterator is still PTE. + * + * @ingroup api_base_utils */ bool dereferenceable() const @@ -209,11 +237,14 @@ class CircularQueue : private std::vector /** InputIterator. */ - /** Equality operator. + /** + * Equality operator. * Two iterators must point to the same, possibly null, circular * queue and the same element on it, including PTE, to be equal. * In case the clients the the PTE iterator and then grow on the back * and expect it to work, we have to check if the PTE is still PTE + * + * @ingroup api_base_utils */ bool operator==(const iterator& that) const { @@ -221,42 +252,62 @@ class CircularQueue : private std::vector _round == that._round; } - /** Inequality operator. + /** + * Inequality operator. * Conversely, two iterators are different if they both point to * different circular queues or they point to different elements. + * + * @ingroup api_base_utils */ bool operator!=(const iterator& that) { return !(*this == that); } - /** Dereference operator. */ + /** + * Dereference operator. + * + * @ingroup api_base_utils + */ reference operator*() { /* this has to be dereferenceable. */ return (*_cq)[_idx]; } + /** + * @ingroup api_base_utils + */ const_reference operator*() const { /* this has to be dereferenceable. */ return (*_cq)[_idx]; } - /** Dereference operator. + /** + * Dereference operator. * Rely on operator* to check for dereferenceability. + * + * @ingroup api_base_utils */ pointer operator->() { return &((*_cq)[_idx]); } + /** + * @ingroup api_base_utils + */ const_pointer operator->() const { return &((*_cq)[_idx]); } - /** Pre-increment operator. */ + /** + * Pre-increment operator. + * + * @ingroup api_base_utils + */ iterator& operator++() { /* this has to be dereferenceable. */ @@ -266,7 +317,11 @@ class CircularQueue : private std::vector return *this; } - /** Post-increment operator. */ + /** + * Post-increment operator. + * + * @ingroup api_base_utils + */ iterator operator++(int) { @@ -298,7 +353,11 @@ class CircularQueue : private std::vector } public: - /** Pre-decrement operator. */ + /** + * Pre-decrement operator. + * + * @ingroup api_base_utils + */ iterator& operator--() { /* this has to be decrementable. */ @@ -309,10 +368,18 @@ class CircularQueue : private std::vector return *this; } - /** Post-decrement operator. */ + /** + * Post-decrement operator. + * + * @ingroup api_base_utils + */ iterator operator--(int ) { iterator t = *this; --*this; return t; } - /** RandomAccessIterator requirements.*/ + /** + * RandomAccessIterator requirements. + * + * @ingroup api_base_utils + */ iterator& operator+=(const difference_type& t) { assert(_cq); @@ -321,6 +388,9 @@ class CircularQueue : private std::vector return *this; } + /** + * @ingroup api_base_utils + */ iterator& operator-=(const difference_type& t) { assert(_cq); @@ -335,34 +405,51 @@ class CircularQueue : private std::vector return *this; } - /** Addition operator. */ + /** + * Addition operator. + * + * @ingroup api_base_utils + */ iterator operator+(const difference_type& t) { iterator ret(*this); return ret += t; } + /** + * @ingroup api_base_utils + */ friend iterator operator+(const difference_type& t, iterator& it) { iterator ret = it; return ret += t; } - /** Substraction operator. */ + /** + * Substraction operator. + * + * @ingroup api_base_utils + */ iterator operator-(const difference_type& t) { iterator ret(*this); return ret -= t; } + /** + * @ingroup api_base_utils + */ friend iterator operator-(const difference_type& t, iterator& it) { iterator ret = it; return ret -= t; } - /** Difference operator. + /** + * Difference operator. * that + ret == this + * + * @ingroup api_base_utils */ difference_type operator-(const iterator& that) { @@ -375,14 +462,21 @@ class CircularQueue : private std::vector return ret; } - /** Index operator. + /** + * Index operator. * The use of * tests for dereferenceability. + * + * @ingroup api_base_utils */ template typename std::enable_if::value,reference>::type operator[](const Idx& index) { return *(*this + index); } - /** Comparisons. */ + /** + * Comparisons. + * + * @ingroup api_base_utils + */ bool operator<(const iterator& that) const { @@ -391,23 +485,40 @@ class CircularQueue : private std::vector (this->_round == that._round && _idx < that._idx); } + /** + * @ingroup api_base_utils + */ bool operator>(const iterator& that) const { return !(*this <= that); } + /** + * @ingroup api_base_utils + */ bool operator>=(const iterator& that) const { return !(*this < that); } + /** + * @ingroup api_base_utils + */ bool operator<=(const iterator& that) const { return !(that < *this); } - /** OutputIterator has no extra requirements.*/ + /** + * OutputIterator has no extra requirements. + */ size_t idx() const { return _idx; } }; public: + /** + * @ingroup api_base_utils + */ using Base::operator[]; + /** + * @ingroup api_base_utils + */ explicit CircularQueue(uint32_t size = 0) : _capacity(size), _head(1), _tail(0), _empty(true), _round(0) { @@ -419,6 +530,8 @@ class CircularQueue : private std::vector * * Note: This does not actually remove elements from the backing * store. + * + * @ingroup api_base_utils */ void flush() { @@ -428,7 +541,9 @@ class CircularQueue : private std::vector _empty = true; } - /** Test if the index is in the range of valid elements. */ + /** + * Test if the index is in the range of valid elements. + */ bool isValidIdx(size_t idx) const { /* An index is invalid if: @@ -449,7 +564,8 @@ class CircularQueue : private std::vector )) || (_tail < idx && idx < _head)); } - /** Test if the index is in the range of valid elements. + /** + * Test if the index is in the range of valid elements. * The round counter is used to disambiguate aliasing. */ bool isValidIdx(size_t idx, uint32_t round) const @@ -486,12 +602,34 @@ class CircularQueue : private std::vector )); } + /** + * @ingroup api_base_utils + */ reference front() { return (*this)[_head]; } + + /** + * @ingroup api_base_utils + */ reference back() { return (*this)[_tail]; } + + /** + * @ingroup api_base_utils + */ uint32_t head() const { return _head; } + + /** + * @ingroup api_base_utils + */ uint32_t tail() const { return _tail; } + + /** + * @ingroup api_base_utils + */ size_t capacity() const { return _capacity; } + /** + * @ingroup api_base_utils + */ uint32_t size() const { if (_empty) @@ -519,6 +657,8 @@ class CircularQueue : private std::vector * had only one value prior to insertion. * * @params num_elem number of elements to remove + * + * @ingroup api_base_utils */ void pop_front(size_t num_elem = 1) { @@ -530,7 +670,11 @@ class CircularQueue : private std::vector _head = hIt._idx; } - /** Circularly decrease the tail pointer. */ + /** + * Circularly decrease the tail pointer. + * + * @ingroup api_base_utils + */ void pop_back() { assert (!_empty); @@ -540,15 +684,22 @@ class CircularQueue : private std::vector decrease(_tail); } - /** Pushes an element at the end of the queue. */ + /** + * Pushes an element at the end of the queue. + * + * @ingroup api_base_utils + */ void push_back(typename Base::value_type val) { advance_tail(); (*this)[_tail] = val; } - /** Increases the tail by one. + /** + * Increases the tail by one. * Check for wrap-arounds to update the round counter. + * + * @ingroup api_base_utils */ void advance_tail() { @@ -562,9 +713,12 @@ class CircularQueue : private std::vector _empty = false; } - /** Increases the tail by a specified number of steps + /** + * Increases the tail by a specified number of steps * * @param len Number of steps + * + * @ingroup api_base_utils */ void advance_tail(uint32_t len) { @@ -572,13 +726,20 @@ class CircularQueue : private std::vector advance_tail(); } - /** Is the queue empty? */ + /** + * Is the queue empty? + * + * @ingroup api_base_utils + */ bool empty() const { return _empty; } - /** Is the queue full? + /** + * Is the queue full? * A queue is full if the head is the 0^{th} element and the tail is * the (size-1)^{th} element, or if the head is the n^{th} element and * the tail the (n-1)^{th} element. + * + * @ingroup api_base_utils */ bool full() const { @@ -586,7 +747,11 @@ class CircularQueue : private std::vector (_tail + 1 == _head || (_tail + 1 == _capacity && _head == 0)); } - /** Iterators. */ + /** + * Iterators. + * + * @ingroup api_base_utils + */ iterator begin() { if (_empty) @@ -598,6 +763,9 @@ class CircularQueue : private std::vector } /* TODO: This should return a const_iterator. */ + /** + * @ingroup api_base_utils + */ iterator begin() const { if (_empty) @@ -610,6 +778,9 @@ class CircularQueue : private std::vector _round); } + /** + * @ingroup api_base_utils + */ iterator end() { auto poi = moduloAdd(_tail, 1); @@ -619,6 +790,9 @@ class CircularQueue : private std::vector return iterator(this, poi, round); } + /** + * @ingroup api_base_utils + */ iterator end() const { auto poi = moduloAdd(_tail, 1); @@ -628,7 +802,8 @@ class CircularQueue : private std::vector return iterator(const_cast(this), poi, round); } - /** Return an iterator to an index in the vector. + /** + * Return an iterator to an index in the vector. * This poses the problem of round determination. By convention, the round * is picked so that isValidIndex(idx, round) is true. If that is not * possible, then the round value is _round, unless _tail is at the end of -- 2.30.2