Branch data Line data Source code
1 : : /* SPDX-License-Identifier: LGPL-2.1+ */
2 : :
3 : : /*
4 : : * Priority Queue
5 : : * The prioq object implements a priority queue. That is, it orders objects by
6 : : * their priority and allows O(1) access to the object with the highest
7 : : * priority. Insertion and removal are Θ(log n). Optionally, the caller can
8 : : * provide a pointer to an index which will be kept up-to-date by the prioq.
9 : : *
10 : : * The underlying algorithm used in this implementation is a Heap.
11 : : */
12 : :
13 : : #include <errno.h>
14 : : #include <stdlib.h>
15 : :
16 : : #include "alloc-util.h"
17 : : #include "hashmap.h"
18 : : #include "prioq.h"
19 : :
20 : : struct prioq_item {
21 : : void *data;
22 : : unsigned *idx;
23 : : };
24 : :
25 : : struct Prioq {
26 : : compare_func_t compare_func;
27 : : unsigned n_items, n_allocated;
28 : :
29 : : struct prioq_item *items;
30 : : };
31 : :
32 : 788 : Prioq *prioq_new(compare_func_t compare_func) {
33 : : Prioq *q;
34 : :
35 : 788 : q = new(Prioq, 1);
36 [ - + ]: 788 : if (!q)
37 : 0 : return q;
38 : :
39 : 788 : *q = (Prioq) {
40 : : .compare_func = compare_func,
41 : : };
42 : :
43 : 788 : return q;
44 : : }
45 : :
46 : 2276 : Prioq* prioq_free(Prioq *q) {
47 [ + + ]: 2276 : if (!q)
48 : 1500 : return NULL;
49 : :
50 : 776 : free(q->items);
51 : 776 : return mfree(q);
52 : : }
53 : :
54 : 8488 : int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
55 [ - + ]: 8488 : assert(q);
56 : :
57 [ + + ]: 8488 : if (*q)
58 : 7708 : return 0;
59 : :
60 : 780 : *q = prioq_new(compare_func);
61 [ - + ]: 780 : if (!*q)
62 : 0 : return -ENOMEM;
63 : :
64 : 780 : return 0;
65 : : }
66 : :
67 : 10007619 : static void swap(Prioq *q, unsigned j, unsigned k) {
68 [ - + ]: 10007619 : assert(q);
69 [ - + ]: 10007619 : assert(j < q->n_items);
70 [ - + ]: 10007619 : assert(k < q->n_items);
71 : :
72 [ + + - + ]: 10007619 : assert(!q->items[j].idx || *(q->items[j].idx) == j);
73 [ + + - + ]: 10007619 : assert(!q->items[k].idx || *(q->items[k].idx) == k);
74 : :
75 : 10007619 : SWAP_TWO(q->items[j].data, q->items[k].data);
76 : 10007619 : SWAP_TWO(q->items[j].idx, q->items[k].idx);
77 : :
78 [ + + ]: 10007619 : if (q->items[j].idx)
79 : 9832747 : *q->items[j].idx = j;
80 : :
81 [ + + ]: 10007619 : if (q->items[k].idx)
82 : 9832747 : *q->items[k].idx = k;
83 : 10007619 : }
84 : :
85 : 1889231 : static unsigned shuffle_up(Prioq *q, unsigned idx) {
86 [ - + ]: 1889231 : assert(q);
87 [ - + ]: 1889231 : assert(idx < q->n_items);
88 : :
89 [ + + ]: 2059312 : while (idx > 0) {
90 : : unsigned k;
91 : :
92 : 1782065 : k = (idx-1)/2;
93 : :
94 [ + + ]: 1782065 : if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
95 : 1611984 : break;
96 : :
97 : 170081 : swap(q, idx, k);
98 : 170081 : idx = k;
99 : : }
100 : :
101 : 1889231 : return idx;
102 : : }
103 : :
104 : 1643478 : static unsigned shuffle_down(Prioq *q, unsigned idx) {
105 [ - + ]: 1643478 : assert(q);
106 : :
107 : 9837538 : for (;;) {
108 : : unsigned j, k, s;
109 : :
110 : 11481016 : k = (idx+1)*2; /* right child */
111 : 11481016 : j = k-1; /* left child */
112 : :
113 [ + + ]: 11481016 : if (j >= q->n_items)
114 : 1401357 : break;
115 : :
116 [ + + ]: 10079659 : if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
117 : :
118 : : /* So our left child is smaller than we are, let's
119 : : * remember this fact */
120 : 9071185 : s = j;
121 : : else
122 : 1008474 : s = idx;
123 : :
124 [ + + + + ]: 20076448 : if (k < q->n_items &&
125 : 9996789 : q->compare_func(q->items[k].data, q->items[s].data) < 0)
126 : :
127 : : /* So our right child is smaller than we are, let's
128 : : * remember this fact */
129 : 4645827 : s = k;
130 : :
131 : : /* s now points to the smallest of the three items */
132 : :
133 [ + + ]: 10079659 : if (s == idx)
134 : : /* No swap necessary, we're done */
135 : 242121 : break;
136 : :
137 : 9837538 : swap(q, idx, s);
138 : 9837538 : idx = s;
139 : : }
140 : :
141 : 1643478 : return idx;
142 : : }
143 : :
144 : 245753 : int prioq_put(Prioq *q, void *data, unsigned *idx) {
145 : : struct prioq_item *i;
146 : : unsigned k;
147 : :
148 [ - + ]: 245753 : assert(q);
149 : :
150 [ + + ]: 245753 : if (q->n_items >= q->n_allocated) {
151 : : unsigned n;
152 : : struct prioq_item *j;
153 : :
154 : 968 : n = MAX((q->n_items+1) * 2, 16u);
155 : 968 : j = reallocarray(q->items, n, sizeof(struct prioq_item));
156 [ - + ]: 968 : if (!j)
157 : 0 : return -ENOMEM;
158 : :
159 : 968 : q->items = j;
160 : 968 : q->n_allocated = n;
161 : : }
162 : :
163 : 245753 : k = q->n_items++;
164 : 245753 : i = q->items + k;
165 : 245753 : i->data = data;
166 : 245753 : i->idx = idx;
167 : :
168 [ + + ]: 245753 : if (idx)
169 : 229369 : *idx = k;
170 : :
171 : 245753 : shuffle_up(q, k);
172 : :
173 : 245753 : return 0;
174 : : }
175 : :
176 : 245753 : static void remove_item(Prioq *q, struct prioq_item *i) {
177 : : struct prioq_item *l;
178 : :
179 [ - + ]: 245753 : assert(q);
180 [ - + ]: 245753 : assert(i);
181 : :
182 : 245753 : l = q->items + q->n_items - 1;
183 : :
184 [ + + ]: 245753 : if (i == l)
185 : : /* Last entry, let's just remove it */
186 : 67989 : q->n_items--;
187 : : else {
188 : : unsigned k;
189 : :
190 : : /* Not last entry, let's replace the last entry with
191 : : * this one, and reshuffle */
192 : :
193 : 177764 : k = i - q->items;
194 : :
195 : 177764 : i->data = l->data;
196 : 177764 : i->idx = l->idx;
197 [ + + ]: 177764 : if (i->idx)
198 : 161384 : *i->idx = k;
199 : 177764 : q->n_items--;
200 : :
201 : 177764 : k = shuffle_down(q, k);
202 : 177764 : shuffle_up(q, k);
203 : : }
204 : 245753 : }
205 : :
206 : 1731943 : _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
207 : : struct prioq_item *i;
208 : :
209 [ - + ]: 1731943 : assert(q);
210 : :
211 [ + + ]: 1731943 : if (q->n_items <= 0)
212 : 8 : return NULL;
213 : :
214 [ + + ]: 1731935 : if (idx) {
215 [ + - ]: 1715555 : if (*idx == PRIOQ_IDX_NULL ||
216 [ + + ]: 1715555 : *idx >= q->n_items)
217 : 16384 : return NULL;
218 : :
219 : 1699171 : i = q->items + *idx;
220 [ + + ]: 1699171 : if (i->data != data)
221 : 16380 : return NULL;
222 : :
223 : 1682791 : return i;
224 : : } else {
225 [ + + ]: 33562620 : for (i = q->items; i < q->items + q->n_items; i++)
226 [ - + ]: 33546240 : if (i->data == data)
227 : 0 : return i;
228 : 16380 : return NULL;
229 : : }
230 : : }
231 : :
232 : 266229 : int prioq_remove(Prioq *q, void *data, unsigned *idx) {
233 : : struct prioq_item *i;
234 : :
235 [ - + ]: 266229 : if (!q)
236 : 0 : return 0;
237 : :
238 : 266229 : i = find_item(q, data, idx);
239 [ + + ]: 266229 : if (!i)
240 : 49152 : return 0;
241 : :
242 : 217077 : remove_item(q, i);
243 : 217077 : return 1;
244 : : }
245 : :
246 : 1465714 : int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
247 : : struct prioq_item *i;
248 : : unsigned k;
249 : :
250 [ - + ]: 1465714 : assert(q);
251 : :
252 : 1465714 : i = find_item(q, data, idx);
253 [ - + ]: 1465714 : if (!i)
254 : 0 : return 0;
255 : :
256 : 1465714 : k = i - q->items;
257 : 1465714 : k = shuffle_down(q, k);
258 : 1465714 : shuffle_up(q, k);
259 : 1465714 : return 1;
260 : : }
261 : :
262 : 3333019 : void *prioq_peek_by_index(Prioq *q, unsigned idx) {
263 [ + + ]: 3333019 : if (!q)
264 : 1221378 : return NULL;
265 : :
266 [ + + ]: 2111641 : if (idx >= q->n_items)
267 : 66557 : return NULL;
268 : :
269 : 2045084 : return q->items[idx].data;
270 : : }
271 : :
272 : 28676 : void *prioq_pop(Prioq *q) {
273 : : void *data;
274 : :
275 [ - + ]: 28676 : if (!q)
276 : 0 : return NULL;
277 : :
278 [ - + ]: 28676 : if (q->n_items <= 0)
279 : 0 : return NULL;
280 : :
281 : 28676 : data = q->items[0].data;
282 : 28676 : remove_item(q, q->items);
283 : 28676 : return data;
284 : : }
285 : :
286 : 45056 : unsigned prioq_size(Prioq *q) {
287 : :
288 [ - + ]: 45056 : if (!q)
289 : 0 : return 0;
290 : :
291 : 45056 : return q->n_items;
292 : : }
293 : :
294 : 312 : bool prioq_isempty(Prioq *q) {
295 : :
296 [ - + ]: 312 : if (!q)
297 : 0 : return true;
298 : :
299 : 312 : return q->n_items <= 0;
300 : : }
|
