TLLinearQueue< T, _OP > Class Template Reference

#warning linear (non-priority) 2-ended queue template. (Fifo and Stack.) More...

#include <tllinearqueue.h>

Collaboration diagram for TLLinearQueue< T, _OP >:

[legend]List of all members.

Public Member Functions
	TLLinearQueue (size_t _chunk_size, int _keep_old=4, const _OP &op=_OP())
	Construct empty linear queue.
	~TLLinearQueue ()
	Destructor: cleans up queue.
bool	IsEmpty () const
	Is the queue empty? O(1) (constant) time.
size_t	NElem () const
	Get the number of elements in the queue. O(1) (constant) time.
void	clear ()
	Clear the whole list (removing all elements).
T *	head ()
	Get element at the head end (last) of the queue.
T *	tail ()
	Get element at the tail end (first) of the queue.
void	PushTail (const T &e)
	Append entry at the tail end (=first) of the queue.
void	PushHead (const T &e)
	Append entry at the head end (=last) of the queue.
int	PopTail (T *re=NULL)
	Remove element from the tail of the list.
int	PopHead (T *re=NULL)
	Remove element from the head of the list.
Public Attributes
_OP	OP
	These are the operators...
Protected Attributes
size_t	chunk_size
	Number of elements per chunk.
int	keep_old
	Number of old unused chunks to keep around.
LinkedList< Chunk >	clist
	List of chunks.
size_t	nelem
	Total number of elements in the queue.
size_t	first_idx
size_t	last_idx
LinkedList< Chunk >	old_list
	List of empty (unused) chunks.
int	old_nents
	Number of chunks in old_list.
Private Member Functions
Chunk *	_AllocChunk ()
	Allocate a new chunk on the heap.
void	_FreeChunk (Chunk *c)
	Free an indivitual chunk. May not be in any list.
void	_FreeAllOld ()
	Free all chunks in the old_list.
void	_Add2Cache (Chunk *c)
Chunk *	_NewChunkCache ()
	Get a mew chunk from the cache or (if there is non) by allocation.
void	_AddChunkTail ()
void	_AddChunkHead ()
void	_PopChunkTail ()
	Remove a chunk from the tail end.
void	_PopChunkHead ()
	Remove a chunk from the head end.
void	_DoPopTail ()
	Internally used by PopTail().
void	_DoPopHead ()
	Internally used by PopHead().
	TLLinearQueue (const TLLinearQueue &)
	Do not use.
void	operator= (const TLLinearQueue &)
	Do not use.

---

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
class TLLinearQueue< T, _OP >

#warning linear (non-priority) 2-ended queue template. (Fifo and Stack.)

Author:

