]>
Commit | Line | Data |
---|---|---|
30bdd695 LP |
1 | /*** |
2 | This file is part of systemd. | |
3 | ||
4 | Copyright 2013 Lennart Poettering | |
5 | ||
6 | systemd is free software; you can redistribute it and/or modify it | |
7 | under the terms of the GNU Lesser General Public License as published by | |
8 | the Free Software Foundation; either version 2.1 of the License, or | |
9 | (at your option) any later version. | |
10 | ||
11 | systemd is distributed in the hope that it will be useful, but | |
12 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Lesser General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU Lesser General Public License | |
17 | along with systemd; If not, see <http://www.gnu.org/licenses/>. | |
18 | ***/ | |
19 | ||
f36f8f78 DH |
20 | /* |
21 | * Priority Queue | |
22 | * The prioq object implements a priority queue. That is, it orders objects by | |
23 | * their priority and allows O(1) access to the object with the highest | |
24 | * priority. Insertion and removal are Θ(log n). Optionally, the caller can | |
25 | * provide a pointer to an index which will be kept up-to-date by the prioq. | |
26 | * | |
27 | * The underlying algorithm used in this implementation is a Heap. | |
28 | */ | |
29 | ||
11c3a366 TA |
30 | #include <errno.h> |
31 | #include <stdlib.h> | |
32 | ||
b5efdb8a | 33 | #include "alloc-util.h" |
11c3a366 | 34 | #include "hashmap.h" |
93cc7779 | 35 | #include "prioq.h" |
30bdd695 LP |
36 | |
37 | struct prioq_item { | |
38 | void *data; | |
39 | unsigned *idx; | |
40 | }; | |
41 | ||
42 | struct Prioq { | |
43 | compare_func_t compare_func; | |
44 | unsigned n_items, n_allocated; | |
45 | ||
46 | struct prioq_item *items; | |
47 | }; | |
48 | ||
49 | Prioq *prioq_new(compare_func_t compare_func) { | |
50 | Prioq *q; | |
51 | ||
52 | q = new0(Prioq, 1); | |
53 | if (!q) | |
54 | return q; | |
55 | ||
56 | q->compare_func = compare_func; | |
57 | return q; | |
58 | } | |
59 | ||
cab5b059 | 60 | Prioq* prioq_free(Prioq *q) { |
30bdd695 | 61 | if (!q) |
cab5b059 | 62 | return NULL; |
30bdd695 LP |
63 | |
64 | free(q->items); | |
6b430fdb | 65 | return mfree(q); |
30bdd695 LP |
66 | } |
67 | ||
e3017af9 LP |
68 | int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) { |
69 | assert(q); | |
70 | ||
71 | if (*q) | |
72 | return 0; | |
73 | ||
74 | *q = prioq_new(compare_func); | |
75 | if (!*q) | |
76 | return -ENOMEM; | |
77 | ||
78 | return 0; | |
79 | } | |
80 | ||
30bdd695 LP |
81 | static void swap(Prioq *q, unsigned j, unsigned k) { |
82 | void *saved_data; | |
83 | unsigned *saved_idx; | |
84 | ||
85 | assert(q); | |
86 | assert(j < q->n_items); | |
87 | assert(k < q->n_items); | |
88 | ||
89 | assert(!q->items[j].idx || *(q->items[j].idx) == j); | |
90 | assert(!q->items[k].idx || *(q->items[k].idx) == k); | |
91 | ||
92 | saved_data = q->items[j].data; | |
93 | saved_idx = q->items[j].idx; | |
94 | q->items[j].data = q->items[k].data; | |
95 | q->items[j].idx = q->items[k].idx; | |
96 | q->items[k].data = saved_data; | |
97 | q->items[k].idx = saved_idx; | |
98 | ||
99 | if (q->items[j].idx) | |
100 | *q->items[j].idx = j; | |
101 | ||
102 | if (q->items[k].idx) | |
103 | *q->items[k].idx = k; | |
104 | } | |
105 | ||
106 | static unsigned shuffle_up(Prioq *q, unsigned idx) { | |
107 | assert(q); | |
108 | ||
109 | while (idx > 0) { | |
110 | unsigned k; | |
111 | ||
112 | k = (idx-1)/2; | |
113 | ||
8a9d23e4 | 114 | if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0) |
30bdd695 LP |
115 | break; |
116 | ||
117 | swap(q, idx, k); | |
118 | idx = k; | |
119 | } | |
120 | ||
121 | return idx; | |
122 | } | |
123 | ||
124 | static unsigned shuffle_down(Prioq *q, unsigned idx) { | |
125 | assert(q); | |
126 | ||
127 | for (;;) { | |
128 | unsigned j, k, s; | |
129 | ||
130 | k = (idx+1)*2; /* right child */ | |
131 | j = k-1; /* left child */ | |
132 | ||
133 | if (j >= q->n_items) | |
134 | break; | |
135 | ||
136 | if (q->compare_func(q->items[j].data, q->items[idx].data) < 0) | |
137 | ||
138 | /* So our left child is smaller than we are, let's | |
139 | * remember this fact */ | |
140 | s = j; | |
141 | else | |
142 | s = idx; | |
143 | ||
144 | if (k < q->n_items && | |
145 | q->compare_func(q->items[k].data, q->items[s].data) < 0) | |
146 | ||
147 | /* So our right child is smaller than we are, let's | |
148 | * remember this fact */ | |
149 | s = k; | |
150 | ||
151 | /* s now points to the smallest of the three items */ | |
152 | ||
153 | if (s == idx) | |
154 | /* No swap necessary, we're done */ | |
155 | break; | |
156 | ||
157 | swap(q, idx, s); | |
158 | idx = s; | |
159 | } | |
160 | ||
161 | return idx; | |
162 | } | |
163 | ||
164 | int prioq_put(Prioq *q, void *data, unsigned *idx) { | |
165 | struct prioq_item *i; | |
166 | unsigned k; | |
167 | ||
168 | assert(q); | |
169 | ||
170 | if (q->n_items >= q->n_allocated) { | |
171 | unsigned n; | |
172 | struct prioq_item *j; | |
173 | ||
9607d947 | 174 | n = MAX((q->n_items+1) * 2, 16u); |
30bdd695 LP |
175 | j = realloc(q->items, sizeof(struct prioq_item) * n); |
176 | if (!j) | |
177 | return -ENOMEM; | |
178 | ||
179 | q->items = j; | |
180 | q->n_allocated = n; | |
181 | } | |
182 | ||
183 | k = q->n_items++; | |
184 | i = q->items + k; | |
185 | i->data = data; | |
186 | i->idx = idx; | |
187 | ||
188 | if (idx) | |
189 | *idx = k; | |
190 | ||
191 | shuffle_up(q, k); | |
192 | ||
193 | return 0; | |
194 | } | |
195 | ||
196 | static void remove_item(Prioq *q, struct prioq_item *i) { | |
197 | struct prioq_item *l; | |
198 | ||
199 | assert(q); | |
200 | assert(i); | |
201 | ||
202 | l = q->items + q->n_items - 1; | |
203 | ||
204 | if (i == l) | |
205 | /* Last entry, let's just remove it */ | |
206 | q->n_items--; | |
207 | else { | |
208 | unsigned k; | |
209 | ||
210 | /* Not last entry, let's replace the last entry with | |
211 | * this one, and reshuffle */ | |
212 | ||
213 | k = i - q->items; | |
214 | ||
215 | i->data = l->data; | |
216 | i->idx = l->idx; | |
217 | if (i->idx) | |
218 | *i->idx = k; | |
219 | q->n_items--; | |
220 | ||
221 | k = shuffle_down(q, k); | |
222 | shuffle_up(q, k); | |
223 | } | |
224 | } | |
225 | ||
44a6b1b6 | 226 | _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) { |
30bdd695 LP |
227 | struct prioq_item *i; |
228 | ||
229 | assert(q); | |
230 | ||
231 | if (idx) { | |
c2ba3ad6 LP |
232 | if (*idx == PRIOQ_IDX_NULL || |
233 | *idx > q->n_items) | |
e3017af9 LP |
234 | return NULL; |
235 | ||
30bdd695 | 236 | i = q->items + *idx; |
e3017af9 LP |
237 | if (i->data != data) |
238 | return NULL; | |
30bdd695 LP |
239 | |
240 | return i; | |
241 | } else { | |
242 | for (i = q->items; i < q->items + q->n_items; i++) | |
243 | if (i->data == data) | |
244 | return i; | |
245 | return NULL; | |
246 | } | |
247 | } | |
248 | ||
249 | int prioq_remove(Prioq *q, void *data, unsigned *idx) { | |
250 | struct prioq_item *i; | |
251 | ||
a3de5ae1 LP |
252 | if (!q) |
253 | return 0; | |
30bdd695 LP |
254 | |
255 | i = find_item(q, data, idx); | |
256 | if (!i) | |
257 | return 0; | |
258 | ||
259 | remove_item(q, i); | |
260 | return 1; | |
261 | } | |
262 | ||
263 | int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) { | |
264 | struct prioq_item *i; | |
265 | unsigned k; | |
266 | ||
267 | assert(q); | |
268 | ||
269 | i = find_item(q, data, idx); | |
270 | if (!i) | |
271 | return 0; | |
272 | ||
273 | k = i - q->items; | |
274 | k = shuffle_down(q, k); | |
275 | shuffle_up(q, k); | |
276 | return 1; | |
277 | } | |
278 | ||
279 | void *prioq_peek(Prioq *q) { | |
a3de5ae1 LP |
280 | |
281 | if (!q) | |
282 | return NULL; | |
30bdd695 LP |
283 | |
284 | if (q->n_items <= 0) | |
285 | return NULL; | |
286 | ||
287 | return q->items[0].data; | |
288 | } | |
289 | ||
290 | void *prioq_pop(Prioq *q) { | |
291 | void *data; | |
292 | ||
a3de5ae1 LP |
293 | if (!q) |
294 | return NULL; | |
30bdd695 LP |
295 | |
296 | if (q->n_items <= 0) | |
297 | return NULL; | |
298 | ||
299 | data = q->items[0].data; | |
300 | remove_item(q, q->items); | |
301 | return data; | |
302 | } | |
303 | ||
304 | unsigned prioq_size(Prioq *q) { | |
a3de5ae1 LP |
305 | |
306 | if (!q) | |
307 | return 0; | |
30bdd695 LP |
308 | |
309 | return q->n_items; | |
30bdd695 | 310 | } |
718db961 | 311 | |
30bdd695 | 312 | bool prioq_isempty(Prioq *q) { |
a3de5ae1 LP |
313 | |
314 | if (!q) | |
315 | return true; | |
30bdd695 LP |
316 | |
317 | return q->n_items <= 0; | |
318 | } |