]>
Commit | Line | Data |
---|---|---|
36bf1958 EN |
1 | #include "git-compat-util.h" |
2 | #include "alloc.h" | |
b4b594a3 JH |
3 | #include "prio-queue.h" |
4 | ||
6d63baa4 JK |
5 | static inline int compare(struct prio_queue *queue, int i, int j) |
6 | { | |
e8f91e3d | 7 | int cmp = queue->compare(queue->array[i].data, queue->array[j].data, |
6d63baa4 | 8 | queue->cb_data); |
e8f91e3d JK |
9 | if (!cmp) |
10 | cmp = queue->array[i].ctr - queue->array[j].ctr; | |
6d63baa4 JK |
11 | return cmp; |
12 | } | |
13 | ||
14 | static inline void swap(struct prio_queue *queue, int i, int j) | |
15 | { | |
35d803bc | 16 | SWAP(queue->array[i], queue->array[j]); |
6d63baa4 JK |
17 | } |
18 | ||
da24b104 JH |
19 | void prio_queue_reverse(struct prio_queue *queue) |
20 | { | |
21 | int i, j; | |
22 | ||
afe8a907 | 23 | if (queue->compare) |
033abf97 | 24 | BUG("prio_queue_reverse() on non-LIFO queue"); |
1f9e18b7 | 25 | for (i = 0; i < (j = (queue->nr - 1) - i); i++) |
6d63baa4 | 26 | swap(queue, i, j); |
da24b104 JH |
27 | } |
28 | ||
b4b594a3 JH |
29 | void clear_prio_queue(struct prio_queue *queue) |
30 | { | |
88ce3ef6 | 31 | FREE_AND_NULL(queue->array); |
b4b594a3 JH |
32 | queue->nr = 0; |
33 | queue->alloc = 0; | |
e8f91e3d | 34 | queue->insertion_ctr = 0; |
b4b594a3 JH |
35 | } |
36 | ||
37 | void 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 | ||
59 | void *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 | } | |
aca4240f DS |
89 | |
90 | void *prio_queue_peek(struct prio_queue *queue) | |
91 | { | |
92 | if (!queue->nr) | |
93 | return NULL; | |
94 | if (!queue->compare) | |
95 | return queue->array[queue->nr - 1].data; | |
96 | return queue->array[0].data; | |
97 | } |