Line | Count | Source (jump to first uncovered line) |
1 | | #include "git-compat-util.h" |
2 | | #include "prio-queue.h" |
3 | | |
4 | | static inline int compare(struct prio_queue *queue, int i, int j) |
5 | 0 | { |
6 | 0 | int cmp = queue->compare(queue->array[i].data, queue->array[j].data, |
7 | 0 | queue->cb_data); |
8 | 0 | if (!cmp) |
9 | 0 | cmp = queue->array[i].ctr - queue->array[j].ctr; |
10 | 0 | return cmp; |
11 | 0 | } |
12 | | |
13 | | static inline void swap(struct prio_queue *queue, int i, int j) |
14 | 0 | { |
15 | 0 | SWAP(queue->array[i], queue->array[j]); |
16 | 0 | } |
17 | | |
18 | | void prio_queue_reverse(struct prio_queue *queue) |
19 | 0 | { |
20 | 0 | int i, j; |
21 | |
|
22 | 0 | if (queue->compare) |
23 | 0 | BUG("prio_queue_reverse() on non-LIFO queue"); |
24 | 0 | for (i = 0; i < (j = (queue->nr - 1) - i); i++) |
25 | 0 | swap(queue, i, j); |
26 | 0 | } |
27 | | |
28 | | void clear_prio_queue(struct prio_queue *queue) |
29 | 0 | { |
30 | 0 | FREE_AND_NULL(queue->array); |
31 | 0 | queue->nr = 0; |
32 | 0 | queue->alloc = 0; |
33 | 0 | queue->insertion_ctr = 0; |
34 | 0 | } |
35 | | |
36 | | void prio_queue_put(struct prio_queue *queue, void *thing) |
37 | 0 | { |
38 | 0 | int ix, parent; |
39 | | |
40 | | /* Append at the end */ |
41 | 0 | ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc); |
42 | 0 | queue->array[queue->nr].ctr = queue->insertion_ctr++; |
43 | 0 | queue->array[queue->nr].data = thing; |
44 | 0 | queue->nr++; |
45 | 0 | if (!queue->compare) |
46 | 0 | return; /* LIFO */ |
47 | | |
48 | | /* Bubble up the new one */ |
49 | 0 | for (ix = queue->nr - 1; ix; ix = parent) { |
50 | 0 | parent = (ix - 1) / 2; |
51 | 0 | if (compare(queue, parent, ix) <= 0) |
52 | 0 | break; |
53 | | |
54 | 0 | swap(queue, parent, ix); |
55 | 0 | } |
56 | 0 | } |
57 | | |
58 | | void *prio_queue_get(struct prio_queue *queue) |
59 | 0 | { |
60 | 0 | void *result; |
61 | 0 | int ix, child; |
62 | |
|
63 | 0 | if (!queue->nr) |
64 | 0 | return NULL; |
65 | 0 | if (!queue->compare) |
66 | 0 | return queue->array[--queue->nr].data; /* LIFO */ |
67 | | |
68 | 0 | result = queue->array[0].data; |
69 | 0 | if (!--queue->nr) |
70 | 0 | return result; |
71 | | |
72 | 0 | queue->array[0] = queue->array[queue->nr]; |
73 | | |
74 | | /* Push down the one at the root */ |
75 | 0 | for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) { |
76 | 0 | child = ix * 2 + 1; /* left */ |
77 | 0 | if (child + 1 < queue->nr && |
78 | 0 | compare(queue, child, child + 1) >= 0) |
79 | 0 | child++; /* use right child */ |
80 | |
|
81 | 0 | if (compare(queue, ix, child) <= 0) |
82 | 0 | break; |
83 | | |
84 | 0 | swap(queue, child, ix); |
85 | 0 | } |
86 | 0 | return result; |
87 | 0 | } |
88 | | |
89 | | void *prio_queue_peek(struct prio_queue *queue) |
90 | 0 | { |
91 | 0 | if (!queue->nr) |
92 | 0 | return NULL; |
93 | 0 | if (!queue->compare) |
94 | 0 | return queue->array[queue->nr - 1].data; |
95 | 0 | return queue->array[0].data; |
96 | 0 | } |