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 */
51 typedef 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 */
InsertNode(TQueNodeHdr * pNode,TQueNodeHdr * pPrev,TQueNodeHdr * pNext)74 static 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 */
RemoveNode(TQueNodeHdr * pPrev,TQueNodeHdr * pNext)85 static 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 */
AddToHead(TQueNodeHdr * pNode,TQueNodeHdr * pListHead)94 static 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 */
AddToTail(TQueNodeHdr * pNode,TQueNodeHdr * pListHead)102 static 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 */
DelFromTail(TQueNodeHdr * pNode)110 static 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 */
que_Create(TI_HANDLE hOs,TI_HANDLE hReport,TI_UINT32 uLimit,TI_UINT32 uNodeHeaderOffset)137 TI_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 */
que_Destroy(TI_HANDLE hQue)176 TI_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 */
que_Init(TI_HANDLE hQue,TI_HANDLE hOs,TI_HANDLE hReport)208 TI_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 */
que_Enqueue(TI_HANDLE hQue,TI_HANDLE hItem)231 TI_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 */
que_Dequeue(TI_HANDLE hQue)290 TI_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 */
que_Requeue(TI_HANDLE hQue,TI_HANDLE hItem)334 TI_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;
361 TRACE0(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++;
375 TRACE0(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 */
que_Size(TI_HANDLE hQue)393 TI_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
que_Print(TI_HANDLE hQue)415 void 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