/*++

Copyright (C) Microsoft Corporation, 1993 - 1998

Module Name:

    queue.c

Abstract:

   Creates a simple Queue that works in Kernel Mode.

Author:

    Robbie Harris (Hewlett-Packard) 22-May-1998

Environment:

    Kernel mode

Revision History :

--*/
#include "pch.h"

void Queue_Create(Queue *pQueue, int size)
{
    if (!pQueue)
    {
        ParDump(PARERRORS, ("Queue_Create: Queue is Bad"));
        return;
    }

    if (pQueue->theArray)
        Queue_Delete(pQueue);
        
    pQueue->theArray = (UCHAR *)ExAllocatePool(NonPagedPool, size);
    pQueue->max      = size;
    pQueue->head     = pQueue->tail = 0;
}

BOOLEAN Queue_Delete(Queue *pQueue)
{
    if (!pQueue)
    {
        return FALSE;
    }

    if (pQueue->theArray) {
    
        ExFreePool(pQueue->theArray);
        pQueue->theArray = NULL;
    }
    
    pQueue->head = 0;
    pQueue->tail = 0;
    pQueue->max  = 0;
    // NOTE: This can come back to haunt you!
    pQueue = 0;
    
    return TRUE;
}

BOOLEAN Queue_Dequeue(Queue *pQueue, PUCHAR data)
{
    // Validity of pQueue is checked in Queue_IsEmpty proc. 
    if (Queue_IsEmpty(pQueue))
    {
        ParDump(PARERRORS, ("Queue_Dequeue: Queue is Empty"));
        return FALSE;
    }

    *data = pQueue->theArray[pQueue->head++];
    return TRUE;
}

BOOLEAN Queue_Enqueue(Queue *pQueue, UCHAR data)
{
    // Validity of pQueue is checked in Queue_IsFull proc. 
    if (Queue_IsFull(pQueue)) {
    
        ParDump(PARERRORS, ("Queue_Enqueue: Queue is full. Data is lost"));
        return FALSE;
    
    } else {
        pQueue->theArray[pQueue->tail++] = data;
    }

    return TRUE;
}

/* Return TRUE if we were able to free some space in the Queue
*/
BOOLEAN Queue_GarbageCollect(Queue *pQueue)
{
    int     iListSize;
    int     i;

    if (!pQueue)
    {
        ParDump(PARERRORS, ("Queue_GarbageCollect: Queue is Bad"));
        return FALSE;
    }

    iListSize = pQueue->tail - pQueue->head;

    // Check to see if there is any free entries
    if (pQueue->head == 0 && pQueue->tail == pQueue->max)
        return FALSE;
         
    for (i = 0; i < iListSize; i++) {
    
        pQueue->theArray[i] = pQueue->theArray[pQueue->head+i];
    }

    pQueue->head = 0;
    pQueue->tail = iListSize;

    return TRUE;
}

//============================================================================
// NAME:    HPKQueue::IsEmpty()
//  
// PARAMETERS: None
//
// RETURNS: True is Queue is empty or doesn't exist.  Otherwise False.
//
//============================================================================
BOOLEAN Queue_IsEmpty(Queue *pQueue)
{
    if (!pQueue)
    {
        ParDump(PARERRORS, ("Queue_IsEmpty: Queue is Bad"));
        return TRUE;
    }

    if (pQueue->theArray) {
    
        return ((BOOLEAN) (pQueue->head == pQueue->tail));
    }
    ParDump(PARERRORS, ("Queue_IsEmpty: Queue->theArray is Bad"));
    return TRUE;
}

//============================================================================
// NAME:    HPKQueue::IsFull()
//  
// PARAMETERS: None
//
// RETURNS: True is Queue is full or doesn't exist.  Otherwise False.
//
//============================================================================
BOOLEAN Queue_IsFull(Queue *pQueue)
{
    if (!pQueue)
    {
        ParDump(PARERRORS, ("Queue_IsFull: Queue is Bad"));
        return TRUE;
    }

    if (pQueue->theArray) {
    
        if (pQueue->tail == pQueue->max)
            return !(Queue_GarbageCollect(pQueue));

        return FALSE;
    }
    ParDump(PARERRORS, ("Queue_IsFull: Queue->theArray is Bad"));
    return TRUE;
}