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
36 struct 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 */
list_add_after(struct list * elem,struct list * to_add)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 */
list_add_before(struct list * elem,struct list * to_add)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 */
list_add_head(struct list * list,struct list * elem)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 */
list_add_tail(struct list * list,struct list * elem)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 */
list_remove(struct list * elem)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 */
list_next(const struct list * list,const struct list * elem)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 */
list_prev(const struct list * list,const struct list * elem)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 */
list_head(const struct list * list)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 */
list_tail(const struct list * list)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 */
list_empty(const struct list * list)143 __WINE_SERVER_LIST_INLINE int list_empty( const struct list *list )
144 {
145 return list->next == list;
146 }
147
148 /* initialize a list */
list_init(struct list * 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 */
list_count(const struct list * 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 */
list_move_tail(struct list * dst,struct list * src)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 */
list_move_head(struct list * dst,struct list * src)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 */
248