1/******************************************************************************/
2/*                                                                            */
3/* Broadcom BCM5700 Linux Network Driver, Copyright (c) 2000 - 2004 Broadcom  */
4/* Corporation.                                                               */
5/* All rights reserved.                                                       */
6/*                                                                            */
7/* This program is free software; you can redistribute it and/or modify       */
8/* it under the terms of the GNU General Public License as published by       */
9/* the Free Software Foundation, located in the file LICENSE.                 */
10/*                                                                            */
11/* Queue functions.                                                           */
12/*    void          QQ_InitQueue(PQQ_CONTAINER pQueue)                        */
13/*    char          QQ_Full(PQQ_CONTAINER pQueue)                             */
14/*    char          QQ_Empty(PQQ_CONTAINER pQueue)                            */
15/*    unsigned int QQ_GetSize(PQQ_CONTAINER pQueue)                          */
16/*    unsigned int QQ_GetEntryCnt(PQQ_CONTAINER pQueue)                      */
17/*    char          QQ_PushHead(PQQ_CONTAINER pQueue, PQQ_ENTRY pEntry)       */
18/*    char          QQ_PushTail(PQQ_CONTAINER pQueue, PQQ_ENTRY pEntry)       */
19/*    PQQ_ENTRY     QQ_PopHead(PQQ_CONTAINER pQueue)                          */
20/*    PQQ_ENTRY     QQ_PopTail(PQQ_CONTAINER pQueue)                          */
21/*    PQQ_ENTRY     QQ_GetHead(PQQ_CONTAINER pQueue, unsigned int Idx)       */
22/*    PQQ_ENTRY     QQ_GetTail(PQQ_CONTAINER pQueue, unsigned int Idx)       */
23/*                                                                            */
24/*                                                                            */
25/* History:                                                                   */
26/*    02/25/00 Hav Khauv        Initial version.                              */
27/******************************************************************************/
28
29#ifndef BCM_QUEUE_H
30#define BCM_QUEUE_H
31
32
33
34/******************************************************************************/
35/* Queue definitions. */
36/******************************************************************************/
37
38/* Entry for queueing. */
39typedef void *PQQ_ENTRY;
40
41
42/* Queue header -- base type. */
43typedef struct {
44    unsigned int Head;
45    unsigned int Tail;
46    unsigned int Size;
47    MM_ATOMIC_T EntryCnt;
48    PQQ_ENTRY Array[1];
49} QQ_CONTAINER, *PQQ_CONTAINER;
50
51
52/* Declare queue type macro. */
53#define DECLARE_QUEUE_TYPE(_QUEUE_TYPE, _QUEUE_SIZE)            \
54                                                                \
55    typedef struct {                                            \
56        QQ_CONTAINER Container;                                 \
57        PQQ_ENTRY EntryBuffer[_QUEUE_SIZE];                     \
58    } _QUEUE_TYPE, *P##_QUEUE_TYPE
59
60
61
62/******************************************************************************/
63/* Compilation switches. */
64/******************************************************************************/
65
66#if DBG
67#undef QQ_NO_OVERFLOW_CHECK
68#undef QQ_NO_UNDERFLOW_CHECK
69#endif /* DBG */
70
71#ifdef QQ_USE_MACROS
72/* notdone */
73#else
74
75#ifdef QQ_NO_INLINE
76#define __inline
77#endif /* QQ_NO_INLINE */
78
79
80
81/******************************************************************************/
82/* Description:                                                               */
83/*                                                                            */
84/* Return:                                                                    */
85/******************************************************************************/
86__inline static void
87QQ_InitQueue(
88PQQ_CONTAINER pQueue,
89unsigned int QueueSize) {
90    pQueue->Head = 0;
91    pQueue->Tail = 0;
92    pQueue->Size = QueueSize+1;
93    MM_ATOMIC_SET(&pQueue->EntryCnt, 0);
94} /* QQ_InitQueue */
95
96
97
98/******************************************************************************/
99/* Description:                                                               */
100/*                                                                            */
101/* Return:                                                                    */
102/******************************************************************************/
103__inline static char
104QQ_Full(
105PQQ_CONTAINER pQueue) {
106    unsigned int NewHead;
107
108    NewHead = (pQueue->Head + 1) % pQueue->Size;
109
110    return(NewHead == pQueue->Tail);
111} /* QQ_Full */
112
113
114
115/******************************************************************************/
116/* Description:                                                               */
117/*                                                                            */
118/* Return:                                                                    */
119/******************************************************************************/
120__inline static char
121QQ_Empty(
122PQQ_CONTAINER pQueue) {
123    return(pQueue->Head == pQueue->Tail);
124} /* QQ_Empty */
125
126
127
128/******************************************************************************/
129/* Description:                                                               */
130/*                                                                            */
131/* Return:                                                                    */
132/******************************************************************************/
133__inline static unsigned int
134QQ_GetSize(
135PQQ_CONTAINER pQueue) {
136    return pQueue->Size;
137} /* QQ_GetSize */
138
139
140
141/******************************************************************************/
142/* Description:                                                               */
143/*                                                                            */
144/* Return:                                                                    */
145/******************************************************************************/
146__inline static unsigned int
147QQ_GetEntryCnt(
148PQQ_CONTAINER pQueue) {
149    return MM_ATOMIC_READ(&pQueue->EntryCnt);
150} /* QQ_GetEntryCnt */
151
152
153
154/******************************************************************************/
155/* Description:                                                               */
156/*                                                                            */
157/* Return:                                                                    */
158/*    TRUE entry was added successfully.                                      */
159/*    FALSE queue is full.                                                    */
160/******************************************************************************/
161__inline static char
162QQ_PushHead(
163PQQ_CONTAINER pQueue,
164PQQ_ENTRY pEntry) {
165    unsigned int Head;
166
167    Head = (pQueue->Head + 1) % pQueue->Size;
168
169#if !defined(QQ_NO_OVERFLOW_CHECK)
170    if(Head == pQueue->Tail) {
171        return 0;
172    } /* if */
173#endif /* QQ_NO_OVERFLOW_CHECK */
174
175    pQueue->Array[pQueue->Head] = pEntry;
176    MM_WMB();
177    pQueue->Head = Head;
178    MM_ATOMIC_INC(&pQueue->EntryCnt);
179
180    return -1;
181} /* QQ_PushHead */
182
183
184
185/******************************************************************************/
186/* Description:                                                               */
187/*                                                                            */
188/* Return:                                                                    */
189/*    TRUE entry was added successfully.                                      */
190/*    FALSE queue is full.                                                    */
191/******************************************************************************/
192__inline static char
193QQ_PushTail(
194PQQ_CONTAINER pQueue,
195PQQ_ENTRY pEntry) {
196    unsigned int Tail;
197
198    Tail = pQueue->Tail;
199    if(Tail == 0) {
200        Tail = pQueue->Size;
201    } /* if */
202    Tail--;
203
204#if !defined(QQ_NO_OVERFLOW_CHECK)
205    if(Tail == pQueue->Head) {
206        return 0;
207    } /* if */
208#endif /* QQ_NO_OVERFLOW_CHECK */
209
210    pQueue->Array[Tail] = pEntry;
211    MM_WMB();
212    pQueue->Tail = Tail;
213    MM_ATOMIC_INC(&pQueue->EntryCnt);
214
215    return -1;
216} /* QQ_PushTail */
217
218
219
220/******************************************************************************/
221/* Description:                                                               */
222/*                                                                            */
223/* Return:                                                                    */
224/******************************************************************************/
225__inline static PQQ_ENTRY
226QQ_PopHead(
227PQQ_CONTAINER pQueue) {
228    unsigned int Head;
229    unsigned int Tail;
230    PQQ_ENTRY Entry;
231
232    Head = pQueue->Head;
233    Tail = pQueue->Tail;
234
235    MM_MB();
236#if !defined(QQ_NO_UNDERFLOW_CHECK)
237    if(Head == Tail) {
238        return (PQQ_ENTRY) 0;
239    } /* if */
240#endif /* QQ_NO_UNDERFLOW_CHECK */
241
242    if(Head == 0) {
243        Head = pQueue->Size;
244    } /* if */
245    Head--;
246
247    Entry = pQueue->Array[Head];
248    MM_MB();
249    pQueue->Head = Head;
250    MM_ATOMIC_DEC(&pQueue->EntryCnt);
251
252    return Entry;
253} /* QQ_PopHead */
254
255
256
257/******************************************************************************/
258/* Description:                                                               */
259/*                                                                            */
260/* Return:                                                                    */
261/******************************************************************************/
262__inline static PQQ_ENTRY
263QQ_PopTail(
264PQQ_CONTAINER pQueue) {
265    unsigned int Head;
266    unsigned int Tail;
267    PQQ_ENTRY Entry;
268
269    Head = pQueue->Head;
270    Tail = pQueue->Tail;
271
272    MM_MB();
273#if !defined(QQ_NO_UNDERFLOW_CHECK)
274    if(Tail == Head) {
275        return (PQQ_ENTRY) 0;
276    } /* if */
277#endif /* QQ_NO_UNDERFLOW_CHECK */
278
279    Entry = pQueue->Array[Tail];
280    MM_MB();
281    pQueue->Tail = (Tail + 1) % pQueue->Size;
282    MM_ATOMIC_DEC(&pQueue->EntryCnt);
283
284    return Entry;
285} /* QQ_PopTail */
286
287
288
289/******************************************************************************/
290/* Description:                                                               */
291/*                                                                            */
292/* Return:                                                                    */
293/******************************************************************************/
294__inline static PQQ_ENTRY
295QQ_GetHead(
296    PQQ_CONTAINER pQueue,
297    unsigned int Idx)
298{
299    if(Idx >= (unsigned int) MM_ATOMIC_READ(&pQueue->EntryCnt))
300    {
301        return (PQQ_ENTRY) 0;
302    }
303
304    if(pQueue->Head > Idx)
305    {
306        Idx = pQueue->Head - Idx;
307    }
308    else
309    {
310        Idx = pQueue->Size - (Idx - pQueue->Head);
311    }
312    Idx--;
313
314    return pQueue->Array[Idx];
315}
316
317
318
319/******************************************************************************/
320/* Description:                                                               */
321/*                                                                            */
322/* Return:                                                                    */
323/******************************************************************************/
324__inline static PQQ_ENTRY
325QQ_GetTail(
326    PQQ_CONTAINER pQueue,
327    unsigned int Idx)
328{
329    if(Idx >= (unsigned int) MM_ATOMIC_READ(&pQueue->EntryCnt))
330    {
331        return (PQQ_ENTRY) 0;
332    }
333
334    Idx += pQueue->Tail;
335    if(Idx >= pQueue->Size)
336    {
337        Idx = Idx - pQueue->Size;
338    }
339
340    return pQueue->Array[Idx];
341}
342
343#endif /* QQ_USE_MACROS */
344
345
346
347#endif /* QUEUE_H */
348