3 #include "prio-queue.h"
5 void clear_prio_queue(struct prio_queue
*queue
)
13 void prio_queue_put(struct prio_queue
*queue
, void *thing
)
15 prio_queue_compare_fn compare
= queue
->compare
;
18 /* Append at the end */
19 ALLOC_GROW(queue
->array
, queue
->nr
+ 1, queue
->alloc
);
20 queue
->array
[queue
->nr
++] = thing
;
24 /* Bubble up the new one */
25 for (ix
= queue
->nr
- 1; ix
; ix
= parent
) {
26 parent
= (ix
- 1) / 2;
27 if (compare(queue
->array
[parent
], queue
->array
[ix
],
31 thing
= queue
->array
[parent
];
32 queue
->array
[parent
] = queue
->array
[ix
];
33 queue
->array
[ix
] = thing
;
37 void *prio_queue_get(struct prio_queue
*queue
)
41 prio_queue_compare_fn compare
= queue
->compare
;
46 return queue
->array
[--queue
->nr
]; /* LIFO */
48 result
= queue
->array
[0];
52 queue
->array
[0] = queue
->array
[queue
->nr
];
54 /* Push down the one at the root */
55 for (ix
= 0; ix
* 2 + 1 < queue
->nr
; ix
= child
) {
56 child
= ix
* 2 + 1; /* left */
57 if ((child
+ 1 < queue
->nr
) &&
58 (compare(queue
->array
[child
], queue
->array
[child
+ 1],
59 queue
->cb_data
) >= 0))
60 child
++; /* use right child */
62 if (compare(queue
->array
[ix
], queue
->array
[child
],
66 swap
= queue
->array
[child
];
67 queue
->array
[child
] = queue
->array
[ix
];
68 queue
->array
[ix
] = swap
;