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