1a04d0423SBen Skeggs/*
2a04d0423SBen Skeggs * Copyright �� 2010 Intel Corporation
3a04d0423SBen Skeggs * Copyright �� 2010 Francisco Jerez <currojerez@riseup.net>
4a04d0423SBen Skeggs *
5a04d0423SBen Skeggs * Permission is hereby granted, free of charge, to any person obtaining a
6a04d0423SBen Skeggs * copy of this software and associated documentation files (the "Software"),
7a04d0423SBen Skeggs * to deal in the Software without restriction, including without limitation
8a04d0423SBen Skeggs * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9a04d0423SBen Skeggs * and/or sell copies of the Software, and to permit persons to whom the
10a04d0423SBen Skeggs * Software is furnished to do so, subject to the following conditions:
11a04d0423SBen Skeggs *
12a04d0423SBen Skeggs * The above copyright notice and this permission notice (including the next
13a04d0423SBen Skeggs * paragraph) shall be included in all copies or substantial portions of the
14a04d0423SBen Skeggs * Software.
15a04d0423SBen Skeggs *
22a04d0423SBen Skeggs * IN THE SOFTWARE.
23a04d0423SBen Skeggs *
24a04d0423SBen Skeggs */
25a04d0423SBen Skeggs
26a04d0423SBen Skeggs/* Modified by Ben Skeggs <bskeggs@redhat.com> to match kernel list APIs */
27a04d0423SBen Skeggs
28a04d0423SBen Skeggs#ifndef _XORG_LIST_H_
29a04d0423SBen Skeggs#define _XORG_LIST_H_
30a04d0423SBen Skeggs
31a04d0423SBen Skeggs/**
32a04d0423SBen Skeggs * @file Classic doubly-link circular list implementation.
33a04d0423SBen Skeggs * For real usage examples of the linked list, see the file test/list.c
34a04d0423SBen Skeggs *
35a04d0423SBen Skeggs * Example:
36a04d0423SBen Skeggs * We need to keep a list of struct foo in the parent struct bar, i.e. what
37a04d0423SBen Skeggs * we want is something like this.
38a04d0423SBen Skeggs *
39a04d0423SBen Skeggs *     struct bar {
40a04d0423SBen Skeggs *          ...
41a04d0423SBen Skeggs *          struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{}
42a04d0423SBen Skeggs *          ...
43a04d0423SBen Skeggs *     }
44a04d0423SBen Skeggs *
45a04d0423SBen Skeggs * We need one list head in bar and a list element in all list_of_foos (both are of
46a04d0423SBen Skeggs * data type 'struct list_head').
47a04d0423SBen Skeggs *
48a04d0423SBen Skeggs *     struct bar {
49a04d0423SBen Skeggs *          ...
50a04d0423SBen Skeggs *          struct list_head list_of_foos;
51a04d0423SBen Skeggs *          ...
52a04d0423SBen Skeggs *     }
53a04d0423SBen Skeggs *
54a04d0423SBen Skeggs *     struct foo {
55a04d0423SBen Skeggs *          ...
56a04d0423SBen Skeggs *          struct list_head entry;
57a04d0423SBen Skeggs *          ...
58a04d0423SBen Skeggs *     }
59a04d0423SBen Skeggs *
60a04d0423SBen Skeggs * Now we initialize the list head:
61a04d0423SBen Skeggs *
62a04d0423SBen Skeggs *     struct bar bar;
63a04d0423SBen Skeggs *     ...
64a04d0423SBen Skeggs *     INIT_LIST_HEAD(&bar.list_of_foos);
65a04d0423SBen Skeggs *
66a04d0423SBen Skeggs * Then we create the first element and add it to this list:
67a04d0423SBen Skeggs *
68a04d0423SBen Skeggs *     struct foo *foo = malloc(...);
69a04d0423SBen Skeggs *     ....
70a04d0423SBen Skeggs *     list_add(&foo->entry, &bar.list_of_foos);
71a04d0423SBen Skeggs *
72a04d0423SBen Skeggs * Repeat the above for each element you want to add to the list. Deleting
73a04d0423SBen Skeggs * works with the element itself.
74a04d0423SBen Skeggs *      list_del(&foo->entry);
75a04d0423SBen Skeggs *      free(foo);
76a04d0423SBen Skeggs *
77a04d0423SBen Skeggs * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty
78a04d0423SBen Skeggs * list again.
79a04d0423SBen Skeggs *
80a04d0423SBen Skeggs * Looping through the list requires a 'struct foo' as iterator and the
81a04d0423SBen Skeggs * name of the field the subnodes use.
82a04d0423SBen Skeggs *
83a04d0423SBen Skeggs * struct foo *iterator;
84a04d0423SBen Skeggs * list_for_each_entry(iterator, &bar.list_of_foos, entry) {
85a04d0423SBen Skeggs *      if (iterator->something == ...)
86a04d0423SBen Skeggs *             ...
87a04d0423SBen Skeggs * }
88a04d0423SBen Skeggs *
89a04d0423SBen Skeggs * Note: You must not call list_del() on the iterator if you continue the
90a04d0423SBen Skeggs * loop. You need to run the safe for-each loop instead:
91a04d0423SBen Skeggs *
92a04d0423SBen Skeggs * struct foo *iterator, *next;
93a04d0423SBen Skeggs * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) {
94a04d0423SBen Skeggs *      if (...)
95a04d0423SBen Skeggs *              list_del(&iterator->entry);
96a04d0423SBen Skeggs * }
97a04d0423SBen Skeggs *
98a04d0423SBen Skeggs */
99a04d0423SBen Skeggs
100a04d0423SBen Skeggs/**
101a04d0423SBen Skeggs * The linkage struct for list nodes. This struct must be part of your
102a04d0423SBen Skeggs * to-be-linked struct. struct list_head is required for both the head of the
103a04d0423SBen Skeggs * list and for each list node.
104a04d0423SBen Skeggs *
105a04d0423SBen Skeggs * Position and name of the struct list_head field is irrelevant.
106a04d0423SBen Skeggs * There are no requirements that elements of a list are of the same type.
107a04d0423SBen Skeggs * There are no requirements for a list head, any struct list_head can be a list
108a04d0423SBen Skeggs * head.
109a04d0423SBen Skeggs */
110a04d0423SBen Skeggsstruct list_head {
111a04d0423SBen Skeggs    struct list_head *next, *prev;
112a04d0423SBen Skeggs};
113a04d0423SBen Skeggs
114a04d0423SBen Skeggs/**
115a04d0423SBen Skeggs * Initialize the list as an empty list.
116a04d0423SBen Skeggs *
117a04d0423SBen Skeggs * Example:
118a04d0423SBen Skeggs * INIT_LIST_HEAD(&bar->list_of_foos);
119a04d0423SBen Skeggs *
120a04d0423SBen Skeggs * @param The list to initialized.
121a04d0423SBen Skeggs */
122a04d0423SBen Skeggs#define LIST_HEAD_INIT(name) { &(name), &(name) }
123a04d0423SBen Skeggs
124a04d0423SBen Skeggs#define LIST_HEAD(name) \
125a04d0423SBen Skeggs	struct list_head name = LIST_HEAD_INIT(name)
126a04d0423SBen Skeggs
127a04d0423SBen Skeggsstatic inline void
128a04d0423SBen SkeggsINIT_LIST_HEAD(struct list_head *list)
129a04d0423SBen Skeggs{
130a04d0423SBen Skeggs    list->next = list->prev = list;
131a04d0423SBen Skeggs}
132a04d0423SBen Skeggs
133a04d0423SBen Skeggsstatic inline void
134a04d0423SBen Skeggs__list_add(struct list_head *entry,
135a04d0423SBen Skeggs                struct list_head *prev, struct list_head *next)
136a04d0423SBen Skeggs{
137a04d0423SBen Skeggs    next->prev = entry;
138a04d0423SBen Skeggs    entry->next = next;
139a04d0423SBen Skeggs    entry->prev = prev;
140a04d0423SBen Skeggs    prev->next = entry;
141a04d0423SBen Skeggs}
142a04d0423SBen Skeggs
143a04d0423SBen Skeggs/**
144a04d0423SBen Skeggs * Insert a new element after the given list head. The new element does not
145a04d0423SBen Skeggs * need to be initialised as empty list.
146a04d0423SBen Skeggs * The list changes from:
147a04d0423SBen Skeggs *      head ��� some element ��� ...
148a04d0423SBen Skeggs * to
149a04d0423SBen Skeggs *      head ��� new element ��� older element ��� ...
150a04d0423SBen Skeggs *
151a04d0423SBen Skeggs * Example:
152a04d0423SBen Skeggs * struct foo *newfoo = malloc(...);
153a04d0423SBen Skeggs * list_add(&newfoo->entry, &bar->list_of_foos);
154a04d0423SBen Skeggs *
155a04d0423SBen Skeggs * @param entry The new element to prepend to the list.
156a04d0423SBen Skeggs * @param head The existing list.
157a04d0423SBen Skeggs */
158a04d0423SBen Skeggsstatic inline void
159a04d0423SBen Skeggslist_add(struct list_head *entry, struct list_head *head)
160a04d0423SBen Skeggs{
161a04d0423SBen Skeggs    __list_add(entry, head, head->next);
162a04d0423SBen Skeggs}
163a04d0423SBen Skeggs
164a04d0423SBen Skeggs/**
165a04d0423SBen Skeggs * Append a new element to the end of the list given with this list head.
166a04d0423SBen Skeggs *
167a04d0423SBen Skeggs * The list changes from:
168a04d0423SBen Skeggs *      head ��� some element ��� ... ��� lastelement
169a04d0423SBen Skeggs * to
170a04d0423SBen Skeggs *      head ��� some element ��� ... ��� lastelement ��� new element
171a04d0423SBen Skeggs *
172a04d0423SBen Skeggs * Example:
173a04d0423SBen Skeggs * struct foo *newfoo = malloc(...);
174a04d0423SBen Skeggs * list_add_tail(&newfoo->entry, &bar->list_of_foos);
175a04d0423SBen Skeggs *
176a04d0423SBen Skeggs * @param entry The new element to prepend to the list.
177a04d0423SBen Skeggs * @param head The existing list.
178a04d0423SBen Skeggs */
179a04d0423SBen Skeggsstatic inline void
180a04d0423SBen Skeggslist_add_tail(struct list_head *entry, struct list_head *head)
181a04d0423SBen Skeggs{
182a04d0423SBen Skeggs    __list_add(entry, head->prev, head);
183a04d0423SBen Skeggs}
184a04d0423SBen Skeggs
185a04d0423SBen Skeggsstatic inline void
186a04d0423SBen Skeggs__list_del(struct list_head *prev, struct list_head *next)
187a04d0423SBen Skeggs{
188a04d0423SBen Skeggs    next->prev = prev;
189a04d0423SBen Skeggs    prev->next = next;
190a04d0423SBen Skeggs}
191a04d0423SBen Skeggs
192a04d0423SBen Skeggs/**
193a04d0423SBen Skeggs * Remove the element from the list it is in. Using this function will reset
194a04d0423SBen Skeggs * the pointers to/from this element so it is removed from the list. It does
195a04d0423SBen Skeggs * NOT free the element itself or manipulate it otherwise.
196a04d0423SBen Skeggs *
197a04d0423SBen Skeggs * Using list_del on a pure list head (like in the example at the top of
198a04d0423SBen Skeggs * this file) will NOT remove the first element from
199a04d0423SBen Skeggs * the list but rather reset the list as empty list.
200a04d0423SBen Skeggs *
201a04d0423SBen Skeggs * Example:
202a04d0423SBen Skeggs * list_del(&foo->entry);
203a04d0423SBen Skeggs *
204a04d0423SBen Skeggs * @param entry The element to remove.
205a04d0423SBen Skeggs */
206a04d0423SBen Skeggsstatic inline void
207a04d0423SBen Skeggslist_del(struct list_head *entry)
208a04d0423SBen Skeggs{
209a04d0423SBen Skeggs    __list_del(entry->prev, entry->next);
210a04d0423SBen Skeggs}
211a04d0423SBen Skeggs
212a04d0423SBen Skeggsstatic inline void
213a04d0423SBen Skeggslist_del_init(struct list_head *entry)
214a04d0423SBen Skeggs{
215a04d0423SBen Skeggs    __list_del(entry->prev, entry->next);
216a04d0423SBen Skeggs    INIT_LIST_HEAD(entry);
217a04d0423SBen Skeggs}
218a04d0423SBen Skeggs
219a04d0423SBen Skeggsstatic inline void list_move_tail(struct list_head *list,
220a04d0423SBen Skeggs				  struct list_head *head)
221a04d0423SBen Skeggs{
222a04d0423SBen Skeggs	__list_del(list->prev, list->next);
223a04d0423SBen Skeggs	list_add_tail(list, head);
224a04d0423SBen Skeggs}
225a04d0423SBen Skeggs
226a04d0423SBen Skeggs/**
227a04d0423SBen Skeggs * Check if the list is empty.
228a04d0423SBen Skeggs *
229a04d0423SBen Skeggs * Example:
230a04d0423SBen Skeggs * list_empty(&bar->list_of_foos);
231a04d0423SBen Skeggs *
232a04d0423SBen Skeggs * @return True if the list contains one or more elements or False otherwise.
233a04d0423SBen Skeggs */
234a04d0423SBen Skeggsstatic inline bool
235a04d0423SBen Skeggslist_empty(struct list_head *head)
236a04d0423SBen Skeggs{
237a04d0423SBen Skeggs    return head->next == head;
238a04d0423SBen Skeggs}
239a04d0423SBen Skeggs
240a04d0423SBen Skeggs/**
241a04d0423SBen Skeggs * Returns a pointer to the container of this list element.
242a04d0423SBen Skeggs *
243a04d0423SBen Skeggs * Example:
244a04d0423SBen Skeggs * struct foo* f;
245a04d0423SBen Skeggs * f = container_of(&foo->entry, struct foo, entry);
246a04d0423SBen Skeggs * assert(f == foo);
247a04d0423SBen Skeggs *
248a04d0423SBen Skeggs * @param ptr Pointer to the struct list_head.
249a04d0423SBen Skeggs * @param type Data type of the list element.
250a04d0423SBen Skeggs * @param member Member name of the struct list_head field in the list element.
251a04d0423SBen Skeggs * @return A pointer to the data struct containing the list head.
252a04d0423SBen Skeggs */
253a04d0423SBen Skeggs#ifndef container_of
254a04d0423SBen Skeggs#define container_of(ptr, type, member) \
255a04d0423SBen Skeggs    (type *)((char *)(ptr) - (char *) &((type *)0)->member)
256a04d0423SBen Skeggs#endif
257a04d0423SBen Skeggs
258a04d0423SBen Skeggs/**
259a04d0423SBen Skeggs * Alias of container_of
260a04d0423SBen Skeggs */
261a04d0423SBen Skeggs#define list_entry(ptr, type, member) \
262a04d0423SBen Skeggs    container_of(ptr, type, member)
263a04d0423SBen Skeggs
264a04d0423SBen Skeggs/**
265a04d0423SBen Skeggs * Retrieve the first list entry for the given list pointer.
266a04d0423SBen Skeggs *
267a04d0423SBen Skeggs * Example:
268a04d0423SBen Skeggs * struct foo *first;
269a04d0423SBen Skeggs * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos);
270a04d0423SBen Skeggs *
271a04d0423SBen Skeggs * @param ptr The list head
272a04d0423SBen Skeggs * @param type Data type of the list element to retrieve
273a04d0423SBen Skeggs * @param member Member name of the struct list_head field in the list element.
274a04d0423SBen Skeggs * @return A pointer to the first list element.
275a04d0423SBen Skeggs */
276a04d0423SBen Skeggs#define list_first_entry(ptr, type, member) \
277a04d0423SBen Skeggs    list_entry((ptr)->next, type, member)
278a04d0423SBen Skeggs
279a04d0423SBen Skeggs/**
280a04d0423SBen Skeggs * Retrieve the last list entry for the given listpointer.
281a04d0423SBen Skeggs *
282a04d0423SBen Skeggs * Example:
283a04d0423SBen Skeggs * struct foo *first;
284a04d0423SBen Skeggs * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos);
285a04d0423SBen Skeggs *
286a04d0423SBen Skeggs * @param ptr The list head
287a04d0423SBen Skeggs * @param type Data type of the list element to retrieve
288a04d0423SBen Skeggs * @param member Member name of the struct list_head field in the list element.
289a04d0423SBen Skeggs * @return A pointer to the last list element.
290a04d0423SBen Skeggs */
291a04d0423SBen Skeggs#define list_last_entry(ptr, type, member) \
292a04d0423SBen Skeggs    list_entry((ptr)->prev, type, member)
293a04d0423SBen Skeggs
294a04d0423SBen Skeggs#define __container_of(ptr, sample, member)				\
295a04d0423SBen Skeggs    (void *)container_of((ptr), typeof(*(sample)), member)
296a04d0423SBen Skeggs
297a04d0423SBen Skeggs/**
298a04d0423SBen Skeggs * Loop through the list given by head and set pos to struct in the list.
299a04d0423SBen Skeggs *
300a04d0423SBen Skeggs * Example:
301a04d0423SBen Skeggs * struct foo *iterator;
302a04d0423SBen Skeggs * list_for_each_entry(iterator, &bar->list_of_foos, entry) {
303a04d0423SBen Skeggs *      [modify iterator]
304a04d0423SBen Skeggs * }
305a04d0423SBen Skeggs *
306a04d0423SBen Skeggs * This macro is not safe for node deletion. Use list_for_each_entry_safe
307a04d0423SBen Skeggs * instead.
308a04d0423SBen Skeggs *
309a04d0423SBen Skeggs * @param pos Iterator variable of the type of the list elements.
310a04d0423SBen Skeggs * @param head List head
311a04d0423SBen Skeggs * @param member Member name of the struct list_head in the list elements.
312a04d0423SBen Skeggs *
313a04d0423SBen Skeggs */
314a04d0423SBen Skeggs#define list_for_each_entry(pos, head, member)				\
315a04d0423SBen Skeggs    for (pos = __container_of((head)->next, pos, member);		\
316a04d0423SBen Skeggs	 &pos->member != (head);					\
317a04d0423SBen Skeggs	 pos = __container_of(pos->member.next, pos, member))
318a04d0423SBen Skeggs
319a04d0423SBen Skeggs/**
320a04d0423SBen Skeggs * Loop through the list, keeping a backup pointer to the element. This
321a04d0423SBen Skeggs * macro allows for the deletion of a list element while looping through the
322a04d0423SBen Skeggs * list.
323a04d0423SBen Skeggs *
324a04d0423SBen Skeggs * See list_for_each_entry for more details.
325a04d0423SBen Skeggs */
326a04d0423SBen Skeggs#define list_for_each_entry_safe(pos, tmp, head, member)		\
327a04d0423SBen Skeggs    for (pos = __container_of((head)->next, pos, member),		\
328a04d0423SBen Skeggs	 tmp = __container_of(pos->member.next, pos, member);		\
329a04d0423SBen Skeggs	 &pos->member != (head);					\
330a04d0423SBen Skeggs	 pos = tmp, tmp = __container_of(pos->member.next, tmp, member))
331a04d0423SBen Skeggs
332a04d0423SBen Skeggs
333a04d0423SBen Skeggs#define list_for_each_entry_reverse(pos, head, member)			\
334a04d0423SBen Skeggs	for (pos = __container_of((head)->prev, pos, member);		\
335a04d0423SBen Skeggs	     &pos->member != (head);					\
336a04d0423SBen Skeggs	     pos = __container_of(pos->member.prev, pos, member))
337a04d0423SBen Skeggs
338a04d0423SBen Skeggs#define list_for_each_entry_continue(pos, head, member)			\
339a04d0423SBen Skeggs	for (pos = __container_of(pos->member.next, pos, member);	\
340a04d0423SBen Skeggs	     &pos->member != (head);					\
341a04d0423SBen Skeggs	     pos = __container_of(pos->member.next, pos, member))
342a04d0423SBen Skeggs
343a04d0423SBen Skeggs#define list_for_each_entry_continue_reverse(pos, head, member)		\
344a04d0423SBen Skeggs	for (pos = __container_of(pos->member.prev, pos, member);	\
345a04d0423SBen Skeggs	     &pos->member != (head);					\
346a04d0423SBen Skeggs	     pos = __container_of(pos->member.prev, pos, member))
347a04d0423SBen Skeggs
348a04d0423SBen Skeggs#define list_for_each_entry_from(pos, head, member)			\
349a04d0423SBen Skeggs	for (;								\
350a04d0423SBen Skeggs	     &pos->member != (head);					\
351a04d0423SBen Skeggs	     pos = __container_of(pos->member.next, pos, member))
352a04d0423SBen Skeggs
353a04d0423SBen Skeggs#endif