1/* 2 * queue.c 3 * 4 * Copyright(c) 1998 - 2010 Texas Instruments. All rights reserved. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name Texas Instruments nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 35 36/** \file queue.c 37 * \brief This module provides generic queueing services, including enqueue, dequeue 38 * and requeue of any object that contains TQueNodeHdr in its structure. 39 * 40 * \see queue.h 41 */ 42 43 44 45#define __FILE_ID__ FILE_ID_130 46#include "report.h" 47#include "queue.h" 48 49 50/* Queue structure */ 51typedef struct 52{ 53 TQueNodeHdr tHead; /* The queue first node */ 54 TI_UINT32 uCount; /* Current number of nodes in queue */ 55 TI_UINT32 uLimit; /* Upper limit of nodes in queue */ 56 TI_UINT32 uMaxCount; /* Maximum uCount value (for debug) */ 57 TI_UINT32 uOverflow; /* Number of overflow occurences - couldn't insert node (for debug) */ 58 TI_UINT32 uNodeHeaderOffset; /* Offset of NodeHeader field from the entry of the queued item */ 59 TI_HANDLE hOs; 60 TI_HANDLE hReport; 61} TQueue; 62 63 64 65/* 66 * INTERNAL FUNCTIONS 67 * =============================== 68 */ 69 70 71/* 72 * InsertNode(): Insert new node between pPrev and pNext 73 */ 74static INLINE void InsertNode( TQueNodeHdr *pNode, TQueNodeHdr *pPrev, TQueNodeHdr *pNext) 75{ 76 pNext->pPrev = pNode; 77 pNode->pNext = pNext; 78 pNode->pPrev = pPrev; 79 pPrev->pNext = pNode; 80} 81 82/* 83 * RemoveNode(): Remove node from between pPrev and pNext 84 */ 85static INLINE void RemoveNode( TQueNodeHdr *pPrev, TQueNodeHdr *pNext) 86{ 87 pNext->pPrev = pPrev; 88 pPrev->pNext = pNext; 89} 90 91/* 92 * AddToHead(): Add node to queue head (last in queue) 93 */ 94static INLINE void AddToHead( TQueNodeHdr *pNode, TQueNodeHdr *pListHead) 95{ 96 InsertNode (pNode, pListHead, pListHead->pNext); 97} 98 99/* 100 * AddToTail(): Add node to queue tail (first in queue) 101 */ 102static INLINE void AddToTail( TQueNodeHdr *pNode, TQueNodeHdr *pListHead) 103{ 104 InsertNode( pNode, pListHead->pPrev, pListHead ); 105} 106 107/* 108 * DelFromTail(): Delete node from queue tail (first in queue) 109 */ 110static INLINE void DelFromTail (TQueNodeHdr *pNode) 111{ 112 RemoveNode (pNode->pPrev, pNode->pNext); 113} 114 115 116 117/* 118 * EXTERNAL FUNCTIONS 119 * =============================== 120 */ 121 122 123/** 124 * \fn que_Create 125 * \brief Create a queue. 126 * 127 * Allocate and init a queue object. 128 * 129 * \note 130 * \param hOs - Handle to Os Abstraction Layer 131 * \param hReport - Handle to report module 132 * \param uLimit - Maximum items to store in queue 133 * \param uNodeHeaderOffset - Offset of NodeHeader field from the entry of the queued item. 134 * \return Handle to the allocated queue 135 * \sa que_Destroy 136 */ 137TI_HANDLE que_Create (TI_HANDLE hOs, TI_HANDLE hReport, TI_UINT32 uLimit, TI_UINT32 uNodeHeaderOffset) 138{ 139 TQueue *pQue; 140 141 /* allocate queue module */ 142 pQue = os_memoryAlloc (hOs, sizeof(TQueue)); 143 144 if (!pQue) 145 { 146 WLAN_OS_REPORT (("Error allocating the Queue Module\n")); 147 return NULL; 148 } 149 150 os_memoryZero (hOs, pQue, sizeof(TQueue)); 151 152 /* Intialize the queue header */ 153 pQue->tHead.pNext = pQue->tHead.pPrev = &pQue->tHead; 154 155 /* Set the Queue parameters */ 156 pQue->hOs = hOs; 157 pQue->hReport = hReport; 158 pQue->uLimit = uLimit; 159 pQue->uNodeHeaderOffset = uNodeHeaderOffset; 160 161 return (TI_HANDLE)pQue; 162} 163 164 165/** 166 * \fn que_Destroy 167 * \brief Destroy the queue. 168 * 169 * Free the queue memory. 170 * 171 * \note The queue's owner should first free the queued items! 172 * \param hQue - The queue object 173 * \return TI_OK on success or TI_NOK on failure 174 * \sa que_Create 175 */ 176TI_STATUS que_Destroy (TI_HANDLE hQue) 177{ 178 TQueue *pQue = (TQueue *)hQue; 179 180 if (pQue) 181 { 182 /* Alert if the queue is unloaded before it was cleared from items */ 183 if (pQue->uCount) 184 { 185 TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING, "que_Destroy() Queue Not Empty!!"); 186 } 187 /* free Queue object */ 188 os_memoryFree (pQue->hOs, pQue, sizeof(TQueue)); 189 } 190 191 return TI_OK; 192} 193 194 195/** 196 * \fn que_Init 197 * \brief Init required handles 198 * 199 * Init required handles. 200 * 201 * \note 202 * \param hQue - The queue object 203 * \param hOs - Handle to Os Abstraction Layer 204 * \param hReport - Handle to report module 205 * \return TI_OK on success or TI_NOK on failure 206 * \sa 207 */ 208TI_STATUS que_Init (TI_HANDLE hQue, TI_HANDLE hOs, TI_HANDLE hReport) 209{ 210 TQueue *pQue = (TQueue *)hQue; 211 212 pQue->hOs = hOs; 213 pQue->hReport = hReport; 214 215 return TI_OK; 216} 217 218 219/** 220 * \fn que_Enqueue 221 * \brief Enqueue an item 222 * 223 * Enqueue an item at the queue's head (last in queue). 224 * 225 * \note 226 * \param hQue - The queue object 227 * \param hItem - Handle to queued item 228 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow 229 * \sa que_Dequeue, que_Requeue 230 */ 231TI_STATUS que_Enqueue (TI_HANDLE hQue, TI_HANDLE hItem) 232{ 233 TQueue *pQue = (TQueue *)hQue; 234 TQueNodeHdr *pQueNodeHdr; /* the Node-Header in the given item */ 235 236 if (pQue) 237 { 238 /* Check queue limit */ 239 if(pQue->uCount < pQue->uLimit) 240 { 241 /* Find NodeHeader in the given item */ 242 pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset); 243 244 /* Verify that pNext is NULL --> Sanity check that this item is not already linked to a queue */ 245 if (pQueNodeHdr->pNext) 246 { 247 /* Not an error since we have a case where a timer may expire twice in a row (in TxDataQueue) */ 248 TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING, "que_Enqueue(): Trying to enqueue an item that is already enqueued!!"); 249 return TI_NOK; 250 } 251 252 /* Enqueue item and increment items counter */ 253 AddToHead (pQueNodeHdr, &pQue->tHead); 254 pQue->uCount++; 255 256#ifdef TI_DBG 257 if (pQue->uCount > pQue->uMaxCount) 258 { 259 pQue->uMaxCount = pQue->uCount; 260 } 261 TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Enqueue(): Enqueued Successfully\n"); 262#endif 263 264 return TI_OK; 265 } 266 267 /* 268 * Queue is overflowed, return TI_NOK. 269 */ 270#ifdef TI_DBG 271 pQue->uOverflow++; 272 TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING , "que_Enqueue(): Queue Overflow\n"); 273#endif 274 } 275 return TI_NOK; 276} 277 278 279/** 280 * \fn que_Dequeue 281 * \brief Dequeue an item 282 * 283 * Dequeue an item from the queue's tail (first in queue). 284 * 285 * \note 286 * \param hQue - The queue object 287 * \return pointer to dequeued item or NULL if queue is empty 288 * \sa que_Enqueue, que_Requeue 289 */ 290TI_HANDLE que_Dequeue (TI_HANDLE hQue) 291{ 292 TQueue *pQue = (TQueue *)hQue; 293 TI_HANDLE hItem; 294 295 if (pQue) 296 { 297 if (pQue->uCount) 298 { 299 /* Queue is not empty, take packet from the queue tail */ 300 301 /* find pointer to the node entry */ 302 hItem = (TI_HANDLE)((TI_UINT8*)pQue->tHead.pPrev - pQue->uNodeHeaderOffset); 303 304 DelFromTail (pQue->tHead.pPrev); /* remove node from the queue */ 305 pQue->uCount--; 306 307#ifdef TI_DBG 308 /* Clear the pNext so we can do a sanity check when enqueuing this structre in the future */ 309 ((TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset))->pNext = NULL; 310#endif 311 312 return (hItem); 313 } 314 } 315 316 /* Queue is empty */ 317 TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Dequeue(): Queue is empty\n"); 318 return NULL; 319} 320 321 322/** 323 * \fn que_Requeue 324 * \brief Requeue an item 325 * 326 * Requeue an item at the queue's tail (first in queue). 327 * 328 * \note 329 * \param hQue - The queue object 330 * \param hItem - Handle to queued item 331 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow 332 * \sa que_Enqueue, que_Dequeue 333 */ 334TI_STATUS que_Requeue (TI_HANDLE hQue, TI_HANDLE hItem) 335{ 336 TQueue *pQue = (TQueue *)hQue; 337 TQueNodeHdr *pQueNodeHdr; /* the NodeHeader in the given item */ 338 339 /* 340 * If queue's limits not exceeded add the packet to queue's tail and return TI_OK 341 */ 342 if (pQue->uCount < pQue->uLimit) 343 { 344 /* Find NodeHeader in the given item */ 345 pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset); 346 347 /* Verify that pNext is NULL --> Sanity check that this item is not already linked to a queue */ 348 if (pQueNodeHdr->pNext) 349 { 350 TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Requeue(): Trying to Requeue an item that is already enqueued!!"); 351 return TI_NOK; 352 } 353 354 /* Enqueue item and increment items counter */ 355 AddToTail (pQueNodeHdr, &pQue->tHead); 356 pQue->uCount++; 357 358#ifdef TI_DBG 359 if (pQue->uCount > pQue->uMaxCount) 360 pQue->uMaxCount = pQue->uCount; 361TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Requeue(): Requeued successfully\n"); 362#endif 363 364 return TI_OK; 365 } 366 367 368 /* 369 * Queue is overflowed, return TI_NOK. 370 * Note: This is not expected in the current design, since Tx packet may be requeued 371 * only right after it was dequeued in the same context so the queue can't be full. 372 */ 373#ifdef TI_DBG 374 pQue->uOverflow++; 375TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR , "que_Requeue(): Queue Overflow\n"); 376#endif 377 378 return TI_NOK; 379} 380 381 382/** 383 * \fn que_Size 384 * \brief Return queue size 385 * 386 * Return number of items in queue. 387 * 388 * \note 389 * \param hQue - The queue object 390 * \return TI_UINT32 - the items count 391 * \sa 392 */ 393TI_UINT32 que_Size (TI_HANDLE hQue) 394{ 395 TQueue *pQue = (TQueue *)hQue; 396 397 return (pQue->uCount); 398} 399 400 401/** 402 * \fn que_Print 403 * \brief Print queue status 404 * 405 * Print the queue's parameters (not the content). 406 * 407 * \note 408 * \param hQue - The queue object 409 * \return void 410 * \sa 411 */ 412 413#ifdef TI_DBG 414 415void que_Print(TI_HANDLE hQue) 416{ 417#ifdef REPORT_LOG 418 TQueue *pQue = (TQueue *)hQue; 419 420 WLAN_OS_REPORT(("que_Print: Count=%u MaxCount=%u Limit=%u Overflow=%u NodeHeaderOffset=%u Next=0x%x Prev=0x%x\n", 421 pQue->uCount, pQue->uMaxCount, pQue->uLimit, pQue->uOverflow, 422 pQue->uNodeHeaderOffset, pQue->tHead.pNext, pQue->tHead.pPrev)); 423#endif 424} 425 426#endif /* TI_DBG */ 427