| 37 | } |
| 38 | |
| 39 | void prio_queue_put(struct prio_queue *queue, void *thing) |
| 40 | { |
| 41 | size_t ix, parent; |
| 42 | |
| 43 | /* Append at the end */ |
| 44 | ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc); |
| 45 | queue->array[queue->nr].ctr = queue->insertion_ctr++; |
| 46 | queue->array[queue->nr].data = thing; |
| 47 | queue->nr++; |
| 48 | if (!queue->compare) |
| 49 | return; /* LIFO */ |
| 50 | |
| 51 | /* Bubble up the new one */ |
| 52 | for (ix = queue->nr - 1; ix; ix = parent) { |
| 53 | parent = (ix - 1) / 2; |
| 54 | if (compare(queue, parent, ix) <= 0) |
| 55 | break; |
| 56 | |
| 57 | swap(queue, parent, ix); |
| 58 | } |
| 59 | } |
| 60 | |
| 61 | static void sift_down_root(struct prio_queue *queue) |
| 62 | { |