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