]>
git.ipfire.org Git - thirdparty/openssl.git/blob - ssl/priority_queue.c
2 * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
10 #include <openssl/crypto.h>
11 #include <openssl/err.h>
13 #include "internal/priority_queue.h"
14 #include "internal/safe_math.h"
15 #include "internal/numbers.h"
17 OSSL_SAFE_MATH_UNSIGNED(size_t, size_t)
20 * Fundamental operations:
21 * Binary Heap Fibonacci Heap
22 * Get smallest O(1) O(1)
23 * Delete any O(log n) O(log n) average but worst O(n)
24 * Insert O(log n) O(1)
27 * Merge two structures O(log n) O(1)
28 * Decrease key O(log n) O(1)
29 * Increase key O(log n) ?
31 * The Fibonacci heap is quite a bit more complicated to implement and has
32 * larger overhead in practice. We favour the binary heap here. A multi-way
33 * (ternary or quaternary) heap might elicit a performance advantage via better
34 * cache access patterns.
38 void *data
; /* User supplied data pointer */
39 size_t index
; /* Constant index in elements[] */
43 size_t posn
; /* Current index in heap[] or link in free list */
45 int used
; /* Debug flag indicating that this is in use */
51 struct pq_heap_st
*heap
;
52 struct pq_elem_st
*elements
;
53 int (*compare
)(const void *, const void *);
54 size_t htop
; /* Highest used heap element */
55 size_t hmax
; /* Allocated heap & element space */
56 size_t freelist
; /* Index into elements[], start of free element list */
60 * The initial and maximum number of elements in the heap.
62 static const size_t min_nodes
= 8;
63 static const size_t max_nodes
=
64 SIZE_MAX
/ (sizeof(struct pq_heap_st
) > sizeof(struct pq_elem_st
)
65 ? sizeof(struct pq_heap_st
) : sizeof(struct pq_elem_st
));
68 /* Some basic sanity checking of the data structure */
69 # define ASSERT_USED(pq, idx) \
70 assert(pq->elements[pq->heap[idx].index].used); \
71 assert(pq->elements[pq->heap[idx].index].posn == idx)
72 # define ASSERT_ELEM_USED(pq, elem) \
73 assert(pq->elements[elem].used)
75 # define ASSERT_USED(pq, idx)
76 # define ASSERT_ELEM_USED(pq, elem)
80 * Calculate the array growth based on the target size.
82 * The growth factor is a rational number and is defined by a numerator
83 * and a denominator. According to Andrew Koenig in his paper "Why Are
84 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
85 * than the golden ratio (1.618...).
87 * We use an expansion factor of 8 / 5 = 1.6
89 static ossl_inline
size_t compute_pqueue_growth(size_t target
, size_t current
)
93 while (current
< target
) {
94 if (current
>= max_nodes
)
97 current
= safe_muldiv_size_t(current
, 8, 5, &err
);
100 if (current
>= max_nodes
)
106 static ossl_inline
void pqueue_swap_elem(OSSL_PQUEUE
*pq
, size_t i
, size_t j
)
108 struct pq_heap_st
*h
= pq
->heap
, t_h
;
109 struct pq_elem_st
*e
= pq
->elements
;
118 e
[h
[i
].index
].posn
= i
;
119 e
[h
[j
].index
].posn
= j
;
122 static ossl_inline
void pqueue_move_elem(OSSL_PQUEUE
*pq
, size_t from
, size_t to
)
124 struct pq_heap_st
*h
= pq
->heap
;
125 struct pq_elem_st
*e
= pq
->elements
;
127 ASSERT_USED(pq
, from
);
130 e
[h
[to
].index
].posn
= to
;
134 * Force the specified element to the front of the heap. This breaks
135 * the heap partial ordering pre-condition.
137 static ossl_inline
void pqueue_force_bottom(OSSL_PQUEUE
*pq
, size_t n
)
141 const size_t p
= (n
- 1) / 2;
144 pqueue_swap_elem(pq
, n
, p
);
150 * Move an element down to its correct position to restore the partial
151 * order pre-condition.
153 static ossl_inline
void pqueue_move_down(OSSL_PQUEUE
*pq
, size_t n
)
155 struct pq_heap_st
*h
= pq
->heap
;
159 const size_t p
= (n
- 1) / 2;
162 if (pq
->compare(h
[n
].data
, h
[p
].data
) >= 0)
164 pqueue_swap_elem(pq
, n
, p
);
170 * Move an element up to its correct position to restore the partial
171 * order pre-condition.
173 static ossl_inline
void pqueue_move_up(OSSL_PQUEUE
*pq
, size_t n
)
175 struct pq_heap_st
*h
= pq
->heap
;
176 size_t p
= n
* 2 + 1;
179 if (pq
->htop
> p
+ 1) {
181 ASSERT_USED(pq
, p
+ 1);
182 if (pq
->compare(h
[p
].data
, h
[p
+ 1].data
) > 0)
185 while (pq
->htop
> p
&& pq
->compare(h
[p
].data
, h
[n
].data
) < 0) {
187 pqueue_swap_elem(pq
, n
, p
);
190 if (pq
->htop
> p
+ 1) {
191 ASSERT_USED(pq
, p
+ 1);
192 if (pq
->compare(h
[p
].data
, h
[p
+ 1].data
) > 0)
198 int ossl_pqueue_push(OSSL_PQUEUE
*pq
, void *data
, size_t *elem
)
202 if (!ossl_pqueue_reserve(pq
, 1))
207 pq
->freelist
= pq
->elements
[m
].posn
;
209 pq
->heap
[n
].data
= data
;
210 pq
->heap
[n
].index
= m
;
212 pq
->elements
[m
].posn
= n
;
214 pq
->elements
[m
].used
= 1;
216 pqueue_move_down(pq
, n
);
222 void *ossl_pqueue_peek(const OSSL_PQUEUE
*pq
)
226 return pq
->heap
->data
;
231 void *ossl_pqueue_pop(OSSL_PQUEUE
*pq
)
236 if (pq
== NULL
|| pq
->htop
== 0)
240 res
= pq
->heap
->data
;
241 elem
= pq
->heap
->index
;
243 if (--pq
->htop
!= 0) {
244 pqueue_move_elem(pq
, pq
->htop
, 0);
245 pqueue_move_up(pq
, 0);
248 pq
->elements
[elem
].posn
= pq
->freelist
;
251 pq
->elements
[elem
].used
= 0;
256 void *ossl_pqueue_remove(OSSL_PQUEUE
*pq
, size_t elem
)
260 if (pq
== NULL
|| elem
>= pq
->hmax
|| pq
->htop
== 0)
263 ASSERT_ELEM_USED(pq
, elem
);
264 n
= pq
->elements
[elem
].posn
;
268 if (n
== pq
->htop
- 1) {
269 pq
->elements
[elem
].posn
= pq
->freelist
;
272 pq
->elements
[elem
].used
= 0;
274 return pq
->heap
[--pq
->htop
].data
;
277 pqueue_force_bottom(pq
, n
);
278 return ossl_pqueue_pop(pq
);
281 static void pqueue_add_freelist(OSSL_PQUEUE
*pq
, size_t from
)
283 struct pq_elem_st
*e
= pq
->elements
;
287 for (i
= from
; i
< pq
->hmax
; i
++)
290 e
[from
].posn
= pq
->freelist
;
291 for (i
= from
+ 1; i
< pq
->hmax
; i
++)
293 pq
->freelist
= pq
->hmax
- 1;
296 int ossl_pqueue_reserve(OSSL_PQUEUE
*pq
, size_t n
)
298 size_t new_max
, cur_max
;
299 struct pq_heap_st
*h
;
300 struct pq_elem_st
*e
;
305 if (pq
->htop
+ n
< cur_max
)
308 new_max
= compute_pqueue_growth(n
+ cur_max
, cur_max
);
310 ERR_raise(ERR_LIB_SSL
, ERR_R_INTERNAL_ERROR
);
314 h
= OPENSSL_realloc(pq
->heap
, new_max
* sizeof(*pq
->heap
));
319 e
= OPENSSL_realloc(pq
->elements
, new_max
* sizeof(*pq
->elements
));
325 pqueue_add_freelist(pq
, cur_max
);
329 OSSL_PQUEUE
*ossl_pqueue_new(int (*compare
)(const void *, const void *))
336 pq
= OPENSSL_malloc(sizeof(*pq
));
339 pq
->compare
= compare
;
340 pq
->hmax
= min_nodes
;
343 pq
->heap
= OPENSSL_malloc(sizeof(*pq
->heap
) * min_nodes
);
344 pq
->elements
= OPENSSL_malloc(sizeof(*pq
->elements
) * min_nodes
);
345 if (pq
->heap
== NULL
|| pq
->elements
== NULL
) {
346 ossl_pqueue_free(pq
);
349 pqueue_add_freelist(pq
, 0);
353 void ossl_pqueue_free(OSSL_PQUEUE
*pq
)
356 OPENSSL_free(pq
->heap
);
357 OPENSSL_free(pq
->elements
);
362 void ossl_pqueue_pop_free(OSSL_PQUEUE
*pq
, void (*freefunc
)(void *))
367 for (i
= 0; i
< pq
->htop
; i
++)
368 (*freefunc
)(pq
->heap
[i
].data
);
369 ossl_pqueue_free(pq
);
373 size_t ossl_pqueue_num(const OSSL_PQUEUE
*pq
)
375 return pq
!= NULL
? pq
->htop
: 0;