/* * queue.c * * Copyright(c) 1998 - 2010 Texas Instruments. All rights reserved. * All rights reserved. * * 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)); 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; if (pQue) { /* Alert if the queue is unloaded before it was cleared from items */ if (pQue->uCount) { TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING, "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 */ if (pQue) { /* Check queue limit */ if(pQue->uCount < pQue->uLimit) { /* Find NodeHeader in the given item */ pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset); /* Verify that pNext is NULL --> Sanity check that this item is not already linked to a queue */ if (pQueNodeHdr->pNext) { /* Not an error since we have a case where a timer may expire twice in a row (in TxDataQueue) */ TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING, "que_Enqueue(): Trying to enqueue an item that is already enqueued!!"); 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) { 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); /* Verify that pNext is NULL --> Sanity check that this item is not already linked to a queue */ if (pQueNodeHdr->pNext) { TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Requeue(): Trying to Requeue an item that is already enqueued!!"); return TI_NOK; } /* 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) { #ifdef REPORT_LOG 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 } #endif /* TI_DBG */