/*

 * queue.c

 *

 * Copyright(c) 1998 - 2010 Texas Instruments. All rights reserved.      

 * All rights reserved.      

 * 

 * This program and the accompanying materials are made available under the 

 * terms of the Eclipse Public License v1.0 or BSD License which accompanies

 * this distribution. The Eclipse Public License is available at

 * http://www.eclipse.org/legal/epl-v10.html and the BSD License is as below.                                   

 *                                                                       

 * Redistribution and use in source and binary forms, with or without    

 * modification, are permitted provided that the following conditions    

 * are met:                                                              

 *                                                                       

 *  * Redistributions of source code must retain the above copyright     

 *    notice, this list of conditions and the following disclaimer.      

 *  * Redistributions in binary form must reproduce the above copyright  

 *    notice, this list of conditions and the following disclaimer in    

 *    the documentation and/or other materials provided with the         

 *    distribution.                                                      

 *  * Neither the name Texas Instruments nor the names of its            

 *    contributors may be used to endorse or promote products derived    

 *    from this software without specific prior written permission.      

 *                                                                       

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS   

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT     

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT  

 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT      

 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT   

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/** \file   queue.c 

 *  \brief  This module provides generic queueing services, including enqueue, dequeue

 *            and requeue of any object that contains TQueNodeHdr in its structure.                                  

 *

 *  \see    queue.h

 */

#define __FILE_ID__  FILE_ID_130

#include "report.h"

#include "queue.h"

/* Queue structure */

typedef struct 

{

    TQueNodeHdr tHead;          /* The queue first node */

    TI_UINT32   uCount;         /* Current number of nodes in queue */

    TI_UINT32   uLimit;         /* Upper limit of nodes in queue */

    TI_UINT32   uMaxCount;      /* Maximum uCount value (for debug) */

    TI_UINT32   uOverflow;      /* Number of overflow occurences - couldn't insert node (for debug) */

    TI_UINT32   uNodeHeaderOffset; /* Offset of NodeHeader field from the entry of the queued item */

	TI_HANDLE   hOs;

	TI_HANDLE   hReport; 

} TQueue;	

/*

 *              INTERNAL  FUNCTIONS 

 *        =============================== 

 */

/*

 *  InsertNode():  Insert new node between pPrev and pNext 

 */

static INLINE void InsertNode( TQueNodeHdr *pNode, TQueNodeHdr *pPrev, TQueNodeHdr *pNext)

{

	pNext->pPrev = pNode;

	pNode->pNext = pNext;

	pNode->pPrev = pPrev;

	pPrev->pNext = pNode;

}

/*

 *  RemoveNode():  Remove node from between pPrev and pNext 

 */

static INLINE void RemoveNode( TQueNodeHdr *pPrev, TQueNodeHdr *pNext)

{

	pNext->pPrev = pPrev;

	pPrev->pNext = pNext;

}

/*

 *  AddToHead():  Add node to queue head (last in queue) 

 */

static INLINE void AddToHead( TQueNodeHdr *pNode, TQueNodeHdr *pListHead)

{

	InsertNode (pNode, pListHead, pListHead->pNext);

}

/*

 *  AddToTail():  Add node to queue tail (first in queue)

 */

static INLINE void AddToTail( TQueNodeHdr *pNode, TQueNodeHdr *pListHead)

{

	InsertNode( pNode, pListHead->pPrev, pListHead );

}

/*

 *  DelFromTail():  Delete node from queue tail (first in queue)

 */

static INLINE void DelFromTail (TQueNodeHdr *pNode)

{

	RemoveNode (pNode->pPrev, pNode->pNext);

}

/*

 *              EXTERNAL  FUNCTIONS 

 *        =============================== 

 */

/** 

 * \fn     que_Create 

 * \brief  Create a queue. 

 * 

 * Allocate and init a queue object.

 * 

 * \note    

 * \param  hOs               - Handle to Os Abstraction Layer

 * \param  hReport           - Handle to report module

 * \param  uLimit            - Maximum items to store in queue

 * \param  uNodeHeaderOffset - Offset of NodeHeader field from the entry of the queued item.

 * \return Handle to the allocated queue 

 * \sa     que_Destroy

 */ 

