Queue< T > Class Template Reference

Templated Queue for arbitrary objects. More...

#include <queue.h>

Classes
class	Iterator
	Minimal forward iterator You can use this iterator to iterate the queue like a normal STL container. It only supports forward iteration, since the queue is single linked. More...

Public Member Functions
	Queue (unsigned link_index, NextFunc get_link=default_get_link)
	Constructor.
bool	enqueue (T &item)
	Enqueues the provided item at the end of the queue. If the element is already contained in the queue, false will be returned.
bool	insertFirst (T &item)
	insert a new element at the start of the queue
bool	insertAfter (T &after, T &item)
	Insert a new element item into the list after an element after. Returns false if item is already in the/a list or after is not in this list.
T *	next (T &item)
	return the next element of a given one or nullptr if the end is reached
bool	is_empty ()
	Return whether or not the queue is empty.
T *	dequeue ()
	Removes the first element in the queue and returns it.
T *	remove (T *that)
	Removes a given element from the queue and returns that element, or nullptr if it was not present.
Queue< T >::Iterator	begin ()
	get an iterator to the first element
Queue< T >::Iterator	end ()
	get an iterator that marks the end of list
T *	first ()
	get the first element of the queue
T *	last ()
	get the last element of the queue

Private Types
typedef T **(*	NextFunc) (T &, unsigned)
	Type definition for the get_link function.

Static Private Member Functions
static T **	default_get_link (T &obj, unsigned link_index)
	Default get_link implementation returns a pointer to the link_index'th element of the next-pointer array. The function assumes a member named "queue_link" that stores the next-pointer.

Private Attributes
unsigned	link_index
	Queue-local index into the next-pointer array.
const NextFunc	get_link
T *	head
T *	tail

Detailed Description

template<class T>
class Queue< T >

Templated Queue for arbitrary objects.

Queue is implemented by a head-object (Queue<T>) and next-pointers embedded in the queued objects. This Queue supports arrays of next-pointers by passing an index into the constructor identifying the index into the next-pointer array. By passing a different get_link function into the constructor, the member name of the next-pointer array can be changed and objects can be contained in different independent queues.

Constructor & Destructor Documentation

Queue()

template<class T >

Queue< T >::Queue ( unsigned  link_index, NextFunc  get_link = default_get_link  )

inlineexplicit

Constructor.

Parameters

[in]	link_index	denotes the index into the next-pointer array to be used by this queue-object
[in]	get_link	A function pointer to the get_link, i.e. a function which returns a pointer to the next-pointer of an element in the Queue.

Member Function Documentation

default_get_link()

template<class T >

static T ** Queue< T >::default_get_link ( T &  obj, unsigned  link_index  )

inlinestaticprivate

Default get_link implementation returns a pointer to the link_index'th element of the next-pointer array. The function assumes a member named "queue_link" that stores the next-pointer.

If your object contains a queue_link member you can just ignore this function and the get_link keyword argument of the constructor.

Parameters

[in]	obj	the object which link should be accessed.
[in]	link_index	the index within the array.

Returns

A pointer to the next-object pointer.

dequeue()

template<class T >

T * Queue< T >::dequeue ( )

inline

Removes the first element in the queue and returns it.

Note

Does not update the tail-pointer

Returns

Pointer to the removed item or nullptr if the queue was empty.

enqueue()

template<class T >

bool Queue< T >::enqueue ( T &  item )

inline

Enqueues the provided item at the end of the queue. If the element is already contained in the queue, false will be returned.

Parameters

[in]

item

element to be appended (enqueued).

Returns

false if the element already was enqueued (and nothing was done) or not (and it is now enqueued, then true)

insertAfter()

template<class T >

bool Queue< T >::insertAfter ( T &  after, T &  item  )

inline

Insert a new element item into the list after an element after. Returns false if item is already in the/a list or after is not in this list.

Parameters

[in]	after	the element after which the new one should be inserted
[in]	item	the new element to add

Returns

true if successful, false if item was in the list or after was not

insertFirst()

template<class T >

bool Queue< T >::insertFirst ( T &  item )

inline

insert a new element at the start of the queue

Parameters

[in]

item

the new item to add

Returns

true if successful, false if item was already in the queue

is_empty()

template<class T >

bool Queue< T >::is_empty ( )

inline

Return whether or not the queue is empty.

Returns

True if the queue is empty or false otherwise.

next()

template<class T >

T * Queue< T >::next ( T &  item )

inline

return the next element of a given one or nullptr if the end is reached

Parameters

[in]

item

the current item

Returns

the next element or nullptr if the end is reached or the item is not in this list

remove()

template<class T >

T * Queue< T >::remove ( T *  that )

inline

Removes a given element from the queue and returns that element, or nullptr if it was not present.

Returns

pointer to the removed element, or nullptr if not present

Member Data Documentation

get_link

template<class T >

const NextFunc Queue< T >::get_link

private

Function pointer to the get_link function, called whenever the next pointer array is referenced

head

template<class T >

T* Queue< T >::head

private

head points to the first element (the one returned on first dequeue). Can be nullptr if the queue is empty.

tail

template<class T >

T* Queue< T >::tail

private

tail points to the last element (the one last added). Is only valid if head != nullptr

---

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

• interrupt/gate.h
• object/queue.h