2 * Copyright 1995-2024 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
11 #include "internal/cryptlib.h"
12 #include "internal/numbers.h"
13 #include "internal/safe_math.h"
14 #include <openssl/stack.h>
16 #include <openssl/e_os2.h> /* For ossl_inline */
18 OSSL_SAFE_MATH_SIGNED(int, int)
21 * The initial number of nodes in the array.
23 static const int min_nodes
= 4;
24 static const int max_nodes
= SIZE_MAX
/ sizeof(void *) < INT_MAX
25 ? (int)(SIZE_MAX
/ sizeof(void *)) : INT_MAX
;
32 OPENSSL_sk_compfunc comp
;
35 OPENSSL_sk_compfunc
OPENSSL_sk_set_cmp_func(OPENSSL_STACK
*sk
,
36 OPENSSL_sk_compfunc c
)
38 OPENSSL_sk_compfunc old
= sk
->comp
;
47 OPENSSL_STACK
*OPENSSL_sk_dup(const OPENSSL_STACK
*sk
)
51 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
)
59 /* direct structure assignment */
63 if (sk
== NULL
|| sk
->num
== 0) {
64 /* postpone |ret->data| allocation */
70 /* duplicate |sk->data| content */
71 ret
->data
= OPENSSL_malloc(sizeof(*ret
->data
) * sk
->num_alloc
);
72 if (ret
->data
== NULL
)
74 memcpy(ret
->data
, sk
->data
, sizeof(void *) * sk
->num
);
82 OPENSSL_STACK
*OPENSSL_sk_deep_copy(const OPENSSL_STACK
*sk
,
83 OPENSSL_sk_copyfunc copy_func
,
84 OPENSSL_sk_freefunc free_func
)
89 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
)
97 /* direct structure assignment */
101 if (sk
== NULL
|| sk
->num
== 0) {
102 /* postpone |ret| data allocation */
108 ret
->num_alloc
= sk
->num
> min_nodes
? sk
->num
: min_nodes
;
109 ret
->data
= OPENSSL_zalloc(sizeof(*ret
->data
) * ret
->num_alloc
);
110 if (ret
->data
== NULL
)
113 for (i
= 0; i
< ret
->num
; ++i
) {
114 if (sk
->data
[i
] == NULL
)
116 if ((ret
->data
[i
] = copy_func(sk
->data
[i
])) == NULL
) {
118 if (ret
->data
[i
] != NULL
)
119 free_func((void *)ret
->data
[i
]);
126 OPENSSL_sk_free(ret
);
130 OPENSSL_STACK
*OPENSSL_sk_new_null(void)
132 return OPENSSL_sk_new_reserve(NULL
, 0);
135 OPENSSL_STACK
*OPENSSL_sk_new(OPENSSL_sk_compfunc c
)
137 return OPENSSL_sk_new_reserve(c
, 0);
141 * Calculate the array growth based on the target size.
143 * The growth factor is a rational number and is defined by a numerator
144 * and a denominator. According to Andrew Koenig in his paper "Why Are
145 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
146 * than the golden ratio (1.618...).
148 * Considering only the Fibonacci ratios less than the golden ratio, the
149 * number of steps from the minimum allocation to integer overflow is:
150 * factor decimal growths
155 * All larger factors have the same number of growths.
157 * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice.
159 static ossl_inline
int compute_growth(int target
, int current
)
163 while (current
< target
) {
164 if (current
>= max_nodes
)
167 current
= safe_muldiv_int(current
, 8, 5, &err
);
170 if (current
>= max_nodes
)
176 /* internal STACK storage allocation */
177 static int sk_reserve(OPENSSL_STACK
*st
, int n
, int exact
)
179 const void **tmpdata
;
182 /* Check to see the reservation isn't exceeding the hard limit */
183 if (n
> max_nodes
- st
->num
) {
184 ERR_raise(ERR_LIB_CRYPTO
, CRYPTO_R_TOO_MANY_RECORDS
);
188 /* Figure out the new size */
189 num_alloc
= st
->num
+ n
;
190 if (num_alloc
< min_nodes
)
191 num_alloc
= min_nodes
;
193 /* If |st->data| allocation was postponed */
194 if (st
->data
== NULL
) {
196 * At this point, |st->num_alloc| and |st->num| are 0;
197 * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
199 if ((st
->data
= OPENSSL_zalloc(sizeof(void *) * num_alloc
)) == NULL
)
201 st
->num_alloc
= num_alloc
;
206 if (num_alloc
<= st
->num_alloc
)
208 num_alloc
= compute_growth(num_alloc
, st
->num_alloc
);
209 if (num_alloc
== 0) {
210 ERR_raise(ERR_LIB_CRYPTO
, CRYPTO_R_TOO_MANY_RECORDS
);
213 } else if (num_alloc
== st
->num_alloc
) {
217 tmpdata
= OPENSSL_realloc((void *)st
->data
, sizeof(void *) * num_alloc
);
222 st
->num_alloc
= num_alloc
;
226 OPENSSL_STACK
*OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c
, int n
)
228 OPENSSL_STACK
*st
= OPENSSL_zalloc(sizeof(OPENSSL_STACK
));
238 if (!sk_reserve(st
, n
, 1)) {
246 int OPENSSL_sk_reserve(OPENSSL_STACK
*st
, int n
)
249 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_PASSED_NULL_PARAMETER
);
255 return sk_reserve(st
, n
, 1);
258 int OPENSSL_sk_insert(OPENSSL_STACK
*st
, const void *data
, int loc
)
261 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_PASSED_NULL_PARAMETER
);
264 if (st
->num
== max_nodes
) {
265 ERR_raise(ERR_LIB_CRYPTO
, CRYPTO_R_TOO_MANY_RECORDS
);
269 if (!sk_reserve(st
, 1, 0))
272 if ((loc
>= st
->num
) || (loc
< 0)) {
273 st
->data
[st
->num
] = data
;
275 memmove(&st
->data
[loc
+ 1], &st
->data
[loc
],
276 sizeof(st
->data
[0]) * (st
->num
- loc
));
277 st
->data
[loc
] = data
;
284 static ossl_inline
void *internal_delete(OPENSSL_STACK
*st
, int loc
)
286 const void *ret
= st
->data
[loc
];
288 if (loc
!= st
->num
- 1)
289 memmove(&st
->data
[loc
], &st
->data
[loc
+ 1],
290 sizeof(st
->data
[0]) * (st
->num
- loc
- 1));
296 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK
*st
, const void *p
)
303 for (i
= 0; i
< st
->num
; i
++)
304 if (st
->data
[i
] == p
)
305 return internal_delete(st
, i
);
309 void *OPENSSL_sk_delete(OPENSSL_STACK
*st
, int loc
)
311 if (st
== NULL
|| loc
< 0 || loc
>= st
->num
)
314 return internal_delete(st
, loc
);
317 static int internal_find(OPENSSL_STACK
*st
, const void *data
,
318 int ret_val_options
, int *pnum_matched
)
322 int *pnum
= pnum_matched
;
324 if (st
== NULL
|| st
->num
== 0)
330 if (st
->comp
== NULL
) {
331 for (i
= 0; i
< st
->num
; i
++)
332 if (st
->data
[i
] == data
) {
346 for (i
= 0; i
< st
->num
; i
++)
347 if (st
->comp(&data
, st
->data
+ i
) == 0) {
351 /* Check if only one result is wanted and exit if so */
352 if (pnum_matched
== NULL
)
360 if (pnum_matched
!= NULL
)
361 ret_val_options
|= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH
;
362 r
= ossl_bsearch(&data
, st
->data
, st
->num
, sizeof(void *), st
->comp
,
365 if (pnum_matched
!= NULL
) {
368 const void **p
= (const void **)r
;
370 while (p
< st
->data
+ st
->num
) {
371 if (st
->comp(&data
, p
) != 0)
379 return r
== NULL
? -1 : (int)((const void **)r
- st
->data
);
382 int OPENSSL_sk_find(OPENSSL_STACK
*st
, const void *data
)
384 return internal_find(st
, data
, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH
, NULL
);
387 int OPENSSL_sk_find_ex(OPENSSL_STACK
*st
, const void *data
)
389 return internal_find(st
, data
, OSSL_BSEARCH_VALUE_ON_NOMATCH
, NULL
);
392 int OPENSSL_sk_find_all(OPENSSL_STACK
*st
, const void *data
, int *pnum
)
394 return internal_find(st
, data
, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH
, pnum
);
397 int OPENSSL_sk_push(OPENSSL_STACK
*st
, const void *data
)
401 return OPENSSL_sk_insert(st
, data
, st
->num
);
404 int OPENSSL_sk_unshift(OPENSSL_STACK
*st
, const void *data
)
406 return OPENSSL_sk_insert(st
, data
, 0);
409 void *OPENSSL_sk_shift(OPENSSL_STACK
*st
)
411 if (st
== NULL
|| st
->num
== 0)
413 return internal_delete(st
, 0);
416 void *OPENSSL_sk_pop(OPENSSL_STACK
*st
)
418 if (st
== NULL
|| st
->num
== 0)
420 return internal_delete(st
, st
->num
- 1);
423 void OPENSSL_sk_zero(OPENSSL_STACK
*st
)
425 if (st
== NULL
|| st
->num
== 0)
427 memset(st
->data
, 0, sizeof(*st
->data
) * st
->num
);
431 void OPENSSL_sk_pop_free(OPENSSL_STACK
*st
, OPENSSL_sk_freefunc func
)
437 for (i
= 0; i
< st
->num
; i
++)
438 if (st
->data
[i
] != NULL
)
439 func((char *)st
->data
[i
]);
443 void OPENSSL_sk_free(OPENSSL_STACK
*st
)
447 OPENSSL_free(st
->data
);
451 int OPENSSL_sk_num(const OPENSSL_STACK
*st
)
453 return st
== NULL
? -1 : st
->num
;
456 void *OPENSSL_sk_value(const OPENSSL_STACK
*st
, int i
)
458 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
460 return (void *)st
->data
[i
];
463 void *OPENSSL_sk_set(OPENSSL_STACK
*st
, int i
, const void *data
)
466 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_PASSED_NULL_PARAMETER
);
469 if (i
< 0 || i
>= st
->num
) {
470 ERR_raise_data(ERR_LIB_CRYPTO
, ERR_R_PASSED_INVALID_ARGUMENT
,
476 return (void *)st
->data
[i
];
479 void OPENSSL_sk_sort(OPENSSL_STACK
*st
)
481 if (st
!= NULL
&& !st
->sorted
&& st
->comp
!= NULL
) {
483 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
484 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
488 int OPENSSL_sk_is_sorted(const OPENSSL_STACK
*st
)
490 return st
== NULL
? 1 : st
->sorted
;