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 '_'

Definition at line 82 of file circular_queue.hh.

Member Typedef Documentation

◆ Base

template<typename T>

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

protected

Definition at line 85 of file circular_queue.hh.

Constructor & Destructor Documentation

◆ CircularQueue()

template<typename T>

CircularQueue< T >::CircularQueue ( uint32_t size = 0 )

inlineexplicit

Definition at line 411 of file circular_queue.hh.

Member Function Documentation

◆ advance_tail() [1/2]

template<typename T>

void CircularQueue< T >::advance_tail ( )

inline

Increases the tail by one.

Check for wrap-arounds to update the round counter.

Definition at line 553 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::advance_tail(), LSQUnit< Impl >::insertLoad(), CircularQueue< Tick >::push_back(), and CircleBuf< char >::write().

◆ advance_tail() [2/2]

template<typename T>

void CircularQueue< T >::advance_tail ( uint32_t len )

inline

Increases the tail by a specified number of steps.

Parameters

len	Number of steps

Definition at line 569 of file circular_queue.hh.

◆ back()

template<typename T>

reference CircularQueue< T >::back ( )

inline

Definition at line 490 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::insertLoad(), LSQUnit< Impl >::squash(), and TEST().

◆ begin() [1/2]

template<typename T>

iterator CircularQueue< T >::begin ( )

inline

Iterators.

Definition at line 590 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::checkSnoop(), CircleBuf< char >::peek(), CircularQueue< Tick >::pop_front(), and TEST().

◆ begin() [2/2]

template<typename T>

iterator CircularQueue< T >::begin ( ) const

inline

Definition at line 601 of file circular_queue.hh.

◆ capacity()

template<typename T>

size_t CircularQueue< T >::capacity ( ) const

inline

Definition at line 493 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::drainSanityCheck(), LSQUnit< Impl >::insertLoad(), LSQUnit< Impl >::numFreeLoadEntries(), CircularQueue< T >::iterator::operator+=(), CircularQueue< T >::iterator::operator-(), CircularQueue< T >::iterator::operator-=(), TEST(), CircleBuf< char >::write(), and Fifo< uint8_t >::write().

◆ decrease()

template<typename T>

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

inlineprotected

Definition at line 130 of file circular_queue.hh.

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

◆ empty()

template<typename T>

bool CircularQueue< T >::empty ( ) const

inline

Is the queue empty?

Definition at line 576 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::checkSnoop(), Terminal::console_in(), Terminal::dataAvailable(), CircularQueue< T >::iterator::decrementable(), Terminal::readData(), and TEST().

◆ end() [1/2]

template<typename T>

iterator CircularQueue< T >::end ( )

inline

Definition at line 613 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::begin(), LSQUnit< Impl >::checkSnoop(), LSQUnit< Impl >::checkViolations(), CircularQueue< Tick >::getIterator(), LSQUnit< Impl >::insertStore(), CircularQueue< Tick >::pop_front(), TEST(), and CircleBuf< char >::write().

◆ end() [2/2]

template<typename T>

iterator CircularQueue< T >::end ( ) const

inline

Definition at line 622 of file circular_queue.hh.

◆ flush()

template<typename T>

void CircularQueue< T >::flush ( )

inline

Remove all the elements in the queue.

Note: This does not actually remove elements from the backing store.

Definition at line 423 of file circular_queue.hh.

Referenced by arrayParamIn().

◆ front()

template<typename T>

reference CircularQueue< T >::front ( )

inline

Definition at line 489 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::commitLoad(), LSQUnit< Impl >::commitLoads(), LSQUnit< Impl >::getLoadHeadSeqNum(), LSQUnit< Impl >::getStoreHeadSeqNum(), Prefetcher::SBOOE::notifyFill(), and TEST().

◆ full()

template<typename T>

bool CircularQueue< T >::full ( ) const

inline

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.

Definition at line 583 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::insertLoad(), LSQUnit< Impl >::lqFull(), Prefetcher::SBOOE::notifyFill(), and TEST().

◆ 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 637 of file circular_queue.hh.

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

◆ head()

template<typename T>

uint32_t CircularQueue< T >::head ( ) const

inline

Definition at line 491 of file circular_queue.hh.