TI_HANDLE que_Create (TI_HANDLE hOs, TI_HANDLE hReport, TI_UINT32 uLimit, TI_UINT32 uNodeHeaderOffset)

{

	TQueue *pQue;

	/* allocate queue module */

	pQue = os_memoryAlloc (hOs, sizeof(TQueue),MemoryNormal);

	if (!pQue)

	{

		WLAN_OS_REPORT (("Error allocating the Queue Module\n"));

		return NULL;

	}

    os_memoryZero (hOs, pQue, sizeof(TQueue));

	/* Intialize the queue header */

    pQue->tHead.pNext = pQue->tHead.pPrev = &pQue->tHead;

	/* Set the Queue parameters */

    pQue->hOs               = hOs;

    pQue->hReport           = hReport;

	pQue->uLimit            = uLimit;

	pQue->uNodeHeaderOffset = uNodeHeaderOffset;

	return (TI_HANDLE)pQue;

}

/** 

 * \fn     que_Destroy

 * \brief  Destroy the queue. 

 * 

 * Free the queue memory.

 * 

 * \note   The queue's owner should first free the queued items!

 * \param  hQue - The queue object

 * \return TI_OK on success or TI_NOK on failure 

 * \sa     que_Create

 */ 

TI_STATUS que_Destroy (TI_HANDLE hQue)

{

    TQueue *pQue = (TQueue *)hQue;

    /* Alert if the queue is unloaded before it was cleared from items */

    if (pQue->uCount)

    {

        TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Destroy() Queue Not Empty!!");

    }

    /* free Queue object */

	os_memoryFree (pQue->hOs, pQue, sizeof(TQueue));

    return TI_OK;

}

/** 

 * \fn     que_Init 

 * \brief  Init required handles 

 * 

 * Init required handles.

 * 

 * \note    

 * \param  hQue      - The queue object

 * \param  hOs       - Handle to Os Abstraction Layer

 * \param  hReport   - Handle to report module

 * \return TI_OK on success or TI_NOK on failure  

 * \sa     

 */ 

TI_STATUS que_Init (TI_HANDLE hQue, TI_HANDLE hOs, TI_HANDLE hReport)

{

	TQueue *pQue = (TQueue *)hQue;

    pQue->hOs = hOs;

    pQue->hReport = hReport;

	return TI_OK;

}

/** 

 * \fn     que_Enqueue

 * \brief  Enqueue an item 

 * 

 * Enqueue an item at the queue's head (last in queue).

 * 

 * \note   

 * \param  hQue   - The queue object

 * \param  hItem  - Handle to queued item

 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow

 * \sa     que_Dequeue, que_Requeue

 */ 

TI_STATUS que_Enqueue (TI_HANDLE hQue, TI_HANDLE hItem)

{

	TQueue      *pQue = (TQueue *)hQue;

    TQueNodeHdr *pQueNodeHdr;  /* the Node-Header in the given item */

    /* Check queue limit */

	if(pQue->uCount < pQue->uLimit)

	{

        /* Find NodeHeader in the given item */

        pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset);

            /* Check that (pNext == NULL) --> Sanity check that this item was dequeued before */

            if (pQueNodeHdr->pNext)

            {

                TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Enqueue(): Trying to enqueue an item that wasn't dequeued!");

                return TI_NOK;

            }

        /* Enqueue item and increment items counter */

		AddToHead (pQueNodeHdr, &pQue->tHead);

		pQue->uCount++;

        #ifdef TI_DBG

		    if (pQue->uCount > pQue->uMaxCount)

            {

                pQue->uMaxCount = pQue->uCount;

            }

            TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Enqueue(): Enqueued Successfully\n");

        #endif

        return TI_OK;

	}

	/* 

	 *  Queue is overflowed, return TI_NOK.

	 */

#ifdef TI_DBG

	pQue->uOverflow++;

TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING , "que_Enqueue(): Queue Overflow\n");

