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__
rbtree.h