Circular queue. More...

#include <circular_queue.hh>

Inheritance diagram for CircularQueue< T >:

Classes
struct	iterator
	Iterator to the circular queue. More...

Public Member Functions
	CircularQueue (uint32_t size=0)

void	flush ()
	Remove all the elements in the queue. More...

bool	isValidIdx (size_t idx) const
	Test if the index is in the range of valid elements. More...

bool	isValidIdx (size_t idx, uint32_t round) const
	Test if the index is in the range of valid elements. More...

reference	front ()

reference	back ()

uint32_t	head () const

uint32_t	tail () const

size_t	capacity () const

uint32_t	size () const

uint32_t	moduloAdd (uint32_t s1, uint32_t s2) const

uint32_t	moduloSub (uint32_t s1, uint32_t s2) const

void	pop_front (size_t num_elem=1)
	Circularly increase the head pointer. More...

void	pop_back ()
	Circularly decrease the tail pointer. More...

void	push_back (typename Base::value_type val)
	Pushes an element at the end of the queue. More...

void	advance_tail ()
	Increases the tail by one. More...

void	advance_tail (uint32_t len)
	Increases the tail by a specified number of steps. More...

bool	empty () const
	Is the queue empty? More...

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} element, or if the head is the n^{th} element and the tail the (n-1)^{th} element. More...

iterator	begin ()
	Iterators. More...

iterator	begin () const

iterator	end ()

iterator	end () const

iterator	getIterator (size_t idx)
	Return an iterator to an index in the vector. More...

Protected Types
using	Base = std::vector< T >

Protected Member Functions
void	increase (uint32_t &v, size_t delta=1)

void	decrease (uint32_t &v)

Static Protected Member Functions
static uint32_t	moduloAdd (uint32_t op1, uint32_t op2, uint32_t size)
	General modular addition. More...

static uint32_t	moduloSub (uint32_t op1, uint32_t op2, uint32_t size)
	General modular subtraction. More...

static int32_t	sub (uint32_t op1, uint32_t op2, uint32_t size)

Protected Attributes
const uint32_t	_capacity

uint32_t	_head

uint32_t	_tail

uint32_t	_empty

uint32_t	_round
	Counter for how many times the tail wraps around. More...

Additional Inherited Members
Private Attributes inherited from std::vector< T >
T	item
	Dummy Item. More...

Detailed Description

template<typename T>
class CircularQueue< T >

Circular queue.

Circular queue implemented on top of a standard vector. Instead of using a sentinel entry, we use a boolean to distinguish the case in which the queue is full or empty. Thus, a circular queue is represented by the 5-tuple (Capacity, IsEmpty?, Head, Tail, Round) Where:

