Xenomai  3.1
shared-list.h
1 /*
2  * Copyright (C) 2010 Philippe Gerum <rpm@xenomai.org>.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13 
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
17  */
18 #ifndef _BOILERPLATE_SHARED_LIST_H
19 #define _BOILERPLATE_SHARED_LIST_H
20 
21 #ifndef _BOILERPLATE_LIST_H
22 #error "Do not include this file directly. Use <boilerplate/list.h> instead."
23 #endif
24 
25 #define __hoff(h, a) __memoff(h, a)
26 #define __hptr(h, v) ((struct holder *)__memptr(h, v))
27 #define __hchk(h, a) __memchk(h, a)
28 
29 struct holder {
30  dref_type(struct holder *) next;
31  dref_type(struct holder *) prev;
32 };
33 
34 struct listobj {
35  struct holder head;
36 };
37 
38 static inline void __inith_nocheck(void *heap, struct holder *holder)
39 {
40  holder->next = __hoff(heap, holder);
41  holder->prev = __hoff(heap, holder);
42 }
43 
44 static inline void __inith(void *heap, struct holder *holder)
45 {
46  assert(__hchk(heap, holder));
47  __inith_nocheck(heap, holder);
48 }
49 
50 static inline void inith(struct holder *holder)
51 {
52  __inith(__main_heap, holder);
53 }
54 
55 static inline void __ath(void *heap, struct holder *head,
56  struct holder *holder)
57 {
58  /* Inserts the new element right after the heading one. */
59  holder->prev = __hoff(heap, head);
60  holder->next = head->next;
61  __hptr(heap, holder->next)->prev = __hoff(heap, holder);
62  head->next = __hoff(heap, holder);
63 }
64 
65 static inline void ath(struct holder *head, struct holder *holder)
66 {
67  __ath(__main_heap, head, holder);
68 }
69 
70 static inline void __dth(void *heap, struct holder *holder)
71 {
72  __hptr(heap, holder->prev)->next = holder->next;
73  __hptr(heap, holder->next)->prev = holder->prev;
74 }
75 
76 static inline void dth(struct holder *holder)
77 {
78  __dth(__main_heap, holder);
79 }
80 
81 static inline void __list_init(void *heap, struct listobj *list)
82 {
83  __inith(heap, &list->head);
84 }
85 
86 static inline void __list_init_nocheck(void *heap, struct listobj *list)
87 {
88  __inith_nocheck(heap, &list->head);
89 }
90 
91 static inline void list_init(struct listobj *list)
92 {
93  __list_init(__main_heap, list);
94 }
95 
96 static inline void __holder_init(void *heap, struct holder *holder)
97 {
98  __inith(heap, holder);
99 }
100 
101 static inline void __holder_init_nocheck(void *heap, struct holder *holder)
102 {
103  __inith_nocheck(heap, holder);
104 }
105 
106 static inline void holder_init(struct holder *holder)
107 {
108  inith(holder);
109 }
110 
111 static inline int __holder_linked(void *heap, const struct holder *holder)
112 {
113  return !(holder->prev == holder->next &&
114  holder->prev == __hoff(heap, holder));
115 }
116 
117 /*
118  * XXX: holder_init() is mandatory if you later want to use this
119  * predicate.
120  */
121 static inline int holder_linked(const struct holder *holder)
122 {
123  return __holder_linked(__main_heap, holder);
124 }
125 
126 static inline void __list_prepend(void *heap, struct holder *holder,
127  struct listobj *list)
128 {
129  __ath(heap, &list->head, holder);
130 }
131 
132 static inline void list_prepend(struct holder *holder, struct listobj *list)
133 {
134  __list_prepend(__main_heap, holder, list);
135 }
136 
137 static inline void __list_append(void *heap, struct holder *holder,
138  struct listobj *list)
139 {
140  __ath(heap, __hptr(heap, list->head.prev), holder);
141 }
142 
143 static inline void list_append(struct holder *holder, struct listobj *list)
144 {
145  __list_append(__main_heap, holder, list);
146 }
147 
148 static inline void __list_insert(void *heap, struct holder *next, struct holder *prev)
149 {
150  __ath(heap, prev, next);
151 }
152 
153 static inline void list_insert(struct holder *next, struct holder *prev)
154 {
155  __list_insert(__main_heap, next, prev);
156 }
157 
158 static inline void __list_join(void *heap, struct listobj *lsrc,
159  struct listobj *ldst)
160 {
161  struct holder *headsrc = __hptr(heap, lsrc->head.next);
162  struct holder *tailsrc = __hptr(heap, lsrc->head.prev);
163  struct holder *headdst = &ldst->head;
164 
165  __hptr(heap, headsrc->prev)->next = tailsrc->next;
166  __hptr(heap, tailsrc->next)->prev = headsrc->prev;
167  headsrc->prev = __hoff(heap, headdst);
168  tailsrc->next = headdst->next;
169  __hptr(heap, headdst->next)->prev = __hoff(heap, tailsrc);
170  headdst->next = __hoff(heap, headsrc);
171 }
172 
173 static inline void list_join(struct listobj *lsrc, struct listobj *ldst)
174 {
175  __list_join(__main_heap, lsrc, ldst);
176 }
177 
178 static inline void __list_remove(void *heap, struct holder *holder)
179 {
180  __dth(heap, holder);
181 }
182 
183 static inline void list_remove(struct holder *holder)
184 {
185  __list_remove(__main_heap, holder);
186 }
187 
188 static inline void __list_remove_init(void *heap, struct holder *holder)
189 {
190  __dth(heap, holder);
191  __inith(heap, holder);
192 }
193 
194 static inline void list_remove_init(struct holder *holder)
195 {
196  __list_remove_init(__main_heap, holder);
197 }
198 
199 static inline int __list_empty(void *heap, const struct listobj *list)
200 {
201  return list->head.next == __hoff(heap, &list->head);
202 }
203 
204 static inline int list_empty(const struct listobj *list)
205 {
206  return __list_empty(__main_heap, list);
207 }
208 
209 static inline struct holder *__list_pop(void *heap, struct listobj *list)
210 {
211  struct holder *holder = __hptr(heap, list->head.next);
212  __list_remove(heap, holder);
213  return holder;
214 }
215 
216 static inline struct holder *list_pop(struct listobj *list)
217 {
218  return __list_pop(__main_heap, list);
219 }
220 
221 static inline int __list_heading_p(void *heap, const struct holder *holder,
222  const struct listobj *list)
223 {
224  return list->head.next == __hoff(heap, holder);
225 }
226 
227 static inline int list_heading_p(const struct holder *holder,
228  const struct listobj *list)
229 {
230  return __list_heading_p(__main_heap, holder, list);
231 }
232 
233 #define list_entry(ptr, type, member) \
234  container_of(ptr, type, member)
235 
236 #define __list_first_entry(heap, list, type, member) \
237  list_entry(__hptr((heap), (list)->head.next), type, member)
238 
239 #define list_first_entry(list, type, member) \
240  __list_first_entry(__main_heap, list, type, member)
241 
242 #define __list_last_entry(heap, list, type, member) \
243  list_entry(__hptr((heap), (list)->head.prev), type, member)
244 
245 #define list_last_entry(list, type, member) \
246  __list_last_entry(__main_heap, list, type, member)
247 
248 #define __list_prev_entry(heap, pos, list, member) \
249  ({ \
250  typeof(*pos) *__prev = NULL; \
251  if ((list)->head.next != __hoff(heap, &(pos)->member)) \
252  __prev = list_entry(__hptr((heap), \
253  (pos)->member.prev), typeof(*pos), member); \
254  __prev; \
255  })
256 
257 #define list_prev_entry(pos, list, member) \
258  __list_prev_entry(__main_heap, pos, list, member)
259 
260 #define __list_next_entry(heap, pos, list, member) \
261  ({ \
262  typeof(*pos) *__next = NULL; \
263  if ((list)->head.prev != __hoff(heap, &(pos)->member)) \
264  __next = list_entry(__hptr((heap), \
265  (pos)->member.next), typeof(*pos), member); \
266  __next; \
267  })
268 
269 #define list_next_entry(pos, list, member) \
270  __list_next_entry(__main_heap, pos, list, member)
271 
272 #define __list_pop_entry(heap, list, type, member) ({ \
273  struct holder *__holder = __list_pop((heap), list); \
274  list_entry(__holder, type, member); })
275 
276 #define list_pop_entry(list, type, member) \
277  __list_pop_entry(__main_heap, list, type, member)
278 
279 #define __list_for_each(heap, pos, list) \
280  for (pos = __hptr((heap), (list)->head.next); \
281  pos != &(list)->head; pos = __hptr((heap), (pos)->next))
282 
283 #define list_for_each(pos, list) \
284  __list_for_each(__main_heap, pos, list)
285 
286 #define __list_for_each_reverse(heap, pos, list) \
287  for (pos = __hptr((heap), (list)->head.prev); \
288  pos != &(list)->head; pos = __hptr((heap), (pos)->prev))
289 
290 #define list_for_each_reverse(pos, list) \
291  __list_for_each_reverse(__main_heap, pos, list)
292 
293 #define __list_for_each_safe(heap, pos, tmp, list) \
294  for (pos = __hptr((heap), (list)->head.next), \
295  tmp = __hptr((heap), (pos)->next); \
296  pos != &(list)->head; \
297  pos = tmp, tmp = __hptr((heap), (pos)->next))
298 
299 #define list_for_each_safe(pos, tmp, list) \
300  __list_for_each_safe(__main_heap, pos, tmp, list)
301 
302 #define __list_for_each_entry(heap, pos, list, member) \
303  for (pos = list_entry(__hptr((heap), (list)->head.next), \
304  typeof(*pos), member); \
305  &(pos)->member != &(list)->head; \
306  pos = list_entry(__hptr((heap), (pos)->member.next), \
307  typeof(*pos), member))
308 
309 #define list_for_each_entry(pos, list, member) \
310  __list_for_each_entry(__main_heap, pos, list, member)
311 
312 #define __list_for_each_entry_safe(heap, pos, tmp, list, member) \
313  for (pos = list_entry(__hptr((heap), (list)->head.next), \
314  typeof(*pos), member), \
315  tmp = list_entry(__hptr((heap), (pos)->member.next), \
316  typeof(*pos), member); \
317  &(pos)->member != &(list)->head; \
318  pos = tmp, tmp = list_entry(__hptr((heap), (pos)->member.next), \
319  typeof(*pos), member))
320 
321 #define __list_for_each_entry_reverse_safe(heap, pos, tmp, list, member) \
322  for (pos = list_entry(__hptr((heap), (list)->head.prev), \
323  typeof(*pos), member), \
324  tmp = list_entry(__hptr((heap), (pos)->member.prev), \
325  typeof(*pos), member); \
326  &(pos)->member != &(list)->head; \
327  pos = tmp, tmp = list_entry(__hptr((heap), (pos)->member.prev), \
328  typeof(*pos), member))
329 
330 #define list_for_each_entry_safe(pos, tmp, list, member) \
331  __list_for_each_entry_safe(__main_heap, pos, tmp, list, member)
332 
333 #define __list_for_each_entry_reverse(heap, pos, list, member) \
334  for (pos = list_entry(__hptr((heap), (list)->head.prev), \
335  typeof(*pos), member); \
336  &pos->member != &(list)->head; \
337  pos = list_entry(__hptr((heap), pos->member.prev), \
338  typeof(*pos), member))
339 
340 #define list_for_each_entry_reverse(pos, list, member) \
341  __list_for_each_entry_reverse(__main_heap, pos, list, member)
342 
343 #define list_for_each_entry_reverse_safe(pos, tmp, list, member) \
344  __list_for_each_entry_reverse_safe(__main_heap, pos, tmp, list, member)
345 
346 #endif /* !_BOILERPLATE_SHARED_LIST_H */