Merge branch 'rs/fix-alt-odb-path-comparison' into maint
[git.git] / prio-queue.c
blobc9f8c6d2532b23ff07194c99c6f4121a7000bed4
1 #include "cache.h"
2 #include "commit.h"
3 #include "prio-queue.h"
5 void prio_queue_reverse(struct prio_queue *queue)
7 int i, j;
9 if (queue->compare != NULL)
10 die("BUG: prio_queue_reverse() on non-LIFO queue");
11 for (i = 0; i <= (j = (queue->nr - 1) - i); i++) {
12 struct commit *swap = queue->array[i];
13 queue->array[i] = queue->array[j];
14 queue->array[j] = swap;
18 void clear_prio_queue(struct prio_queue *queue)
20 free(queue->array);
21 queue->nr = 0;
22 queue->alloc = 0;
23 queue->array = NULL;
26 void prio_queue_put(struct prio_queue *queue, void *thing)
28 prio_queue_compare_fn compare = queue->compare;
29 int ix, parent;
31 /* Append at the end */
32 ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
33 queue->array[queue->nr++] = thing;
34 if (!compare)
35 return; /* LIFO */
37 /* Bubble up the new one */
38 for (ix = queue->nr - 1; ix; ix = parent) {
39 parent = (ix - 1) / 2;
40 if (compare(queue->array[parent], queue->array[ix],
41 queue->cb_data) <= 0)
42 break;
44 thing = queue->array[parent];
45 queue->array[parent] = queue->array[ix];
46 queue->array[ix] = thing;
50 void *prio_queue_get(struct prio_queue *queue)
52 void *result, *swap;
53 int ix, child;
54 prio_queue_compare_fn compare = queue->compare;
56 if (!queue->nr)
57 return NULL;
58 if (!compare)
59 return queue->array[--queue->nr]; /* LIFO */
61 result = queue->array[0];
62 if (!--queue->nr)
63 return result;
65 queue->array[0] = queue->array[queue->nr];
67 /* Push down the one at the root */
68 for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
69 child = ix * 2 + 1; /* left */
70 if ((child + 1 < queue->nr) &&
71 (compare(queue->array[child], queue->array[child + 1],
72 queue->cb_data) >= 0))
73 child++; /* use right child */
75 if (compare(queue->array[ix], queue->array[child],
76 queue->cb_data) <= 0)
77 break;
79 swap = queue->array[child];
80 queue->array[child] = queue->array[ix];
81 queue->array[ix] = swap;
83 return result;