2 * shl - Double Linked List
4 * Copyright (c) 2011-2012 David Herrmann <dh.herrmann@googlemail.com>
5 * Copyright (c) 2011 University of Tuebingen
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files
9 * (the "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
15 * The above copyright notice and this permission notice shall be included
16 * in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
21 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
22 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 * A simple double linked list implementation
41 #define shl_offsetof(pointer, type, member) ({ \
42 const typeof(((type*)0)->member) *__ptr = (pointer); \
43 (type*)(((char*)__ptr) - offsetof(type, member)); \
46 /* double linked list */
49 struct shl_dlist *next;
50 struct shl_dlist *prev;
53 #define SHL_DLIST_INIT(head) { &(head), &(head) }
55 static inline void shl_dlist_init(struct shl_dlist *list)
61 static inline void shl_dlist__link(struct shl_dlist *prev,
62 struct shl_dlist *next,
71 static inline void shl_dlist_link(struct shl_dlist *head,
74 return shl_dlist__link(head, head->next, n);
77 static inline void shl_dlist_link_tail(struct shl_dlist *head,
80 return shl_dlist__link(head->prev, head, n);
83 static inline void shl_dlist__unlink(struct shl_dlist *prev,
84 struct shl_dlist *next)
90 static inline void shl_dlist_unlink(struct shl_dlist *e)
92 shl_dlist__unlink(e->prev, e->next);
97 static inline bool shl_dlist_empty(struct shl_dlist *head)
99 return head->next == head;
102 #define shl_dlist_entry(ptr, type, member) \
103 shl_offsetof((ptr), type, member)
105 #define shl_dlist_first(head, type, member) \
106 shl_dlist_entry((head)->next, type, member)
108 #define shl_dlist_last(head, type, member) \
109 shl_dlist_entry((head)->prev, type, member)
111 #define shl_dlist_for_each(iter, head) \
112 for (iter = (head)->next; iter != (head); iter = iter->next)
114 #define shl_dlist_for_each_but_one(iter, start, head) \
115 for (iter = ((start)->next == (head)) ? \
116 (start)->next->next : \
119 iter = (iter->next == (head) && (start) != (head)) ? \
123 #define shl_dlist_for_each_safe(iter, tmp, head) \
124 for (iter = (head)->next, tmp = iter->next; iter != (head); \
125 iter = tmp, tmp = iter->next)
127 #define shl_dlist_for_each_reverse(iter, head) \
128 for (iter = (head)->prev; iter != (head); iter = iter->prev)
130 #define shl_dlist_for_each_reverse_but_one(iter, start, head) \
131 for (iter = ((start)->prev == (head)) ? \
132 (start)->prev->prev : \
135 iter = (iter->prev == (head) && (start) != (head)) ? \
139 #define shl_dlist_for_each_reverse_safe(iter, tmp, head) \
140 for (iter = (head)->prev, tmp = iter->prev; iter != (head); \
141 iter = tmp, tmp = iter->prev)
143 #endif /* SHL_DLIST_H */