prio-queue: factor out compare and swap operations
[git/git.git] / prio-queue.c
CommitLineData
b4b594a3 1#include "cache.h"
b4b594a3
JH
2#include "prio-queue.h"
3
6d63baa4
JK
4static inline int compare(struct prio_queue *queue, int i, int j)
5{
6 int cmp = queue->compare(queue->array[i], queue->array[j],
7 queue->cb_data);
8 return cmp;
9}
10
11static inline void swap(struct prio_queue *queue, int i, int j)
12{
13 void *tmp = queue->array[i];
14 queue->array[i] = queue->array[j];
15 queue->array[j] = tmp;
16}
17
da24b104
JH
18void prio_queue_reverse(struct prio_queue *queue)
19{
20 int i, j;
21
22 if (queue->compare != NULL)
23 die("BUG: prio_queue_reverse() on non-LIFO queue");
6d63baa4
JK
24 for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
25 swap(queue, i, j);
da24b104
JH
26}
27
b4b594a3
JH
28void clear_prio_queue(struct prio_queue *queue)
29{
30 free(queue->array);
31 queue->nr = 0;
32 queue->alloc = 0;
33 queue->array = NULL;
34}
35
36void prio_queue_put(struct prio_queue *queue, void *thing)
37{
b4b594a3
JH
38 int ix, parent;
39
40 /* Append at the end */
41 ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
42 queue->array[queue->nr++] = thing;
6d63baa4 43 if (!queue->compare)
b4b594a3
JH
44 return; /* LIFO */
45
46 /* Bubble up the new one */
47 for (ix = queue->nr - 1; ix; ix = parent) {
48 parent = (ix - 1) / 2;
6d63baa4 49 if (compare(queue, parent, ix) <= 0)
b4b594a3
JH
50 break;
51
6d63baa4 52 swap(queue, parent, ix);
b4b594a3
JH
53 }
54}
55
56void *prio_queue_get(struct prio_queue *queue)
57{
6d63baa4 58 void *result;
b4b594a3 59 int ix, child;
b4b594a3
JH
60
61 if (!queue->nr)
62 return NULL;
6d63baa4 63 if (!queue->compare)
b4b594a3
JH
64 return queue->array[--queue->nr]; /* LIFO */
65
66 result = queue->array[0];
67 if (!--queue->nr)
68 return result;
69
70 queue->array[0] = queue->array[queue->nr];
71
72 /* Push down the one at the root */
73 for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
74 child = ix * 2 + 1; /* left */
6d63baa4
JK
75 if (child + 1 < queue->nr &&
76 compare(queue, child, child + 1) >= 0)
b4b594a3
JH
77 child++; /* use right child */
78
6d63baa4 79 if (compare(queue, ix, child) <= 0)
b4b594a3
JH
80 break;
81
6d63baa4 82 swap(queue, child, ix);
b4b594a3
JH
83 }
84 return result;
85}