| 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 | queue->get_pending = 0; |
| 38 | } |
| 39 | |
| 40 | static void sift_down_root(struct prio_queue *queue) |
| 41 | { |
| 42 | size_t ix, child; |
| 43 | |
| 44 | /* Push down the one at the root */ |
| 45 | for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) { |
| 46 | child = ix * 2 + 1; /* left */ |
| 47 | if (child + 1 < queue->nr_ && |
| 48 | compare(queue, child, child + 1) >= 0) |
| 49 | child++; /* use right child */ |
| 50 | |
| 51 | if (compare(queue, ix, child) <= 0) |
| 52 | break; |
| 53 | |
| 54 | swap(queue, child, ix); |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | static inline void flush_get(struct prio_queue *queue) |
| 59 | { |
| 60 | if (!queue->get_pending) |
| 61 | return; |
| 62 | queue->get_pending = 0; |
| 63 | queue->array[0] = queue->array[--queue->nr_]; |
| 64 | sift_down_root(queue); |
| 65 | } |
| 66 | |
| 67 | void prio_queue_put(struct prio_queue *queue, void *thing) |
| 68 | { |
| 69 | size_t ix, parent; |
| 70 | |
| 71 | if (queue->get_pending) { |
| 72 | queue->get_pending = 0; |
| 73 | queue->array[0].ctr = queue->insertion_ctr++; |
| 74 | queue->array[0].data = thing; |
| 75 | sift_down_root(queue); |
| 76 | return; |
| 77 | } |
| 78 | |
| 79 | /* Append at the end */ |
| 80 | ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc); |
| 81 | queue->array[queue->nr_].ctr = queue->insertion_ctr++; |
| 82 | queue->array[queue->nr_].data = thing; |
| 83 | queue->nr_++; |
| 84 | if (!queue->compare) |
| 85 | return; /* LIFO */ |
| 86 | |
| 87 | /* Bubble up the new one */ |
| 88 | for (ix = queue->nr_ - 1; ix; ix = parent) { |
| 89 | parent = (ix - 1) / 2; |
| 90 | if (compare(queue, parent, ix) <= 0) |
| 91 | break; |
| 92 | |
| 93 | swap(queue, parent, ix); |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | void *prio_queue_get(struct prio_queue *queue) |
| 98 | { |
| 99 | if (queue->nr_ <= queue->get_pending) { |
| 100 | queue->nr_ = 0; |
| 101 | queue->get_pending = 0; |
| 102 | return NULL; |
| 103 | } |
| 104 | if (!queue->compare) |
| 105 | return queue->array[--queue->nr_].data; /* LIFO */ |
| 106 | |
| 107 | flush_get(queue); |
| 108 | |
| 109 | queue->get_pending = 1; |
| 110 | return queue->array[0].data; |
| 111 | } |
| 112 | |
| 113 | void *prio_queue_peek(struct prio_queue *queue) |
| 114 | { |
| 115 | if (queue->nr_ <= queue->get_pending) { |
| 116 | queue->nr_ = 0; |
| 117 | queue->get_pending = 0; |
| 118 | return NULL; |
| 119 | } |
| 120 | if (!queue->compare) |
| 121 | return queue->array[queue->nr_ - 1].data; |
| 122 | |
| 123 | flush_get(queue); |
| 124 | |
| 125 | return queue->array[0].data; |
| 126 | } |