← Back to branch summary

~ubuntu-branches/ubuntu/trusty/systemd/trusty

« back to all changes in this revision

Viewing changes to src/shared/prioq.c

Tags: upstream-202
Import upstream version 202

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
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 > q->n_items)
 
221
                        return NULL;
 
222
 
 
223
                i = q->items + *idx;
 
224
                if (i->data != data)
 
225
                        return NULL;
 
226
 
 
227
                return i;
 
228
        } else {
 
229
                for (i = q->items; i < q->items + q->n_items; i++)
 
230
                        if (i->data == data)
 
231
                                return i;
 
232
                return NULL;
 
233
        }
 
234
}
 
235
 
 
236
int prioq_remove(Prioq *q, void *data, unsigned *idx) {
 
237
        struct prioq_item *i;
 
238
 
 
239
        if (!q)
 
240
                return 0;
 
241
 
 
242
        i = find_item(q, data, idx);
 
243
        if (!i)
 
244
                return 0;
 
245
 
 
246
        remove_item(q, i);
 
247
        return 1;
 
248
}
 
249
 
 
250
int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
 
251
        struct prioq_item *i;
 
252
        unsigned k;
 
253
 
 
254
        assert(q);
 
255
 
 
256
        i = find_item(q, data, idx);
 
257
        if (!i)
 
258
                return 0;
 
259
 
 
260
        k = i - q->items;
 
261
        k = shuffle_down(q, k);
 
262
        shuffle_up(q, k);
 
263
        return 1;
 
264
}
 
265
 
 
266
void *prioq_peek(Prioq *q) {
 
267
 
 
268
        if (!q)
 
269
                return NULL;
 
270
 
 
271
        if (q->n_items <= 0)
 
272
                return NULL;
 
273
 
 
274
        return q->items[0].data;
 
275
}
 
276
 
 
277
void *prioq_pop(Prioq *q) {
 
278
        void *data;
 
279
 
 
280
        if (!q)
 
281
                return NULL;
 
282
 
 
283
        if (q->n_items <= 0)
 
284
                return NULL;
 
285
 
 
286
        data = q->items[0].data;
 
287
        remove_item(q, q->items);
 
288
        return data;
 
289
}
 
290
 
 
291
unsigned prioq_size(Prioq *q) {
 
292
 
 
293
        if (!q)
 
294
                return 0;
 
295
 
 
296
        return q->n_items;
 
297
 
 
298
}
 
299
bool prioq_isempty(Prioq *q) {
 
300
 
 
301
        if (!q)
 
302
                return true;
 
303
 
 
304
        return q->n_items <= 0;
 
305
}