5e940cc111057d5ff725ec591bea376bc272d201
[wimlib] / include / wimlib / list.h
1
2 /*
3  * This file is based on include/linux/list.h in the Linux kernel source code.
4  */
5
6 #ifndef _WIMLIB_LIST_H
7 #define _WIMLIB_LIST_H
8
9 #include <stdbool.h>
10 #include <stddef.h>
11
12 struct list_head {
13         struct list_head *next, *prev;
14 };
15 struct hlist_head {
16         struct hlist_node *first;
17 };
18
19 struct hlist_node {
20         struct hlist_node *next, **pprev;
21 };
22
23 /*
24  * Simple doubly linked list implementation.
25  *
26  * Some of the internal functions ("__xxx") are useful when
27  * manipulating whole lists rather than single entries, as
28  * sometimes we already know the next/prev entries and we can
29  * generate better code by using them directly rather than
30  * using the generic single-entry routines.
31  */
32
33 #define LIST_HEAD_INIT(name) { &(name), &(name) }
34
35 #ifdef LIST_HEAD /* BSD sys/queue.h defines this... */
36 #  undef LIST_HEAD
37 #endif
38
39 #define LIST_HEAD(name) \
40         struct list_head name = LIST_HEAD_INIT(name)
41
42 static inline void
43 INIT_LIST_HEAD(struct list_head *list)
44 {
45         list->next = list;
46         list->prev = list;
47 }
48
49 /*
50  * Insert a new entry between two known consecutive entries.
51  *
52  * This is only for internal list manipulation where we know
53  * the prev/next entries already!
54  */
55 static inline void
56 __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
57 {
58         next->prev = new;
59         new->next = next;
60         new->prev = prev;
61         prev->next = new;
62 }
63
64 /**
65  * list_add - add a new entry
66  * @new: new entry to be added
67  * @head: list head to add it after
68  *
69  * Insert a new entry after the specified head.
70  * This is good for implementing stacks.
71  */
72 static inline void
73 list_add(struct list_head *new, struct list_head *head)
74 {
75         __list_add(new, head, head->next);
76 }
77
78 /**
79  * list_add_tail - add a new entry
80  * @new: new entry to be added
81  * @head: list head to add it before
82  *
83  * Insert a new entry before the specified head.
84  * This is useful for implementing queues.
85  */
86 static inline void
87 list_add_tail(struct list_head *new, struct list_head *head)
88 {
89         __list_add(new, head->prev, head);
90 }
91
92 /**
93  * list_replace - replace old entry by new one
94  * @old : the element to be replaced
95  * @new : the new element to insert
96  *
97  * If @old was empty, it will be overwritten.
98  */
99 static inline void
100 list_replace(struct list_head *old, struct list_head *new)
101 {
102         new->next = old->next;
103         new->next->prev = new;
104         new->prev = old->prev;
105         new->prev->next = new;
106 }
107
108 /**
109  * list_del - deletes entry from list.
110  * @entry: the element to delete from the list.
111  * Note: list_empty() on entry does not return true after this, the entry is
112  * in an undefined state.
113  */
114 static inline void
115 list_del(struct list_head *entry)
116 {
117         struct list_head *prev = entry->prev;
118         struct list_head *next = entry->next;
119
120         prev->next = next;
121         next->prev = prev;
122 }
123
124 /**
125  * list_empty - tests whether a list is empty
126  * @head: the list to test.
127  */
128 static inline bool
129 list_empty(const struct list_head *head)
130 {
131         return head->next == head;
132 }
133
134 static inline void
135 __list_splice(const struct list_head *list,
136               struct list_head *prev,
137               struct list_head *next)
138 {
139         struct list_head *first = list->next;
140         struct list_head *last = list->prev;
141
142         first->prev = prev;
143         prev->next = first;
144
145         last->next = next;
146         next->prev = last;
147 }
148
149 /**
150  * list_splice - join two lists, this is designed for stacks
151  * @list: the new list to add.
152  * @head: the place to add it in the first list.
153  */
154 static inline void
155 list_splice(const struct list_head *list, struct list_head *head)
156 {
157         if (!list_empty(list))
158                 __list_splice(list, head, head->next);
159 }
160
161 /* Move the entire list @old to the list @new, overwriting it. */
162 static inline void
163 list_transfer(struct list_head *old, struct list_head *new)
164 {
165         struct list_head *prev, *next;
166
167         if (list_empty(old)) {
168                 INIT_LIST_HEAD(new);
169         } else {
170                 prev = old->prev;
171                 next = old->next;
172                 new->next = next;
173                 new->prev = prev;
174                 prev->next = new;
175                 next->prev = new;
176         }
177 }
178
179 /**
180  * list_move - delete from one list and add as another's head
181  * @list: the entry to move
182  * @head: the head that will precede our entry
183  */
184 static inline void
185 list_move(struct list_head *list, struct list_head *head)
186 {
187         list_del(list);
188         list_add(list, head);
189 }
190
191 /**
192  * list_move_tail - delete from one list and add as another's tail
193  * @list: the entry to move
194  * @head: the head that will follow our entry
195  */
196 static inline void
197 list_move_tail(struct list_head *list, struct list_head *head)
198 {
199         list_del(list);
200         list_add_tail(list, head);
201 }
202
203 /**
204  * list_splice_tail - join two lists, each list being a queue
205  * @list: the new list to add.
206  * @head: the place to add it in the first list.
207  */
208 static inline void
209 list_splice_tail(struct list_head *list, struct list_head *head)
210 {
211         if (!list_empty(list))
212                 __list_splice(list, head->prev, head);
213 }
214
215 /**
216  * list_entry - get the struct for this entry
217  * @ptr:        the &struct list_head pointer.
218  * @type:       the type of the struct this is embedded in.
219  * @member:     the name of the list_struct within the struct.
220  */
221 #define list_entry(ptr, type, member) \
222         container_of(ptr, type, member)
223
224 /**
225  * list_first_entry - get the first element from a list
226  * @ptr:        the list head to take the element from.
227  * @type:       the type of the struct this is embedded in.
228  * @member:     the name of the list_struct within the struct.
229  *
230  * Note, that list is expected to be not empty.
231  */
232 #define list_first_entry(ptr, type, member) \
233         list_entry((ptr)->next, type, member)
234
235 /**
236  * list_last_entry - get the last element from a list
237  * @ptr:        the list head to take the element from.
238  * @type:       the type of the struct this is embedded in.
239  * @member:     the name of the list_struct within the struct.
240  *
241  * Note, that list is expected to be not empty.
242  */
243 #define list_last_entry(ptr, type, member) \
244         list_entry((ptr)->prev, type, member)
245
246 /**
247  * list_next_entry - get the next element in list
248  * @pos:        the type * to cursor
249  * @member:     the name of the list_struct within the struct.
250  */
251 #define list_next_entry(pos, member) \
252         list_entry((pos)->member.next, typeof(*(pos)), member)
253
254 /**
255  * list_prev_entry - get the prev element in list
256  * @pos:        the type * to cursor
257  * @member:     the name of the list_struct within the struct.
258  */
259 #define list_prev_entry(pos, member) \
260         list_entry((pos)->member.prev, typeof(*(pos)), member)
261
262
263 /**
264  * list_for_each        -       iterate over a list
265  * @pos:        the &struct list_head to use as a loop cursor.
266  * @head:       the head for your list.
267  */
268 #define list_for_each(pos, head) \
269         for (pos = (head)->next; pos != (head); pos = pos->next)
270
271 /**
272  * list_for_each_entry  -       iterate over list of given type
273  * @pos:        the type * to use as a loop cursor.
274  * @head:       the head for your list.
275  * @member:     the name of the list_struct within the struct.
276  */
277 #define list_for_each_entry(pos, head, member)                          \
278         for (pos = list_first_entry(head, typeof(*pos), member);        \
279              &pos->member != (head);                                    \
280              pos = list_next_entry(pos, member))
281
282 /**
283  * list_for_each_entry_reverse - iterate backwards over list of given type.
284  * @pos:        the type * to use as a loop cursor.
285  * @head:       the head for your list.
286  * @member:     the name of the list_struct within the struct.
287  */
288 #define list_for_each_entry_reverse(pos, head, member)                  \
289         for (pos = list_last_entry(head, typeof(*pos), member);         \
290              &pos->member != (head);                                    \
291              pos = list_prev_entry(pos, member))
292
293 /**
294  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
295  * @pos:        the type * to use as a loop cursor.
296  * @n:          another type * to use as temporary storage
297  * @head:       the head for your list.
298  * @member:     the name of the list_struct within the struct.
299  */
300 #define list_for_each_entry_safe(pos, n, head, member)                  \
301         for (pos = list_entry((head)->next, typeof(*pos), member),      \
302                 n = list_entry(pos->member.next, typeof(*pos), member); \
303              &pos->member != (head);                                    \
304              pos = n, n = list_entry(n->member.next, typeof(*n), member))
305
306 /*
307  * Double linked lists with a single pointer list head.
308  * Mostly useful for hash tables where the two pointer list head is
309  * too wasteful.
310  * You lose the ability to access the tail in O(1).
311  */
312
313 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
314
315 static inline bool
316 hlist_unhashed(const struct hlist_node *h)
317 {
318         return !h->pprev;
319 }
320
321 static inline bool
322 hlist_empty(const struct hlist_head *h)
323 {
324         return !h->first;
325 }
326
327 static inline void
328 hlist_del(struct hlist_node *n)
329 {
330         struct hlist_node *next = n->next;
331         struct hlist_node **pprev = n->pprev;
332         *pprev = next;
333         if (next)
334                 next->pprev = pprev;
335 }
336
337 static inline void
338 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
339 {
340         struct hlist_node *first = h->first;
341         n->next = first;
342         if (first)
343                 first->pprev = &n->next;
344         h->first = n;
345         n->pprev = &h->first;
346 }
347
348 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
349
350 /**
351  * hlist_for_each_entry - iterate over list of given type
352  * @tpos:       the type * to use as a loop cursor.
353  * @pos:        the &struct hlist_node to use as a loop cursor.
354  * @head:       the head for your list.
355  * @member:     the name of the hlist_node within the struct.
356  */
357 #define hlist_for_each_entry(tpos, pos, head, member)                    \
358         for (pos = (head)->first;                                        \
359              pos &&                                                      \
360                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
361              pos = pos->next)
362
363 /**
364  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
365  * @tpos:       the type * to use as a loop cursor.
366  * @pos:        the &struct hlist_node to use as a loop cursor.
367  * @n:          another &struct hlist_node to use as temporary storage
368  * @head:       the head for your list.
369  * @member:     the name of the hlist_node within the struct.
370  */
371 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
372         for (pos = (head)->first;                                        \
373              pos && ({ n = pos->next; 1; }) &&                           \
374                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
375              pos = n)
376
377 #endif /* _WIMLIB_LIST_H */