source: svn/trunk/newcon3bcm2_21bu/magnum/commonutils/lst/blst_circleq.h

Last change on this file was 2, checked in by jglee, 11 years ago

first commit
  • Property svn:executable set to *
File size: 11.6 KB
Line 
1/***************************************************************************
2 *     Copyright (c) 2003-2007, Broadcom Corporation
3 *     All Rights Reserved
4 *     Confidential Property of Broadcom Corporation
5 *
6 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
7 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
8 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
9 *
10 * $brcm_Workfile: blst_circleq.h $
11 * $brcm_Revision: Hydra_Software_Devel/4 $
12 * $brcm_Date: 9/13/07 5:56p $
13 *
14 * Module Description:
15 *
16 * Revision History:
17 *
18 * $brcm_Log: /magnum/commonutils/lst/blst_circleq.h $
19 *
20 * Hydra_Software_Devel/4   9/13/07 5:56p nilesh
21 * PR34873: Fixed typo in BLST_CQ_REMOVE
22 *
23 * Hydra_Software_Devel/3   12/11/03 4:39p vsilyaev
24 * PR 8962: Remove semicolons after while(0)
25 *
26 * Hydra_Software_Devel/2   12/11/03 4:24p vsilyaev
27 * PR 8959: Fixed name of the argument in macro BLST_CQ_INSERT_TAIL
28 *
29 * Hydra_Software_Devel/1   10/14/03 10:17a vsilyaev
30 * Implementation for the circular queue.
31 *
32 *
33 ***************************************************************************/
34
35#ifndef BLST_CIRCLEQ_H
36#define BLST_CIRCLEQ_H   
37
38/*================== Module Overview =====================================
39This modules defines macros to control doubly linked queue.
40All operations are typesafe (doesn't required typecasting) and constant time.
41
42This list allow:
43  o Insert a new entry at the head of the list
44  o Insert a new entry after/before any element in the list
45  o O(1) removal of any entry in the list
46  o Forward traversal through the list
47  o Each element requires two pointers
48  o Code size and execution time is about 3.0 that for singly-linked list
49 
50========================================================================*/
51
52 
53/***************************************************************************
54Summary:
55    Creates new data type for the list head
56       
57Description:
58    Creates new data type for the list head, this type used to create variable for the lists head.
59    User should create new the list head data type for every different element datatype.
60       
61Input:
62        name - name for the new data type (structure)
63    type - existing user data type used for element of the list
64
65Example:   
66     BLST_CQ_HEAD(block_head, block);
67     struct block_head  head;
68
69Returns:
70    <none>
71****************************************************************************/
72#define BLST_CQ_HEAD(name, type) struct name { struct type *cq_first, *cq_last; }
73
74/***************************************************************************
75Summary:
76    Defines links entry
77       
78Description:
79    Defines entrys for the list inside the user structure.for the element.
80       
81Input:
82    type - the datatype for element
83
84Example:
85     struct block {
86        BLST_CQ_ENTRY(block) link;
87        char string[256];
88     }; 
89
90Returns:
91    <none>
92****************************************************************************/
93#define BLST_CQ_ENTRY(type)  struct { struct type *cq_next, *cq_prev; }
94
95/***************************************************************************
96Summary:
97    Initializes lists head
98       
99Description:
100    Initializes the head of the list. The head shall be initialized before list can be used.
101    This macro used for dynamic initialization.
102       
103Input:
104    head - pointer to the list head
105
106See also:
107    BLST_CQ_INITIALIZER
108
109Example:
110    BLST_CQ_INIT(&head);
111
112Returns:
113    <none>
114****************************************************************************/
115#define BLST_CQ_INIT(head) ((head)->cq_last = (head)->cq_first=NULL)
116
117/***************************************************************************
118Summary:
119    Initializes lists head
120       
121Description:
122    Initializes the head of the list. The head shall be initialized before list can be used.
123    This macro used for static initialization.
124       
125Input:
126    head - pointer to the list head
127
128See also:
129    BLST_CQ_INIT
130
131Example:
132    static struct block_head  head = BLST_CQ_INITIALIZER(&head);
133
134Returns:
135    <none>
136****************************************************************************/
137#define BLST_CQ_INITIALIZER(head) {NULL, NULL}
138
139/***************************************************************************
140Summary:
141    Tests if list is empty
142       
143Description:
144    Tests if list is empty.
145       
146Input:
147    head - pointer to the list head
148
149Returns:
150    true - list empty
151    false - list has elements
152
153Example:
154    if (BLST_CQ_EMPTY(&head)) { return ; }
155
156****************************************************************************/
157#define BLST_CQ_EMPTY(head) ((head)->cq_first == NULL)
158
159/***************************************************************************
160Summary:
161    Returns the lists first element
162       
163Description:
164    Returns pointer to the first element from the list
165       
166Input:
167    head - pointer to the list head
168
169Returns:
170    pointer to the first element from the list.
171
172Example:
173    struct block *first=BLST_CQ_FIRST(&head);
174****************************************************************************/
175#define BLST_CQ_FIRST(head) ((head)->cq_first)
176
177/***************************************************************************
178Summary:
179    Returns the lists first element
180       
181Description:
182    Returns pointer to the last element from the list
183       
184Input:
185    head - pointer to the list head
186
187Returns:
188    pointer to the last element from the list.
189
190Example:
191    struct block *first=BLST_CQ_FIRST(&head);
192****************************************************************************/
193#define BLST_CQ_LAST(head) ((head)->cq_last)
194
195/***************************************************************************
196Summary:
197    Returns next element from the lists
198       
199Description:
200    Returns pointer to the next element from the list
201       
202Input:
203    elm - pointer to the list element
204    field - name of the elements link field
205
206Returns:
207    pointer to the next element from the list
208
209Example:
210    struct block *second=BLST_CQ_NEXT(first);
211****************************************************************************/
212#define BLST_CQ_NEXT(elm, field) ((elm)->field.cq_next)
213
214
215/***************************************************************************
216Summary:
217    Returns next element from the lists
218       
219Description:
220    Returns pointer to the previous element from the list
221       
222Input:
223    elm - pointer to the list element
224    field - name of the elements link field
225
226Returns:
227    pointer to the previous element from the list
228
229Example:
230    struct block *first=BLST_CQ_PREV(second);
231****************************************************************************/
232#define BLST_CQ_PREV(elm, field) ((elm)->field.cq_prev)
233
234/***************************************************************************
235Summary:
236    Inserts element into the list
237       
238Description:
239    Inserts new element at the head of the list.
240       
241Input:
242    head - pointer to the list head
243    elm - pointer to the new element
244    field - name of the elements link field
245
246Returns:
247    <none>
248
249Example:
250    BLST_Q_INSERT_HEAD(&head, new_block, link);
251****************************************************************************/
252#define BLST_CQ_INSERT_HEAD(head, elm, field) do { \
253   if ( (head)->cq_first != NULL ) { \
254        (elm)->field.cq_next = (head)->cq_first; \
255        (elm)->field.cq_prev = (head)->cq_last; \
256        (head)->cq_first->field.cq_prev = (head)->cq_last->field.cq_next = (elm); \
257   } else { \
258     (elm)->field.cq_prev = (elm)->field.cq_next = (head)->cq_last = (elm); \
259   } \
260   (head)->cq_first = (elm);}  while(0)
261
262/***************************************************************************
263Summary:
264    Inserts element into the list
265       
266Description:
267Description:
268    Inserts the new element at the end of the list.
269       
270Input:
271    head - pointer to the list head
272    elm - pointer to the new element
273    field - name of the elements link field
274
275Returns:
276    <none>
277
278Example:
279    BLST_CQ_INSERT_TAIL(&head, elm, link);
280****************************************************************************/
281#define BLST_CQ_INSERT_TAIL(head, elm, field) do {                              \
282   if ( (head)->cq_last != NULL) { \
283    (elm)->field.cq_next = (head)->cq_first; \
284    (elm)->field.cq_prev = (head)->cq_last; \
285    (head)->cq_first->field.cq_prev = (head)->cq_last->field.cq_next = (elm); \
286   } else { \
287     (elm)->field.cq_prev = (elm)->field.cq_next = (head)->cq_first = (elm);\
288   }\
289   (head)->cq_last = (elm); } while(0)
290
291 
292/***************************************************************************
293Summary:
294    Inserts element into the list
295       
296Description:
297    Inserts new element after existing element.
298       
299Input:
300    head - pointer to the list head
301    elm - pointer to the element from the list
302    new_elm - pointer to the new element
303    field - name of the elements link field
304
305Returns:
306    <none>
307
308Example:
309    BLST_CQ_INSERT_AFTER(&head, first, second, link);
310****************************************************************************/
311#define BLST_CQ_INSERT_AFTER(head, elm, new_elm, field) do { \
312        (new_elm)->field.cq_prev = (elm); \
313        (new_elm)->field.cq_next = (elm)->field.cq_next; \
314        (elm)->field.cq_next->field.cq_prev = (new_elm); \
315        if ((elm) == (head)->cq_last)  (head)->cq_last = (new_elm);\
316        (elm)->field.cq_next = (new_elm); } while(0)
317
318/***************************************************************************
319Summary:
320    Inserts element into the list
321       
322Description:
323    Inserts new element before existing element.
324       
325Input:
326    head - pointer to the list head
327    elm - pointer to the element from the list
328    new_elm - pointer to the new element
329    field - name of the elements link field
330
331Returns:
332    <none>
333
334Example:
335    BLST_CQ_INSERT_BEFORE(&head, second, first, link);
336****************************************************************************/
337#define BLST_CQ_INSERT_BEFORE(head, elm, new_elm, field) do { \
338        (new_elm)->field.cq_next = (elm); \
339        (new_elm)->field.cq_prev = (elm)->field.cq_prev;\
340        (elm)->field.cq_prev->field.cq_next = (new_elm); \
341        if ((elm) == (head)->cq_first) (head)->cq_first = (new_elm);\
342        (elm)->field.cq_prev = (new_elm); } while(0)
343
344
345
346/***************************************************************************
347Summary:
348    Removes element from the list
349       
350Description:
351    Removes element from the list.
352       
353Input:
354    head - pointer to the list head
355    elm - pointer to the list element
356    field - name of the elements link field
357
358See also:
359    BLST_CQ_REMOVE_HEAD
360
361Returns:
362    <none>
363
364Example:
365    BLST_CQ_REMOVE(&head, first, link);
366****************************************************************************/
367#define BLST_CQ_REMOVE(head, elm, field) do { \
368    (elm)->field.cq_next->field.cq_prev = (elm)->field.cq_prev; \
369    if ( (elm) == (head)->cq_last ) { \
370        if ( (elm)==(head)->cq_first ) (head)->cq_first = (head)->cq_last = NULL;\
371        else (head)->cq_last = (elm)->field.cq_prev; \
372    }\
373    (elm)->field.cq_prev->field.cq_next = (elm)->field.cq_next; \
374    if ( (elm) == (head)->cq_first) (head)->cq_first = (elm)->field.cq_next; \
375   } while(0)
376
377/***************************************************************************
378Summary:
379    Removes element from the list
380       
381Description:
382    Removes element from the head of the list.
383       
384Input:
385    head - pointer to the list head
386    field - name of the elements link field
387
388See also:
389    BLST_CQ_REMOVE
390
391Returns:
392    <none>
393
394Example:
395    BLST_CQ_REMOVE_HEAD(&head, first, link);
396****************************************************************************/
397#define BLST_CQ_REMOVE_HEAD(head, field) do { \
398    if ((head)->cq_first == (head)->cq_last) (head)->cq_first = (head)->cq_last = NULL;\
399    else {\
400      (head)->cq_first = (head)->cq_first->field.cq_next; \
401      (head)->cq_last->field.cq_next = (head)->cq_first; \
402    } } while(0)
403
404
405#endif /* BLST_CIRCLEQ_H     */
Note: See TracBrowser for help on using the repository browser.