1 /*
2 * queue.c
3 *
4 * Copyright(c) 1998 - 2009 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 /* Alert if the queue is unloaded before it was cleared from items */
181 if (pQue->uCount)
182 {
183 TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Destroy() Queue Not Empty!!");
184 }
185 /* free Queue object */
186 os_memoryFree (pQue->hOs, pQue, sizeof(TQueue));
187
188 return TI_OK;
189 }
190
191
192 /**
193 * \fn que_Init
194 * \brief Init required handles
195 *
196 * Init required handles.
197 *
198 * \note
199 * \param hQue - The queue object
200 * \param hOs - Handle to Os Abstraction Layer
201 * \param hReport - Handle to report module
202 * \return TI_OK on success or TI_NOK on failure
203 * \sa
204 */
que_Init(TI_HANDLE hQue,TI_HANDLE hOs,TI_HANDLE hReport)205 TI_STATUS que_Init (TI_HANDLE hQue, TI_HANDLE hOs, TI_HANDLE hReport)
206 {
207 TQueue *pQue = (TQueue *)hQue;
208
209 pQue->hOs = hOs;
210 pQue->hReport = hReport;
211
212 return TI_OK;
213 }
214
215
216 /**
217 * \fn que_Enqueue
218 * \brief Enqueue an item
219 *
220 * Enqueue an item at the queue's head (last in queue).
221 *
222 * \note
223 * \param hQue - The queue object
224 * \param hItem - Handle to queued item
225 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow
226 * \sa que_Dequeue, que_Requeue
227 */
que_Enqueue(TI_HANDLE hQue,TI_HANDLE hItem)228 TI_STATUS que_Enqueue (TI_HANDLE hQue, TI_HANDLE hItem)
229 {
230 TQueue *pQue = (TQueue *)hQue;
231 TQueNodeHdr *pQueNodeHdr; /* the Node-Header in the given item */
232
233
234 /* Check queue limit */
235 if(pQue->uCount < pQue->uLimit)
236 {
237 /* Find NodeHeader in the given item */
238 pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset);
239
240 #if 0
241 /* Check that (pNext == NULL) --> Sanity check that this item was dequeued before */
242 if (pQueNodeHdr->pNext)
243 {
244 TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR, "que_Enqueue(): Trying to enqueue an item that wasn't dequeued!");
245 return TI_NOK;
246 }
247 #endif
248
249 /* Enqueue item and increment items counter */
250 AddToHead (pQueNodeHdr, &pQue->tHead);
251 pQue->uCount++;
252
253 #ifdef TI_DBG
254 if (pQue->uCount > pQue->uMaxCount)
255 {
256 pQue->uMaxCount = pQue->uCount;
257 }
258 TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Enqueue(): Enqueued Successfully\n");
259 #endif
260
261 return TI_OK;
262 }
263
264 /*
265 * Queue is overflowed, return TI_NOK.
266 */
267 #ifdef TI_DBG
268 pQue->uOverflow++;
269 TRACE0(pQue->hReport, REPORT_SEVERITY_WARNING , "que_Enqueue(): Queue Overflow\n");
270 #endif
271
272 return TI_NOK;
273 }
274
275
276 /**
277 * \fn que_Dequeue
278 * \brief Dequeue an item
279 *
280 * Dequeue an item from the queue's tail (first in queue).
281 *
282 * \note
283 * \param hQue - The queue object
284 * \return pointer to dequeued item or NULL if queue is empty
285 * \sa que_Enqueue, que_Requeue
286 */
que_Dequeue(TI_HANDLE hQue)287 TI_HANDLE que_Dequeue (TI_HANDLE hQue)
288 {
289 TQueue *pQue = (TQueue *)hQue;
290 TI_HANDLE hItem;
291
292 if (pQue->uCount)
293 {
294 /* Queue is not empty, take packet from the queue tail */
295
296 /* find pointer to the node entry */
297 hItem = (TI_HANDLE)((TI_UINT8*)pQue->tHead.pPrev - pQue->uNodeHeaderOffset);
298
299 DelFromTail (pQue->tHead.pPrev); /* remove node from the queue */
300 pQue->uCount--;
301
302 #ifdef TI_DBG
303 /* Clear the pNext so we can do a sanity check when enqueuing this structre in the future */
304 ((TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset))->pNext = NULL;
305 #endif
306
307 return (hItem);
308 }
309
310 /* Queue is empty */
311 TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Dequeue(): Queue is empty\n");
312 return NULL;
313 }
314
315
316 /**
317 * \fn que_Requeue
318 * \brief Requeue an item
319 *
320 * Requeue an item at the queue's tail (first in queue).
321 *
322 * \note
323 * \param hQue - The queue object
324 * \param hItem - Handle to queued item
325 * \return TI_OK if item was queued, or TI_NOK if not queued due to overflow
326 * \sa que_Enqueue, que_Dequeue
327 */
que_Requeue(TI_HANDLE hQue,TI_HANDLE hItem)328 TI_STATUS que_Requeue (TI_HANDLE hQue, TI_HANDLE hItem)
329 {
330 TQueue *pQue = (TQueue *)hQue;
331 TQueNodeHdr *pQueNodeHdr; /* the NodeHeader in the given item */
332
333 /*
334 * If queue's limits not exceeded add the packet to queue's tail and return TI_OK
335 */
336 if (pQue->uCount < pQue->uLimit)
337 {
338 /* Find NodeHeader in the given item */
339 pQueNodeHdr = (TQueNodeHdr *)((TI_UINT8*)hItem + pQue->uNodeHeaderOffset);
340
341 /* Enqueue item and increment items counter */
342 AddToTail (pQueNodeHdr, &pQue->tHead);
343 pQue->uCount++;
344
345 #ifdef TI_DBG
346 if (pQue->uCount > pQue->uMaxCount)
347 pQue->uMaxCount = pQue->uCount;
348 TRACE0(pQue->hReport, REPORT_SEVERITY_INFORMATION , "que_Requeue(): Requeued successfully\n");
349 #endif
350
351 return TI_OK;
352 }
353
354
355 /*
356 * Queue is overflowed, return TI_NOK.
357 * Note: This is not expected in the current design, since Tx packet may be requeued
358 * only right after it was dequeued in the same context so the queue can't be full.
359 */
360 #ifdef TI_DBG
361 pQue->uOverflow++;
362 TRACE0(pQue->hReport, REPORT_SEVERITY_ERROR , "que_Requeue(): Queue Overflow\n");
363 #endif
364
365 return TI_NOK;
366 }
367
368
369 /**
370 * \fn que_Size
371 * \brief Return queue size
372 *
373 * Return number of items in queue.
374 *
375 * \note
376 * \param hQue - The queue object
377 * \return TI_UINT32 - the items count
378 * \sa
379 */
que_Size(TI_HANDLE hQue)380 TI_UINT32 que_Size (TI_HANDLE hQue)
381 {
382 TQueue *pQue = (TQueue *)hQue;
383
384 return (pQue->uCount);
385 }
386
387
388 /**
389 * \fn que_Print
390 * \brief Print queue status
391 *
392 * Print the queue's parameters (not the content).
393 *
394 * \note
395 * \param hQue - The queue object
396 * \return void
397 * \sa
398 */
399
400 #ifdef TI_DBG
401
que_Print(TI_HANDLE hQue)402 void que_Print(TI_HANDLE hQue)
403 {
404 #ifdef REPORT_LOG
405 TQueue *pQue = (TQueue *)hQue;
406
407 WLAN_OS_REPORT(("que_Print: Count=%u MaxCount=%u Limit=%u Overflow=%u NodeHeaderOffset=%u Next=0x%x Prev=0x%x\n",
408 pQue->uCount, pQue->uMaxCount, pQue->uLimit, pQue->uOverflow,
409 pQue->uNodeHeaderOffset, pQue->tHead.pNext, pQue->tHead.pPrev));
410 #endif
411 }
412
413 #endif /* TI_DBG */
414
415
416
417