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