15263807472

/* SPDX-License-Identifier: LGPL-2.1-or-later */

/*
 * Priority Queue
 * The prioq object implements a priority queue. That is, it orders objects by
 * their priority and allows O(1) access to the object with the highest
 * priority. Insertion and removal are Θ(log n). Optionally, the caller can
 * provide a pointer to an index which will be kept up-to-date by the prioq.
 *
 * The underlying algorithm used in this implementation is a Heap.
 */

#include "alloc-util.h"
#include "prioq.h"

struct prioq_item {
        void *data;
        unsigned *idx;
};

struct Prioq {
        compare_func_t compare_func;
        unsigned n_items;
        struct prioq_item *items;
};

Prioq* prioq_new(compare_func_t compare_func) {
        Prioq *q;

        q = new(Prioq, 1);
        if (!q)
                return q;

        *q = (Prioq) {
                .compare_func = compare_func,
        };

        return q;
}

Prioq* prioq_free(Prioq *q) {
        if (!q)
                return NULL;

        /* Invalidate the index fields of any remaining objects */
        FOREACH_ARRAY(item, q->items, q->n_items)
                if (item->idx)
                        *(item->idx) = PRIOQ_IDX_NULL;

        free(q->items);
        return mfree(q);
}

int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
        assert(q);

        if (*q) {
                assert((*q)->compare_func == compare_func);
                return 0;
        }

        *q = prioq_new(compare_func);
        if (!*q)
                return -ENOMEM;

        return 0;
}

static void swap(Prioq *q, unsigned j, unsigned k) {
        assert(q);
        assert(j < q->n_items);
        assert(k < q->n_items);

        assert(!q->items[j].idx || *(q->items[j].idx) == j);
        assert(!q->items[k].idx || *(q->items[k].idx) == k);

        SWAP_TWO(q->items[j].data, q->items[k].data);
        SWAP_TWO(q->items[j].idx, q->items[k].idx);

        if (q->items[j].idx)
                *q->items[j].idx = j;

        if (q->items[k].idx)
                *q->items[k].idx = k;
}

static unsigned shuffle_up(Prioq *q, unsigned idx) {
        assert(q);
        assert(idx < q->n_items);

        while (idx > 0) {
                unsigned k;

                k = (idx-1)/2;

                if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
                        break;

                swap(q, idx, k);
                idx = k;
        }

        return idx;
}

static unsigned shuffle_down(Prioq *q, unsigned idx) {
        assert(q);

        for (;;) {
                unsigned j, k, s;

                k = (idx+1)*2; /* right child */
                j = k-1;       /* left child */

                if (j >= q->n_items)
                        break;

                if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)

                        /* So our left child is smaller than we are, let's
                         * remember this fact */
                        s = j;
                else
                        s = idx;

                if (k < q->n_items &&
                    q->compare_func(q->items[k].data, q->items[s].data) < 0)

                        /* So our right child is smaller than we are, let's
                         * remember this fact */
                        s = k;

                /* s now points to the smallest of the three items */

                if (s == idx)
                        /* No swap necessary, we're done */
                        break;

                swap(q, idx, s);
                idx = s;
        }

        return idx;
}

int prioq_put(Prioq *q, void *data, unsigned *idx) {
        unsigned k;

        assert(q);

        if (!GREEDY_REALLOC(q->items, MAX(q->n_items + 1, 16u)))
                return -ENOMEM;

        k = q->n_items++;
        q->items[k] = (struct prioq_item) {
                .data = data,
                .idx = idx,
        };

        if (idx)
                *idx = k;

        shuffle_up(q, k);

        return 0;
}

int _prioq_ensure_put(Prioq **q, compare_func_t compare_func, void *data, unsigned *idx) {
        int r;

        r = prioq_ensure_allocated(q, compare_func);
        if (r < 0)
                return r;

        return prioq_put(*q, data, idx);
}

