StarPU Internal Handbook
prio_list.h
Go to the documentation of this file.
1 /* StarPU --- Runtime system for heterogeneous multicore architectures.
2  *
3  * Copyright (C) 2015-2021 Université de Bordeaux, CNRS (LaBRI UMR 5800), Inria
4  *
5  * StarPU is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU Lesser General Public License as published by
7  * the Free Software Foundation; either version 2.1 of the License, or (at
8  * your option) any later version.
9  *
10  * StarPU is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13  *
14  * See the GNU Lesser General Public License in COPYING.LGPL for more details.
15  */
16 
19 /*
20  * This implements list with priorities (as an int), by using two stages:
21  * - an RB tree stage sorted by priority, whose leaves are...
22  * - ... double-linked lists sorted by insertion order.
23  *
24  * We always keep the 0-priority list allocated, to avoid keeping
25  * allocating/deallocating it when all priorities are 0.
26  *
27  * We maintain an "empty" flag, to allow lockless FOO_prio_list_empty call.
28  *
29  * PRIO_LIST_TYPE(FOO, priority_field)
30  *
31  * - Declares the following type:
32  * + priority list: struct FOO_prio_list
33  *
34  * - Declares the following inlines (all O(1) except stated otherwise, n is the
35  * number of elements, p is the number of different priorities):
36  *
37  * * Initialize a new priority list
38  * void FOO_prio_list_init(struct FOO_prio_list*)
39  *
40  * * Free an empty priority list
41  * void FOO_prio_list_deinit(struct FOO_prio_list*)
42  *
43  * * Add a new cell at the end of the list of the priority of the cell (O(log2 p))
44  * void FOO_prio_list_push_back(struct FOO_prio_list*, struct FOO*)
45  *
46  * * Add a new cell at the beginning of the list of the priority of the cell (O(log2 p))
47  * void FOO_prio_list_push_front(struct FOO_prio_list*, struct FOO*)
48  *
49  * * Test whether the priority list is empty
50  * void FOO_prio_list_empty(struct FOO_prio_list*)
51  *
52  * * Remove given cell from the priority list
53  * void FOO_prio_list_erase(struct FOO_prio_list*, struct FOO*)
54  *
55  * * Return and remove the first cell of highest priority of the priority list
56  * void FOO_prio_list_pop_front_highest(struct FOO_prio_list*)
57  * * Return and remove the first cell of lowest priority of the priority list
58  * void FOO_prio_list_pop_front_lowest(struct FOO_prio_list*)
59  *
60  * * Return and remove the last cell of highest priority of the priority list
61  * void FOO_prio_list_pop_back_highest(struct FOO_prio_list*)
62  * * Return and remove the last cell of lowest priority of the priority list
63  * void FOO_prio_list_pop_back_lowest(struct FOO_prio_list*)
64  *
65  * * Return the first cell of highest priority of the priority list
66  * void FOO_prio_list_front_highest(struct FOO_prio_list*)
67  * * Return the first cell of lowest priority of the priority list
68  * void FOO_prio_list_front_lowest(struct FOO_prio_list*)
69  *
70  * * Return the last cell of highest priority of sthe priority list
71  * void FOO_prio_list_back_highest(struct FOO_prio_list*)
72  * * Return the last cell of lowest priority of sthe priority list
73  * void FOO_prio_list_back_lowest(struct FOO_prio_list*)
74  *
75  * * Append second priority list at ends of the first priority list (O(log2 p))
76  * void FOO_prio_list_push_prio_list_back(struct FOO_prio_list*, struct FOO_prio_list*)
77  *
78  * * Test whether cell is part of the list (O(n))
79  * void FOO_prio_list_ismember(struct FOO_prio_list*, struct FOO*)
80  *
81  * * Return the first cell of the list
82  * struct FOO* FOO_prio_list_begin(struct FOO_prio_list*);
83  *
84  * * Return the value to test at the end of the list
85  * struct FOO* FOO_prio_list_end(struct FOO_prio_list*);
86  *
87  * * Return the next cell of the list
88  * struct FOO* FOO_prio_list_next(struct FOO_prio_list*, struct FOO*)
89  *
90  * * Return the last cell of the list
91  * struct FOO* FOO_prio_list_last(struct FOO_prio_list*);
92  *
93  * * Return the value to test at the beginning of the list
94  * struct FOO* FOO_prio_list_alpha(struct FOO_prio_list*);
95  *
96  * * Return the previous cell of the list
97  * struct FOO* FOO_prio_list_prev(struct FOO_prio_list*, struct FOO*)
98  *
99  * PRIO_LIST_TYPE assumes that LIST_TYPE has already been called to create the
100  * final structure.
101  *
102  * *********************************************************
103  * Usage example:
104  * LIST_TYPE(my_struct,
105  * int a;
106  * int b;
107  * int prio;
108  * );
109  * PRIO_LIST_TYPE(my_struct, prio);
110  *
111  * and then my_struct_prio_list_* inlines are available
112  */
113 
114 #ifndef __PRIO_LIST_H__
115 #define __PRIO_LIST_H__
116 
117 #include <common/rbtree.h>
118 
119 #ifndef PRIO_LIST_INLINE
120 #define PRIO_LIST_INLINE static inline
121 #endif
122 
123 #define PRIO_LIST_TYPE(ENAME, PRIOFIELD) \
124  PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD)
125 
126 #ifndef STARPU_DEBUG
127 
128 #define PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD) \
129  /* The main type: an RB binary tree */ \
130  struct ENAME##_prio_list { \
131  struct starpu_rbtree tree; \
132  int empty; \
133  }; \
134  /* The second stage: a list */ \
135  struct ENAME##_prio_list_stage { \
136  struct starpu_rbtree_node node; /* Keep this first so ENAME##_node_to_list_stage can work. */ \
137  int prio; \
138  struct ENAME##_list list; \
139  }; \
140  PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage(struct starpu_rbtree_node *node) \
141  { \
142  /* This assumes node is first member of stage */ \
143  return (struct ENAME##_prio_list_stage *) node; \
144  } \
145  PRIO_LIST_INLINE const struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage_const(const struct starpu_rbtree_node *node) \
146  { \
147  /* This assumes node is first member of stage */ \
148  return (struct ENAME##_prio_list_stage *) node; \
149  } \
150  PRIO_LIST_INLINE void ENAME##_prio_list_init(struct ENAME##_prio_list *priolist) \
151  { \
152  starpu_rbtree_init(&priolist->tree); \
153  priolist->empty = 1; \
154  } \
155  PRIO_LIST_INLINE void ENAME##_prio_list_deinit(struct ENAME##_prio_list *priolist) \
156  { \
157  if (starpu_rbtree_empty(&priolist->tree)) \
158  return; \
159  struct starpu_rbtree_node *root = priolist->tree.root; \
160  struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(root); \
161  assert(ENAME##_list_empty(&stage->list)); \
162  assert(!root->children[0] && !root->children[1]); \
163  starpu_rbtree_remove(&priolist->tree, root); \
164  free(stage); \
165  } \
166  PRIO_LIST_INLINE int ENAME##_prio_list_cmp_fn(int prio, const struct starpu_rbtree_node *node) \
167  { \
168  /* Sort by decreasing order */ \
169  const struct ENAME##_prio_list_stage *e2 = ENAME##_node_to_list_stage_const(node); \
170  if (e2->prio < prio) \
171  return -1; \
172  if (e2->prio == prio) \
173  return 0; \
174  /* e2->prio > prio */ \
175  return 1; \
176  } \
177  PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_prio_list_add(struct ENAME##_prio_list *priolist, int prio) \
178  { \
179  uintptr_t slot; \
180  struct starpu_rbtree_node *node; \
181  struct ENAME##_prio_list_stage *stage; \
182  node = starpu_rbtree_lookup_slot(&priolist->tree, prio, ENAME##_prio_list_cmp_fn, slot); \
183  if (node) \
184  stage = ENAME##_node_to_list_stage(node); \
185  else { \
186  _STARPU_MALLOC(stage, sizeof(*stage)); \
187  starpu_rbtree_node_init(&stage->node); \
188  stage->prio = prio; \
189  ENAME##_list_init(&stage->list); \
190  starpu_rbtree_insert_slot(&priolist->tree, slot, &stage->node); \
191  } \
192  return stage; \
193  } \
194  PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
195  { \
196  struct ENAME##_prio_list_stage *stage = ENAME##_prio_list_add(priolist, e->PRIOFIELD); \
197  ENAME##_list_push_back(&stage->list, e); \
198  priolist->empty = 0; \
199  } \
200  PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
201  { \
202  struct ENAME##_prio_list_stage *stage = ENAME##_prio_list_add(priolist, e->PRIOFIELD); \
203  ENAME##_list_push_front(&stage->list, e); \
204  priolist->empty = 0; \
205  } \
206  PRIO_LIST_INLINE int ENAME##_prio_list_empty(const struct ENAME##_prio_list *priolist) \
207  { \
208  return priolist->empty; \
209  } \
210  /* Version of list_empty which does not use the cached empty flag,
211  * typically used to compute the value of the flag */ \
212  PRIO_LIST_INLINE int ENAME##_prio_list_empty_slow(const struct ENAME##_prio_list *priolist) \
213  { \
214  if (starpu_rbtree_empty(&priolist->tree)) \
215  return 1; \
216  struct starpu_rbtree_node *root = priolist->tree.root; \
217  const struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage_const(root); \
218  if (ENAME##_list_empty(&stage->list) && !root->children[0] && !root->children[1]) \
219  /* Just one empty list */ \
220  return 1; \
221  return 0; \
222  } \
223  /* To be called when removing an element from a stage, to potentially remove this stage */ \
224  PRIO_LIST_INLINE void ENAME##_prio_list_check_empty_stage(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list_stage *stage) \
225  { \
226  if (ENAME##_list_empty(&stage->list)) { \
227  if (stage->prio != 0) \
228  { \
229  /* stage got empty, remove it */ \
230  starpu_rbtree_remove(&priolist->tree, &stage->node); \
231  free(stage); \
232  } \
233  priolist->empty = ENAME##_prio_list_empty_slow(priolist); \
234  } \
235  } \
236  PRIO_LIST_INLINE void ENAME##_prio_list_erase(struct ENAME##_prio_list *priolist, struct ENAME *e) \
237  { \
238  struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
239  struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(node); \
240  ENAME##_list_erase(&stage->list, e); \
241  ENAME##_prio_list_check_empty_stage(priolist, stage); \
242  } \
243  PRIO_LIST_INLINE int ENAME##_prio_list_get_next_nonempty_stage(struct ENAME##_prio_list *priolist, struct starpu_rbtree_node *node, struct starpu_rbtree_node **pnode, struct ENAME##_prio_list_stage **pstage) \
244  { \
245  struct ENAME##_prio_list_stage *stage; \
246  while(1) { \
247  struct starpu_rbtree_node *next; \
248  if (!node) \
249  /* Tree is empty */ \
250  return 0; \
251  stage = ENAME##_node_to_list_stage(node); \
252  if (!ENAME##_list_empty(&stage->list)) \
253  break; \
254  /* Empty list, skip to next tree entry */ \
255  next = starpu_rbtree_next(node); \
256  /* drop it if not 0-prio */ \
257  if (stage->prio != 0) \
258  { \
259  starpu_rbtree_remove(&priolist->tree, node); \
260  free(stage); \
261  } \
262  node = next; \
263  } \
264  *pnode = node; \
265  *pstage = stage; \
266  return 1; \
267  } \
268  PRIO_LIST_INLINE int ENAME##_prio_list_get_prev_nonempty_stage(struct ENAME##_prio_list *priolist, struct starpu_rbtree_node *node, struct starpu_rbtree_node **pnode, struct ENAME##_prio_list_stage **pstage) \
269  { \
270  struct ENAME##_prio_list_stage *stage; \
271  while(1) { \
272  struct starpu_rbtree_node *prev; \
273  if (!node) \
274  /* Tree is empty */ \
275  return 0; \
276  stage = ENAME##_node_to_list_stage(node); \
277  if (!ENAME##_list_empty(&stage->list)) \
278  break; \
279  /* Empty list, skip to prev tree entry */ \
280  prev = starpu_rbtree_prev(node); \
281  /* drop it if not 0-prio */ \
282  if (stage->prio != 0) \
283  { \
284  starpu_rbtree_remove(&priolist->tree, node); \
285  free(stage); \
286  } \
287  node = prev; \
288  } \
289  *pnode = node; \
290  *pstage = stage; \
291  return 1; \
292  } \
293  PRIO_LIST_INLINE int ENAME##_prio_list_get_first_nonempty_stage(struct ENAME##_prio_list *priolist, struct starpu_rbtree_node **pnode, struct ENAME##_prio_list_stage **pstage) \
294  { \
295  struct starpu_rbtree_node *node = starpu_rbtree_first(&priolist->tree); \
296  return ENAME##_prio_list_get_next_nonempty_stage(priolist, node, pnode, pstage); \
297  } \
298  PRIO_LIST_INLINE int ENAME##_prio_list_get_last_nonempty_stage(struct ENAME##_prio_list *priolist, struct starpu_rbtree_node **pnode, struct ENAME##_prio_list_stage **pstage) \
299  { \
300  struct starpu_rbtree_node *node = starpu_rbtree_last(&priolist->tree); \
301  return ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, pnode, pstage); \
302  } \
303  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_highest(struct ENAME##_prio_list *priolist) \
304  { \
305  struct starpu_rbtree_node *node; \
306  struct ENAME##_prio_list_stage *stage; \
307  struct ENAME *ret; \
308  if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
309  return NULL; \
310  ret = ENAME##_list_pop_front(&stage->list); \
311  ENAME##_prio_list_check_empty_stage(priolist, stage); \
312  return ret; \
313  } \
314  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_lowest(struct ENAME##_prio_list *priolist) \
315  { \
316  struct starpu_rbtree_node *node; \
317  struct ENAME##_prio_list_stage *stage; \
318  struct ENAME *ret; \
319  if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
320  return NULL; \
321  ret = ENAME##_list_pop_front(&stage->list); \
322  ENAME##_prio_list_check_empty_stage(priolist, stage); \
323  return ret; \
324  } \
325  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_highest(struct ENAME##_prio_list *priolist) \
326  { \
327  struct starpu_rbtree_node *node; \
328  struct ENAME##_prio_list_stage *stage; \
329  if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
330  return NULL; \
331  return ENAME##_list_front(&stage->list); \
332  } \
333  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_lowest(struct ENAME##_prio_list *priolist) \
334  { \
335  struct starpu_rbtree_node *node; \
336  struct ENAME##_prio_list_stage *stage; \
337  if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
338  return NULL; \
339  return ENAME##_list_front(&stage->list); \
340  } \
341  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_highest(struct ENAME##_prio_list *priolist) \
342  { \
343  struct starpu_rbtree_node *node; \
344  struct ENAME##_prio_list_stage *stage; \
345  struct ENAME *ret; \
346  if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
347  return NULL; \
348  ret = ENAME##_list_pop_back(&stage->list); \
349  ENAME##_prio_list_check_empty_stage(priolist, stage); \
350  return ret; \
351  } \
352  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_lowest(struct ENAME##_prio_list *priolist) \
353  { \
354  struct starpu_rbtree_node *node; \
355  struct ENAME##_prio_list_stage *stage; \
356  struct ENAME *ret; \
357  if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
358  return NULL; \
359  ret = ENAME##_list_pop_back(&stage->list); \
360  ENAME##_prio_list_check_empty_stage(priolist, stage); \
361  return ret; \
362  } \
363  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_highest(struct ENAME##_prio_list *priolist) \
364  { \
365  struct starpu_rbtree_node *node; \
366  struct ENAME##_prio_list_stage *stage; \
367  if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
368  return NULL; \
369  return ENAME##_list_back(&stage->list); \
370  } \
371  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_lowest(struct ENAME##_prio_list *priolist) \
372  { \
373  struct starpu_rbtree_node *node; \
374  struct ENAME##_prio_list_stage *stage; \
375  if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
376  return NULL; \
377  return ENAME##_list_back(&stage->list); \
378  } \
379  PRIO_LIST_INLINE void ENAME##_prio_list_push_prio_list_back(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list *priolist_toadd) \
380  { \
381  struct starpu_rbtree_node *node_toadd, *tmp; \
382  starpu_rbtree_for_each_remove(&priolist_toadd->tree, node_toadd, tmp) { \
383  struct ENAME##_prio_list_stage *stage_toadd = ENAME##_node_to_list_stage(node_toadd); \
384  uintptr_t slot; \
385  struct starpu_rbtree_node *node = starpu_rbtree_lookup_slot(&priolist->tree, stage_toadd->prio, ENAME##_prio_list_cmp_fn, slot); \
386  if (node) \
387  { \
388  /* Catenate the lists */ \
389  if (!ENAME##_list_empty(&stage_toadd->list)) { \
390  struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(node); \
391  ENAME##_list_push_list_back(&stage->list, &stage_toadd->list); \
392  free(node_toadd); \
393  priolist->empty = 0; \
394  } \
395  } \
396  else \
397  { \
398  if (!ENAME##_list_empty(&stage_toadd->list)) { \
399  /* Just move the node between the trees */ \
400  starpu_rbtree_insert_slot(&priolist->tree, slot, node_toadd); \
401  priolist->empty = 0; \
402  } \
403  else \
404  { \
405  /* Actually empty, don't bother moving the list */ \
406  free(node_toadd); \
407  } \
408  } \
409  } \
410  } \
411  PRIO_LIST_INLINE int ENAME##_prio_list_ismember(const struct ENAME##_prio_list *priolist, const struct ENAME *e) \
412  { \
413  struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
414  if (node) { \
415  const struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage_const(node); \
416  return ENAME##_list_ismember(&stage->list, e); \
417  } \
418  return 0; \
419  } \
420  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_begin(struct ENAME##_prio_list *priolist) \
421  { \
422  struct starpu_rbtree_node *node; \
423  struct ENAME##_prio_list_stage *stage; \
424  if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
425  return NULL; \
426  return ENAME##_list_begin(&stage->list); \
427  } \
428  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_end(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
429  { return NULL; } \
430  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
431  { \
432  struct ENAME *next = ENAME##_list_next(i); \
433  if (next != ENAME##_list_end(NULL)) \
434  return next; \
435  struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
436  struct ENAME##_prio_list_stage *stage; \
437  node = starpu_rbtree_next(node); \
438  if (!ENAME##_prio_list_get_next_nonempty_stage(priolist, node, &node, &stage)) \
439  return NULL; \
440  return ENAME##_list_begin(&stage->list); \
441  } \
442  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_last(struct ENAME##_prio_list *priolist) \
443  { \
444  struct starpu_rbtree_node *node; \
445  struct ENAME##_prio_list_stage *stage; \
446  if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
447  return NULL; \
448  return ENAME##_list_last(&stage->list); \
449  } \
450  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_alpha(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
451  { return NULL; } \
452  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
453  { \
454  struct ENAME *next = ENAME##_list_prev(i); \
455  if (next != ENAME##_list_alpha(NULL)) \
456  return next; \
457  struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
458  struct ENAME##_prio_list_stage *stage; \
459  node = starpu_rbtree_prev(node); \
460  if (!ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, &node, &stage)) \
461  return NULL; \
462  return ENAME##_list_last(&stage->list); \
463  } \
464 
465 #else
466 
467 /* gdbinit can't recurse in a tree. Use a mere list in debugging mode. */
468 #define PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD) \
469  struct ENAME##_prio_list { struct ENAME##_list list; }; \
470  PRIO_LIST_INLINE void ENAME##_prio_list_init(struct ENAME##_prio_list *priolist) \
471  { ENAME##_list_init(&(priolist)->list); } \
472  PRIO_LIST_INLINE void ENAME##_prio_list_deinit(struct ENAME##_prio_list *priolist) \
473  { (void) (priolist); /* ENAME##_list_deinit(&(priolist)->list); */ } \
474  PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
475  { \
476  struct ENAME *cur; \
477  for (cur = ENAME##_list_begin(&(priolist)->list); \
478  cur != ENAME##_list_end(&(priolist)->list); \
479  cur = ENAME##_list_next(cur)) \
480  if ((e)->PRIOFIELD > cur->PRIOFIELD) \
481  break; \
482  if (cur == ENAME##_list_end(&(priolist)->list)) \
483  ENAME##_list_push_back(&(priolist)->list, (e)); \
484  else \
485  ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
486  } \
487  PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
488  { \
489  struct ENAME *cur; \
490  for (cur = ENAME##_list_begin(&(priolist)->list); \
491  cur != ENAME##_list_end(&(priolist)->list); \
492  cur = ENAME##_list_next(cur)) \
493  if ((e)->PRIOFIELD >= cur->PRIOFIELD) \
494  break; \
495  if (cur == ENAME##_list_end(&(priolist)->list)) \
496  ENAME##_list_push_back(&(priolist)->list, (e)); \
497  else \
498  ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
499  } \
500  PRIO_LIST_INLINE int ENAME##_prio_list_empty(const struct ENAME##_prio_list *priolist) \
501  { return ENAME##_list_empty(&(priolist)->list); } \
502  PRIO_LIST_INLINE void ENAME##_prio_list_erase(struct ENAME##_prio_list *priolist, struct ENAME *e) \
503  { ENAME##_list_erase(&(priolist)->list, (e)); } \
504  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_highest(struct ENAME##_prio_list *priolist) \
505  { return ENAME##_list_pop_front(&(priolist)->list); } \
506  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_lowest(struct ENAME##_prio_list *priolist) \
507  { return ENAME##_list_pop_front(&(priolist)->list); } \
508  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_highest(struct ENAME##_prio_list *priolist) \
509  { return ENAME##_list_pop_back(&(priolist)->list); } \
510  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_lowest(struct ENAME##_prio_list *priolist) \
511  { return ENAME##_list_pop_back(&(priolist)->list); } \
512  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_highest(struct ENAME##_prio_list *priolist) \
513  { return ENAME##_list_front(&(priolist)->list); } \
514  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_lowest(struct ENAME##_prio_list *priolist) \
515  { return ENAME##_list_front(&(priolist)->list); } \
516  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_highest(struct ENAME##_prio_list *priolist) \
517  { return ENAME##_list_back(&(priolist)->list); } \
518  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_lowest(struct ENAME##_prio_list *priolist) \
519  { return ENAME##_list_back(&(priolist)->list); } \
520  PRIO_LIST_INLINE void ENAME##_prio_list_push_prio_list_back(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list *priolist_toadd) \
521  { ENAME##_list_push_list_back(&(priolist)->list, &(priolist_toadd)->list); } \
522  PRIO_LIST_INLINE int ENAME##_prio_list_ismember(const struct ENAME##_prio_list *priolist, const struct ENAME *e) \
523  { return ENAME##_list_ismember(&(priolist)->list, (e)); } \
524  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_begin(struct ENAME##_prio_list *priolist) \
525  { return ENAME##_list_begin(&(priolist)->list); } \
526  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_end(struct ENAME##_prio_list *priolist) \
527  { return ENAME##_list_end(&(priolist)->list); } \
528  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
529  { return ENAME##_list_next(i); } \
530  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_last(struct ENAME##_prio_list *priolist) \
531  { return ENAME##_list_last(&(priolist)->list); } \
532  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_alpha(struct ENAME##_prio_list *priolist) \
533  { return ENAME##_list_alpha(&(priolist)->list); } \
534  PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
535  { return ENAME##_list_prev(i); } \
536 
537 #endif
538 
539 #endif // __PRIO_LIST_H__