StarPU Internal Handbook
Loading...
Searching...
No Matches
prio_list.h
Go to the documentation of this file.
1/* StarPU --- Runtime system for heterogeneous multicore architectures.
2 *
3 * Copyright (C) 2015-2023 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 * * Initialize a new priority list, assuming that the content of FOO_prio_list was already zeroed
41 * void FOO_prio_list_init0(struct FOO_prio_list*)
42 *
43 * * Free an empty priority list
44 * void FOO_prio_list_deinit(struct FOO_prio_list*)
45 *
46 * * Add a new cell at the end of the list of the priority of the cell (O(log2 p))
47 * void FOO_prio_list_push_back(struct FOO_prio_list*, struct FOO*)
48 *
49 * * Add a new cell at the beginning of the list of the priority of the cell (O(log2 p))
50 * void FOO_prio_list_push_front(struct FOO_prio_list*, struct FOO*)
51 *
52 * * Test whether the priority list is empty
53 * void FOO_prio_list_empty(struct FOO_prio_list*)
54 *
55 * * Remove given cell from the priority list
56 * void FOO_prio_list_erase(struct FOO_prio_list*, struct FOO*)
57 *
58 * * Return and remove the first cell of highest priority of the priority list
59 * void FOO_prio_list_pop_front_highest(struct FOO_prio_list*)
60 * * Return and remove the first cell of lowest priority of the priority list
61 * void FOO_prio_list_pop_front_lowest(struct FOO_prio_list*)
62 *
63 * * Return and remove the last cell of highest priority of the priority list
64 * void FOO_prio_list_pop_back_highest(struct FOO_prio_list*)
65 * * Return and remove the last cell of lowest priority of the priority list
66 * void FOO_prio_list_pop_back_lowest(struct FOO_prio_list*)
67 *
68 * * Return the first cell of highest priority of the priority list
69 * void FOO_prio_list_front_highest(struct FOO_prio_list*)
70 * * Return the first cell of lowest priority of the priority list
71 * void FOO_prio_list_front_lowest(struct FOO_prio_list*)
72 *
73 * * Return the last cell of highest priority of sthe priority list
74 * void FOO_prio_list_back_highest(struct FOO_prio_list*)
75 * * Return the last cell of lowest priority of sthe priority list
76 * void FOO_prio_list_back_lowest(struct FOO_prio_list*)
77 *
78 * * Append second priority list at ends of the first priority list (O(log2 p))
79 * void FOO_prio_list_push_prio_list_back(struct FOO_prio_list*, struct FOO_prio_list*)
80 *
81 * * Test whether cell is part of the list (O(n))
82 * void FOO_prio_list_ismember(struct FOO_prio_list*, struct FOO*)
83 *
84 * * Return the first cell of the list
85 * struct FOO* FOO_prio_list_begin(struct FOO_prio_list*);
86 *
87 * * Return the value to test at the end of the list
88 * struct FOO* FOO_prio_list_end(struct FOO_prio_list*);
89 *
90 * * Return the next cell of the list
91 * struct FOO* FOO_prio_list_next(struct FOO_prio_list*, struct FOO*)
92 *
93 * * Return the last cell of the list
94 * struct FOO* FOO_prio_list_last(struct FOO_prio_list*);
95 *
96 * * Return the value to test at the beginning of the list
97 * struct FOO* FOO_prio_list_alpha(struct FOO_prio_list*);
98 *
99 * * Return the previous cell of the list
100 * struct FOO* FOO_prio_list_prev(struct FOO_prio_list*, struct FOO*)
101 *
102 * Return the previous cell of the same priority, or the last cell of next highest priority
103 * struct FOO* FOO_prio_list_prev_highest(struct FOO_prio_list*, struct FOO*)
104 *
105 * Return the next cell of the same priority, or the first cell of next lowest priority
106 * struct FOO* FOO_prio_list_next_lowest(struct FOO_prio_list*, struct FOO*)
107 *
108 * PRIO_LIST_TYPE assumes that LIST_TYPE has already been called to create the
109 * final structure.
110 *
111 * *********************************************************
112 * Usage example:
113 * LIST_TYPE(my_struct,
114 * int a;
115 * int b;
116 * int prio;
117 * );
118 * PRIO_LIST_TYPE(my_struct, prio);
119 *
120 * and then my_struct_prio_list_* inlines are available
121 */
122
123#ifndef __PRIO_LIST_H__
124#define __PRIO_LIST_H__
125
126#include <common/rbtree.h>
127
128#ifndef PRIO_LIST_INLINE
129#define PRIO_LIST_INLINE static inline
130#endif
131
132#define PRIO_LIST_TYPE(ENAME, PRIOFIELD) \
133 PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD)
134
135#ifndef STARPU_DEBUG
136
137#define PRIO_LIST_CREATE_TYPE(ENAME, PRIOFIELD) \
138 /* The main type: an RB binary tree */ \
139 struct ENAME##_prio_list { \
140 struct starpu_rbtree tree; \
141 int empty; \
142 }; \
143 /* The second stage: a list */ \
144 struct ENAME##_prio_list_stage { \
145 struct starpu_rbtree_node node; /* Keep this first so ENAME##_node_to_list_stage can work. */ \
146 int prio; \
147 struct ENAME##_list list; \
148 }; \
149 PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage(struct starpu_rbtree_node *node) \
150 { \
151 /* This assumes node is first member of stage */ \
152 return (struct ENAME##_prio_list_stage *) node; \
153 } \
154 PRIO_LIST_INLINE const struct ENAME##_prio_list_stage *ENAME##_node_to_list_stage_const(const struct starpu_rbtree_node *node) \
155 { \
156 /* This assumes node is first member of stage */ \
157 return (struct ENAME##_prio_list_stage *) node; \
158 } \
159 PRIO_LIST_INLINE void ENAME##_prio_list_init(struct ENAME##_prio_list *priolist) \
160 { \
161 starpu_rbtree_init(&priolist->tree); \
162 priolist->empty = 1; \
163 } \
164 PRIO_LIST_INLINE void ENAME##_prio_list_init0(struct ENAME##_prio_list *priolist) \
165 { \
166 starpu_rbtree_init0(&priolist->tree); \
167 priolist->empty = 1; \
168 } \
169 PRIO_LIST_INLINE void ENAME##_prio_list_deinit(struct ENAME##_prio_list *priolist) \
170 { \
171 if (starpu_rbtree_empty(&priolist->tree)) \
172 return; \
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); \
178 free(stage); \
179 } \
180 PRIO_LIST_INLINE int ENAME##_prio_list_cmp_fn(int prio, const struct starpu_rbtree_node *node) \
181 { \
182 /* Sort by decreasing order */ \
183 const struct ENAME##_prio_list_stage *e2 = ENAME##_node_to_list_stage_const(node); \
184 if (e2->prio < prio) \
185 return -1; \
186 if (e2->prio == prio) \
187 return 0; \
188 /* e2->prio > prio */ \
189 return 1; \
190 } \
191 PRIO_LIST_INLINE struct ENAME##_prio_list_stage *ENAME##_prio_list_add(struct ENAME##_prio_list *priolist, int prio) \
192 { \
193 uintptr_t slot; \
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); \
197 if (node) \
198 stage = ENAME##_node_to_list_stage(node); \
199 else { \
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); \
205 } \
206 return stage; \
207 } \
208 PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
209 { \
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; \
213 } \
214 PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
215 { \
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; \
219 } \
220 PRIO_LIST_INLINE int ENAME##_prio_list_empty(const struct ENAME##_prio_list *priolist) \
221 { \
222 return priolist->empty; \
223 } \
224 /* Version of list_empty which does not use the cached empty flag,
225 * typically used to compute the value of the flag */ \
226 PRIO_LIST_INLINE int ENAME##_prio_list_empty_slow(const struct ENAME##_prio_list *priolist) \
227 { \
228 if (starpu_rbtree_empty(&priolist->tree)) \
229 return 1; \
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]) \
233 /* Just one empty list */ \
234 return 1; \
235 return 0; \
236 } \
237 /* To be called when removing an element from a stage, to potentially remove this stage */ \
238 PRIO_LIST_INLINE void ENAME##_prio_list_check_empty_stage(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list_stage *stage) \
239 { \
240 if (ENAME##_list_empty(&stage->list)) { \
241 if (stage->prio != 0) \
242 { \
243 /* stage got empty, remove it */ \
244 starpu_rbtree_remove(&priolist->tree, &stage->node); \
245 free(stage); \
246 } \
247 priolist->empty = ENAME##_prio_list_empty_slow(priolist); \
248 } \
249 } \
250 PRIO_LIST_INLINE void ENAME##_prio_list_erase(struct ENAME##_prio_list *priolist, struct ENAME *e) \
251 { \
252 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
253 assert(node); \
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); \
257 } \
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) \
259 { \
260 struct ENAME##_prio_list_stage *stage; \
261 while(1) { \
262 struct starpu_rbtree_node *next; \
263 if (!node) \
264 /* Tree is empty */ \
265 return 0; \
266 stage = ENAME##_node_to_list_stage(node); \
267 if (!ENAME##_list_empty(&stage->list)) \
268 break; \
269 /* Empty list, skip to next tree entry */ \
270 next = starpu_rbtree_next(node); \
271 /* drop it if not 0-prio */ \
272 if (stage->prio != 0) \
273 { \
274 starpu_rbtree_remove(&priolist->tree, node); \
275 free(stage); \
276 } \
277 node = next; \
278 } \
279 *pnode = node; \
280 *pstage = stage; \
281 return 1; \
282 } \
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) \
284 { \
285 struct ENAME##_prio_list_stage *stage; \
286 while(1) { \
287 struct starpu_rbtree_node *prev; \
288 if (!node) \
289 /* Tree is empty */ \
290 return 0; \
291 stage = ENAME##_node_to_list_stage(node); \
292 if (!ENAME##_list_empty(&stage->list)) \
293 break; \
294 /* Empty list, skip to prev tree entry */ \
295 prev = starpu_rbtree_prev(node); \
296 /* drop it if not 0-prio */ \
297 if (stage->prio != 0) \
298 { \
299 starpu_rbtree_remove(&priolist->tree, node); \
300 free(stage); \
301 } \
302 node = prev; \
303 } \
304 *pnode = node; \
305 *pstage = stage; \
306 return 1; \
307 } \
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) \
309 { \
310 struct starpu_rbtree_node *node = starpu_rbtree_first(&priolist->tree); \
311 return ENAME##_prio_list_get_next_nonempty_stage(priolist, node, pnode, pstage); \
312 } \
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) \
314 { \
315 struct starpu_rbtree_node *node = starpu_rbtree_last(&priolist->tree); \
316 return ENAME##_prio_list_get_prev_nonempty_stage(priolist, node, pnode, pstage); \
317 } \
318 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_highest(struct ENAME##_prio_list *priolist) \
319 { \
320 struct starpu_rbtree_node *node; \
321 struct ENAME##_prio_list_stage *stage; \
322 struct ENAME *ret; \
323 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
324 return NULL; \
325 ret = ENAME##_list_pop_front(&stage->list); \
326 ENAME##_prio_list_check_empty_stage(priolist, stage); \
327 return ret; \
328 } \
329 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_front_lowest(struct ENAME##_prio_list *priolist) \
330 { \
331 struct starpu_rbtree_node *node; \
332 struct ENAME##_prio_list_stage *stage; \
333 struct ENAME *ret; \
334 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
335 return NULL; \
336 ret = ENAME##_list_pop_front(&stage->list); \
337 ENAME##_prio_list_check_empty_stage(priolist, stage); \
338 return ret; \
339 } \
340 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_highest(struct ENAME##_prio_list *priolist) \
341 { \
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)) \
345 return NULL; \
346 return ENAME##_list_front(&stage->list); \
347 } \
348 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_front_lowest(struct ENAME##_prio_list *priolist) \
349 { \
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)) \
353 return NULL; \
354 return ENAME##_list_front(&stage->list); \
355 } \
356 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_highest(struct ENAME##_prio_list *priolist) \
357 { \
358 struct starpu_rbtree_node *node; \
359 struct ENAME##_prio_list_stage *stage; \
360 struct ENAME *ret; \
361 if (!ENAME##_prio_list_get_first_nonempty_stage(priolist, &node, &stage)) \
362 return NULL; \
363 ret = ENAME##_list_pop_back(&stage->list); \
364 ENAME##_prio_list_check_empty_stage(priolist, stage); \
365 return ret; \
366 } \
367 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_pop_back_lowest(struct ENAME##_prio_list *priolist) \
368 { \
369 struct starpu_rbtree_node *node; \
370 struct ENAME##_prio_list_stage *stage; \
371 struct ENAME *ret; \
372 if (!ENAME##_prio_list_get_last_nonempty_stage(priolist, &node, &stage)) \
373 return NULL; \
374 ret = ENAME##_list_pop_back(&stage->list); \
375 ENAME##_prio_list_check_empty_stage(priolist, stage); \
376 return ret; \
377 } \
378 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_highest(struct ENAME##_prio_list *priolist) \
379 { \
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)) \
383 return NULL; \
384 return ENAME##_list_back(&stage->list); \
385 } \
386 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_back_lowest(struct ENAME##_prio_list *priolist) \
387 { \
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)) \
391 return NULL; \
392 return ENAME##_list_back(&stage->list); \
393 } \
394 PRIO_LIST_INLINE void ENAME##_prio_list_push_prio_list_back(struct ENAME##_prio_list *priolist, struct ENAME##_prio_list *priolist_toadd) \
395 { \
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); \
399 uintptr_t slot; \
400 struct starpu_rbtree_node *node = starpu_rbtree_lookup_slot(&priolist->tree, stage_toadd->prio, ENAME##_prio_list_cmp_fn, slot); \
401 if (node) \
402 { \
403 /* Catenate the lists */ \
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); \
407 free(node_toadd); \
408 priolist->empty = 0; \
409 } \
410 } \
411 else \
412 { \
413 if (!ENAME##_list_empty(&stage_toadd->list)) { \
414 /* Just move the node between the trees */ \
415 starpu_rbtree_insert_slot(&priolist->tree, slot, node_toadd); \
416 priolist->empty = 0; \
417 } \
418 else \
419 { \
420 /* Actually empty, don't bother moving the list */ \
421 free(node_toadd); \
422 } \
423 } \
424 } \
425 } \
426 PRIO_LIST_INLINE int ENAME##_prio_list_ismember(const struct ENAME##_prio_list *priolist, const struct ENAME *e) \
427 { \
428 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, e->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
429 if (node) { \
430 const struct ENAME##_prio_list_stage *stage = ENAME##_node_to_list_stage_const(node); \
431 return ENAME##_list_ismember(&stage->list, e); \
432 } \
433 return 0; \
434 } \
435 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_begin(struct ENAME##_prio_list *priolist) \
436 { \
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)) \
440 return NULL; \
441 return ENAME##_list_begin(&stage->list); \
442 } \
443 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_end(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
444 { return NULL; } \
445 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
446 { \
447 struct ENAME *next = ENAME##_list_next(i); \
448 if (next != ENAME##_list_end(NULL)) \
449 return next; \
450 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
451 assert(node); \
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)) \
455 return NULL; \
456 return ENAME##_list_begin(&stage->list); \
457 } \
458 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_last(struct ENAME##_prio_list *priolist) \
459 { \
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)) \
463 return NULL; \
464 return ENAME##_list_last(&stage->list); \
465 } \
466 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_alpha(struct ENAME##_prio_list *priolist STARPU_ATTRIBUTE_UNUSED) \
467 { return NULL; } \
468 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
469 { \
470 struct ENAME *next = ENAME##_list_prev(i); \
471 if (next != ENAME##_list_alpha(NULL)) \
472 return next; \
473 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
474 assert(node); \
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)) \
478 return NULL; \
479 return ENAME##_list_last(&stage->list); \
480 } \
481 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_prev_highest(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
482 { \
483 struct ENAME *next = ENAME##_list_prev(i); \
484 if (next != ENAME##_list_alpha(NULL)) \
485 return next; \
486 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
487 assert(node); \
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)) \
491 return NULL; \
492 return ENAME##_list_last(&stage->list); \
493 } \
494 PRIO_LIST_INLINE struct ENAME *ENAME##_prio_list_next_lowest(struct ENAME##_prio_list *priolist, const struct ENAME *i) \
495 { \
496 struct ENAME *next = ENAME##_list_next(i); \
497 if (next != ENAME##_list_end(NULL)) \
498 return next; \
499 struct starpu_rbtree_node *node = starpu_rbtree_lookup(&priolist->tree, i->PRIOFIELD, ENAME##_prio_list_cmp_fn); \
500 assert(node); \
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)) \
504 return NULL; \
505 return ENAME##_list_begin(&stage->list); \
506 } \
507
508#else
509
510/* gdbinit can't recurse in a tree. Use a mere list in debugging mode. */
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); /* ENAME##_list_deinit(&(priolist)->list); */ } \
519 PRIO_LIST_INLINE void ENAME##_prio_list_push_back(struct ENAME##_prio_list *priolist, struct ENAME *e) \
520 { \
521 struct ENAME *cur; \
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) \
526 break; \
527 if (cur == ENAME##_list_end(&(priolist)->list)) \
528 ENAME##_list_push_back(&(priolist)->list, (e)); \
529 else \
530 ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
531 } \
532 PRIO_LIST_INLINE void ENAME##_prio_list_push_front(struct ENAME##_prio_list *priolist, struct ENAME *e) \
533 { \
534 struct ENAME *cur; \
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) \
539 break; \
540 if (cur == ENAME##_list_end(&(priolist)->list)) \
541 ENAME##_list_push_back(&(priolist)->list, (e)); \
542 else \
543 ENAME##_list_insert_before(&(priolist)->list, (e), cur); \
544 } \
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); } \
585
586#endif
587
588#endif // __PRIO_LIST_H__