2 * Copyright 1995-2021 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 <openssl/stack.h>
15 #include <openssl/e_os2.h> /* For ossl_inline */
18 * The initial number of nodes in the array.
20 static const int min_nodes
= 4;
21 static const int max_nodes
= SIZE_MAX
/ sizeof(void *) < INT_MAX
22 ? (int)(SIZE_MAX
/ sizeof(void *))
30 OPENSSL_sk_compfunc comp
;
33 OPENSSL_sk_compfunc
OPENSSL_sk_set_cmp_func(OPENSSL_STACK
*sk
, OPENSSL_sk_compfunc c
)
35 OPENSSL_sk_compfunc old
= sk
->comp
;
44 OPENSSL_STACK
*OPENSSL_sk_dup(const OPENSSL_STACK
*sk
)
48 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
)
56 /* direct structure assignment */
60 if (sk
== NULL
|| sk
->num
== 0) {
61 /* postpone |ret->data| allocation */
67 /* duplicate |sk->data| content */
68 if ((ret
->data
= OPENSSL_malloc(sizeof(*ret
->data
) * sk
->num_alloc
)) == NULL
)
70 memcpy(ret
->data
, sk
->data
, sizeof(void *) * sk
->num
);
74 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
79 OPENSSL_STACK
*OPENSSL_sk_deep_copy(const OPENSSL_STACK
*sk
,
80 OPENSSL_sk_copyfunc copy_func
,
81 OPENSSL_sk_freefunc free_func
)
86 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
)
94 /* direct structure assignment */
98 if (sk
== NULL
|| sk
->num
== 0) {
99 /* postpone |ret| data allocation */
105 ret
->num_alloc
= sk
->num
> min_nodes
? sk
->num
: min_nodes
;
106 ret
->data
= OPENSSL_zalloc(sizeof(*ret
->data
) * ret
->num_alloc
);
107 if (ret
->data
== NULL
)
110 for (i
= 0; i
< ret
->num
; ++i
) {
111 if (sk
->data
[i
] == NULL
)
113 if ((ret
->data
[i
] = copy_func(sk
->data
[i
])) == NULL
) {
115 if (ret
->data
[i
] != NULL
)
116 free_func((void *)ret
->data
[i
]);
123 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
124 OPENSSL_sk_free(ret
);
128 OPENSSL_STACK
*OPENSSL_sk_new_null(void)
130 return OPENSSL_sk_new_reserve(NULL
, 0);
133 OPENSSL_STACK
*OPENSSL_sk_new(OPENSSL_sk_compfunc c
)
135 return OPENSSL_sk_new_reserve(c
, 0);
139 * Calculate the array growth based on the target size.
141 * The growth fraction is a rational number and is defined by a numerator
142 * and a denominator. According to Andrew Koenig in his paper "Why Are
143 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
144 * than the golden ratio (1.618...).
146 * We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
147 * Another option 8/5 = 1.6 allows for slightly faster growth, although safe
148 * computation is more difficult.
150 * The limit to avoid overflow is spot on. The modulo three correction term
151 * ensures that the limit is the largest number than can be expanded by the
152 * growth factor without exceeding the hard limit.
154 * Do not call it with |current| lower than 2, or it will infinitely loop.
156 static ossl_inline
int compute_growth(int target
, int current
)
158 const int limit
= (max_nodes
/ 3) * 2 + (max_nodes
% 3 ? 1 : 0);
160 while (current
< target
) {
161 /* Check to see if we're at the hard limit */
162 if (current
>= max_nodes
)
165 /* Expand the size by a factor of 3/2 if it is within range */
166 current
= current
< limit
? current
+ current
/ 2 : max_nodes
;
171 /* internal STACK storage allocation */
172 static int sk_reserve(OPENSSL_STACK
*st
, int n
, int exact
)
174 const void **tmpdata
;
177 /* Check to see the reservation isn't exceeding the hard limit */
178 if (n
> max_nodes
- st
->num
)
181 /* Figure out the new size */
182 num_alloc
= st
->num
+ n
;
183 if (num_alloc
< min_nodes
)
184 num_alloc
= min_nodes
;
186 /* If |st->data| allocation was postponed */
187 if (st
->data
== NULL
) {
189 * At this point, |st->num_alloc| and |st->num| are 0;
190 * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
192 if ((st
->data
= OPENSSL_zalloc(sizeof(void *) * num_alloc
)) == NULL
) {
193 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
196 st
->num_alloc
= num_alloc
;
201 if (num_alloc
<= st
->num_alloc
)
203 num_alloc
= compute_growth(num_alloc
, st
->num_alloc
);
206 } else if (num_alloc
== st
->num_alloc
) {
210 tmpdata
= OPENSSL_realloc((void *)st
->data
, sizeof(void *) * num_alloc
);
215 st
->num_alloc
= num_alloc
;
219 OPENSSL_STACK
*OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c
, int n
)
221 OPENSSL_STACK
*st
= OPENSSL_zalloc(sizeof(OPENSSL_STACK
));
231 if (!sk_reserve(st
, n
, 1)) {
239 int OPENSSL_sk_reserve(OPENSSL_STACK
*st
, int n
)
246 return sk_reserve(st
, n
, 1);
249 int OPENSSL_sk_insert(OPENSSL_STACK
*st
, const void *data
, int loc
)
251 if (st
== NULL
|| st
->num
== max_nodes
)
254 if (!sk_reserve(st
, 1, 0))
257 if ((loc
>= st
->num
) || (loc
< 0)) {
258 st
->data
[st
->num
] = data
;
260 memmove(&st
->data
[loc
+ 1], &st
->data
[loc
],
261 sizeof(st
->data
[0]) * (st
->num
- loc
));
262 st
->data
[loc
] = data
;
269 static ossl_inline
void *internal_delete(OPENSSL_STACK
*st
, int loc
)
271 const void *ret
= st
->data
[loc
];
273 if (loc
!= st
->num
- 1)
274 memmove(&st
->data
[loc
], &st
->data
[loc
+ 1],
275 sizeof(st
->data
[0]) * (st
->num
- loc
- 1));
281 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK
*st
, const void *p
)
285 for (i
= 0; i
< st
->num
; i
++)
286 if (st
->data
[i
] == p
)
287 return internal_delete(st
, i
);
291 void *OPENSSL_sk_delete(OPENSSL_STACK
*st
, int loc
)
293 if (st
== NULL
|| loc
< 0 || loc
>= st
->num
)
296 return internal_delete(st
, loc
);
299 static int internal_find(OPENSSL_STACK
*st
, const void *data
,
305 if (st
== NULL
|| st
->num
== 0)
308 if (st
->comp
== NULL
) {
309 for (i
= 0; i
< st
->num
; i
++)
310 if (st
->data
[i
] == data
)
317 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
318 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
322 r
= ossl_bsearch(&data
, st
->data
, st
->num
, sizeof(void *), st
->comp
,
325 return r
== NULL
? -1 : (int)((const void **)r
- st
->data
);
328 int OPENSSL_sk_find(OPENSSL_STACK
*st
, const void *data
)
330 return internal_find(st
, data
, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH
);
333 int OPENSSL_sk_find_ex(OPENSSL_STACK
*st
, const void *data
)
335 return internal_find(st
, data
, OSSL_BSEARCH_VALUE_ON_NOMATCH
);
338 int OPENSSL_sk_push(OPENSSL_STACK
*st
, const void *data
)
342 return OPENSSL_sk_insert(st
, data
, st
->num
);
345 int OPENSSL_sk_unshift(OPENSSL_STACK
*st
, const void *data
)
347 return OPENSSL_sk_insert(st
, data
, 0);
350 void *OPENSSL_sk_shift(OPENSSL_STACK
*st
)
352 if (st
== NULL
|| st
->num
== 0)
354 return internal_delete(st
, 0);
357 void *OPENSSL_sk_pop(OPENSSL_STACK
*st
)
359 if (st
== NULL
|| st
->num
== 0)
361 return internal_delete(st
, st
->num
- 1);
364 void OPENSSL_sk_zero(OPENSSL_STACK
*st
)
366 if (st
== NULL
|| st
->num
== 0)
368 memset(st
->data
, 0, sizeof(*st
->data
) * st
->num
);
372 void OPENSSL_sk_pop_free(OPENSSL_STACK
*st
, OPENSSL_sk_freefunc func
)
378 for (i
= 0; i
< st
->num
; i
++)
379 if (st
->data
[i
] != NULL
)
380 func((char *)st
->data
[i
]);
384 void OPENSSL_sk_free(OPENSSL_STACK
*st
)
388 OPENSSL_free(st
->data
);
392 int OPENSSL_sk_num(const OPENSSL_STACK
*st
)
394 return st
== NULL
? -1 : st
->num
;
397 void *OPENSSL_sk_value(const OPENSSL_STACK
*st
, int i
)
399 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
401 return (void *)st
->data
[i
];
404 void *OPENSSL_sk_set(OPENSSL_STACK
*st
, int i
, const void *data
)
406 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
410 return (void *)st
->data
[i
];
413 void OPENSSL_sk_sort(OPENSSL_STACK
*st
)
415 if (st
!= NULL
&& !st
->sorted
&& st
->comp
!= NULL
) {
417 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
418 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
422 int OPENSSL_sk_is_sorted(const OPENSSL_STACK
*st
)
424 return st
== NULL
? 1 : st
->sorted
;