Capacity is the size of the underlying vector.
IsEmpty? can be T or F.
Head is the index in the vector of the first element of the queue.
Tail is the index in the vector of the last element of the queue.
Round is the counter of how many times the Tail has wrapped around. A queue is empty when Head == (Tail + 1 mod Capacity) && IsEmpty?. Conversely, a queue if full when Head == (Tail + 1 mod Capacity) && !IsEmpty?. Comments may show depictions of the underlying vector in the following format: '|' delimit the 'cells' of the underlying vector. '-' represents an element of the vector that is out-of-bounds of the circular queue, while 'o' represents and element that is inside the bounds. The characters '[' and ']' are added to mark the entries that hold the head and tail of the circular queue respectively. E.g.:
Empty queues of capacity 4: (4,T,1,0,_): |-]|[-|-|-| (4,T,3,2): |-|-|-]|[-|
Full queues of capacity 4: (4,F,1,0,_): |o]|[o|o|o| (4,F,3,2): |o|o|o]|[o|
Queues of capacity 4 with 2 elements: (4,F,0,1,_): |[o|o]|-|-| (4,F,3,0): |o]|-|-|[o|

The Round number is only relevant for checking validity of indices, therefore it will be omitted or shown as '_'

Template Parameters

T	Type of the elements in the queue

Definition at line 86 of file circular_queue.hh.

Member Typedef Documentation

◆ Base

template<typename T >

using CircularQueue< T >::Base = std::vector<T>

protected

Definition at line 89 of file circular_queue.hh.

Member Function Documentation

◆ decrease()

template<typename T >

void CircularQueue< T >::decrease ( uint32_t & v )

inlineprotected

Definition at line 134 of file circular_queue.hh.

Referenced by CircularQueue< T >::iterator::operator--(), and CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::pop_back().

◆ getIterator()

template<typename T >

iterator CircularQueue< T >::getIterator ( size_t idx )

inline

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 the storage, in which case the PTE wraps up and becomes _round + 1

Definition at line 812 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::insertLoad(), and Prefetcher::PIF::notifyRetiredInst().

◆ increase()

template<typename T >

void CircularQueue< T >::increase	(	uint32_t &	v,
		size_t	delta = `1`
	)

inlineprotected

Definition at line 129 of file circular_queue.hh.

Referenced by CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::advance_tail(), and CircularQueue< T >::iterator::operator++().

◆ isValidIdx() [1/2]

template<typename T >

bool CircularQueue< T >::isValidIdx ( size_t idx ) const

inline

Test if the index is in the range of valid elements.

Definition at line 547 of file circular_queue.hh.

Referenced by CircularQueue< T >::iterator::dereferenceable(), and CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::getIterator().

◆ isValidIdx() [2/2]

template<typename T >

bool CircularQueue< T >::isValidIdx	(	size_t	idx,
		uint32_t	round
	)		const

inline

Test if the index is in the range of valid elements.

The round counter is used to disambiguate aliasing.

Definition at line 571 of file circular_queue.hh.

◆ moduloAdd() [1/2]

template<typename T >

static uint32_t CircularQueue< T >::moduloAdd	(	uint32_t	op1,
		uint32_t	op2,
		uint32_t	size
	)

inlinestaticprotected

General modular addition.

Definition at line 107 of file circular_queue.hh.

Referenced by CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::end(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::getIterator(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::increase(), LSQUnit< Impl >::insertStore(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::moduloAdd(), and CircularQueue< T >::iterator::operator+=().

◆ moduloAdd() [2/2]

template<typename T >

uint32_t CircularQueue< T >::moduloAdd	(	uint32_t	s1,
		uint32_t	s2
	)		const

inline

Definition at line 643 of file circular_queue.hh.

◆ moduloSub() [1/2]

template<typename T >

static uint32_t CircularQueue< T >::moduloSub	(	uint32_t	op1,
		uint32_t	op2,
		uint32_t	size
	)

inlinestaticprotected

General modular subtraction.

Definition at line 114 of file circular_queue.hh.

Referenced by CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::moduloSub(), and CircularQueue< T >::iterator::operator-=().

◆ moduloSub() [2/2]

template<typename T >

uint32_t CircularQueue< T >::moduloSub	(	uint32_t	s1,
		uint32_t	s2
	)		const

inline

Definition at line 648 of file circular_queue.hh.

◆ sub()

template<typename T >

static int32_t CircularQueue< T >::sub	(	uint32_t	op1,
		uint32_t	op2,
		uint32_t	size
	)

inlinestaticprotected

Definition at line 121 of file circular_queue.hh.

Referenced by CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::moduloSub(), and CircularQueue< T >::iterator::operator-().

Member Data Documentation

◆ _capacity

template<typename T >

const uint32_t CircularQueue< T >::_capacity

protected

Definition at line 92 of file circular_queue.hh.

◆ _empty

template<typename T >

uint32_t CircularQueue< T >::_empty

protected

Definition at line 95 of file circular_queue.hh.

◆ _head

template<typename T >

uint32_t CircularQueue< T >::_head

protected

Definition at line 93 of file circular_queue.hh.

◆ _round

template<typename T >

uint32_t CircularQueue< T >::_round

protected

Counter for how many times the tail wraps around.

Some parts of the code rely on getting the past the end iterator, and expect to use it after inserting on the tail. To support this without ambiguity, we need the round number to guarantee that it did not become a before-the-beginning iterator.

Definition at line 103 of file circular_queue.hh.

Referenced by CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::advance_tail(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::begin(), CircularQueue< T >::iterator::decrementable(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::end(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::flush(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::getIterator(), CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::isValidIdx(), and CircularQueue< Prefetcher::STeMS::RegionMissOrderBufferEntry >::pop_back().

◆ _tail

template<typename T >

uint32_t CircularQueue< T >::_tail

protected

Definition at line 94 of file circular_queue.hh.

The documentation for this class was generated from the following file:

base/circular_queue.hh

Classes

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

template<typename T> class CircularQueue< T >

Member Typedef Documentation

◆ Base

Member Function Documentation

◆ decrease()

◆ getIterator()

◆ increase()

◆ isValidIdx() [1/2]

◆ isValidIdx() [2/2]

◆ moduloAdd() [1/2]

◆ moduloAdd() [2/2]

◆ moduloSub() [1/2]

◆ moduloSub() [2/2]

◆ sub()

Member Data Documentation

◆ _capacity

◆ _empty

◆ _head

◆ _round

◆ _tail

template<typename T>
class CircularQueue< T >