gem5  v21.1.0.2
circular_queue.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017-2018 ARM Limited
3  * All rights reserved
4  *
5  * The license below extends only to copyright in the software and shall
6  * not be construed as granting a license to any other intellectual
7  * property including but not limited to intellectual property relating
8  * to a hardware implementation of the functionality of the software
9  * licensed hereunder. You may use the software subject to the license
10  * terms below provided that you ensure that this notice is replicated
11  * unmodified and in its entirety in all distributions of the software,
12  * modified or unmodified, in source code or in binary form.
13  *
14  * Redistribution and use in source and binary forms, with or without
15  * modification, are permitted provided that the following conditions are
16  * met: redistributions of source code must retain the above copyright
17  * notice, this list of conditions and the following disclaimer;
18  * redistributions in binary form must reproduce the above copyright
19  * notice, this list of conditions and the following disclaimer in the
20  * documentation and/or other materials provided with the distribution;
21  * neither the name of the copyright holders nor the names of its
22  * contributors may be used to endorse or promote products derived from
23  * this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #ifndef __BASE_CIRCULAR_QUEUE_HH__
39 #define __BASE_CIRCULAR_QUEUE_HH__
40 
41 #include <cassert>
42 #include <cstddef>
43 #include <cstdint>
44 #include <iterator>
45 #include <type_traits>
46 #include <vector>
47 
48 namespace gem5
49 {
50 
68 template <typename T>
70 {
71  protected:
73 
76  const size_t _capacity;
77  size_t _size = 0;
78  size_t _head = 1;
79 
84  public:
85  struct iterator
86  {
87  public:
88  CircularQueue* _cq = nullptr;
89  size_t _idx = 0;
90 
94  iterator(CircularQueue* cq, size_t idx) : _cq(cq), _idx(idx) {}
95  iterator() = default;
96 
103  using value_type = T;
104  using difference_type = std::ptrdiff_t;
106  using const_reference = const value_type&;
107  using pointer = value_type*;
108  using const_pointer = const value_type*;
109  using iterator_category = std::random_access_iterator_tag; // end of api_base_utils
111 
115  static_assert(std::is_same<reference, T&>::value,
116  "reference type is not assignable as required");
117 
121  iterator(const iterator& it) : _cq(it._cq), _idx(it._idx) {}
122 
126  iterator&
127  operator=(const iterator& it)
128  {
129  _cq = it._cq;
130  _idx = it._idx;
131  return *this;
132  }
133 
142  bool
144  {
145  return _cq != nullptr && _cq->isValidIdx(_idx);
146  }
147 
157  bool
158  operator==(const iterator& that) const
159  {
160  return _cq == that._cq && _idx == that._idx;
161  }
162 
170  bool operator!=(const iterator& that) { return !(*this == that); }
171 
177  reference
179  {
180  // This has to be dereferenceable.
181  return (*_cq)[_idx];
182  }
183 
188  operator*() const
189  {
190  // This has to be dereferenceable.
191  return (*_cq)[_idx];
192  }
193 
200  pointer operator->() { return &**this; }
201 
205  const_pointer operator->() const { return &**this; }
206 
212  iterator&
214  {
215  ++_idx;
216  return *this;
217  }
218 
224  iterator
226  {
227  iterator t = *this;
228  ++*this;
229  return t;
230  }
231 
237  public:
243  iterator&
245  {
246  /* this has to be decrementable. */
247  assert(_cq && _idx > _cq->head());
248  --_idx;
249  return *this;
250  }
251 
257  iterator
259  {
260  iterator t = *this;
261  --*this;
262  return t;
263  }
264 
270  iterator&
272  {
273  _idx += t;
274  return *this;
275  }
276 
280  iterator&
282  {
283  assert(_cq && _idx >= _cq->head() + t);
284  _idx -= t;
285  return *this;
286  }
287 
293  iterator
295  {
296  iterator ret(*this);
297  return ret += t;
298  }
299 
303  friend iterator
305  {
306  iterator ret = it;
307  return ret += t;
308  }
309 
315  iterator
317  {
318  iterator ret(*this);
319  return ret -= t;
320  }
321 
325  friend iterator
327  {
328  iterator ret = it;
329  return ret -= t;
330  }
331 
339  operator-(const iterator& that)
340  {
341  return (ssize_t)_idx - (ssize_t)that._idx;
342  }
343 
350  template<typename Idx>
351  typename std::enable_if_t<std::is_integral<Idx>::value, reference>
352  operator[](const Idx& index)
353  {
354  return *(*this + index);
355  }
356 
362  bool
363  operator<(const iterator& that) const
364  {
365  return _idx < that._idx;
366  }
367 
371  bool operator>(const iterator& that) const { return !(*this <= that); }
372 
376  bool operator>=(const iterator& that) const { return !(*this < that); }
377 
381  bool operator<=(const iterator& that) const { return !(that < *this); }
382 
386  size_t idx() const { return _idx; }
387  };
388 
389  public:
393  template <typename Idx>
394  typename std::enable_if_t<std::is_integral<Idx>::value, reference>
395  operator[](const Idx& index)
396  {
397  assert(index >= 0);
398  return data[index % _capacity];
399  }
400 
401  template <typename Idx>
402  typename std::enable_if_t<std::is_integral<Idx>::value, const_reference>
403  operator[](const Idx& index) const
404  {
405  assert(index >= 0);
406  return data[index % _capacity];
407  }
408 
412  explicit CircularQueue(size_t size=0) : data(size), _capacity(size) {}
413 
422  void
424  {
425  _head = 1;
426  _size = 0;
427  }
428 
432  bool
433  isValidIdx(size_t idx) const
434  {
435  return _head <= idx && idx < (_head + _size);
436  }
437 
441  reference front() { return (*this)[head()]; }
442 
446  reference back() { return (*this)[tail()]; }
447 
451  size_t head() const { return _head; }
452 
456  size_t tail() const { return _head + _size - 1; }
457 
461  size_t capacity() const { return _capacity; }
462 
466  size_t size() const { return _size; }
467 
476  void
477  pop_front(size_t num_elem=1)
478  {
479  assert(num_elem <= size());
480  _head += num_elem;
481  _size -= num_elem;
482  }
483 
489  void
491  {
492  assert(!empty());
493  --_size;
494  }
495 
501  void
503  {
504  advance_tail();
505  back() = val;
506  }
507 
514  void
516  {
517  if (full())
518  ++_head;
519  else
520  ++_size;
521  }
522 
531  void
533  {
534  size_t remaining = _capacity - _size;
535  if (len > remaining) {
536  size_t overflow = len - remaining;
537  _head += overflow;
538  len -= overflow;
539  }
540  _size += len;
541  }
542 
548  bool empty() const { return _size == 0; }
549 
558  bool full() const { return _size == _capacity; }
559 
565  iterator begin() { return iterator(this, _head); }
566 
567  /* TODO: This should return a const_iterator. */
571  iterator
572  begin() const
573  {
574  return iterator(const_cast<CircularQueue*>(this), _head);
575  }
576 
580  iterator end() { return iterator(this, tail() + 1); }
581 
585  iterator
586  end() const
587  {
588  return iterator(const_cast<CircularQueue*>(this), tail() + 1);
589  }
590 
592  iterator getIterator(size_t idx) { return iterator(this, idx); }
593 };
594 
595 } // namespace gem5
596 
597 #endif /* __BASE_CIRCULARQUEUE_HH__ */
gem5::CircularQueue::iterator::idx
size_t idx() const
OutputIterator has no extra requirements.
Definition: circular_queue.hh:386
gem5::CircularQueue::back
reference back()
Definition: circular_queue.hh:446
gem5::ArmISA::len
Bitfield< 18, 16 > len
Definition: misc_types.hh:444
gem5::CircularQueue::advance_tail
void advance_tail()
Increases the tail by one.
Definition: circular_queue.hh:515
gem5::CircularQueue::iterator::operator+=
iterator & operator+=(const difference_type &t)
RandomAccessIterator requirements.
Definition: circular_queue.hh:271
gem5::CircularQueue::data
std::vector< T > data
Definition: circular_queue.hh:72
gem5::CircularQueue::iterator::operator+
friend iterator operator+(const difference_type &t, iterator &it)
Definition: circular_queue.hh:304
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::CircularQueue::iterator::difference_type
std::ptrdiff_t difference_type
Definition: circular_queue.hh:104
gem5::CircularQueue::advance_tail
void advance_tail(size_t len)
Increases the tail by a specified number of steps.
Definition: circular_queue.hh:532
gem5::CircularQueue::iterator::operator!=
bool operator!=(const iterator &that)
Inequality operator.
Definition: circular_queue.hh:170
gem5::CircularQueue::iterator::operator--
iterator & operator--()
ForwardIterator The multipass guarantee is provided by the reliance on _idx.
Definition: circular_queue.hh:244
gem5::CircularQueue::iterator::operator*
reference operator*()
Dereference operator.
Definition: circular_queue.hh:178
gem5::CircularQueue< Tick >::const_reference
typename std::vector< Tick >::const_reference const_reference
Definition: circular_queue.hh:75
gem5::CircularQueue::isValidIdx
bool isValidIdx(size_t idx) const
Test if the index is in the range of valid elements.
Definition: circular_queue.hh:433
sc_dt::overflow
static void overflow(double &c, const scfx_params &params, bool &o_flag)
Definition: sc_fxnum.cc:459
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:775
gem5::CircularQueue::iterator::operator-
difference_type operator-(const iterator &that)
Difference operator.
Definition: circular_queue.hh:339
gem5::CircularQueue::iterator::_idx
size_t _idx
Definition: circular_queue.hh:89
std::vector
STL vector class.
Definition: stl.hh:37
gem5::CircularQueue::iterator::iterator
iterator(const iterator &it)
Trait reference type iterator satisfies OutputIterator, therefore reference must be T&.
Definition: circular_queue.hh:121
gem5::CircularQueue::push_back
void push_back(typename std::vector< T >::value_type val)
Pushes an element at the end of the queue.
Definition: circular_queue.hh:502
gem5::CircularQueue::full
bool full() const
Is the queue full? A queue is full if the head is the 0^{th} element and the tail is the (size-1)^{th...
Definition: circular_queue.hh:558
gem5::CircularQueue::iterator::operator*
const_reference operator*() const
Definition: circular_queue.hh:188
gem5::CircularQueue::iterator::operator=
iterator & operator=(const iterator &it)
Definition: circular_queue.hh:127
gem5::CircularQueue::iterator::operator--
iterator operator--(int)
Post-decrement operator.
Definition: circular_queue.hh:258
gem5::CircularQueue::iterator::iterator
iterator(CircularQueue *cq, size_t idx)
Definition: circular_queue.hh:94
gem5::CircularQueue::operator[]
std::enable_if_t< std::is_integral< Idx >::value, const_reference > operator[](const Idx &index) const
Definition: circular_queue.hh:403
gem5::CircularQueue::iterator::operator-=
iterator & operator-=(const difference_type &t)
Definition: circular_queue.hh:281
gem5::CircularQueue::end
iterator end() const
Definition: circular_queue.hh:586
gem5::CircularQueue::flush
void flush()
Remove all the elements in the queue.
Definition: circular_queue.hh:423
gem5::CircularQueue::iterator::iterator
iterator()=default
gem5::CircularQueue::tail
size_t tail() const
Definition: circular_queue.hh:456
gem5::CircularQueue::size
size_t size() const
Definition: circular_queue.hh:466
gem5::CircularQueue::iterator
Iterator to the circular queue.
Definition: circular_queue.hh:85
gem5::CircularQueue::iterator::operator->
pointer operator->()
Dereference operator.
Definition: circular_queue.hh:200
gem5::CircularQueue::begin
iterator begin() const
Definition: circular_queue.hh:572
gem5::CircularQueue::iterator::operator[]
std::enable_if_t< std::is_integral< Idx >::value, reference > operator[](const Idx &index)
Index operator.
Definition: circular_queue.hh:352
gem5::CircularQueue::iterator::operator>
bool operator>(const iterator &that) const
Definition: circular_queue.hh:371
gem5::CircularQueue::operator[]
std::enable_if_t< std::is_integral< Idx >::value, reference > operator[](const Idx &index)
Definition: circular_queue.hh:395
gem5::CircularQueue::begin
iterator begin()
Iterators.
Definition: circular_queue.hh:565
gem5::CircularQueue::iterator::operator<
bool operator<(const iterator &that) const
Comparisons.
Definition: circular_queue.hh:363
gem5::CircularQueue::front
reference front()
Definition: circular_queue.hh:441
gem5::CircularQueue::_capacity
const size_t _capacity
Definition: circular_queue.hh:76
gem5::CircularQueue::iterator::operator>=
bool operator>=(const iterator &that) const
Definition: circular_queue.hh:376
gem5::CircularQueue::iterator::dereferenceable
bool dereferenceable() const
Test dereferenceability.
Definition: circular_queue.hh:143
gem5::ArmISA::t
Bitfield< 5 > t
Definition: misc_types.hh:70
gem5::CircularQueue::iterator::const_reference
const value_type & const_reference
Definition: circular_queue.hh:106
gem5::CircularQueue::iterator::_cq
CircularQueue * _cq
Definition: circular_queue.hh:88
gem5::CircularQueue::iterator::operator++
iterator & operator++()
Pre-increment operator.
Definition: circular_queue.hh:213
gem5::CircularQueue::iterator::pointer
value_type * pointer
Definition: circular_queue.hh:107
gem5::CircularQueue< Tick >::reference
typename std::vector< Tick >::reference reference
Definition: circular_queue.hh:74
gem5::CircularQueue::iterator::const_pointer
const value_type * const_pointer
Definition: circular_queue.hh:108
gem5::CircularQueue::iterator::operator+
iterator operator+(const difference_type &t)
Addition operator.
Definition: circular_queue.hh:294
gem5::CircularQueue::iterator::value_type
T value_type
Iterator Traits.
Definition: circular_queue.hh:103
gem5::CircularQueue::iterator::operator-
friend iterator operator-(const difference_type &t, iterator &it)
Definition: circular_queue.hh:326
gem5::CircularQueue::pop_front
void pop_front(size_t num_elem=1)
Circularly increase the head pointer.
Definition: circular_queue.hh:477
gem5::CircularQueue::pop_back
void pop_back()
Circularly decrease the tail pointer.
Definition: circular_queue.hh:490
gem5::CircularQueue::empty
bool empty() const
Is the queue empty?
Definition: circular_queue.hh:548
gem5::CircularQueue::CircularQueue
CircularQueue(size_t size=0)
Definition: circular_queue.hh:412
gem5::CircularQueue::head
size_t head() const
Definition: circular_queue.hh:451
gem5::CircularQueue::end
iterator end()
Definition: circular_queue.hh:580
gem5::CircularQueue::iterator::operator->
const_pointer operator->() const
Definition: circular_queue.hh:205
gem5::CircularQueue::iterator::operator<=
bool operator<=(const iterator &that) const
Definition: circular_queue.hh:381
gem5::CircularQueue::capacity
size_t capacity() const
Definition: circular_queue.hh:461
gem5::CircularQueue::_size
size_t _size
Definition: circular_queue.hh:77
gem5::CircularQueue::getIterator
iterator getIterator(size_t idx)
Return an iterator to an index in the queue.
Definition: circular_queue.hh:592
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::CircularQueue::iterator::operator==
bool operator==(const iterator &that) const
InputIterator.
Definition: circular_queue.hh:158
gem5::CircularQueue::_head
size_t _head
Definition: circular_queue.hh:78
gem5::CircularQueue::iterator::reference
value_type & reference
Definition: circular_queue.hh:105
gem5::CircularQueue
Circular queue.
Definition: circular_queue.hh:69
gem5::CircularQueue::iterator::operator++
iterator operator++(int)
Post-increment operator.
Definition: circular_queue.hh:225
gem5::CircularQueue::iterator::iterator_category
std::random_access_iterator_tag iterator_category
Definition: circular_queue.hh:109
gem5::CircularQueue::iterator::operator-
iterator operator-(const difference_type &t)
Substraction operator.
Definition: circular_queue.hh:316

Generated on Tue Sep 21 2021 12:24:55 for gem5 by doxygen 1.8.17