519 lines
8.4 KiB
C++
519 lines
8.4 KiB
C++
|
|
/*++
|
|
|
|
Copyright (c) 1998-2000 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
drqueue.h
|
|
|
|
Abstract:
|
|
|
|
Generic Queue Template Class
|
|
|
|
Author:
|
|
|
|
Tad Brockway 10/99
|
|
|
|
Revision History:
|
|
|
|
--*/
|
|
|
|
#ifndef __DRQUEUE_H__
|
|
#define __DRQUEUE_H__
|
|
|
|
#include "drobject.h"
|
|
#include "atrcapi.h"
|
|
|
|
|
|
///////////////////////////////////////////////////////////////
|
|
//
|
|
// DrQueue
|
|
//
|
|
// Template Queue Class
|
|
//
|
|
|
|
template <class T> class DrQueue : public DrObject
|
|
{
|
|
|
|
private:
|
|
|
|
typedef struct _QUEUEELEMENT {
|
|
T data;
|
|
_QUEUEELEMENT *next;
|
|
_QUEUEELEMENT *prev;
|
|
} QUEUEELEMENT, *PQUEUEELEMENT;
|
|
|
|
//
|
|
// Queue Pointers
|
|
//
|
|
PQUEUEELEMENT _head;
|
|
PQUEUEELEMENT _tail;
|
|
|
|
//
|
|
// Lock
|
|
//
|
|
CRITICAL_SECTION _cs;
|
|
|
|
//
|
|
// Number of elements in the queue.
|
|
//
|
|
ULONG _count;
|
|
|
|
public:
|
|
|
|
//
|
|
// Constructor/Destructor
|
|
//
|
|
DrQueue();
|
|
~DrQueue();
|
|
|
|
//
|
|
// Initialize.
|
|
//
|
|
DWORD Initialize();
|
|
|
|
//
|
|
// Peek at the next element in the queue without dequeueing.
|
|
//
|
|
BOOL PeekNextEntry(T &data);
|
|
|
|
//
|
|
// Grab the next element out of the queue.
|
|
//
|
|
BOOL Dequeue(T &data);
|
|
|
|
//
|
|
// Add an element to the queue in FIFO fashion.
|
|
//
|
|
BOOL Enqueue(T &data);
|
|
|
|
//
|
|
// Requeue an element at the tail of the queue in LIFO fashion.
|
|
//
|
|
BOOL Requeue(T &data);
|
|
|
|
// Returns the number of elements in the queue.
|
|
//
|
|
ULONG GetCount() {
|
|
return _count;
|
|
}
|
|
|
|
//
|
|
// Lock/Unlock the queue.
|
|
//
|
|
VOID Lock() {
|
|
EnterCriticalSection(&_cs);
|
|
}
|
|
VOID Unlock() {
|
|
LeaveCriticalSection(&_cs);
|
|
}
|
|
|
|
//
|
|
// Return the class name.
|
|
//
|
|
virtual DRSTRING ClassName() { return TEXT("DrQueue"); }
|
|
};
|
|
|
|
|
|
|
|
///////////////////////////////////////////////////////////////
|
|
//
|
|
// DrQueue Inline Methods
|
|
//
|
|
|
|
template <class T>
|
|
inline DrQueue<T>::DrQueue()
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Constructor
|
|
|
|
Arguments:
|
|
|
|
initialSize - Initial number of elements in the queue.
|
|
|
|
Return Value:
|
|
|
|
NA
|
|
|
|
--*/
|
|
{
|
|
DC_BEGIN_FN("DrQueue::DrQueue");
|
|
|
|
//
|
|
// Initialize the queue pointers.
|
|
//
|
|
_tail = NULL;
|
|
_head = NULL;
|
|
|
|
//
|
|
// Initialize the queue count.
|
|
//
|
|
_count = 0;
|
|
|
|
//
|
|
// Not valid until initialized.
|
|
//
|
|
SetValid(FALSE);
|
|
|
|
CleanUp:
|
|
|
|
DC_END_FN();
|
|
}
|
|
|
|
template <class T>
|
|
inline DrQueue<T>::~DrQueue()
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Destructor
|
|
|
|
Arguments:
|
|
|
|
NA
|
|
|
|
Return Value:
|
|
|
|
NA
|
|
|
|
--*/
|
|
{
|
|
DC_BEGIN_FN("DrQueue::~DrQueue");
|
|
|
|
T element;
|
|
|
|
//
|
|
// Clean up the queue nodes.
|
|
//
|
|
while (Dequeue(element));
|
|
|
|
//
|
|
// Clean up the critical section.
|
|
//
|
|
if (IsValid()) {
|
|
DeleteCriticalSection(&_cs);
|
|
}
|
|
|
|
DC_END_FN();
|
|
}
|
|
|
|
|
|
template <class T>
|
|
inline DWORD DrQueue<T>::Initialize()
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Initialize
|
|
|
|
Arguments:
|
|
|
|
Return Value:
|
|
|
|
ERROR_SUCCESS on success. Otherwise, an error code is returned.
|
|
|
|
--*/
|
|
{
|
|
DC_BEGIN_FN("DrQueue::Initialize");
|
|
|
|
DWORD result;
|
|
|
|
//
|
|
// Initialize the critical section.
|
|
//
|
|
__try {
|
|
InitializeCriticalSection(&_cs);
|
|
SetValid(TRUE);
|
|
result = ERROR_SUCCESS;
|
|
}
|
|
__except(EXCEPTION_EXECUTE_HANDLER) {
|
|
result = GetExceptionCode();
|
|
}
|
|
|
|
DC_END_FN();
|
|
|
|
return result;
|
|
}
|
|
|
|
template <class T>
|
|
inline BOOL DrQueue<T>::PeekNextEntry(T &data)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Peek at the next entry in the queue without dequeueing.
|
|
|
|
Arguments:
|
|
|
|
data - Data for next entry in the queue
|
|
|
|
Return Value:
|
|
|
|
NA
|
|
|
|
--*/
|
|
{
|
|
BOOL result;
|
|
|
|
DC_BEGIN_FN("DrQueue::PeekNextEntry");
|
|
|
|
//
|
|
// Make sure we are valid.
|
|
//
|
|
ASSERT(IsValid());
|
|
result = IsValid();
|
|
|
|
if (result) {
|
|
Lock();
|
|
|
|
if (_tail == NULL) {
|
|
ASSERT(_head == NULL);
|
|
ASSERT(_count == 0);
|
|
result = FALSE;
|
|
}
|
|
else {
|
|
data = _tail->data;
|
|
result = TRUE;
|
|
}
|
|
|
|
Unlock();
|
|
}
|
|
|
|
DC_END_FN();
|
|
return result;
|
|
}
|
|
|
|
template <class T>
|
|
inline BOOL DrQueue<T>::Dequeue(T &data)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Grab the next element out of the queue.
|
|
|
|
Arguments:
|
|
|
|
data - Data for the next item in the queue.
|
|
|
|
Return Value:
|
|
|
|
TRUE if there was an element in the queue to be dequeued.
|
|
|
|
--*/
|
|
{
|
|
BOOL result;
|
|
PQUEUEELEMENT element;
|
|
|
|
DC_BEGIN_FN("DrQueue::Dequeue");
|
|
|
|
//
|
|
// Make sure we are valid.
|
|
//
|
|
ASSERT(IsValid());
|
|
result = IsValid();
|
|
|
|
if (result) {
|
|
Lock();
|
|
|
|
if (_tail == NULL) {
|
|
ASSERT(_head == NULL);
|
|
ASSERT(_count == 0);
|
|
result = FALSE;
|
|
}
|
|
else {
|
|
data = _tail->data;
|
|
|
|
element = _tail;
|
|
_tail = _tail->prev;
|
|
|
|
//
|
|
// If the list is now empty.
|
|
//
|
|
if (_tail == NULL) {
|
|
ASSERT(_count == 1);
|
|
_head = NULL;
|
|
}
|
|
else {
|
|
_tail->next = NULL;
|
|
}
|
|
delete element;
|
|
_count--;
|
|
result = TRUE;
|
|
}
|
|
|
|
Unlock();
|
|
}
|
|
|
|
DC_END_FN();
|
|
return result;
|
|
}
|
|
|
|
template <class T>
|
|
inline BOOL DrQueue<T>::Enqueue(T &data)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Add an element to the queue in FIFO fashion.
|
|
|
|
Arguments:
|
|
|
|
data - Data to be added to the queue.
|
|
|
|
Return Value:
|
|
|
|
TRUE if the new element could be successfully queued. FALSE,
|
|
otherwise. If FALSE is returned then GetLastError() can be
|
|
used to retrieve the exact error code.
|
|
|
|
--*/
|
|
{
|
|
BOOL result;
|
|
|
|
DC_BEGIN_FN("DrQueue::Enqueue");
|
|
|
|
//
|
|
// Make sure we are valid.
|
|
//
|
|
ASSERT(IsValid());
|
|
result = IsValid();
|
|
|
|
if (result) {
|
|
|
|
PQUEUEELEMENT element = new QUEUEELEMENT;
|
|
Lock();
|
|
if (element != NULL) {
|
|
element->data = data;
|
|
element->next = _head;
|
|
element->prev = NULL;
|
|
|
|
//
|
|
// If the list is empy.
|
|
//
|
|
if (_head == NULL) {
|
|
ASSERT(_count == 0);
|
|
ASSERT(_tail == NULL);
|
|
_head = element;
|
|
_tail = element;
|
|
}
|
|
else {
|
|
_head->prev = element;
|
|
_head = element;
|
|
}
|
|
_count++;
|
|
result = TRUE;
|
|
}
|
|
else {
|
|
TRC_NRM((TB, _T("Alloc failed.")));
|
|
SetLastError(ERROR_NOT_ENOUGH_MEMORY);
|
|
result = FALSE;
|
|
}
|
|
Unlock();
|
|
}
|
|
|
|
DC_END_FN();
|
|
return result;
|
|
}
|
|
|
|
template <class T>
|
|
inline BOOL DrQueue<T>::Requeue(T &data)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Requeue an element at the tail of the queue in LIFO fashion.
|
|
|
|
Arguments:
|
|
|
|
data - Data to be requeued.
|
|
|
|
Return Value:
|
|
|
|
TRUE if the new element could be successfully queued. FALSE,
|
|
otherwise. If FALSE is returned then GetLastError() can be
|
|
used to retrieve the exact error code.
|
|
|
|
--*/
|
|
{
|
|
BOOL result;
|
|
|
|
DC_BEGIN_FN("DrQueue::Requeue");
|
|
|
|
//
|
|
// Make sure we are valid.
|
|
//
|
|
ASSERT(IsValid());
|
|
result = IsValid();
|
|
|
|
if (result) {
|
|
|
|
PQUEUEELEMENT element = new QUEUEELEMENT;
|
|
Lock();
|
|
|
|
if (element != NULL) {
|
|
|
|
element->data = data;
|
|
element->next = NULL;
|
|
element->prev = _tail;
|
|
|
|
//
|
|
// If the queue is empty.
|
|
//
|
|
if (_tail == NULL) {
|
|
ASSERT(_count == 0);
|
|
_head = element;
|
|
_tail = element;
|
|
}
|
|
else {
|
|
_tail->next = element;
|
|
_tail = element;
|
|
}
|
|
|
|
_count++;
|
|
result = TRUE;
|
|
}
|
|
else {
|
|
TRC_NRM((TB, _T("Alloc failed.")));
|
|
SetLastError(ERROR_NOT_ENOUGH_MEMORY);
|
|
result = FALSE;
|
|
}
|
|
Unlock();
|
|
}
|
|
|
|
DC_END_FN();
|
|
|
|
return result;
|
|
}
|
|
|
|
|
|
|
|
|
|
#endif
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|