Referenced by CircularQueue< T >::iterator::decrementable(), LSQUnit< Impl >::getLoadHead(), LSQUnit< Impl >::getStoreHead(), LSQUnit< Impl >::read(), and TEST().

◆ increase()

template<typename T>

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

inlineprotected

Definition at line 125 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::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 432 of file circular_queue.hh.

Referenced by CircularQueue< T >::iterator::dereferenceable(), and CircularQueue< Tick >::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 455 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 103 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::end(), CircularQueue< Tick >::getIterator(), CircularQueue< Tick >::increase(), LSQUnit< Impl >::insertStore(), CircularQueue< Tick >::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 505 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 110 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::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 510 of file circular_queue.hh.

◆ pop_back()

template<typename T>

void CircularQueue< T >::pop_back ( )

inline

Circularly decrease the tail pointer.

Definition at line 534 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::squash().

◆ pop_front()

template<typename T>

void CircularQueue< T >::pop_front ( size_t num_elem = 1 )

inline

Circularly increase the head pointer.

By increasing the head pointer we are removing elements from the begin of the circular queue. Check that the queue is not empty. And set it to empty if it had only one value prior to insertion.

num_elem number of elements to remove

Definition at line 523 of file circular_queue.hh.

Referenced by LSQUnit< Impl >::commitLoad(), CircleBuf< char >::read(), and TEST().

◆ push_back()

template<typename T>

void CircularQueue< T >::push_back ( typename Base::value_type val )

inline

Pushes an element at the end of the queue.

Definition at line 544 of file circular_queue.hh.

Referenced by Prefetcher::SBOOE::notifyFill(), Prefetcher::PIF::notifyRetiredInst(), and TEST().

◆ size()

template<typename T>

uint32_t CircularQueue< T >::size ( ) const

inline

Definition at line 495 of file circular_queue.hh.

Referenced by Terminal::accept(), arrayParamOut(), CircularQueue< Tick >::CircularQueue(), CircularQueue< Tick >::moduloAdd(), CircularQueue< Tick >::moduloSub(), Prefetcher::SBOOE::notifyFill(), CircleBuf< char >::peek(), CircularQueue< Tick >::sub(), TEST(), and Fifo< uint8_t >::write().

◆ sub()

template<typename T>

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

inlinestaticprotected

Definition at line 117 of file circular_queue.hh.

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

◆ tail()

template<typename T>

uint32_t CircularQueue< T >::tail ( ) const

inline

Definition at line 492 of file circular_queue.hh.

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

Member Data Documentation

◆ _capacity

template<typename T>

const uint32_t CircularQueue< T >::_capacity

protected

Definition at line 88 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::capacity(), and CircularQueue< Tick >::decrease().

◆ _empty

template<typename T>

uint32_t CircularQueue< T >::_empty

protected

Definition at line 91 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::empty().

◆ _head

template<typename T>

uint32_t CircularQueue< T >::_head

protected

Definition at line 89 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::front(), and CircularQueue< Tick >::head().

◆ _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 99 of file circular_queue.hh.

Referenced by CircularQueue< T >::iterator::decrementable().

◆ _tail

template<typename T>

uint32_t CircularQueue< T >::_tail

protected

Definition at line 90 of file circular_queue.hh.

Referenced by CircularQueue< Tick >::back(), CircularQueue< Tick >::isValidIdx(), CircularQueue< Tick >::pop_back(), CircularQueue< Tick >::push_back(), and CircularQueue< Tick >::tail().

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

Constructor & Destructor Documentation

◆ CircularQueue()

Member Function Documentation

◆ advance_tail() [1/2]

◆ advance_tail() [2/2]

◆ back()

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ decrease()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ flush()

◆ front()

◆ full()

◆ getIterator()

◆ head()

◆ increase()

◆ isValidIdx() [1/2]

◆ isValidIdx() [2/2]

◆ moduloAdd() [1/2]

◆ moduloAdd() [2/2]

◆ moduloSub() [1/2]

◆ moduloSub() [2/2]

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ size()

◆ sub()

◆ tail()

Member Data Documentation

◆ _capacity

◆ _empty

◆ _head

◆ _round

◆ _tail

template<typename T>
class CircularQueue< T >