Lines Matching refs:pq
68 # define ASSERT_USED(pq, idx) \ argument
69 assert(pq->elements[pq->heap[idx].index].used); \
70 assert(pq->elements[pq->heap[idx].index].posn == idx)
71 # define ASSERT_ELEM_USED(pq, elem) \ argument
72 assert(pq->elements[elem].used)
74 # define ASSERT_USED(pq, idx) argument
75 # define ASSERT_ELEM_USED(pq, elem) argument
105 static ossl_inline void pqueue_swap_elem(OSSL_PQUEUE *pq, size_t i, size_t j) in pqueue_swap_elem() argument
107 struct pq_heap_st *h = pq->heap, t_h; in pqueue_swap_elem()
108 struct pq_elem_st *e = pq->elements; in pqueue_swap_elem()
110 ASSERT_USED(pq, i); in pqueue_swap_elem()
111 ASSERT_USED(pq, j); in pqueue_swap_elem()
121 static ossl_inline void pqueue_move_elem(OSSL_PQUEUE *pq, size_t from, size_t to) in pqueue_move_elem() argument
123 struct pq_heap_st *h = pq->heap; in pqueue_move_elem()
124 struct pq_elem_st *e = pq->elements; in pqueue_move_elem()
126 ASSERT_USED(pq, from); in pqueue_move_elem()
136 static ossl_inline void pqueue_force_bottom(OSSL_PQUEUE *pq, size_t n) in pqueue_force_bottom() argument
138 ASSERT_USED(pq, n); in pqueue_force_bottom()
142 ASSERT_USED(pq, p); in pqueue_force_bottom()
143 pqueue_swap_elem(pq, n, p); in pqueue_force_bottom()
152 static ossl_inline void pqueue_move_down(OSSL_PQUEUE *pq, size_t n) in pqueue_move_down() argument
154 struct pq_heap_st *h = pq->heap; in pqueue_move_down()
156 ASSERT_USED(pq, n); in pqueue_move_down()
160 ASSERT_USED(pq, p); in pqueue_move_down()
161 if (pq->compare(h[n].data, h[p].data) >= 0) in pqueue_move_down()
163 pqueue_swap_elem(pq, n, p); in pqueue_move_down()
172 static ossl_inline void pqueue_move_up(OSSL_PQUEUE *pq, size_t n) in pqueue_move_up() argument
174 struct pq_heap_st *h = pq->heap; in pqueue_move_up()
177 ASSERT_USED(pq, n); in pqueue_move_up()
178 if (pq->htop > p + 1) { in pqueue_move_up()
179 ASSERT_USED(pq, p); in pqueue_move_up()
180 ASSERT_USED(pq, p + 1); in pqueue_move_up()
181 if (pq->compare(h[p].data, h[p + 1].data) > 0) in pqueue_move_up()
184 while (pq->htop > p && pq->compare(h[p].data, h[n].data) < 0) { in pqueue_move_up()
185 ASSERT_USED(pq, p); in pqueue_move_up()
186 pqueue_swap_elem(pq, n, p); in pqueue_move_up()
189 if (pq->htop > p + 1) { in pqueue_move_up()
190 ASSERT_USED(pq, p + 1); in pqueue_move_up()
191 if (pq->compare(h[p].data, h[p + 1].data) > 0) in pqueue_move_up()
197 int ossl_pqueue_push(OSSL_PQUEUE *pq, void *data, size_t *elem) in ossl_pqueue_push() argument
201 if (!ossl_pqueue_reserve(pq, 1)) in ossl_pqueue_push()
204 n = pq->htop++; in ossl_pqueue_push()
205 m = pq->freelist; in ossl_pqueue_push()
206 pq->freelist = pq->elements[m].posn; in ossl_pqueue_push()
208 pq->heap[n].data = data; in ossl_pqueue_push()
209 pq->heap[n].index = m; in ossl_pqueue_push()
211 pq->elements[m].posn = n; in ossl_pqueue_push()
213 pq->elements[m].used = 1; in ossl_pqueue_push()
215 pqueue_move_down(pq, n); in ossl_pqueue_push()
221 void *ossl_pqueue_peek(const OSSL_PQUEUE *pq) in ossl_pqueue_peek() argument
223 if (pq->htop > 0) { in ossl_pqueue_peek()
224 ASSERT_USED(pq, 0); in ossl_pqueue_peek()
225 return pq->heap->data; in ossl_pqueue_peek()
230 void *ossl_pqueue_pop(OSSL_PQUEUE *pq) in ossl_pqueue_pop() argument
235 if (pq == NULL || pq->htop == 0) in ossl_pqueue_pop()
238 ASSERT_USED(pq, 0); in ossl_pqueue_pop()
239 res = pq->heap->data; in ossl_pqueue_pop()
240 elem = pq->heap->index; in ossl_pqueue_pop()
242 if (--pq->htop != 0) { in ossl_pqueue_pop()
243 pqueue_move_elem(pq, pq->htop, 0); in ossl_pqueue_pop()
244 pqueue_move_up(pq, 0); in ossl_pqueue_pop()
247 pq->elements[elem].posn = pq->freelist; in ossl_pqueue_pop()
248 pq->freelist = elem; in ossl_pqueue_pop()
250 pq->elements[elem].used = 0; in ossl_pqueue_pop()
255 void *ossl_pqueue_remove(OSSL_PQUEUE *pq, size_t elem) in ossl_pqueue_remove() argument
259 if (pq == NULL || elem >= pq->hmax || pq->htop == 0) in ossl_pqueue_remove()
262 ASSERT_ELEM_USED(pq, elem); in ossl_pqueue_remove()
263 n = pq->elements[elem].posn; in ossl_pqueue_remove()
265 ASSERT_USED(pq, n); in ossl_pqueue_remove()
267 if (n == pq->htop - 1) { in ossl_pqueue_remove()
268 pq->elements[elem].posn = pq->freelist; in ossl_pqueue_remove()
269 pq->freelist = elem; in ossl_pqueue_remove()
271 pq->elements[elem].used = 0; in ossl_pqueue_remove()
273 return pq->heap[--pq->htop].data; in ossl_pqueue_remove()
276 pqueue_force_bottom(pq, n); in ossl_pqueue_remove()
277 return ossl_pqueue_pop(pq); in ossl_pqueue_remove()
280 static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from) in pqueue_add_freelist() argument
282 struct pq_elem_st *e = pq->elements; in pqueue_add_freelist()
286 for (i = from; i < pq->hmax; i++) in pqueue_add_freelist()
289 e[from].posn = pq->freelist; in pqueue_add_freelist()
290 for (i = from + 1; i < pq->hmax; i++) in pqueue_add_freelist()
292 pq->freelist = pq->hmax - 1; in pqueue_add_freelist()
295 int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n) in ossl_pqueue_reserve() argument
301 if (pq == NULL) in ossl_pqueue_reserve()
303 cur_max = pq->hmax; in ossl_pqueue_reserve()
304 if (pq->htop + n < cur_max) in ossl_pqueue_reserve()
313 h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap)); in ossl_pqueue_reserve()
316 pq->heap = h; in ossl_pqueue_reserve()
318 e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements)); in ossl_pqueue_reserve()
321 pq->elements = e; in ossl_pqueue_reserve()
323 pq->hmax = new_max; in ossl_pqueue_reserve()
324 pqueue_add_freelist(pq, cur_max); in ossl_pqueue_reserve()
330 OSSL_PQUEUE *pq; in ossl_pqueue_new() local
335 pq = OPENSSL_malloc(sizeof(*pq)); in ossl_pqueue_new()
336 if (pq == NULL) in ossl_pqueue_new()
338 pq->compare = compare; in ossl_pqueue_new()
339 pq->hmax = min_nodes; in ossl_pqueue_new()
340 pq->htop = 0; in ossl_pqueue_new()
341 pq->freelist = 0; in ossl_pqueue_new()
342 pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes); in ossl_pqueue_new()
343 pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes); in ossl_pqueue_new()
344 if (pq->heap == NULL || pq->elements == NULL) { in ossl_pqueue_new()
345 ossl_pqueue_free(pq); in ossl_pqueue_new()
348 pqueue_add_freelist(pq, 0); in ossl_pqueue_new()
349 return pq; in ossl_pqueue_new()
352 void ossl_pqueue_free(OSSL_PQUEUE *pq) in ossl_pqueue_free() argument
354 if (pq != NULL) { in ossl_pqueue_free()
355 OPENSSL_free(pq->heap); in ossl_pqueue_free()
356 OPENSSL_free(pq->elements); in ossl_pqueue_free()
357 OPENSSL_free(pq); in ossl_pqueue_free()
361 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *)) in ossl_pqueue_pop_free() argument
365 if (pq != NULL) { in ossl_pqueue_pop_free()
366 for (i = 0; i < pq->htop; i++) in ossl_pqueue_pop_free()
367 (*freefunc)(pq->heap[i].data); in ossl_pqueue_pop_free()
368 ossl_pqueue_free(pq); in ossl_pqueue_pop_free()
372 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq) in ossl_pqueue_num() argument
374 return pq != NULL ? pq->htop : 0; in ossl_pqueue_num()
