| 1 | #include "git-compat-util.h" |
| 2 | #include "prio-queue.h" |
| 3 | |
| 4 | static inline int compare(struct prio_queue *queue, size_t i, size_t j) |
| 5 | { |
| 6 | int cmp = queue->compare(queue->array[i].data, queue->array[j].data, |
| 7 | queue->cb_data); |
| 8 | if (!cmp) |
| 9 | cmp = (queue->array[i].ctr > queue->array[j].ctr) - |
| 10 | (queue->array[i].ctr < queue->array[j].ctr); |
| 11 | return cmp; |
| 12 | } |
| 13 | |
| 14 | static inline void swap(struct prio_queue *queue, size_t i, size_t j) |
| 15 | { |
| 16 | SWAP(queue->array[i], queue->array[j]); |
| 17 | } |
| 18 | |
| 19 | void prio_queue_reverse(struct prio_queue *queue) |
| 20 | { |
| 21 | size_t i, j; |
| 22 | |
| 23 | if (queue->compare) |
| 24 | BUG("prio_queue_reverse() on non-LIFO queue"); |
| 25 | if (!queue->nr) |
| 26 | return; |
| 27 | for (i = 0; i < (j = (queue->nr - 1) - i); i++) |
| 28 | swap(queue, i, j); |
| 29 | } |
| 30 | |
| 31 | void clear_prio_queue(struct prio_queue *queue) |
| 32 | { |
| 33 | FREE_AND_NULL(queue->array); |
| 34 | queue->nr = 0; |
| 35 | queue->alloc = 0; |
| 36 | queue->insertion_ctr = 0; |
| 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 | { |
| 63 | size_t ix, child; |
| 64 | |
| 65 | /* Push down the one at the root */ |
| 66 | for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) { |
| 67 | child = ix * 2 + 1; /* left */ |
| 68 | if (child + 1 < queue->nr && |
| 69 | compare(queue, child, child + 1) >= 0) |
| 70 | child++; /* use right child */ |
| 71 | |
| 72 | if (compare(queue, ix, child) <= 0) |
| 73 | break; |
| 74 | |
| 75 | swap(queue, child, ix); |
| 76 | } |
| 77 | } |
| 78 | |
| 79 | void *prio_queue_get(struct prio_queue *queue) |
| 80 | { |
| 81 | void *result; |
| 82 | |
| 83 | if (!queue->nr) |
| 84 | return NULL; |
| 85 | if (!queue->compare) |
| 86 | return queue->array[--queue->nr].data; /* LIFO */ |
| 87 | |
| 88 | result = queue->array[0].data; |
| 89 | if (!--queue->nr) |
| 90 | return result; |
| 91 | |
| 92 | queue->array[0] = queue->array[queue->nr]; |
| 93 | sift_down_root(queue); |
| 94 | return result; |
| 95 | } |
| 96 | |
| 97 | void *prio_queue_peek(struct prio_queue *queue) |
| 98 | { |
| 99 | if (!queue->nr) |
| 100 | return NULL; |
| 101 | if (!queue->compare) |
| 102 | return queue->array[queue->nr - 1].data; |
| 103 | return queue->array[0].data; |
| 104 | } |
| 105 | |
| 106 | void prio_queue_replace(struct prio_queue *queue, void *thing) |
| 107 | { |
| 108 | if (!queue->nr) { |
| 109 | prio_queue_put(queue, thing); |
| 110 | } else if (!queue->compare) { |
| 111 | queue->array[queue->nr - 1].ctr = queue->insertion_ctr++; |
| 112 | queue->array[queue->nr - 1].data = thing; |
| 113 | } else { |
| 114 | queue->array[0].ctr = queue->insertion_ctr++; |
| 115 | queue->array[0].data = thing; |
| 116 | sift_down_root(queue); |
| 117 | } |
| 118 | } |