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 197 : Prioq *prioq_new(compare_func_t compare_func) {
33 : Prioq *q;
34 :
35 197 : q = new(Prioq, 1);
36 197 : if (!q)
37 0 : return q;
38 :
39 197 : *q = (Prioq) {
40 : .compare_func = compare_func,
41 : };
42 :
43 197 : return q;
44 : }
45 :
46 569 : Prioq* prioq_free(Prioq *q) {
47 569 : if (!q)
48 375 : return NULL;
49 :
50 194 : free(q->items);
51 194 : return mfree(q);
52 : }
53 :
54 2121 : int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
55 2121 : assert(q);
56 :
57 2121 : if (*q)
58 1926 : return 0;
59 :
60 195 : *q = prioq_new(compare_func);
61 195 : if (!*q)
62 0 : return -ENOMEM;
63 :
64 195 : return 0;
65 : }
66 :
67 2543115 : static void swap(Prioq *q, unsigned j, unsigned k) {
68 2543115 : assert(q);
69 2543115 : assert(j < q->n_items);
70 2543115 : assert(k < q->n_items);
71 :
72 2543115 : assert(!q->items[j].idx || *(q->items[j].idx) == j);
73 2543115 : assert(!q->items[k].idx || *(q->items[k].idx) == k);
74 :
75 2543115 : SWAP_TWO(q->items[j].data, q->items[k].data);
76 2543115 : SWAP_TWO(q->items[j].idx, q->items[k].idx);
77 :
78 2543115 : if (q->items[j].idx)
79 2499397 : *q->items[j].idx = j;
80 :
81 2543115 : if (q->items[k].idx)
82 2499397 : *q->items[k].idx = k;
83 2543115 : }
84 :
85 481583 : static unsigned shuffle_up(Prioq *q, unsigned idx) {
86 481583 : assert(q);
87 481583 : assert(idx < q->n_items);
88 :
89 524268 : while (idx > 0) {
90 : unsigned k;
91 :
92 454795 : k = (idx-1)/2;
93 :
94 454795 : if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
95 412110 : break;
96 :
97 42685 : swap(q, idx, k);
98 42685 : idx = k;
99 : }
100 :
101 481583 : return idx;
102 : }
103 :
104 420093 : static unsigned shuffle_down(Prioq *q, unsigned idx) {
105 420093 : assert(q);
106 :
107 2500430 : for (;;) {
108 : unsigned j, k, s;
109 :
110 2920523 : k = (idx+1)*2; /* right child */
111 2920523 : j = k-1; /* left child */
112 :
113 2920523 : if (j >= q->n_items)
114 355026 : break;
115 :
116 2565497 : 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 2289395 : s = j;
121 : else
122 276102 : s = idx;
123 :
124 5110072 : if (k < q->n_items &&
125 2544575 : 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 1181095 : s = k;
130 :
131 : /* s now points to the smallest of the three items */
132 :
133 2565497 : if (s == idx)
134 : /* No swap necessary, we're done */
135 65067 : break;
136 :
137 2500430 : swap(q, idx, s);
138 2500430 : idx = s;
139 : }
140 :
141 420093 : return idx;
142 : }
143 :
144 61490 : int prioq_put(Prioq *q, void *data, unsigned *idx) {
145 : struct prioq_item *i;
146 : unsigned k;
147 :
148 61490 : assert(q);
149 :
150 61490 : if (q->n_items >= q->n_allocated) {
151 : unsigned n;
152 : struct prioq_item *j;
153 :
154 242 : n = MAX((q->n_items+1) * 2, 16u);
155 242 : j = reallocarray(q->items, n, sizeof(struct prioq_item));
156 242 : if (!j)
157 0 : return -ENOMEM;
158 :
159 242 : q->items = j;
160 242 : q->n_allocated = n;
161 : }
162 :
163 61490 : k = q->n_items++;
164 61490 : i = q->items + k;
165 61490 : i->data = data;
166 61490 : i->idx = idx;
167 :
168 61490 : if (idx)
169 57394 : *idx = k;
170 :
171 61490 : shuffle_up(q, k);
172 :
173 61490 : return 0;
174 : }
175 :
176 61490 : static void remove_item(Prioq *q, struct prioq_item *i) {
177 : struct prioq_item *l;
178 :
179 61490 : assert(q);
180 61490 : assert(i);
181 :
182 61490 : l = q->items + q->n_items - 1;
183 :
184 61490 : if (i == l)
185 : /* Last entry, let's just remove it */
186 17026 : 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 44464 : k = i - q->items;
194 :
195 44464 : i->data = l->data;
196 44464 : i->idx = l->idx;
197 44464 : if (i->idx)
198 40369 : *i->idx = k;
199 44464 : q->n_items--;
200 :
201 44464 : k = shuffle_down(q, k);
202 44464 : shuffle_up(q, k);
203 : }
204 61490 : }
205 :
206 442238 : _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
207 : struct prioq_item *i;
208 :
209 442238 : assert(q);
210 :
211 442238 : if (q->n_items <= 0)
212 2 : return NULL;
213 :
214 442236 : if (idx) {
215 438141 : if (*idx == PRIOQ_IDX_NULL ||
216 438141 : *idx >= q->n_items)
217 4097 : return NULL;
218 :
219 434044 : i = q->items + *idx;
220 434044 : if (i->data != data)
221 4094 : return NULL;
222 :
223 429950 : return i;
224 : } else {
225 8390655 : for (i = q->items; i < q->items + q->n_items; i++)
226 8386560 : if (i->data == data)
227 0 : return i;
228 4095 : return NULL;
229 : }
230 : }
231 :
232 66609 : int prioq_remove(Prioq *q, void *data, unsigned *idx) {
233 : struct prioq_item *i;
234 :
235 66609 : if (!q)
236 0 : return 0;
237 :
238 66609 : i = find_item(q, data, idx);
239 66609 : if (!i)
240 12288 : return 0;
241 :
242 54321 : remove_item(q, i);
243 54321 : return 1;
244 : }
245 :
246 375629 : int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
247 : struct prioq_item *i;
248 : unsigned k;
249 :
250 375629 : assert(q);
251 :
252 375629 : i = find_item(q, data, idx);
253 375629 : if (!i)
254 0 : return 0;
255 :
256 375629 : k = i - q->items;
257 375629 : k = shuffle_down(q, k);
258 375629 : shuffle_up(q, k);
259 375629 : return 1;
260 : }
261 :
262 843828 : void *prioq_peek_by_index(Prioq *q, unsigned idx) {
263 843828 : if (!q)
264 306005 : return NULL;
265 :
266 537823 : if (idx >= q->n_items)
267 16648 : return NULL;
268 :
269 521175 : return q->items[idx].data;
270 : }
271 :
272 7169 : void *prioq_pop(Prioq *q) {
273 : void *data;
274 :
275 7169 : if (!q)
276 0 : return NULL;
277 :
278 7169 : if (q->n_items <= 0)
279 0 : return NULL;
280 :
281 7169 : data = q->items[0].data;
282 7169 : remove_item(q, q->items);
283 7169 : return data;
284 : }
285 :
286 11264 : unsigned prioq_size(Prioq *q) {
287 :
288 11264 : if (!q)
289 0 : return 0;
290 :
291 11264 : return q->n_items;
292 : }
293 :
294 78 : bool prioq_isempty(Prioq *q) {
295 :
296 78 : if (!q)
297 0 : return true;
298 :
299 78 : return q->n_items <= 0;
300 : }
|