Wolfgang Wieser ] wwieser (a) gmx <*> de [

This is a linear (non-priority) 2-ended queue.

The linear (2-ended) queue allows efficient appending to either ends of the queue (head and tail) and removing elements on either ends. The primary use is a fifo but it can as well be used as stack.

To use it as a fiFo, feed data into the queue using PushHead() and remove it from the queue using PopTail().

To use is as stack, push data using PushHead() and pop it using PopHead().

Of course, consequently swapping head and tail keeps the functionality.

All operations of the queue (push to either ends, pop from either ends, get number of elements, check if empty) are performed in O(1) constant time. Only the clear() operation (removing all elements) requires O(n) time.

The class is implemented efficienty as only access to the ends of the list is needed. The list elements are packed into chunks of size chunk_size. (entries) to conserve memory and keep allocation overhead down. Additionally, (at most) keep_old number of empty chunks are held ready fo re-use.

NOTE: TLLinearQueue can be relied on to never move any stored object. This means that if you get a pointer to a stored object, this pointer remains a valid pointer to that object as long as it is in the queue.

Thread safety: The complete queue must be protected by a mutex for all "write" operations.

As for the type T, you can use all types you can also use with TLBtree or TLArray. Only the ass(), ini() and clr() as well as the (de)allocation "operators" are needed. Also, the pdt flag should be supplied.

This class is NOT C++-safe.

Definition at line 80 of file tllinearqueue.h.

---

Constructor & Destructor Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLLinearQueue< T, _OP >::TLLinearQueue (  const TLLinearQueue< T, _OP > &   )  [private]

Do not use.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLLinearQueue< T, _OP >::TLLinearQueue (  size_t  _chunk_size, int  _keep_old = 4, const _OP &  op = _OP() )  [inline]

Construct empty linear queue. Parameters: _chunk_size  is the number of elements to store per chunk. (New chunks are allocated when more elements are stored). _keep_old  is the number of old (empty) chunks to keep around so it can be re-used an that no allocation has to be used if a (new) chunk is needed. op:  operator template prototype. Definition at line 267 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLLinearQueue< T, _OP >::~TLLinearQueue (   )  [inline]

Destructor: cleans up queue. Definition at line 274 of file tllinearqueue.h.

---

Member Function Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_Add2Cache (  Chunk *  c  )  [inline, private]

Add passed chunk to the cache of old chunks. Purge old chunk if we have too many of them. Definition at line 195 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_PopChunkHead(), and TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_PopChunkTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_AddChunkHead (   )  [inline, private]

Add a chunk at the head end in order to be able to append a further element at the head. Definition at line 224 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PushHead().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_AddChunkTail (   )  [inline, private]

Add a chunk at the tail end in order to be able to append a further element at the tail. Definition at line 220 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PushTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> Chunk* TLLinearQueue< T, _OP >::_AllocChunk (   )  [inline, private]

Allocate a new chunk on the heap. Definition at line 175 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_NewChunkCache().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_DoPopHead (   )  [inline, private]

Internally used by PopHead(). Definition at line 243 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PopHead().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_DoPopTail (   )  [inline, private]

Internally used by PopTail(). Definition at line 235 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::clear(), and TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PopTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_FreeAllOld (   )  [inline, private]

Free all chunks in the old_list. Definition at line 186 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::~TLLinearQueue().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_FreeChunk (  Chunk *  c  )  [inline, private]

Free an indivitual chunk. May not be in any list. Definition at line 182 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_Add2Cache(), and TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_FreeAllOld().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> Chunk* TLLinearQueue< T, _OP >::_NewChunkCache (   )  [inline, private]

Get a mew chunk from the cache or (if there is non) by allocation. Definition at line 207 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_AddChunkHead(), and TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_AddChunkTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_PopChunkHead (   )  [inline, private]

Remove a chunk from the head end. Definition at line 231 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_DoPopHead().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::_PopChunkTail (   )  [inline, private]

Remove a chunk from the tail end. Definition at line 228 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::_DoPopTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::clear (   )  [inline]

Clear the whole list (removing all elements). Todo: tllinearqueue.h:clear: This could be made more efficient. (especially if OP.pdt==0) Definition at line 286 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::~TLLinearQueue().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> T* TLLinearQueue< T, _OP >::head (   )  [inline]

Get element at the head end (last) of the queue. Runtime is O(1) (constant). Returns NULL if the queue is empty. The returned element may (of course) be modified. Definition at line 303 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> bool TLLinearQueue< T, _OP >::IsEmpty (   )  const [inline]

Is the queue empty? O(1) (constant) time. Definition at line 278 of file tllinearqueue.h. Referenced by TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::clear(), TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PopHead(), and TLLinearQueue< NamespaceInfo::SymbolEntryB, TLDefaultOperators_CDT< NamespaceInfo::SymbolEntryB > >::PopTail().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLLinearQueue< T, _OP >::NElem (   )  const [inline]

Get the number of elements in the queue. O(1) (constant) time. Definition at line 282 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::operator= (  const TLLinearQueue< T, _OP > &   )  [private]

Do not use.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> int TLLinearQueue< T, _OP >::PopHead (  T *  re = NULL  )  [inline]

Remove element from the head of the list. Removes element from the head. If re is non-NULL, a copy of the element is stored there, first (using OP.ass()). Runtime is O(1) (constant). Returns 1 if the queue was empty, 0 on success. Definition at line 371 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> int TLLinearQueue< T, _OP >::PopTail (  T *  re = NULL  )  [inline]

Remove element from the tail of the list. Removes element from the tail. If re is non-NULL, a copy of the element is stored there, first (using OP.ass()). Runtime is O(1) (constant). Returns 1 if the queue was empty, 0 on success. Definition at line 353 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::PushHead (  const T &  e  )  [inline]

Append entry at the head end (=last) of the queue. The element e is (of course) copied to be stored in the queue. Runtime is O(1) (constant). Definition at line 337 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLLinearQueue< T, _OP >::PushTail (  const T &  e  )  [inline]

Append entry at the tail end (=first) of the queue. The element e is (of course) copied to be stored in the queue. Runtime is O(1) (constant). Definition at line 324 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> T* TLLinearQueue< T, _OP >::tail (   )  [inline]

Get element at the tail end (first) of the queue. Runtime is O(1) (constant). Returns NULL if the queue is empty. \ The returned element may (of course) be modified. Definition at line 314 of file tllinearqueue.h.

---

Member Data Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLLinearQueue< T, _OP >::chunk_size [protected]

Number of elements per chunk. Definition at line 141 of file tllinearqueue.h. Referenced by TLLinearQueue< T, _OP >::Iterator::operator++().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> LinkedList<Chunk> TLLinearQueue< T, _OP >::clist [protected]

List of chunks. Definition at line 143 of file tllinearqueue.h. Referenced by TLLinearQueue< T, _OP >::Iterator::_assign().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLLinearQueue< T, _OP >::first_idx [protected]

Index into ent[] of first chunk (tail). NOTE: first_idx is the index of the tail element; this value is in range 0..chunk_size-1. A value of 0 means that a new chunk must be allocated when adding to the tail (as e.g. initially after construction). Definition at line 158 of file tllinearqueue.h. Referenced by TLLinearQueue< T, _OP >::Iterator::_assign().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> int TLLinearQueue< T, _OP >::keep_old [protected]

Number of old unused chunks to keep around. Definition at line 142 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLLinearQueue< T, _OP >::last_idx [protected]

Index into ent[] of last chunk (head). NOTE: last_idx is the index of the head element; this value is in range 0..chunk_size-1. A value of chunk_size-1 means that a new chunk must be allocated when adding to the head (as e.g. initially after construction). Definition at line 164 of file tllinearqueue.h. Referenced by TLLinearQueue< T, _OP >::Iterator::operator++().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLLinearQueue< T, _OP >::nelem [protected]

Total number of elements in the queue. Definition at line 144 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> LinkedList<Chunk> TLLinearQueue< T, _OP >::old_list [protected]

List of empty (unused) chunks. Definition at line 166 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> int TLLinearQueue< T, _OP >::old_nents [protected]

Number of chunks in old_list. Definition at line 167 of file tllinearqueue.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> _OP TLLinearQueue< T, _OP >::OP

These are the operators... Definition at line 171 of file tllinearqueue.h.

---

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

• /ray/src/lib/tl/tllinearqueue.h

---