1
/*********************************************************
2
* Copyright (C) 1998 VMware, Inc. All rights reserved.
4
* This program is free software; you can redistribute it and/or modify it
5
* under the terms of the GNU Lesser General Public License as published
6
* by the Free Software Foundation version 2.1 and no later version.
8
* This program is distributed in the hope that it will be useful, but
9
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
10
* or FITNESS FOR A PARTICULAR PURPOSE. See the Lesser GNU General Public
11
* License for more details.
13
* You should have received a copy of the GNU Lesser General Public License
14
* along with this program; if not, write to the Free Software Foundation, Inc.,
15
* 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17
*********************************************************/
22
* macros, prototypes and struct definitions for double-linked
29
#define INCLUDE_ALLOW_USERLEVEL
30
#define INCLUDE_ALLOW_VMMON
31
#define INCLUDE_ALLOW_VMCORE
32
#define INCLUDE_ALLOW_MODULE
33
#define INCLUDE_ALLOW_VMKERNEL
34
#include "includeCheck.h"
37
typedef struct ListItem {
38
struct ListItem *prev;
39
struct ListItem *next;
42
/* A list with no elements is a null pointer. */
43
#define LIST_ITEM_DEF(name) \
44
ListItem * name = NULL
46
#define LIST_EMPTY(l) ((l) == NULL)
48
/* initialize list item */
49
#define INIT_LIST_ITEM(p) \
51
(p)->prev = (p)->next = (p); \
54
/* check if initialized */
55
#define IS_LIST_ITEM_INITIALIZED(li) \
56
(((li) == (li)->prev) && ((li) == (li)->next))
58
/* return first element in the list */
59
#define LIST_FIRST(l) (l)
60
#define LIST_FIRST_CHK(l) (l)
62
/* return last element in the list */
63
#define LIST_LAST(l) ((l)->prev)
64
#define LIST_LAST_CHK(l) (LIST_EMPTY(l) ? NULL : LIST_LAST(l))
67
* LIST_CONTAINER - get the struct for this entry (like list_entry)
68
* @ptr: the &struct ListItem pointer.
69
* @type: the type of the struct this is embedded in.
70
* @member: the name of the list struct within the struct.
72
#define LIST_CONTAINER(ptr, type, member) \
73
((type *)((char *)(ptr) - offsetof(type, member)))
76
* delete item from the list
78
#define LIST_DEL DelListItem
81
* link two lists together
83
#define LIST_SPLICE SpliceLists
86
* Split a list into two lists
88
#define LIST_SPLIT SplitLists
91
* Add item to front of stack. List pointer points to new head.
93
#define LIST_PUSH PushListItem
96
* Add item at back of queue. List pointer only changes if list was empty.
98
#define LIST_QUEUE QueueListItem
103
#define LIST_SIZE GetListSize
106
* LIST_SCAN_FROM scans the list from "from" up until "until".
107
* The loop variable p should not be destroyed in the process.
108
* "from" is an element in the list where to start scanning.
109
* "until" is the element where search should stop.
110
* member is the field to use for the search - either "next" or "prev".
112
#define LIST_SCAN_FROM(p, from, until, member) \
113
for (p = (from); (p) != NULL; \
114
(p) = (((p)->member == (until)) ? NULL : (p)->member))
116
/* scan the entire list (non-destructively) */
117
#define LIST_SCAN(p, l) \
118
LIST_SCAN_FROM(p, LIST_FIRST(l), LIST_FIRST(l), next)
121
/* scan a list backward from last element to first (non-destructively) */
122
#define LIST_SCAN_BACK(p, l) \
123
LIST_SCAN_FROM(p, LIST_LAST_CHK(l), LIST_LAST(l), prev)
125
/* scan the entire list where loop element may be destroyed */
126
#define LIST_SCAN_SAFE(p, pn, l) \
127
if (!LIST_EMPTY(l)) \
128
for (p = (l), (pn) = NextListItem(p, l); (p) != NULL; \
129
(p) = (pn), (pn) = NextListItem(p, l))
131
/* scan the entire list backwards where loop element may be destroyed */
132
#define LIST_SCAN_BACK_SAFE(p, pn, l) \
133
if (!LIST_EMPTY(l)) \
134
for (p = LIST_LAST(l), (pn) = PrevListItem(p, l); (p) != NULL; \
135
(p) = (pn), (pn) = PrevListItem(p, l))
138
/* function definitions */
141
*----------------------------------------------------------------------
145
* Returns the next member of a doubly linked list, or NULL if last.
146
* Assumes: p is member of the list headed by head.
149
* If head or p is NULL, return NULL. Otherwise,
150
* next list member (or null if last).
155
*----------------------------------------------------------------------
158
static INLINE ListItem *
159
NextListItem(ListItem *p, // IN
160
ListItem *head) // IN
162
if (head == NULL || p == NULL) {
165
/* both p and head are non-null */
167
return p == head ? NULL : p;
172
*----------------------------------------------------------------------
176
* Returns the prev member of a doubly linked list, or NULL if first.
177
* Assumes: p is member of the list headed by head.
180
* If head or prev is NULL, return NULL. Otherwise,
181
* prev list member (or null if first).
186
*----------------------------------------------------------------------
189
static INLINE ListItem *
190
PrevListItem(ListItem *p, // IN
191
ListItem *head) // IN
193
if (head == NULL || p == NULL) {
196
/* both p and head are non-null */
197
return p == head ? NULL : p->prev;
202
*----------------------------------------------------------------------
206
* Deletes a member of a doubly linked list, possibly modifies the
207
* list header itself.
208
* Assumes neither p nor headp is null and p is a member of *headp.
216
*----------------------------------------------------------------------
220
DelListItem(ListItem *p, // IN
221
ListItem **headp) // IN/OUT
232
next->prev = p->prev;
233
p->prev->next = next;
242
*----------------------------------------------------------------------
246
* Adds a new member to the back of a doubly linked list (queue)
247
* Assumes neither p nor headp is null and p is not a member of *headp.
255
*----------------------------------------------------------------------
259
QueueListItem(ListItem *p, // IN
260
ListItem **headp) // IN/OUT
265
if (LIST_EMPTY(head)) {
269
p->prev = head->prev;
278
*----------------------------------------------------------------------
282
* Adds a new member to the front of a doubly linked list (stack)
283
* Assumes neither p nor headp is null and p is not a member of *headp.
291
*----------------------------------------------------------------------
295
PushListItem(ListItem *p, // IN
296
ListItem **headp) // IN/OUT
298
QueueListItem(p, headp);
304
*----------------------------------------------------------------------
308
* Make a single list {l1 l2} from {l1} and {l2} and return it.
309
* It is okay for one or both lists to be NULL.
310
* No checking is done. It is assumed that l1 and l2 are two
317
* Modifies l1 and l2 list pointers.
319
*----------------------------------------------------------------------
322
static INLINE ListItem *
323
SpliceLists(ListItem *l1, // IN
326
ListItem *l1Last, *l2Last;
328
if (LIST_EMPTY(l1)) {
332
if (LIST_EMPTY(l2)) {
336
l1Last = l1->prev; /* last elem of l1 */
337
l2Last = l2->prev; /* last elem of l2 */
340
* l1 -> ... -> l1Last l2 -> ... l2Last
353
*----------------------------------------------------------------------
357
* Make a list l = {l1 l2} into two separate lists {l1} and {l2}, where:
358
* l = { ... x -> p -> ... } split into:
361
* Assumes neither p nor l is null and p is a member of l.
362
* If p is the first element of l, then l1 will be NULL.
368
* Sets *l1p and *l2p to the resulting two lists.
369
* Modifies l's pointers.
371
*----------------------------------------------------------------------
375
SplitLists(ListItem *p, // IN
377
ListItem **l1p, // OUT
378
ListItem **l2p) // OUT
382
if (p == LIST_FIRST(l)) { /* first element */
401
*----------------------------------------------------------------------
405
* Return the number of items in the list.
408
* The number of items in the list.
413
*----------------------------------------------------------------------
417
GetListSize(ListItem *head) // IN
422
LIST_SCAN(li, head) {
428
#endif /* _CIRCLIST_H_ */
added
removed
lib/include/circList.h
