Lines Matching refs:pq
66 #define ASSERT_USED(pq, idx) \
67 assert(pq->elements[pq->heap[idx].index].used); \
68 assert(pq->elements[pq->heap[idx].index].posn == idx)
69 #define ASSERT_ELEM_USED(pq, elem) \
70 assert(pq->elements[elem].used)
72 #define ASSERT_USED(pq, idx)
73 #define ASSERT_ELEM_USED(pq, elem)
103 static ossl_inline void pqueue_swap_elem(OSSL_PQUEUE *pq, size_t i, size_t j)
105 struct pq_heap_st *h = pq->heap, t_h;
106 struct pq_elem_st *e = pq->elements;
108 ASSERT_USED(pq, i);
109 ASSERT_USED(pq, j);
119 static ossl_inline void pqueue_move_elem(OSSL_PQUEUE *pq, size_t from, size_t to)
121 struct pq_heap_st *h = pq->heap;
122 struct pq_elem_st *e = pq->elements;
124 ASSERT_USED(pq, from);
134 static ossl_inline void pqueue_force_bottom(OSSL_PQUEUE *pq, size_t n)
136 ASSERT_USED(pq, n);
140 ASSERT_USED(pq, p);
141 pqueue_swap_elem(pq, n, p);
150 static ossl_inline void pqueue_move_down(OSSL_PQUEUE *pq, size_t n)
152 struct pq_heap_st *h = pq->heap;
154 ASSERT_USED(pq, n);
158 ASSERT_USED(pq, p);
159 if (pq->compare(h[n].data, h[p].data) >= 0)
161 pqueue_swap_elem(pq, n, p);
170 static ossl_inline void pqueue_move_up(OSSL_PQUEUE *pq, size_t n)
172 struct pq_heap_st *h = pq->heap;
175 ASSERT_USED(pq, n);
176 if (pq->htop > p + 1) {
177 ASSERT_USED(pq, p);
178 ASSERT_USED(pq, p + 1);
179 if (pq->compare(h[p].data, h[p + 1].data) > 0)
182 while (pq->htop > p && pq->compare(h[p].data, h[n].data) < 0) {
183 ASSERT_USED(pq, p);
184 pqueue_swap_elem(pq, n, p);
187 if (pq->htop > p + 1) {
188 ASSERT_USED(pq, p + 1);
189 if (pq->compare(h[p].data, h[p + 1].data) > 0)
195 int ossl_pqueue_push(OSSL_PQUEUE *pq, void *data, size_t *elem)
199 if (!ossl_pqueue_reserve(pq, 1))
202 n = pq->htop++;
203 m = pq->freelist;
204 pq->freelist = pq->elements[m].posn;
206 pq->heap[n].data = data;
207 pq->heap[n].index = m;
209 pq->elements[m].posn = n;
211 pq->elements[m].used = 1;
213 pqueue_move_down(pq, n);
219 void *ossl_pqueue_peek(const OSSL_PQUEUE *pq)
221 if (pq->htop > 0) {
222 ASSERT_USED(pq, 0);
223 return pq->heap->data;
228 void *ossl_pqueue_pop(OSSL_PQUEUE *pq)
233 if (pq == NULL || pq->htop == 0)
236 ASSERT_USED(pq, 0);
237 res = pq->heap->data;
238 elem = pq->heap->index;
240 if (--pq->htop != 0) {
241 pqueue_move_elem(pq, pq->htop, 0);
242 pqueue_move_up(pq, 0);
245 pq->elements[elem].posn = pq->freelist;
246 pq->freelist = elem;
248 pq->elements[elem].used = 0;
253 void *ossl_pqueue_remove(OSSL_PQUEUE *pq, size_t elem)
257 if (pq == NULL || elem >= pq->hmax || pq->htop == 0)
260 ASSERT_ELEM_USED(pq, elem);
261 n = pq->elements[elem].posn;
263 ASSERT_USED(pq, n);
265 if (n == pq->htop - 1) {
266 pq->elements[elem].posn = pq->freelist;
267 pq->freelist = elem;
269 pq->elements[elem].used = 0;
271 return pq->heap[--pq->htop].data;
274 pqueue_force_bottom(pq, n);
275 return ossl_pqueue_pop(pq);
278 static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from)
280 struct pq_elem_st *e = pq->elements;
284 for (i = from; i < pq->hmax; i++)
287 e[from].posn = pq->freelist;
288 for (i = from + 1; i < pq->hmax; i++)
290 pq->freelist = pq->hmax - 1;
293 int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n)
299 if (pq == NULL)
301 cur_max = pq->hmax;
302 if (pq->htop + n < cur_max)
311 h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap));
314 pq->heap = h;
316 e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements));
319 pq->elements = e;
321 pq->hmax = new_max;
322 pqueue_add_freelist(pq, cur_max);
328 OSSL_PQUEUE *pq;
333 pq = OPENSSL_malloc(sizeof(*pq));
334 if (pq == NULL)
336 pq->compare = compare;
337 pq->hmax = min_nodes;
338 pq->htop = 0;
339 pq->freelist = 0;
340 pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes);
341 pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes);
342 if (pq->heap == NULL || pq->elements == NULL) {
343 ossl_pqueue_free(pq);
346 pqueue_add_freelist(pq, 0);
347 return pq;
350 void ossl_pqueue_free(OSSL_PQUEUE *pq)
352 if (pq != NULL) {
353 OPENSSL_free(pq->heap);
354 OPENSSL_free(pq->elements);
355 OPENSSL_free(pq);
359 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *))
363 if (pq != NULL) {
364 for (i = 0; i < pq->htop; i++)
365 (*freefunc)(pq->heap[i].data);
366 ossl_pqueue_free(pq);
370 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq)
372 return pq != NULL ? pq->htop : 0;
Indexes created Mon Mar 02 05:31:46 UTC 2026