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
169#ifndef LIST_INLINE
170#define LIST_INLINE static inline
171#endif
172
175#define LIST_TYPE(ENAME, DECL) \
176 LIST_CREATE_TYPE(ENAME, DECL)
177
178#define LIST_CREATE_TYPE(ENAME, DECL) \
179 \
180 struct ENAME \
181 { \
182 struct ENAME *_prev; \
183 struct ENAME *_next; \
184 DECL \
185 }; \
186 LIST_CREATE_TYPE_NOSTRUCT(ENAME, _prev, _next)
187
190#define LIST_CREATE_TYPE_NOSTRUCT(ENAME, _prev, _next) \
191 \
192 /* NOTE: this must not be greater than the struct defined in include/starpu_task_list.h */ \
193 struct ENAME##_list \
194 { \
195 struct ENAME *_head; \
196 struct ENAME *_tail; \
197 }; \
198LIST_INLINE struct ENAME *ENAME##_new(void) \
199 { struct ENAME *e; _STARPU_MALLOC(e, sizeof(struct ENAME)); \
200 e->_next = NULL; e->_prev = NULL; return e; } \
201LIST_INLINE void ENAME##_delete(struct ENAME *e) \
202 { free(e); } \
203LIST_INLINE void ENAME##_list_push_front(struct ENAME##_list *l, struct ENAME *e) \
204 { if(l->_tail == NULL) l->_tail = e; else l->_head->_prev = e; \
205 e->_prev = NULL; e->_next = l->_head; l->_head = e; } \
206LIST_INLINE void ENAME##_list_push_back(struct ENAME##_list *l, struct ENAME *e) \
207 { if(l->_head == NULL) l->_head = e; else l->_tail->_next = e; \
208 e->_next = NULL; e->_prev = l->_tail; l->_tail = e; } \
209LIST_INLINE void ENAME##_list_insert_before(struct ENAME##_list *l, struct ENAME *e, struct ENAME *o) \
210 { struct ENAME *p = o->_prev; if (p) { p->_next = e; e->_prev = p; } else { l->_head = e; e->_prev = NULL; } \
211 e->_next = o; o->_prev = e; } \
212LIST_INLINE void ENAME##_list_insert_after(struct ENAME##_list *l, struct ENAME *e, struct ENAME *o) \
213 { struct ENAME *n = o->_next; if (n) { n->_prev = e; e->_next = n; } else { l->_tail = e; e->_next = NULL; } \
214 e->_prev = o; o->_next = e; } \
215LIST_INLINE void ENAME##_list_push_list_front(struct ENAME##_list *l1, struct ENAME##_list *l2) \
216 { if (l2->_head == NULL) { l2->_head = l1->_head; l2->_tail = l1->_tail; } \
217 else if (l1->_head != NULL) { l1->_tail->_next = l2->_head; l2->_head->_prev = l1->_tail; l2->_head = l1->_head; } } \
218LIST_INLINE void ENAME##_list_push_list_back(struct ENAME##_list *l1, struct ENAME##_list *l2) \
219 { if(l1->_head == NULL) { l1->_head = l2->_head; l1->_tail = l2->_tail; } \
220 else if (l2->_head != NULL) { l1->_tail->_next = l2->_head; l2->_head->_prev = l1->_tail; l1->_tail = l2->_tail; } } \
221LIST_INLINE struct ENAME *ENAME##_list_front(const struct ENAME##_list *l) \
222 { return l->_head; } \
223LIST_INLINE struct ENAME *ENAME##_list_back(const struct ENAME##_list *l) \
224 { return l->_tail; } \
225LIST_INLINE void ENAME##_list_init(struct ENAME##_list *l) \
226 { l->_head=NULL; l->_tail=NULL; } \
227LIST_INLINE void ENAME##_list_init0(struct ENAME##_list *l STARPU_ATTRIBUTE_UNUSED) \
228 { } \
229LIST_INLINE struct ENAME##_list *ENAME##_list_new(void) \
230 { struct ENAME##_list *l; _STARPU_MALLOC(l, sizeof(struct ENAME##_list)); \
231 ENAME##_list_init(l); return l; } \
232LIST_INLINE int ENAME##_list_empty(const struct ENAME##_list *l) \
233 { return (l->_head == NULL); } \
234LIST_INLINE void ENAME##_list_delete(struct ENAME##_list *l) \
235 { free(l); } \
236LIST_INLINE void ENAME##_list_erase(struct ENAME##_list *l, struct ENAME *c) \
237 { struct ENAME *p = c->_prev; if(p) p->_next = c->_next; else l->_head = c->_next; \
238 if(c->_next) c->_next->_prev = p; else l->_tail = p; } \
239LIST_INLINE struct ENAME *ENAME##_list_pop_front(struct ENAME##_list *l) \
240 { struct ENAME *e = ENAME##_list_front(l); \
241 ENAME##_list_erase(l, e); return e; } \
242LIST_INLINE struct ENAME *ENAME##_list_pop_back(struct ENAME##_list *l) \
243 { struct ENAME *e = ENAME##_list_back(l); \
244 ENAME##_list_erase(l, e); return e; } \
245LIST_INLINE struct ENAME *ENAME##_list_begin(const struct ENAME##_list *l) \
246 { return l->_head; } \
247LIST_INLINE struct ENAME *ENAME##_list_end(const struct ENAME##_list *l STARPU_ATTRIBUTE_UNUSED) \
248 { return NULL; } \
249LIST_INLINE struct ENAME *ENAME##_list_next(const struct ENAME *i) \
250 { return i->_next; } \
251LIST_INLINE struct ENAME *ENAME##_list_last(const struct ENAME##_list *l) \
252 { return l->_tail; } \
253LIST_INLINE struct ENAME *ENAME##_list_alpha(const struct ENAME##_list *l STARPU_ATTRIBUTE_UNUSED) \
254 { return NULL; } \
255LIST_INLINE struct ENAME *ENAME##_list_prev(const struct ENAME *i) \
256 { return i->_prev; } \
257LIST_INLINE int ENAME##_list_ismember(const struct ENAME##_list *l, const struct ENAME *e) \
258 { struct ENAME *i=l->_head; while(i!=NULL){ if (i == e) return 1; i=i->_next; } return 0; } \
259LIST_INLINE int ENAME##_list_member(const struct ENAME##_list *l, const struct ENAME *e) \
260 { struct ENAME *i=l->_head; int k=0; while(i!=NULL){if (i == e) return k; k++; i=i->_next; } return -1; } \
261LIST_INLINE int ENAME##_list_size(const struct ENAME##_list *l) \
262 { struct ENAME *i=l->_head; int k=0; while(i!=NULL){k++;i=i->_next;} return k; } \
263LIST_INLINE int ENAME##_list_check(const struct ENAME##_list *l) \
264 { struct ENAME *i=l->_head; while(i) \
265 { if ((i->_next == NULL) && i != l->_tail) return 0; \
266 if (i->_next == i) return 0; \
267 i=i->_next;} return 1; } \
268LIST_INLINE void ENAME##_list_move(struct ENAME##_list *ldst, struct ENAME##_list *lsrc) \
269 { ENAME##_list_init(ldst); ldst->_head = lsrc->_head; ldst->_tail = lsrc->_tail; lsrc->_head = NULL; lsrc->_tail = NULL; }
270
271
272#ifdef STARPU_DEBUG
273#define STARPU_ASSERT_MULTILIST(expr) STARPU_ASSERT(expr)
274#else
275#define STARPU_ASSERT_MULTILIST(expr) ((void) 0)
276#endif
277
278/*
279 * This is an implementation of list allowing to be member of several lists.
280 * - One should first call MULTILIST_CREATE_TYPE for the ENAME and for each
281 * MEMBER type
282 * - Then the main element type should include fields of type
283 * ENAME_multilist_MEMBER
284 * - Then one should call MULTILIST_CREATE_INLINES to create the inlines which
285 * manipulate lists for this MEMBER type.
286 *
287 * *********************************************************
288 * Usage example:
289 *
290 * - initially you'd have:
291 * struct my_struct
292 * {
293 * int a;
294 * int b;
295 * };
296 *
297 * - to make multilists of it, we add MULTILIST_CREATE_TYPE calls before, the
298 * multilist fields, and MULTILIST_CREATE_INLINES calls after::
299 *
300 * MULTILIST_CREATE_TYPE(my_struct, foo);
301 * MULTILIST_CREATE_TYPE(my_struct, bar);
302 *
303 * struct my_struct
304 * {
305 * struct my_struct_multilist_foo foo;
306 * struct my_struct_multilist_bar bar;
307 * int a;
308 * int b;
309 * };
310 *
311 * MULTILIST_CREATE_INLINES(struct my_struct, my_struct, foo);
312 * MULTILIST_CREATE_INLINES(struct my_struct, my_struct, bar);
313 *
314 * - creating a new element and initialize the multilist fields:
315 *
316 * struct my_struct *e = malloc(sizeof(*e));
317 * my_struct_multilist_init_foo(e);
318 * my_struct_multilist_init_bar(e);
319 * e->a = 0;
320 * e->b = 0;
321 *
322 * - setting up an empty list:
323 *
324 * struct my_struct_multilist_foo l;
325 * my_struct_multilist_head_init_foo(&l);
326 *
327 * - add element 'e' at the front of list 'l':
328 * my_struct_multilist_push_front_foo(&l, e);
329 *
330 * - TODO implementation: popping from the front:
331 * struct my_struct *i;
332 * i = my_struct_multilist_front_foo(&l);
333 *
334 * - iterating over a list from the front:
335 * struct my_struct *i;
336 * for(i = my_struct_multilist_begin_foo(&l);
337 * i != my_struct_multilist_end_foo(&l);
338 * i = my_struct_multilist_next_foo(i))
339 * {
340 * printf("a=%d; b=%d\n", i->a, i->b);
341 * }
342 */
343
344/* Create the ENAME_multilist_MEMBER, to be used both as head and as member of main element type */
345#define MULTILIST_CREATE_TYPE(ENAME, MEMBER) \
346struct ENAME##_multilist_##MEMBER { \
347 struct ENAME##_multilist_##MEMBER *next; \
348 struct ENAME##_multilist_##MEMBER *prev; \
349};
350
351/* Create the inlines */
352#define MULTILIST_CREATE_INLINES(TYPE, ENAME, MEMBER) \
353/* Cast from list element to real type. */ \
354LIST_INLINE TYPE *ENAME##_of_multilist_##MEMBER(struct ENAME##_multilist_##MEMBER *elt) { \
355 return ((TYPE *) ((uintptr_t) (elt) - ((uintptr_t) (&((TYPE *) 0)->MEMBER)))); \
356} \
357\
358/* Initialize a list head. */ \
359LIST_INLINE void ENAME##_multilist_head_init_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
360 head->next = head; \
361 head->prev = head; \
362} \
363\
364/* Initialize a list element. */ \
365LIST_INLINE void ENAME##_multilist_init_##MEMBER(TYPE *e) { \
366 (e)->MEMBER.next = NULL; \
367 (e)->MEMBER.prev = NULL; \
368} \
369\
370/* Push element to head of a list. */ \
371LIST_INLINE void ENAME##_multilist_push_front_##MEMBER(struct ENAME##_multilist_##MEMBER *head, TYPE *e) { \
372 STARPU_ASSERT_MULTILIST(e->MEMBER.prev == NULL); \
373 STARPU_ASSERT_MULTILIST(e->MEMBER.next == NULL); \
374 e->MEMBER.next = head->next; \
375 e->MEMBER.prev = head; \
376 head->next->prev = &e->MEMBER; \
377 head->next = &e->MEMBER; \
378} \
379\
380/* Push element to tail of a list. */ \
381LIST_INLINE void ENAME##_multilist_push_back_##MEMBER(struct ENAME##_multilist_##MEMBER *head, TYPE *e) { \
382 STARPU_ASSERT_MULTILIST(e->MEMBER.prev == NULL); \
383 STARPU_ASSERT_MULTILIST(e->MEMBER.next == NULL); \
384 e->MEMBER.prev = head->prev; \
385 e->MEMBER.next = head; \
386 head->prev->next = &e->MEMBER; \
387 head->prev = &e->MEMBER; \
388} \
389\
390/* Erase element from a list. */ \
391LIST_INLINE void ENAME##_multilist_erase_##MEMBER(struct ENAME##_multilist_##MEMBER *head STARPU_ATTRIBUTE_UNUSED, TYPE *e) { \
392 STARPU_ASSERT_MULTILIST(e->MEMBER.next->prev == &e->MEMBER); \
393 e->MEMBER.next->prev = e->MEMBER.prev; \
394 STARPU_ASSERT_MULTILIST(e->MEMBER.prev->next == &e->MEMBER); \
395 e->MEMBER.prev->next = e->MEMBER.next; \
396 e->MEMBER.next = NULL; \
397 e->MEMBER.prev = NULL; \
398} \
399\
400/* Test whether the element was queued on the list. */ \
401LIST_INLINE int ENAME##_multilist_queued_##MEMBER(TYPE *e) { \
402 return ((e)->MEMBER.next != NULL); \
403} \
404\
405/* Test whether the list is empty. */ \
406LIST_INLINE int ENAME##_multilist_empty_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
407 return head->next == head; \
408} \
409\
410/* Test whether the element is alone in a list. */ \
411LIST_INLINE int ENAME##_multilist_alone_##MEMBER(TYPE *e) { \
412 return (e)->MEMBER.next == (e)->MEMBER.prev; \
413} \
414\
415/* Return the first element of the list. */ \
416LIST_INLINE TYPE *ENAME##_multilist_begin_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
417 return ENAME##_of_multilist_##MEMBER(head->next); \
418} \
419/* Return the value to be tested at the end of the list. */ \
420LIST_INLINE TYPE *ENAME##_multilist_end_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
421 return ENAME##_of_multilist_##MEMBER(head); \
422} \
423/* Return the next element of the list. */ \
424LIST_INLINE TYPE *ENAME##_multilist_next_##MEMBER(TYPE *e) { \
425 return ENAME##_of_multilist_##MEMBER(e->MEMBER.next); \
426} \
427/* Return the first element of the list. */ \
428LIST_INLINE TYPE *ENAME##_multilist_front_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
429 return ENAME##_of_multilist_##MEMBER(head->next); \
430} \
431/* Return the last element of the list. */ \
432LIST_INLINE TYPE *ENAME##_multilist_back_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
433 return ENAME##_of_multilist_##MEMBER(head->prev); \
434} \
435\
436/* Return the first element of the list and erase it. */ \
437LIST_INLINE TYPE *ENAME##_multilist_pop_front_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
438 TYPE *e = ENAME##_multilist_front_##MEMBER(head); \
439 ENAME##_multilist_erase_##MEMBER(head, e); return e; \
440} \
441/* Return the last element of the list and erase it. */ \
442LIST_INLINE TYPE *ENAME##_multilist_pop_back_##MEMBER(struct ENAME##_multilist_##MEMBER *head) { \
443 TYPE *e = ENAME##_multilist_back_##MEMBER(head); \
444 ENAME##_multilist_erase_##MEMBER(head, e); return e; \
445} \
446\
447\
448 /* Move a list from its head to another head. Passing newhead == NULL allows to detach the list from any head. */ \
449LIST_INLINE void ENAME##_multilist_move_##MEMBER(struct ENAME##_multilist_##MEMBER *head, struct ENAME##_multilist_##MEMBER *newhead) { \
450 if (ENAME##_multilist_empty_##MEMBER(head)) \
451 ENAME##_multilist_head_init_##MEMBER(newhead); \
452 else { \
453 if (newhead) { \
454 newhead->next = head->next; \
455 newhead->next->prev = newhead; \
456 } else { \
457 head->next->prev = head->prev; \
458 } \
459 if (newhead) { \
460 newhead->prev = head->prev; \
461 newhead->prev->next = newhead; \
462 } else { \
463 head->prev->next = head->next; \
464 } \
465 head->next = head; \
466 head->prev = head; \
467 } \
468}
469
470#endif /* __LIST_H__ */