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