static void remove_item(Prioq *q, struct prioq_item *i) {
        struct prioq_item *l;

        assert(q);
        assert(i);

        /* Let's invalidate the index pointer stored in the user's object to indicate the item is now removed
         * from the priority queue */
        if (i->idx)
                *(i->idx) = PRIOQ_IDX_NULL;

        l = q->items + q->n_items - 1;

        if (i == l)
                /* Last entry, let's just remove it */
                q->n_items--;
        else {
                unsigned k;

                /* Not last entry, let's replace the last entry with
                 * this one, and reshuffle */

                assert(i >= q->items);
                k = i - q->items;

                i->data = l->data;
                i->idx = l->idx;
                if (i->idx)
                        *i->idx = k;
                q->n_items--;

                k = shuffle_down(q, k);
                shuffle_up(q, k);
        }
}

static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
        struct prioq_item *i;

        assert(q);

        if (q->n_items <= 0)
                return NULL;

        if (idx) {
                if (*idx == PRIOQ_IDX_NULL ||
                    *idx >= q->n_items)
                        return NULL;

                i = q->items + *idx;
                if (i->data != data)
                        return NULL;

                return i;
        } else {
                for (i = q->items; i < q->items + q->n_items; i++)
                        if (i->data == data)
                                return i;
                return NULL;
        }
}

int prioq_remove(Prioq *q, void *data, unsigned *idx) {
        struct prioq_item *i;

        if (!q)
                return 0;

        i = find_item(q, data, idx);
        if (!i)
                return 0;

        remove_item(q, i);
        return 1;
}

void prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
        struct prioq_item *i;
        unsigned k;

        assert(q);

        i = find_item(q, data, idx);
        if (!i)
                return;

        assert(i >= q->items);
        k = i - q->items;
        k = shuffle_down(q, k);
        shuffle_up(q, k);
}

void* prioq_peek_by_index(Prioq *q, unsigned idx) {
        if (!q)
                return NULL;

        if (idx >= q->n_items)
                return NULL;

        return q->items[idx].data;
}

void* prioq_pop(Prioq *q) {
        void *data;

        if (!q)
                return NULL;

        if (q->n_items <= 0)
                return NULL;

        data = q->items[0].data;
        remove_item(q, q->items);
        return data;
}

unsigned prioq_size(Prioq *q) {

        if (!q)
                return 0;

        return q->n_items;
}

bool prioq_isempty(Prioq *q) {

        if (!q)
                return true;

        return q->n_items <= 0;
}

