2 * Copyright (c) 2002-2007 Neterion, Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * FileName : xge-list.h
32 * Description: Generic bi-directional linked list implementation
34 * Created: 14 May 2004
40 #include <dev/nxge/include/xge-debug.h>
45 * struct xge_list_t - List item.
46 * @prev: Previous list item.
47 * @next: Next list item.
49 * Item of a bi-directional linked list.
51 typedef struct xge_list_t {
52 struct xge_list_t* prev;
53 struct xge_list_t* next;
57 * xge_list_init - Initialize linked list.
58 * header: first element of the list (head)
60 * Initialize linked list.
61 * See also: xge_list_t{}.
63 static inline void xge_list_init (xge_list_t *header)
65 header->next = header;
66 header->prev = header;
70 * xge_list_is_empty - Is the list empty?
71 * header: first element of the list (head)
73 * Determine whether the bi-directional list is empty. Return '1' in
75 * See also: xge_list_t{}.
77 static inline int xge_list_is_empty(xge_list_t *header)
79 xge_assert(header != NULL);
81 return header->next == header;
85 * xge_list_first_get - Return the first item from the linked list.
86 * header: first element of the list (head)
88 * Returns the next item from the header.
89 * Returns NULL if the next item is header itself
90 * See also: xge_list_remove(), xge_list_insert(), xge_list_t{}.
92 static inline xge_list_t *xge_list_first_get(xge_list_t *header)
94 xge_assert(header != NULL);
95 xge_assert(header->next != NULL);
96 xge_assert(header->prev != NULL);
98 if(header->next == header)
105 * xge_list_remove - Remove the specified item from the linked list.
106 * item: element of the list
108 * Remove item from a list.
109 * See also: xge_list_insert(), xge_list_t{}.
111 static inline void xge_list_remove(xge_list_t *item)
113 xge_assert(item != NULL);
114 xge_assert(item->next != NULL);
115 xge_assert(item->prev != NULL);
117 item->next->prev = item->prev;
118 item->prev->next = item->next;
119 #ifdef XGE_DEBUG_ASSERT
120 item->next = item->prev = NULL;
125 * xge_list_insert - Insert a new item after the specified item.
126 * new_item: new element of the list
127 * prev_item: element of the list after which the new element is
130 * Insert new item (new_item) after given item (prev_item).
131 * See also: xge_list_remove(), xge_list_insert_before(), xge_list_t{}.
133 static inline void xge_list_insert (xge_list_t *new_item,
134 xge_list_t *prev_item)
136 xge_assert(new_item != NULL);
137 xge_assert(prev_item != NULL);
138 xge_assert(prev_item->next != NULL);
140 new_item->next = prev_item->next;
141 new_item->prev = prev_item;
142 prev_item->next->prev = new_item;
143 prev_item->next = new_item;
147 * xge_list_insert_before - Insert a new item before the specified item.
148 * new_item: new element of the list
149 * next_item: element of the list after which the new element is inserted
151 * Insert new item (new_item) before given item (next_item).
153 static inline void xge_list_insert_before (xge_list_t *new_item,
154 xge_list_t *next_item)
156 xge_assert(new_item != NULL);
157 xge_assert(next_item != NULL);
158 xge_assert(next_item->next != NULL);
160 new_item->next = next_item;
161 new_item->prev = next_item->prev;
162 next_item->prev->next = new_item;
163 next_item->prev = new_item;
166 #define xge_list_for_each(_p, _h) \
167 for (_p = (_h)->next, xge_os_prefetch(_p->next); _p != (_h); \
168 _p = _p->next, xge_os_prefetch(_p->next))
170 #define xge_list_for_each_safe(_p, _n, _h) \
171 for (_p = (_h)->next, _n = _p->next; _p != (_h); \
172 _p = _n, _n = _p->next)
176 * xge_container_of - Given a member, return the containing structure.
177 * @ptr: the pointer to the member.
178 * @type: the type of the container struct this is embedded in.
179 * @member: the name of the member within the struct.
181 * Cast a member of a structure out to the containing structure.
183 #define xge_container_of(ptr, type, member) ({ \
184 __typeof( ((type *)0)->member ) *__mptr = (ptr); \
185 (type *)(void *)( (char *)__mptr - ((size_t) &((type *)0)->member) );})
187 /* type unsafe version */
188 #define xge_container_of(ptr, type, member) \
189 ((type*)(void*)((char*)(ptr) - ((size_t) &((type *)0)->member)))
193 * xge_offsetof - Offset of the member in the containing structure.
195 * @m: the name of the member within the struct.
197 * Return the offset of the member @m in the structure @t.
199 #define xge_offsetof(t, m) ((size_t) (&((t *)0)->m))
203 #endif /* XGE_LIST_H */