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