2 * Copyright 1995-2020 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
) {
49 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
53 /* direct structure assignment */
57 /* postpone |ret->data| allocation */
62 /* duplicate |sk->data| content */
63 if ((ret
->data
= OPENSSL_malloc(sizeof(*ret
->data
) * sk
->num_alloc
)) == NULL
)
65 memcpy(ret
->data
, sk
->data
, sizeof(void *) * sk
->num
);
72 OPENSSL_STACK
*OPENSSL_sk_deep_copy(const OPENSSL_STACK
*sk
,
73 OPENSSL_sk_copyfunc copy_func
,
74 OPENSSL_sk_freefunc free_func
)
79 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
) {
80 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
84 /* direct structure assignment */
88 /* postpone |ret| data allocation */
94 ret
->num_alloc
= sk
->num
> min_nodes
? sk
->num
: min_nodes
;
95 ret
->data
= OPENSSL_zalloc(sizeof(*ret
->data
) * ret
->num_alloc
);
96 if (ret
->data
== NULL
) {
101 for (i
= 0; i
< ret
->num
; ++i
) {
102 if (sk
->data
[i
] == NULL
)
104 if ((ret
->data
[i
] = copy_func(sk
->data
[i
])) == NULL
) {
106 if (ret
->data
[i
] != NULL
)
107 free_func((void *)ret
->data
[i
]);
108 OPENSSL_sk_free(ret
);
115 OPENSSL_STACK
*OPENSSL_sk_new_null(void)
117 return OPENSSL_sk_new_reserve(NULL
, 0);
120 OPENSSL_STACK
*OPENSSL_sk_new(OPENSSL_sk_compfunc c
)
122 return OPENSSL_sk_new_reserve(c
, 0);
126 * Calculate the array growth based on the target size.
128 * The growth fraction is a rational number and is defined by a numerator
129 * and a denominator. According to Andrew Koenig in his paper "Why Are
130 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
131 * than the golden ratio (1.618...).
133 * We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
134 * Another option 8/5 = 1.6 allows for slightly faster growth, although safe
135 * computation is more difficult.
137 * The limit to avoid overflow is spot on. The modulo three correction term
138 * ensures that the limit is the largest number than can be expanded by the
139 * growth factor without exceeding the hard limit.
141 * Do not call it with |current| lower than 2, or it will infinitely loop.
143 static ossl_inline
int compute_growth(int target
, int current
)
145 const int limit
= (max_nodes
/ 3) * 2 + (max_nodes
% 3 ? 1 : 0);
147 while (current
< target
) {
148 /* Check to see if we're at the hard limit */
149 if (current
>= max_nodes
)
152 /* Expand the size by a factor of 3/2 if it is within range */
153 current
= current
< limit
? current
+ current
/ 2 : max_nodes
;
158 /* internal STACK storage allocation */
159 static int sk_reserve(OPENSSL_STACK
*st
, int n
, int exact
)
161 const void **tmpdata
;
164 /* Check to see the reservation isn't exceeding the hard limit */
165 if (n
> max_nodes
- st
->num
)
168 /* Figure out the new size */
169 num_alloc
= st
->num
+ n
;
170 if (num_alloc
< min_nodes
)
171 num_alloc
= min_nodes
;
173 /* If |st->data| allocation was postponed */
174 if (st
->data
== NULL
) {
176 * At this point, |st->num_alloc| and |st->num| are 0;
177 * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
179 if ((st
->data
= OPENSSL_zalloc(sizeof(void *) * num_alloc
)) == NULL
) {
180 ERR_raise(ERR_LIB_CRYPTO
, ERR_R_MALLOC_FAILURE
);
183 st
->num_alloc
= num_alloc
;
188 if (num_alloc
<= st
->num_alloc
)
190 num_alloc
= compute_growth(num_alloc
, st
->num_alloc
);
193 } else if (num_alloc
== st
->num_alloc
) {
197 tmpdata
= OPENSSL_realloc((void *)st
->data
, sizeof(void *) * num_alloc
);
202 st
->num_alloc
= num_alloc
;
206 OPENSSL_STACK
*OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c
, int n
)
208 OPENSSL_STACK
*st
= OPENSSL_zalloc(sizeof(OPENSSL_STACK
));
218 if (!sk_reserve(st
, n
, 1)) {
226 int OPENSSL_sk_reserve(OPENSSL_STACK
*st
, int n
)
233 return sk_reserve(st
, n
, 1);
236 int OPENSSL_sk_insert(OPENSSL_STACK
*st
, const void *data
, int loc
)
238 if (st
== NULL
|| st
->num
== max_nodes
)
241 if (!sk_reserve(st
, 1, 0))
244 if ((loc
>= st
->num
) || (loc
< 0)) {
245 st
->data
[st
->num
] = data
;
247 memmove(&st
->data
[loc
+ 1], &st
->data
[loc
],
248 sizeof(st
->data
[0]) * (st
->num
- loc
));
249 st
->data
[loc
] = data
;
256 static ossl_inline
void *internal_delete(OPENSSL_STACK
*st
, int loc
)
258 const void *ret
= st
->data
[loc
];
260 if (loc
!= st
->num
- 1)
261 memmove(&st
->data
[loc
], &st
->data
[loc
+ 1],
262 sizeof(st
->data
[0]) * (st
->num
- loc
- 1));
268 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK
*st
, const void *p
)
272 for (i
= 0; i
< st
->num
; i
++)
273 if (st
->data
[i
] == p
)
274 return internal_delete(st
, i
);
278 void *OPENSSL_sk_delete(OPENSSL_STACK
*st
, int loc
)
280 if (st
== NULL
|| loc
< 0 || loc
>= st
->num
)
283 return internal_delete(st
, loc
);
286 static int internal_find(OPENSSL_STACK
*st
, const void *data
,
292 if (st
== NULL
|| st
->num
== 0)
295 if (st
->comp
== NULL
) {
296 for (i
= 0; i
< st
->num
; i
++)
297 if (st
->data
[i
] == data
)
304 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
305 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
309 r
= ossl_bsearch(&data
, st
->data
, st
->num
, sizeof(void *), st
->comp
,
312 return r
== NULL
? -1 : (int)((const void **)r
- st
->data
);
315 int OPENSSL_sk_find(OPENSSL_STACK
*st
, const void *data
)
317 return internal_find(st
, data
, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH
);
320 int OPENSSL_sk_find_ex(OPENSSL_STACK
*st
, const void *data
)
322 return internal_find(st
, data
, OSSL_BSEARCH_VALUE_ON_NOMATCH
);
325 int OPENSSL_sk_push(OPENSSL_STACK
*st
, const void *data
)
329 return OPENSSL_sk_insert(st
, data
, st
->num
);
332 int OPENSSL_sk_unshift(OPENSSL_STACK
*st
, const void *data
)
334 return OPENSSL_sk_insert(st
, data
, 0);
337 void *OPENSSL_sk_shift(OPENSSL_STACK
*st
)
339 if (st
== NULL
|| st
->num
== 0)
341 return internal_delete(st
, 0);
344 void *OPENSSL_sk_pop(OPENSSL_STACK
*st
)
346 if (st
== NULL
|| st
->num
== 0)
348 return internal_delete(st
, st
->num
- 1);
351 void OPENSSL_sk_zero(OPENSSL_STACK
*st
)
353 if (st
== NULL
|| st
->num
== 0)
355 memset(st
->data
, 0, sizeof(*st
->data
) * st
->num
);
359 void OPENSSL_sk_pop_free(OPENSSL_STACK
*st
, OPENSSL_sk_freefunc func
)
365 for (i
= 0; i
< st
->num
; i
++)
366 if (st
->data
[i
] != NULL
)
367 func((char *)st
->data
[i
]);
371 void OPENSSL_sk_free(OPENSSL_STACK
*st
)
375 OPENSSL_free(st
->data
);
379 int OPENSSL_sk_num(const OPENSSL_STACK
*st
)
381 return st
== NULL
? -1 : st
->num
;
384 void *OPENSSL_sk_value(const OPENSSL_STACK
*st
, int i
)
386 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
388 return (void *)st
->data
[i
];
391 void *OPENSSL_sk_set(OPENSSL_STACK
*st
, int i
, const void *data
)
393 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
397 return (void *)st
->data
[i
];
400 void OPENSSL_sk_sort(OPENSSL_STACK
*st
)
402 if (st
!= NULL
&& !st
->sorted
&& st
->comp
!= NULL
) {
404 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
405 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
409 int OPENSSL_sk_is_sorted(const OPENSSL_STACK
*st
)
411 return st
== NULL
? 1 : st
->sorted
;