1	/* SPDX-License-Identifier: LGPL-2.1-or-later */
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 "alloc-util.h"
14	#include "prioq.h"
15
16	struct prioq_item {
17	void *data;
18	unsigned *idx;
19	};
20
21	struct Prioq {
22	compare_func_t compare_func;
23	unsigned n_items;
24	struct prioq_item *items;
25	};
26
27	Prioq* prioq_new(compare_func_t compare_func) {	525,405✔
28	Prioq *q;	525,405✔
29
30	q = new(Prioq, 1);	525,405✔
31	if (!q)	525,405✔
32	return q;
33
34	*q = (Prioq) {	525,405✔
35	.compare_func = compare_func,
36	};
37
38	return q;	525,405✔
39	}
40
41	Prioq* prioq_free(Prioq *q) {	2,271,051✔
42	if (!q)	2,271,051✔
43	return NULL;
44
45	/* Invalidate the index fields of any remaining objects */
46	FOREACH_ARRAY(item, q->items, q->n_items)	521,851✔
UNCOV 47	if (item->idx)	×
UNCOV 48	*(item->idx) = PRIOQ_IDX_NULL;	×
49
50	free(q->items);	521,851✔
51	return mfree(q);	521,851✔
52	}
53
54	int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {	1,239,211✔
55	assert(q);	1,239,211✔
56
57	if (*q) {	1,239,211✔
58	assert((*q)->compare_func == compare_func);	716,739✔
59	return 0;
60	}
61
62	*q = prioq_new(compare_func);	522,472✔
63	if (!*q)	522,472✔
UNCOV 64	return -ENOMEM;	×
65
66	return 0;
67	}
68
69	static void swap(Prioq *q, unsigned j, unsigned k) {	10,427,903✔
70	assert(q);	10,427,903✔
71	assert(j < q->n_items);	10,427,903✔
72	assert(k < q->n_items);	10,427,903✔
73
74	assert(!q->items[j].idx \|\| *(q->items[j].idx) == j);	10,427,903✔
75	assert(!q->items[k].idx \|\| *(q->items[k].idx) == k);	10,427,903✔
76
77	SWAP_TWO(q->items[j].data, q->items[k].data);	10,427,903✔
78	SWAP_TWO(q->items[j].idx, q->items[k].idx);	10,427,903✔
79
80	if (q->items[j].idx)	10,427,903✔
81	*q->items[j].idx = j;	10,384,185✔
82
83	if (q->items[k].idx)	10,427,903✔
84	*q->items[k].idx = k;	10,384,185✔
85	}	10,427,903✔
86
87	static unsigned shuffle_up(Prioq *q, unsigned idx) {	16,238,600✔
88	assert(q);	16,238,600✔
89	assert(idx < q->n_items);	16,238,600✔
90
91	while (idx > 0) {	17,939,478✔
92	unsigned k;	10,069,609✔
93
94	k = (idx-1)/2;	10,069,609✔
95
96	if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)	10,069,609✔
97	break;
98
99	swap(q, idx, k);	1,700,878✔
100	idx = k;	1,700,878✔
101	}
102
103	return idx;	16,238,600✔
104	}
105
106	static unsigned shuffle_down(Prioq *q, unsigned idx) {	12,668,285✔
107	assert(q);	12,668,285✔
108
109	for (;;) {	8,727,025✔
110	unsigned j, k, s;	21,395,310✔
111
112	k = (idx+1)2; / right child */	21,395,310✔
113	j = k-1; /* left child */	21,395,310✔
114
115	if (j >= q->n_items)	21,395,310✔
116	break;
117
118	if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)	11,942,084✔
119
120	/* So our left child is smaller than we are, let's
121	* remember this fact */
122	s = j;
123	else
124	s = idx;	5,159,369✔
125
126	if (k < q->n_items &&	21,661,413✔
127	q->compare_func(q->items[k].data, q->items[s].data) < 0)	9,719,329✔
128
129	/* So our right child is smaller than we are, let's
130	* remember this fact */
131	s = k;	3,416,671✔
132
133	/* s now points to the smallest of the three items */
134
135	if (s == idx)	11,942,084✔
136	/* No swap necessary, we're done */
137	break;
138
139	swap(q, idx, s);	8,727,025✔
140	idx = s;	8,727,025✔
141	}
142
143	return idx;	12,668,285✔
144	}
145
146	int prioq_put(Prioq q, void data, unsigned *idx) {	3,570,315✔
147	unsigned k;	3,570,315✔
148
149	assert(q);	3,570,315✔
150
151	if (!GREEDY_REALLOC(q->items, MAX(q->n_items + 1, 16u)))	3,570,315✔
152	return -ENOMEM;
153
154	k = q->n_items++;	3,570,315✔
155	q->items[k] = (struct prioq_item) {	3,570,315✔
156	.data = data,
157	.idx = idx,
158	};
159
160	if (idx)	3,570,315✔
161	*idx = k;	3,566,219✔
162
163	shuffle_up(q, k);	3,570,315✔
164
165	return 0;
166	}
167
168	int _prioq_ensure_put(Prioq *q, compare_func_t compare_func, void data, unsigned *idx) {	138✔
169	int r;	138✔
170
171	r = prioq_ensure_allocated(q, compare_func);	138✔
172	if (r < 0)	138✔
173	return r;
174
175	return prioq_put(*q, data, idx);	138✔
176	}
177
178	static void remove_item(Prioq q, struct prioq_item i) {	3,569,813✔
179	struct prioq_item *l;	3,569,813✔
180
181	assert(q);	3,569,813✔
182	assert(i);	3,569,813✔
183
184	/* Let's invalidate the index pointer stored in the user's object to indicate the item is now removed
185	* from the priority queue */
186	if (i->idx)	3,569,813✔
187	*(i->idx) = PRIOQ_IDX_NULL;	3,565,717✔
188
189	l = q->items + q->n_items - 1;	3,569,813✔
190
191	if (i == l)	3,569,813✔
192	/* Last entry, let's just remove it */
193	q->n_items--;	2,394,557✔
194	else {
195	unsigned k;	1,175,256✔
196
197	/* Not last entry, let's replace the last entry with
198	* this one, and reshuffle */
199
200	assert(i >= q->items);	1,175,256✔
201	k = i - q->items;	1,175,256✔
202
203	i->data = l->data;	1,175,256✔
204	i->idx = l->idx;	1,175,256✔
205	if (i->idx)	1,175,256✔
206	*i->idx = k;	1,171,161✔
207	q->n_items--;	1,175,256✔
208
209	k = shuffle_down(q, k);	1,175,256✔
210	shuffle_up(q, k);	1,175,256✔
211	}
212	}	3,569,813✔
213
214	static struct prioq_item* find_item(Prioq q, void data, unsigned *idx) {	15,078,580✔
215	struct prioq_item *i;	15,078,580✔
216
217	assert(q);	15,078,580✔
218
219	if (q->n_items <= 0)	15,078,580✔
220	return NULL;
221
222	if (idx) {	15,075,589✔
223	if (*idx == PRIOQ_IDX_NULL \|\|	15,071,494✔
224	*idx >= q->n_items)
225	return NULL;
226
227	i = q->items + *idx;	15,054,876✔
228	if (i->data != data)	15,054,876✔
229	return NULL;
230
231	return i;	15,054,876✔
232	} else {
233	for (i = q->items; i < q->items + q->n_items; i++)	8,390,655✔
234	if (i->data == data)	8,386,560✔
235	return i;
236	return NULL;
237	}
238	}
239
240	int prioq_remove(Prioq q, void data, unsigned *idx) {	3,624,548✔
241	struct prioq_item *i;	3,624,548✔
242
243	if (!q)	3,624,548✔
244	return 0;
245
246	i = find_item(q, data, idx);	3,585,551✔
247	if (!i)	3,585,551✔
248	return 0;
249
250	remove_item(q, i);	3,561,847✔
251	return 1;	3,561,847✔
252	}
253
254	void prioq_reshuffle(Prioq q, void data, unsigned *idx) {	11,493,029✔
255	struct prioq_item *i;	11,493,029✔
256	unsigned k;	11,493,029✔
257
258	assert(q);	11,493,029✔
259
260	i = find_item(q, data, idx);	11,493,029✔
261	if (!i)	11,493,029✔
262	return;
263
264	assert(i >= q->items);	11,493,029✔
265	k = i - q->items;	11,493,029✔
266	k = shuffle_down(q, k);	11,493,029✔
267	shuffle_up(q, k);	11,493,029✔
268	}
269
270	void* prioq_peek_by_index(Prioq *q, unsigned idx) {	37,186,167✔
271	if (!q)	37,186,167✔
272	return NULL;
273
274	if (idx >= q->n_items)	22,964,624✔
275	return NULL;
276
277	return q->items[idx].data;	19,810,350✔
278	}
279
280	void* prioq_pop(Prioq *q) {	7,966✔
281	void *data;	7,966✔
282
283	if (!q)	7,966✔
284	return NULL;
285
286	if (q->n_items <= 0)	7,966✔
287	return NULL;
288
289	data = q->items[0].data;	7,966✔
290	remove_item(q, q->items);	7,966✔
291	return data;	7,966✔
292	}
293
294	unsigned prioq_size(Prioq *q) {	11,681✔
295
296	if (!q)	11,681✔
297	return 0;
298
299	return q->n_items;	11,655✔
300	}
301
302	bool prioq_isempty(Prioq *q) {	68,875✔
303
304	if (!q)	68,875✔
305	return true;
306
307	return q->n_items <= 0;	55,233✔
308	}

systemd / systemd / 15263807472

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous