Go to the documentation of this file.
123#ifndef __PRIO_LIST_H__
124#define __PRIO_LIST_H__
128#ifndef PRIO_LIST_INLINE
129#define PRIO_LIST_INLINE static inline
132#define PRIO_LIST_TYPE(ENAME, PRIOFIELD) \
133 PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD)
137#define PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD) \
139 struct ENAME##_prio_list { \
140 struct starpu_rbtree tree; \
144 struct ENAME##_prio_list_stage { \
145 struct starpu_rbtree_node node; \
147 struct ENAME##_list list; \
149 PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage(struct starpu_rbtree_node *node) \
152 return (struct ENAME##_prio_list_stage *) node; \
154 PRIO_LIST_INLINE const struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage_const(const struct starpu_rbtree_node *node) \
157 return (struct ENAME##_prio_list_stage *) node; \
159 PRIO_LIST_INLINE void ENAME##_prio_list_init(struct ENAME##_prio_list *priolist) \
161 starpu_rbtree_init(&priolist->tree); \
162 priolist->empty = 1; \
164 PRIO_LIST_INLINE void ENAME##_prio_list_init0(struct ENAME##_prio_list *priolist) \
166 starpu_rbtree_init0(&priolist->tree); \
167 priolist->empty = 1; \
169 PRIO_LIST_INLINE void ENAME##_prio_list_deinit(struct ENAME##_prio_list *priolist) \
171 if (starpu_rbtree_empty(&priolist->tree)) \
173 struct starpu_rbtree_node *root = priolist->tree.root; \
174 struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(root); \
175 assert(ENAME##_list_empty(&stage->list)); \
176 assert(!root->children[0] && !root->children[1]); \
177 starpu_rbtree_remove(&priolist->tree, root); \
180 PRIO_LIST_INLINE int ENAME##_prio_list_cmp_fn(int prio, const struct starpu_rbtree_node *node) \
183 const struct ENAME##_prio_list_stage *e2 = ENAME##_node_to_list_stage_const(node); \
184 if (e2->prio < prio) \
186 if (e2->prio == prio) \
191 PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_prio_list_add(struct ENAME##_prio_list *priolist, int prio) \
194 struct starpu_rbtree_node *node; \
195 struct ENAME##_prio_list_stage *stage; \
196 node = starpu_rbtree_lookup_slot(&priolist->tree, prio, ENAME##_prio_list_cmp_fn, slot); \
198 stage = ENAME##_node_to_list_stage(node); \
200 _STARPU_CALLOC(stage, 1, sizeof(*stage)); \
201 starpu_rbtree_node_init0(&stage->node); \
202 stage->prio = prio; \
203 ENAME##_list_init0(&stage->list); \
204 starpu_rbtree_insert_slot(&priolist->tree, slot, &stage->node); \
208 PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
210 struct ENAME##_prio_list_stage *stage = ENAME##_prio_list_add(priolist, e->PRIOFIELD); \
211 ENAME##_list_push_back(&stage->list, e); \
212 priolist->empty = 0; \
214 PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
216 struct ENAME##_prio_list_stage *stage = ENAME##_prio_list_add(priolist, e->PRIOFIELD); \
217 ENAME##_list_push_front(&stage->list, e); \
218 priolist->empty = 0; \
220 PRIO_LIST_INLINE int ENAME##_prio_list_empty(const struct ENAME##_prio_list *priolist) \
222 return priolist->empty; \
226 PRIO_LIST_INLINE int ENAME##_prio_list_empty_slow(const struct ENAME##_prio_list *priolist) \
228 if (starpu_rbtree_empty(&priolist->tree)) \
230 struct starpu_rbtree_node *root = priolist->tree.root; \
231 const struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage_const(root); \
232 if (ENAME##_list_empty(&stage->list) && !root->children[0] && !root->children[1]) \
238 PRIO_LIST_INLINE void ENAME##_prio_list_check_empty_stage(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list_stage *stage) \
240 if (ENAME##_list_empty(&stage->list)) { \
241 if (stage->prio != 0) \
244 starpu_rbtree_remove(&priolist->tree, &stage->node); \
247 priolist->empty = ENAME##_prio_list_empty_slow(priolist); \
250 PRIO_LIST_INLINE void ENAME##_prio_list_erase(struct ENAME##_prio_list *priolist, struct ENAME *e) \
252 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
254 struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(node); \
255 ENAME##_list_erase(&stage->list, e); \
256 ENAME##_prio_list_check_empty_stage(priolist, stage); \
258 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) \
260 struct ENAME##_prio_list_stage *stage; \
262 struct starpu_rbtree_node *next; \
266 stage = ENAME##_node_to_list_stage(node); \
267 if (!ENAME##_list_empty(&stage->list)) \
270 next = starpu_rbtree_next(node); \
272 if (stage->prio != 0) \
274 starpu_rbtree_remove(&priolist->tree, node); \
283 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) \
285 struct ENAME##_prio_list_stage *stage; \
287 struct starpu_rbtree_node *prev; \
291 stage = ENAME##_node_to_list_stage(node); \
292 if (!ENAME##_list_empty(&stage->list)) \
295 prev = starpu_rbtree_prev(node); \
297 if (stage->prio != 0) \
299 starpu_rbtree_remove(&priolist->tree, node); \
308 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) \
310 struct starpu_rbtree_node *node = starpu_rbtree_first(&priolist->tree); \
311 return ENAME##_prio_list_get_next_nonempty_stage(priolist, node, pnode, pstage); \
313 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) \
315 struct starpu_rbtree_node *node = starpu_rbtree_last(&priolist->tree); \
316 return ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, pnode, pstage); \
318 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_highest(struct ENAME##_prio_list *priolist) \
320 struct starpu_rbtree_node *node; \
321 struct ENAME##_prio_list_stage *stage; \
323 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
325 ret = ENAME##_list_pop_front(&stage->list); \
326 ENAME##_prio_list_check_empty_stage(priolist, stage); \
329 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_lowest(struct ENAME##_prio_list *priolist) \
331 struct starpu_rbtree_node *node; \
332 struct ENAME##_prio_list_stage *stage; \
334 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
336 ret = ENAME##_list_pop_front(&stage->list); \
337 ENAME##_prio_list_check_empty_stage(priolist, stage); \
340 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_highest(struct ENAME##_prio_list *priolist) \
342 struct starpu_rbtree_node *node; \
343 struct ENAME##_prio_list_stage *stage; \
344 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
346 return ENAME##_list_front(&stage->list); \
348 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_lowest(struct ENAME##_prio_list *priolist) \
350 struct starpu_rbtree_node *node; \
351 struct ENAME##_prio_list_stage *stage; \
352 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
354 return ENAME##_list_front(&stage->list); \
356 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_highest(struct ENAME##_prio_list *priolist) \
358 struct starpu_rbtree_node *node; \
359 struct ENAME##_prio_list_stage *stage; \
361 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
363 ret = ENAME##_list_pop_back(&stage->list); \
364 ENAME##_prio_list_check_empty_stage(priolist, stage); \
367 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_lowest(struct ENAME##_prio_list *priolist) \
369 struct starpu_rbtree_node *node; \
370 struct ENAME##_prio_list_stage *stage; \
372 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
374 ret = ENAME##_list_pop_back(&stage->list); \
375 ENAME##_prio_list_check_empty_stage(priolist, stage); \
378 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_highest(struct ENAME##_prio_list *priolist) \
380 struct starpu_rbtree_node *node; \
381 struct ENAME##_prio_list_stage *stage; \
382 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
384 return ENAME##_list_back(&stage->list); \
386 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_lowest(struct ENAME##_prio_list *priolist) \
388 struct starpu_rbtree_node *node; \
389 struct ENAME##_prio_list_stage *stage; \
390 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
392 return ENAME##_list_back(&stage->list); \
394 PRIO_LIST_INLINE void ENAME##_prio_list_push_prio_list_back(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list *priolist_toadd) \
396 struct starpu_rbtree_node *node_toadd, *tmp; \
397 starpu_rbtree_for_each_remove(&priolist_toadd->tree, node_toadd, tmp) { \
398 struct ENAME##_prio_list_stage *stage_toadd = ENAME##_node_to_list_stage(node_toadd); \
400 struct starpu_rbtree_node *node = starpu_rbtree_lookup_slot(&priolist->tree, stage_toadd->prio, ENAME##_prio_list_cmp_fn, slot); \
404 if (!ENAME##_list_empty(&stage_toadd->list)) { \
405 struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage(node); \
406 ENAME##_list_push_list_back(&stage->list, &stage_toadd->list); \
408 priolist->empty = 0; \
413 if (!ENAME##_list_empty(&stage_toadd->list)) { \
415 starpu_rbtree_insert_slot(&priolist->tree, slot, node_toadd); \
416 priolist->empty = 0; \
426 PRIO_LIST_INLINE int ENAME##_prio_list_ismember(const struct ENAME##_prio_list *priolist, const struct ENAME *e) \
428 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
430 const struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage_const(node); \
431 return ENAME##_list_ismember(&stage->list, e); \
435 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_begin(struct ENAME##_prio_list *priolist) \
437 struct starpu_rbtree_node *node; \
438 struct ENAME##_prio_list_stage *stage; \
439 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
441 return ENAME##_list_begin(&stage->list); \
443 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_end(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
445 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
447 struct ENAME *next = ENAME##_list_next(i); \
448 if (next != ENAME##_list_end(NULL)) \
450 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
452 struct ENAME##_prio_list_stage *stage; \
453 node = starpu_rbtree_next(node); \
454 if (!ENAME##_prio_list_get_next_nonempty_stage(priolist, node, &node, &stage)) \
456 return ENAME##_list_begin(&stage->list); \
458 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_last(struct ENAME##_prio_list *priolist) \
460 struct starpu_rbtree_node *node; \
461 struct ENAME##_prio_list_stage *stage; \
462 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
464 return ENAME##_list_last(&stage->list); \
466 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_alpha(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
468 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
470 struct ENAME *next = ENAME##_list_prev(i); \
471 if (next != ENAME##_list_alpha(NULL)) \
473 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
475 struct ENAME##_prio_list_stage *stage; \
476 node = starpu_rbtree_prev(node); \
477 if (!ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, &node, &stage)) \
479 return ENAME##_list_last(&stage->list); \
481 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev_highest(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
483 struct ENAME *next = ENAME##_list_prev(i); \
484 if (next != ENAME##_list_alpha(NULL)) \
486 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
488 struct ENAME##_prio_list_stage *stage; \
489 node = starpu_rbtree_next(node); \
490 if (!ENAME##_prio_list_get_next_nonempty_stage(priolist, node, &node, &stage)) \
492 return ENAME##_list_last(&stage->list); \
494 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next_lowest(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
496 struct ENAME *next = ENAME##_list_next(i); \
497 if (next != ENAME##_list_end(NULL)) \
499 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
501 struct ENAME##_prio_list_stage *stage; \
502 node = starpu_rbtree_prev(node); \
503 if (!ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, &node, &stage)) \
505 return ENAME##_list_begin(&stage->list); \
511#define PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD) \
512 struct ENAME##_prio_list { struct ENAME##_list list; }; \
513 PRIO_LIST_INLINE void ENAME##_prio_list_init(struct ENAME##_prio_list *priolist) \
514 { ENAME##_list_init(&(priolist)->list); } \
515 PRIO_LIST_INLINE void ENAME##_prio_list_init0(struct ENAME##_prio_list *priolist) \
516 { ENAME##_list_init0(&(priolist)->list); } \
517 PRIO_LIST_INLINE void ENAME##_prio_list_deinit(struct ENAME##_prio_list *priolist) \
518 { (void) (priolist); } \
519 PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
522 for (cur = ENAME##_list_begin(&(priolist)->list); \
523 cur != ENAME##_list_end(&(priolist)->list); \
524 cur = ENAME##_list_next(cur)) \
525 if ((e)->PRIOFIELD > cur->PRIOFIELD) \
527 if (cur == ENAME##_list_end(&(priolist)->list)) \
528 ENAME##_list_push_back(&(priolist)->list, (e)); \
530 ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
532 PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
535 for (cur = ENAME##_list_begin(&(priolist)->list); \
536 cur != ENAME##_list_end(&(priolist)->list); \
537 cur = ENAME##_list_next(cur)) \
538 if ((e)->PRIOFIELD >= cur->PRIOFIELD) \
540 if (cur == ENAME##_list_end(&(priolist)->list)) \
541 ENAME##_list_push_back(&(priolist)->list, (e)); \
543 ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
545 PRIO_LIST_INLINE int ENAME##_prio_list_empty(const struct ENAME##_prio_list *priolist) \
546 { return ENAME##_list_empty(&(priolist)->list); } \
547 PRIO_LIST_INLINE void ENAME##_prio_list_erase(struct ENAME##_prio_list *priolist, struct ENAME *e) \
548 { ENAME##_list_erase(&(priolist)->list, (e)); } \
549 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_highest(struct ENAME##_prio_list *priolist) \
550 { return ENAME##_list_pop_front(&(priolist)->list); } \
551 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_lowest(struct ENAME##_prio_list *priolist) \
552 { return ENAME##_list_pop_front(&(priolist)->list); } \
553 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_highest(struct ENAME##_prio_list *priolist) \
554 { return ENAME##_list_pop_back(&(priolist)->list); } \
555 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_lowest(struct ENAME##_prio_list *priolist) \
556 { return ENAME##_list_pop_back(&(priolist)->list); } \
557 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_highest(struct ENAME##_prio_list *priolist) \
558 { return ENAME##_list_front(&(priolist)->list); } \
559 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_lowest(struct ENAME##_prio_list *priolist) \
560 { return ENAME##_list_front(&(priolist)->list); } \
561 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_highest(struct ENAME##_prio_list *priolist) \
562 { return ENAME##_list_back(&(priolist)->list); } \
563 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_lowest(struct ENAME##_prio_list *priolist) \
564 { return ENAME##_list_back(&(priolist)->list); } \
565 PRIO_LIST_INLINE void ENAME##_prio_list_push_prio_list_back(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list *priolist_toadd) \
566 { ENAME##_list_push_list_back(&(priolist)->list, &(priolist_toadd)->list); } \
567 PRIO_LIST_INLINE int ENAME##_prio_list_ismember(const struct ENAME##_prio_list *priolist, const struct ENAME *e) \
568 { return ENAME##_list_ismember(&(priolist)->list, (e)); } \
569 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_begin(struct ENAME##_prio_list *priolist) \
570 { return ENAME##_list_begin(&(priolist)->list); } \
571 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_end(struct ENAME##_prio_list *priolist) \
572 { return ENAME##_list_end(&(priolist)->list); } \
573 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
574 { return ENAME##_list_next(i); } \
575 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_last(struct ENAME##_prio_list *priolist) \
576 { return ENAME##_list_last(&(priolist)->list); } \
577 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_alpha(struct ENAME##_prio_list *priolist) \
578 { return ENAME##_list_alpha(&(priolist)->list); } \
579 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
580 { return ENAME##_list_prev(i); } \
581 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev_highest(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
582 { return ENAME##_list_prev(i); } \
583 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next_lowest(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED, const struct ENAME *i) \
584 { return ENAME##_list_next(i); } \