#endif

	return TI_NOK;

}

/** 

 * \fn     que_Dequeue

 * \brief  Dequeue an item 

 * 

 * Dequeue an item from the queue's tail (first in queue).

 * 

 * \note   

 * \param  hQue - The queue object

 * \return pointer to dequeued item or NULL if queue is empty

 * \sa     que_Enqueue, que_Requeue

 */ 

TI_HANDLE que_Dequeue (TI_HANDLE hQue)

{

    TQueue   *pQue = (TQueue *)hQue;

	TI_HANDLE hItem;

    if (pQue->uCount)

    {

        /* Queue is not empty, take packet from the queue tail */

        /* find pointer to the node entry */

         hItem = (TI_HANDLE)((TI_UINT8*)pQue->tHead.pPrev - pQue->uNodeHeaderOffset); 

         DelFromTail (pQue->tHead.pPrev);    /* remove node from the queue */

         pQue->uCount--;

         #ifdef TI_DBG

            /* Clear the pNext so we can do a sanity check when enqueuing this structre in the future */

            ((TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset))->pNext = NULL;

         #endif

         return (hItem);

    }

	/* Queue is empty */    

    TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Dequeue(): Queue is empty\n");

    return NULL;

}

/** 

 * \fn     que_Requeue

 * \brief  Requeue an item 

 * 

 * Requeue an item at the queue's tail (first in queue).

 * 

 * \note   

 * \param  hQue   - The queue object

 * \param  hItem  - Handle to queued item

 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow

 * \sa     que_Enqueue, que_Dequeue

 */ 

TI_STATUS que_Requeue (TI_HANDLE hQue, TI_HANDLE hItem)

{

    TQueue      *pQue = (TQueue *)hQue;

    TQueNodeHdr *pQueNodeHdr;  /* the NodeHeader in the given item */

    /* 

	 *  If queue's limits not exceeded add the packet to queue's tail and return TI_OK 

	 */

    if (pQue->uCount < pQue->uLimit)

	{

        /* Find NodeHeader in the given item */

        pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset);

        /* Enqueue item and increment items counter */

		AddToTail (pQueNodeHdr, &pQue->tHead);

		pQue->uCount++;

#ifdef TI_DBG

		if (pQue->uCount > pQue->uMaxCount)

			pQue->uMaxCount = pQue->uCount;

TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Requeue(): Requeued successfully\n");

#endif

		return TI_OK;

    }

	/* 

	 *  Queue is overflowed, return TI_NOK.

	 *  Note: This is not expected in the current design, since Tx packet may be requeued

	 *          only right after it was dequeued in the same context so the queue can't be full.

	 */

#ifdef TI_DBG

    pQue->uOverflow++;

TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR , "que_Requeue(): Queue Overflow\n");

#endif

    return TI_NOK;

}

/** 

 * \fn     que_Size

 * \brief  Return queue size 

 * 

 * Return number of items in queue.

 * 

 * \note   

 * \param  hQue - The queue object

 * \return TI_UINT32 - the items count

 * \sa     

 */ 

TI_UINT32 que_Size (TI_HANDLE hQue)

{

    TQueue *pQue = (TQueue *)hQue;

    return (pQue->uCount);

}

/** 

 * \fn     que_Print

 * \brief  Print queue status

 * 

 * Print the queue's parameters (not the content).

 * 

 * \note   

 * \param  hQue - The queue object

 * \return void

 * \sa     

 */ 

#ifdef TI_DBG

void que_Print(TI_HANDLE hQue)

{

	TQueue *pQue = (TQueue *)hQue;

    WLAN_OS_REPORT(("que_Print: Count=%u MaxCount=%u Limit=%u Overflow=%u NodeHeaderOffset=%u Next=0x%x Prev=0x%x\n",

                    pQue->uCount, pQue->uMaxCount, pQue->uLimit, pQue->uOverflow, 

                    pQue->uNodeHeaderOffset, pQue->tHead.pNext, pQue->tHead.pPrev));

}

#endif /* TI_DBG */