use SWAP macro
[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{
e8f91e3d 6 int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
6d63baa4 7 queue->cb_data);
e8f91e3d
JK
8 if (!cmp)
9 cmp = queue->array[i].ctr - queue->array[j].ctr;
6d63baa4
JK
10 return cmp;
11}
12
13static inline void swap(struct prio_queue *queue, int i, int j)
14{
35d803bc 15 SWAP(queue->array[i], queue->array[j]);
6d63baa4
JK
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;
e8f91e3d 34 queue->insertion_ctr = 0;
b4b594a3
JH
35}
36
37void prio_queue_put(struct prio_queue *queue, void *thing)
38{
b4b594a3
JH
39 int ix, parent;
40
41 /* Append at the end */
42 ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
e8f91e3d
JK
43 queue->array[queue->nr].ctr = queue->insertion_ctr++;
44 queue->array[queue->nr].data = thing;
45 queue->nr++;
6d63baa4 46 if (!queue->compare)
b4b594a3
JH
47 return; /* LIFO */
48
49 /* Bubble up the new one */
50 for (ix = queue->nr - 1; ix; ix = parent) {
51 parent = (ix - 1) / 2;
6d63baa4 52 if (compare(queue, parent, ix) <= 0)
b4b594a3
JH
53 break;
54
6d63baa4 55 swap(queue, parent, ix);
b4b594a3
JH
56 }
57}
58
59void *prio_queue_get(struct prio_queue *queue)
60{
6d63baa4 61 void *result;
b4b594a3 62 int ix, child;
b4b594a3
JH
63
64 if (!queue->nr)
65 return NULL;
6d63baa4 66 if (!queue->compare)
e8f91e3d 67 return queue->array[--queue->nr].data; /* LIFO */
b4b594a3 68
e8f91e3d 69 result = queue->array[0].data;
b4b594a3
JH
70 if (!--queue->nr)
71 return result;
72
73 queue->array[0] = queue->array[queue->nr];
74
75 /* Push down the one at the root */
76 for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
77 child = ix * 2 + 1; /* left */
6d63baa4
JK
78 if (child + 1 < queue->nr &&
79 compare(queue, child, child + 1) >= 0)
b4b594a3
JH
80 child++; /* use right child */
81
6d63baa4 82 if (compare(queue, ix, child) <= 0)
b4b594a3
JH
83 break;
84
6d63baa4 85 swap(queue, child, ix);
b4b594a3
JH
86 }
87 return result;
88}