StarPU Internal Handbook
list.h
Go to the documentation of this file.
1/* StarPU --- Runtime system for heterogeneous multicore architectures.
2 *
3 * Copyright (C) 2008-2021 Université de Bordeaux, CNRS (LaBRI UMR 5800), Inria
4 * Copyright (C) 2013 Thibaut Lambert
5 *
6 * StarPU is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as published by
8 * the Free Software Foundation; either version 2.1 of the License, or (at
9 * your option) any later version.
10 *
11 * StarPU is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 *
15 * See the GNU Lesser General Public License in COPYING.LGPL for more details.
16 */
17
18#ifndef __LIST_H__
19#define __LIST_H__
20
23#include <starpu_util.h>
24
166#ifndef LIST_INLINE
167#define LIST_INLINE static inline
168#endif
169
172#define LIST_TYPE(ENAME, DECL) \
173 LIST_CREATE_TYPE(ENAME, DECL)
174
175#define LIST_CREATE_TYPE(ENAME, DECL) \
176 \
177 struct ENAME \
178 { \
179 struct ENAME *_prev; \
180 struct ENAME *_next; \
181 DECL \
182 }; \
183 LIST_CREATE_TYPE_NOSTRUCT(ENAME, _prev, _next)
184
187#define LIST_CREATE_TYPE_NOSTRUCT(ENAME, _prev, _next) \
188 \
189 /* NOTE: this must not be greater than the struct defined in include/starpu_task_list.h */ \
190 struct ENAME##_list \
191 { \
192 struct ENAME *_head; \
193 struct ENAME *_tail; \
194 }; \
195LIST_INLINE struct ENAME *ENAME##_new(void) \
196 { struct ENAME *e; _STARPU_MALLOC(e, sizeof(struct ENAME)); \
197 e->_next = NULL; e->_prev = NULL; return e; } \
198LIST_INLINE void ENAME##_delete(struct ENAME *e) \
199 { free(e); } \
200LIST_INLINE void ENAME##_list_push_front(struct ENAME##_list *l, struct ENAME *e) \
201 { if(l->_tail == NULL) l->_tail = e; else l->_head->_prev = e; \
202 e->_prev = NULL; e->_next = l->_head; l->_head = e; } \
203LIST_INLINE void ENAME##_list_push_back(struct ENAME##_list *l, struct ENAME *e) \
204 { if(l->_head == NULL) l->_head = e; else l->_tail->_next = e; \
205 e->_next = NULL; e->_prev = l->_tail; l->_tail = e; } \
206LIST_INLINE void ENAME##_list_insert_before(struct ENAME##_list *l, struct ENAME *e, struct ENAME *o) \
207 { struct ENAME *p = o->_prev; if (p) { p->_next = e; e->_prev = p; } else { l->_head = e; e->_prev = NULL; } \
208 e->_next = o; o->_prev = e; } \
209LIST_INLINE void ENAME##_list_insert_after(struct ENAME##_list *l, struct ENAME *e, struct ENAME *o) \
210 { struct ENAME *n = o->_next; if (n) { n->_prev = e; e->_next = n; } else { l->_tail = e; e->_next = NULL; } \
211 e->_prev = o; o->_next = e; } \
212LIST_INLINE void ENAME##_list_push_list_front(struct ENAME##_list *l1, struct ENAME##_list *l2) \
213 { if (l2->_head == NULL) { l2->_head = l1->_head; l2->_tail = l1->_tail; } \
214 else if (l1->_head != NULL) { l1->_tail->_next = l2->_head; l2->_head->_prev = l1->_tail; l2->_head = l1->_head; } } \
215LIST_INLINE void ENAME##_list_push_list_back(struct ENAME##_list *l1, struct ENAME##_list *l2) \
216 { if(l1->_head == NULL) { l1->_head = l2->_head; l1->_tail = l2->_tail; } \
217 else if (l2->_head != NULL) { l1->_tail->_next = l2->_head; l2->_head->_prev = l1->_tail; l1->_tail = l2->_tail; } } \
218LIST_INLINE struct ENAME *ENAME##_list_front(const struct ENAME##_list *l) \
219 { return l->_head; } \
220LIST_INLINE struct ENAME *ENAME##_list_back(const struct ENAME##_list *l) \
221 { return l->_tail; } \
222LIST_INLINE void ENAME##_list_init(struct ENAME##_list *l) \
223 { l->_head=NULL; l->_tail=l->_head; } \
224LIST_INLINE struct ENAME##_list *ENAME##_list_new(void) \
225 { struct ENAME##_list *l; _STARPU_MALLOC(l, sizeof(struct ENAME##_list)); \
226 ENAME##_list_init(l); return l; } \
227LIST_INLINE int ENAME##_list_empty(const struct ENAME##_list *l) \
228 { return (l->_head == NULL); } \
229LIST_INLINE void ENAME##_list_delete(struct ENAME##_list *l) \
230 { free(l); } \
231LIST_INLINE void ENAME##_list_erase(struct ENAME##_list *l, struct ENAME *c) \
232 { struct ENAME *p = c->_prev; if(p) p->_next = c->_next; else l->_head = c->_next; \
233 if(c->_next) c->_next->_prev = p; else l->_tail = p; } \
234LIST_INLINE struct ENAME *ENAME##_list_pop_front(struct ENAME##_list *l) \
235 { struct ENAME *e = ENAME##_list_front(l); \
236 ENAME##_list_erase(l, e); return e; } \
237LIST_INLINE struct ENAME *ENAME##_list_pop_back(struct ENAME##_list *l) \
238 { struct ENAME *e = ENAME##_list_back(l); \
239 ENAME##_list_erase(l, e); return e; } \
240LIST_INLINE struct ENAME *ENAME##_list_begin(const struct ENAME##_list *l) \
241 { return l->_head; } \
242LIST_INLINE struct ENAME *ENAME##_list_end(const struct ENAME##_list *l STARPU_ATTRIBUTE_UNUSED) \
243 { return NULL; } \
244LIST_INLINE struct ENAME *ENAME##_list_next(const struct ENAME *i) \
245 { return i->_next; } \
246LIST_INLINE struct ENAME *ENAME##_list_last(const struct ENAME##_list *l) \
247 { return l->_tail; } \
248LIST_INLINE struct ENAME *ENAME##_list_alpha(const struct ENAME##_list *l STARPU_ATTRIBUTE_UNUSED) \
249 { return NULL; } \
250LIST_INLINE struct ENAME *ENAME##_list_prev(const struct ENAME *i) \
251 { return i->_prev; } \
252LIST_INLINE int ENAME##_list_ismember(const struct ENAME##_list *l, const struct ENAME *e) \
253 { struct ENAME *i=l->_head; while(i!=NULL){ if (i == e) return 1; i=i->_next; } return 0; } \
254LIST_INLINE int ENAME##_list_member(const struct ENAME##_list *l, const struct ENAME *e) \
255 { struct ENAME *i=l->_head; int k=0; while(i!=NULL){if (i == e) return k; k++; i=i->_next; } return -1; } \
256LIST_INLINE int ENAME##_list_size(const struct ENAME##_list *l) \
257 { struct ENAME *i=l->_head; int k=0; while(i!=NULL){k++;i=i->_next;} return k; } \
258LIST_INLINE int ENAME##_list_check(const struct ENAME##_list *l) \
259 { struct ENAME *i=l->_head; while(i) \
260 { if ((i->_next == NULL) && i != l->_tail) return 0; \
261 if (i->_next == i) return 0; \
262 i=i->_next;} return 1; } \
263LIST_INLINE void ENAME##_list_move(struct ENAME##_list *ldst, struct ENAME##_list *lsrc) \
264 { ENAME##_list_init(ldst); ldst->_head = lsrc->_head; ldst->_tail = lsrc->_tail; lsrc->_head = NULL; lsrc->_tail = NULL; }
265
266
267#ifdef STARPU_DEBUG
268#define STARPU_ASSERT_MULTILIST(expr) STARPU_ASSERT(expr)
269#else
270#define STARPU_ASSERT_MULTILIST(expr) ((void) 0)
271#endif
272
273/*
274 * This is an implementation of list allowing to be member of several lists.
275 * - One should first call MULTILIST_CREATE_TYPE for the ENAME and for each
276 * MEMBER type
277 * - Then the main element type should include fields of type
278 * ENAME_multilist_MEMBER
279 * - Then one should call MULTILIST_CREATE_INLINES to create the inlines which
280 * manipulate lists for this MEMBER type.
281 */
282
283/* Create the ENAME_multilist_MEMBER, to be used both as head and as member of main element type */
284#define MULTILIST_CREATE_TYPE(ENAME, MEMBER) \
285struct ENAME##_multilist_##MEMBER { \
286 struct ENAME##_multilist_##MEMBER *next; \
287 struct ENAME##_multilist_##MEMBER *prev; \
288};
289
290/* Create the inlines */
291#define MULTILIST_CREATE_INLINES(TYPE, ENAME, MEMBER) \
292/* Cast from list element to real type. */ \
293LIST_INLINE TYPE *ENAME##_of_multilist_##MEMBER(struct ENAME##_multilist_##MEMBER *elt) { \
294 return ((TYPE *) ((uintptr_t) (elt) - ((uintptr_t) (&((TYPE *) 0)->MEMBER)))); \
295} \
296\
297/* Initialize a list head. */ \
298LIST_INLINE void ENAME##_multilist_head_init_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
299 head->next = head; \
300 head->prev = head; \
301} \
302\
303/* Initialize a list element. */ \
304LIST_INLINE void ENAME##_multilist_init_##MEMBER(TYPE *e) { \
305 (e)->MEMBER.next = NULL; \
306 (e)->MEMBER.prev = NULL; \
307} \
308\
309/* Push element to head of a list. */ \
310LIST_INLINE void ENAME##_multilist_push_front_##MEMBER(struct ENAME##_multilist_##MEMBER *head, TYPE *e) { \
311 STARPU_ASSERT_MULTILIST(e->MEMBER.prev == NULL); \
312 STARPU_ASSERT_MULTILIST(e->MEMBER.next == NULL); \
313 e->MEMBER.next = head->next; \
314 e->MEMBER.prev = head; \
315 head->next->prev = &e->MEMBER; \
316 head->next = &e->MEMBER; \
317} \
318\
319/* Push element to tail of a list. */ \
320LIST_INLINE void ENAME##_multilist_push_back_##MEMBER(struct ENAME##_multilist_##MEMBER *head, TYPE *e) { \
321 STARPU_ASSERT_MULTILIST(e->MEMBER.prev == NULL); \
322 STARPU_ASSERT_MULTILIST(e->MEMBER.next == NULL); \
323 e->MEMBER.prev = head->prev; \
324 e->MEMBER.next = head; \
325 head->prev->next = &e->MEMBER; \
326 head->prev = &e->MEMBER; \
327} \
328\
329/* Erase element from a list. */ \
330LIST_INLINE void ENAME##_multilist_erase_##MEMBER(struct ENAME##_multilist_##MEMBER *head STARPU_ATTRIBUTE_UNUSED, TYPE *e) { \
331 STARPU_ASSERT_MULTILIST(e->MEMBER.next->prev == &e->MEMBER); \
332 e->MEMBER.next->prev = e->MEMBER.prev; \
333 STARPU_ASSERT_MULTILIST(e->MEMBER.prev->next == &e->MEMBER); \
334 e->MEMBER.prev->next = e->MEMBER.next; \
335 e->MEMBER.next = NULL; \
336 e->MEMBER.prev = NULL; \
337} \
338\
339/* Test whether the element was queued on the list. */ \
340LIST_INLINE int ENAME##_multilist_queued_##MEMBER(TYPE *e) { \
341 return ((e)->MEMBER.next != NULL); \
342} \
343\
344/* Test whether the list is empty. */ \
345LIST_INLINE int ENAME##_multilist_empty_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
346 return head->next == head; \
347} \
348\
349/* Test whether the element is alone in a list. */ \
350LIST_INLINE int ENAME##_multilist_alone_##MEMBER(TYPE *e) { \
351 return (e)->MEMBER.next == (e)->MEMBER.prev; \
352} \
353\
354/* Return the first element of the list. */ \
355LIST_INLINE TYPE *ENAME##_multilist_begin_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
356 return ENAME##_of_multilist_##MEMBER(head->next); \
357} \
358/* Return the value to be tested at the end of the list. */ \
359LIST_INLINE TYPE *ENAME##_multilist_end_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
360 return ENAME##_of_multilist_##MEMBER(head); \
361} \
362/* Return the next element of the list. */ \
363LIST_INLINE TYPE *ENAME##_multilist_next_##MEMBER(TYPE *e) { \
364 return ENAME##_of_multilist_##MEMBER(e->MEMBER.next); \
365} \
366\
367 /* Move a list from its head to another head. Passing newhead == NULL allows to detach the list from any head. */ \
368LIST_INLINE void ENAME##_multilist_move_##MEMBER(struct ENAME##_multilist_##MEMBER *head, struct ENAME##_multilist_##MEMBER *newhead) { \
369 if (ENAME##_multilist_empty_##MEMBER(head)) \
370 ENAME##_multilist_head_init_##MEMBER(newhead); \
371 else { \
372 if (newhead) { \
373 newhead->next = head->next; \
374 newhead->next->prev = newhead; \
375 } else { \
376 head->next->prev = head->prev; \
377 } \
378 if (newhead) { \
379 newhead->prev = head->prev; \
380 newhead->prev->next = newhead; \
381 } else { \
382 head->prev->next = head->next; \
383 } \
384 head->next = head; \
385 head->prev = head; \
386 } \
387}
388
389#endif /* __LIST_H__ */