huwcampbell.com
Reactos
1/*
2 * Linked lists support
3 *
4 * Copyright (C) 2002 Alexandre Julliard
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
19 */
20
21#ifndef __WINE_SERVER_LIST_H
22#define __WINE_SERVER_LIST_H
23
24#ifdef __cplusplus
25#define __WINE_SERVER_LIST_INLINE inline
26#else
27#if defined(__GNUC__)
28#define __WINE_SERVER_LIST_INLINE extern __inline__ __attribute__((__always_inline__,__gnu_inline__))
29#elif defined(_MSC_VER)
30#define __WINE_SERVER_LIST_INLINE __inline
31#else
32#define __WINE_SERVER_LIST_INLINE static
33#endif
34#endif
35
36struct list
37{
38 struct list *next;
39 struct list *prev;
40};
41
42/* Define a list like so:
43 *
44 * struct gadget
45 * {
46 * struct list entry; <-- doesn't have to be the first item in the struct
47 * int a, b;
48 * };
49 *
50 * static struct list global_gadgets = LIST_INIT( global_gadgets );
51 *
52 * or
53 *
54 * struct some_global_thing
55 * {
56 * struct list gadgets;
57 * };
58 *
59 * list_init( &some_global_thing->gadgets );
60 *
61 * Manipulate it like this:
62 *
63 * list_add_head( &global_gadgets, &new_gadget->entry );
64 * list_remove( &new_gadget->entry );
65 * list_add_after( &some_random_gadget->entry, &new_gadget->entry );
66 *
67 * And to iterate over it:
68 *
69 * struct gadget *gadget;
70 * LIST_FOR_EACH_ENTRY( gadget, &global_gadgets, struct gadget, entry )
71 * {
72 * ...
73 * }
74 *
75 */
76
77/* add an element after the specified one */
78__WINE_SERVER_LIST_INLINE void list_add_after( struct list *elem, struct list *to_add )
79{
80 to_add->next = elem->next;
81 to_add->prev = elem;
82 elem->next->prev = to_add;
83 elem->next = to_add;
84}
85
86/* add an element before the specified one */
87__WINE_SERVER_LIST_INLINE void list_add_before( struct list *elem, struct list *to_add )
88{
89 to_add->next = elem;
90 to_add->prev = elem->prev;
91 elem->prev->next = to_add;
92 elem->prev = to_add;
93}
94
95/* add element at the head of the list */
96__WINE_SERVER_LIST_INLINE void list_add_head( struct list *list, struct list *elem )
97{
98 list_add_after( list, elem );
99}
100
101/* add element at the tail of the list */
102__WINE_SERVER_LIST_INLINE void list_add_tail( struct list *list, struct list *elem )
103{
104 list_add_before( list, elem );
105}
106
107/* remove an element from its list */
108__WINE_SERVER_LIST_INLINE void list_remove( struct list *elem )
109{
110 elem->next->prev = elem->prev;
111 elem->prev->next = elem->next;
112}
113
114/* get the next element */
115__WINE_SERVER_LIST_INLINE struct list *list_next( const struct list *list, const struct list *elem )
116{
117 struct list *ret = elem->next;
118 if (elem->next == list) ret = NULL;
119 return ret;
120}
121
122/* get the previous element */
123__WINE_SERVER_LIST_INLINE struct list *list_prev( const struct list *list, const struct list *elem )
124{
125 struct list *ret = elem->prev;
126 if (elem->prev == list) ret = NULL;
127 return ret;
128}
129
130/* get the first element */
131__WINE_SERVER_LIST_INLINE struct list *list_head( const struct list *list )
132{
133 return list_next( list, list );
134}
135
136/* get the last element */
137__WINE_SERVER_LIST_INLINE struct list *list_tail( const struct list *list )
138{
139 return list_prev( list, list );
140}
141
142/* check if a list is empty */
143__WINE_SERVER_LIST_INLINE int list_empty( const struct list *list )
144{
145 return list->next == list;
146}
147
148/* initialize a list */
149__WINE_SERVER_LIST_INLINE void list_init( struct list *list )
150{
151 list->next = list->prev = list;
152}
153
154/* count the elements of a list */
155__WINE_SERVER_LIST_INLINE unsigned int list_count( const struct list *list )
156{
157 unsigned count = 0;
158 const struct list *ptr;
159 for (ptr = list->next; ptr != list; ptr = ptr->next) count++;
160 return count;
161}
162
163/* move all elements from src to the tail of dst */
164__WINE_SERVER_LIST_INLINE void list_move_tail( struct list *dst, struct list *src )
165{
166 if (list_empty(src)) return;
167
168 dst->prev->next = src->next;
169 src->next->prev = dst->prev;
170 dst->prev = src->prev;
171 src->prev->next = dst;
172 list_init(src);
173}
174
175/* move all elements from src to the head of dst */
176__WINE_SERVER_LIST_INLINE void list_move_head( struct list *dst, struct list *src )
177{
178 if (list_empty(src)) return;
179
180 dst->next->prev = src->prev;
181 src->prev->next = dst->next;
182 dst->next = src->next;
183 src->next->prev = dst;
184 list_init(src);
185}
186
187/* iterate through the list */
188#define LIST_FOR_EACH(cursor,list) \
189 for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next)
190
191/* iterate through the list, with safety against removal */
192#define LIST_FOR_EACH_SAFE(cursor, cursor2, list) \
193 for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \
194 (cursor) != (list); \
195 (cursor) = (cursor2), (cursor2) = (cursor)->next)
196
197/* iterate through the list using a list entry */
198#define LIST_FOR_EACH_ENTRY(elem, list, type, field) \
199 for ((elem) = LIST_ENTRY((list)->next, type, field); \
200 &(elem)->field != (list); \
201 (elem) = LIST_ENTRY((elem)->field.next, type, field))
202
203/* iterate through the list using a list entry, with safety against removal */
204#define LIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field) \
205 for ((cursor) = LIST_ENTRY((list)->next, type, field), \
206 (cursor2) = LIST_ENTRY((cursor)->field.next, type, field); \
207 &(cursor)->field != (list); \
208 (cursor) = (cursor2), \
209 (cursor2) = LIST_ENTRY((cursor)->field.next, type, field))
210
211/* iterate through the list in reverse order */
212#define LIST_FOR_EACH_REV(cursor,list) \
213 for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev)
214
215/* iterate through the list in reverse order, with safety against removal */
216#define LIST_FOR_EACH_SAFE_REV(cursor, cursor2, list) \
217 for ((cursor) = (list)->prev, (cursor2) = (cursor)->prev; \
218 (cursor) != (list); \
219 (cursor) = (cursor2), (cursor2) = (cursor)->prev)
220
221/* iterate through the list in reverse order using a list entry */
222#define LIST_FOR_EACH_ENTRY_REV(elem, list, type, field) \
223 for ((elem) = LIST_ENTRY((list)->prev, type, field); \
224 &(elem)->field != (list); \
225 (elem) = LIST_ENTRY((elem)->field.prev, type, field))
226
227/* iterate through the list in reverse order using a list entry, with safety against removal */
228#define LIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field) \
229 for ((cursor) = LIST_ENTRY((list)->prev, type, field), \
230 (cursor2) = LIST_ENTRY((cursor)->field.prev, type, field); \
231 &(cursor)->field != (list); \
232 (cursor) = (cursor2), \
233 (cursor2) = LIST_ENTRY((cursor)->field.prev, type, field))
234
235/* macros for statically initialized lists */
236#define LIST_INIT(list) { &(list), &(list) }
237
238/* get pointer to object containing list element */
239#ifdef _WIN64
240#define LIST_ENTRY(elem, type, field) \
241 ((type *)((char *)(elem) - (unsigned long long)(&((type *)0)->field)))
242#else
243#define LIST_ENTRY(elem, type, field) \
244 ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field)))
245#endif
246
247#endif /* __WINE_SERVER_LIST_H */