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