chiark / gitweb /
logind: Save the user’s state when a session enters SESSION_ACTIVE
[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 Prioq* prioq_free(Prioq *q) {
49         if (!q)
50                 return NULL;
51
52         free(q->items);
53         free(q);
54
55         return NULL;
56 }
57
58 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
59         assert(q);
60
61         if (*q)
62                 return 0;
63
64         *q = prioq_new(compare_func);
65         if (!*q)
66                 return -ENOMEM;
67
68         return 0;
69 }
70
71 static void swap(Prioq *q, unsigned j, unsigned k) {
72         void *saved_data;
73         unsigned *saved_idx;
74
75         assert(q);
76         assert(j < q->n_items);
77         assert(k < q->n_items);
78
79         assert(!q->items[j].idx || *(q->items[j].idx) == j);
80         assert(!q->items[k].idx || *(q->items[k].idx) == k);
81
82         saved_data = q->items[j].data;
83         saved_idx = q->items[j].idx;
84         q->items[j].data = q->items[k].data;
85         q->items[j].idx = q->items[k].idx;
86         q->items[k].data = saved_data;
87         q->items[k].idx = saved_idx;
88
89         if (q->items[j].idx)
90                 *q->items[j].idx = j;
91
92         if (q->items[k].idx)
93                 *q->items[k].idx = k;
94 }
95
96 static unsigned shuffle_up(Prioq *q, unsigned idx) {
97         assert(q);
98
99         while (idx > 0) {
100                 unsigned k;
101
102                 k = (idx-1)/2;
103
104                 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
105                         break;
106
107                 swap(q, idx, k);
108                 idx = k;
109         }
110
111         return idx;
112 }
113
114 static unsigned shuffle_down(Prioq *q, unsigned idx) {
115         assert(q);
116
117         for (;;) {
118                 unsigned j, k, s;
119
120                 k = (idx+1)*2; /* right child */
121                 j = k-1;       /* left child */
122
123                 if (j >= q->n_items)
124                         break;
125
126                 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
127
128                         /* So our left child is smaller than we are, let's
129                          * remember this fact */
130                         s = j;
131                 else
132                         s = idx;
133
134                 if (k < q->n_items &&
135                     q->compare_func(q->items[k].data, q->items[s].data) < 0)
136
137                         /* So our right child is smaller than we are, let's
138                          * remember this fact */
139                         s = k;
140
141                 /* s now points to the smallest of the three items */
142
143                 if (s == idx)
144                         /* No swap necessary, we're done */
145                         break;
146
147                 swap(q, idx, s);
148                 idx = s;
149         }
150
151         return idx;
152 }
153
154 int prioq_put(Prioq *q, void *data, unsigned *idx) {
155         struct prioq_item *i;
156         unsigned k;
157
158         assert(q);
159
160         if (q->n_items >= q->n_allocated) {
161                 unsigned n;
162                 struct prioq_item *j;
163
164                 n = MAX((q->n_items+1) * 2, 16u);
165                 j = realloc(q->items, sizeof(struct prioq_item) * n);
166                 if (!j)
167                         return -ENOMEM;
168
169                 q->items = j;
170                 q->n_allocated = n;
171         }
172
173         k = q->n_items++;
174         i = q->items + k;
175         i->data = data;
176         i->idx = idx;
177
178         if (idx)
179                 *idx = k;
180
181         shuffle_up(q, k);
182
183         return 0;
184 }
185
186 static void remove_item(Prioq *q, struct prioq_item *i) {
187         struct prioq_item *l;
188
189         assert(q);
190         assert(i);
191
192         l = q->items + q->n_items - 1;
193
194         if (i == l)
195                 /* Last entry, let's just remove it */
196                 q->n_items--;
197         else {
198                 unsigned k;
199
200                 /* Not last entry, let's replace the last entry with
201                  * this one, and reshuffle */
202
203                 k = i - q->items;
204
205                 i->data = l->data;
206                 i->idx = l->idx;
207                 if (i->idx)
208                         *i->idx = k;
209                 q->n_items--;
210
211                 k = shuffle_down(q, k);
212                 shuffle_up(q, k);
213         }
214 }
215
216 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
217         struct prioq_item *i;
218
219         assert(q);
220
221         if (idx) {
222                 if (*idx == PRIOQ_IDX_NULL ||
223                     *idx > q->n_items)
224                         return NULL;
225
226                 i = q->items + *idx;
227                 if (i->data != data)
228                         return NULL;
229
230                 return i;
231         } else {
232                 for (i = q->items; i < q->items + q->n_items; i++)
233                         if (i->data == data)
234                                 return i;
235                 return NULL;
236         }
237 }
238
239 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
240         struct prioq_item *i;
241
242         if (!q)
243                 return 0;
244
245         i = find_item(q, data, idx);
246         if (!i)
247                 return 0;
248
249         remove_item(q, i);
250         return 1;
251 }
252
253 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
254         struct prioq_item *i;
255         unsigned k;
256
257         assert(q);
258
259         i = find_item(q, data, idx);
260         if (!i)
261                 return 0;
262
263         k = i - q->items;
264         k = shuffle_down(q, k);
265         shuffle_up(q, k);
266         return 1;
267 }
268
269 void *prioq_peek(Prioq *q) {
270
271         if (!q)
272                 return NULL;
273
274         if (q->n_items <= 0)
275                 return NULL;
276
277         return q->items[0].data;
278 }
279
280 void *prioq_pop(Prioq *q) {
281         void *data;
282
283         if (!q)
284                 return NULL;
285
286         if (q->n_items <= 0)
287                 return NULL;
288
289         data = q->items[0].data;
290         remove_item(q, q->items);
291         return data;
292 }
293
294 unsigned prioq_size(Prioq *q) {
295
296         if (!q)
297                 return 0;
298
299         return q->n_items;
300 }
301
302 bool prioq_isempty(Prioq *q) {
303
304         if (!q)
305                 return true;
306
307         return q->n_items <= 0;
308 }