2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (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>
14 #include <openssl/objects.h>
16 #include <openssl/e_os2.h> /* For ossl_inline */
19 * The initial number of nodes in the array.
21 static const int min_nodes
= 4;
22 static const int max_nodes
= SIZE_MAX
/ sizeof(void *) < INT_MAX
23 ? (int)(SIZE_MAX
/ sizeof(void *))
31 OPENSSL_sk_compfunc comp
;
34 OPENSSL_sk_compfunc
OPENSSL_sk_set_cmp_func(OPENSSL_STACK
*sk
, OPENSSL_sk_compfunc c
)
36 OPENSSL_sk_compfunc old
= sk
->comp
;
45 OPENSSL_STACK
*OPENSSL_sk_dup(const OPENSSL_STACK
*sk
)
49 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
) {
50 CRYPTOerr(CRYPTO_F_OPENSSL_SK_DUP
, ERR_R_MALLOC_FAILURE
);
54 /* direct structure assignment */
58 /* postpone |ret->data| allocation */
63 /* duplicate |sk->data| content */
64 if ((ret
->data
= OPENSSL_malloc(sizeof(*ret
->data
) * sk
->num_alloc
)) == NULL
)
66 memcpy(ret
->data
, sk
->data
, sizeof(void *) * sk
->num
);
73 OPENSSL_STACK
*OPENSSL_sk_deep_copy(const OPENSSL_STACK
*sk
,
74 OPENSSL_sk_copyfunc copy_func
,
75 OPENSSL_sk_freefunc free_func
)
80 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
) {
81 CRYPTOerr(CRYPTO_F_OPENSSL_SK_DEEP_COPY
, ERR_R_MALLOC_FAILURE
);
85 /* direct structure assignment */
89 /* postpone |ret| data allocation */
95 ret
->num_alloc
= sk
->num
> min_nodes
? sk
->num
: min_nodes
;
96 ret
->data
= OPENSSL_zalloc(sizeof(*ret
->data
) * ret
->num_alloc
);
97 if (ret
->data
== NULL
) {
102 for (i
= 0; i
< ret
->num
; ++i
) {
103 if (sk
->data
[i
] == NULL
)
105 if ((ret
->data
[i
] = copy_func(sk
->data
[i
])) == NULL
) {
107 if (ret
->data
[i
] != NULL
)
108 free_func((void *)ret
->data
[i
]);
109 OPENSSL_sk_free(ret
);
116 OPENSSL_STACK
*OPENSSL_sk_new_null(void)
118 return OPENSSL_sk_new_reserve(NULL
, 0);
121 OPENSSL_STACK
*OPENSSL_sk_new(OPENSSL_sk_compfunc c
)
123 return OPENSSL_sk_new_reserve(c
, 0);
127 * Calculate the array growth based on the target size.
129 * The growth fraction is a rational number and is defined by a numerator
130 * and a denominator. According to Andrew Koenig in his paper "Why Are
131 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
132 * than the golden ratio (1.618...).
134 * We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
135 * Another option 8/5 = 1.6 allows for slightly faster growth, although safe
136 * computation is more difficult.
138 * The limit to avoid overflow is spot on. The modulo three correction term
139 * ensures that the limit is the largest number than can be expanded by the
140 * growth factor without exceeding the hard limit.
142 * Do not call it with |current| lower than 2, or it will infinitely loop.
144 static ossl_inline
int compute_growth(int target
, int current
)
146 const int limit
= (max_nodes
/ 3) * 2 + (max_nodes
% 3 ? 1 : 0);
148 while (current
< target
) {
149 /* Check to see if we're at the hard limit */
150 if (current
>= max_nodes
)
153 /* Expand the size by a factor of 3/2 if it is within range */
154 current
= current
< limit
? current
+ current
/ 2 : max_nodes
;
159 /* internal STACK storage allocation */
160 static int sk_reserve(OPENSSL_STACK
*st
, int n
, int exact
)
162 const void **tmpdata
;
165 /* Check to see the reservation isn't exceeding the hard limit */
166 if (n
> max_nodes
- st
->num
)
169 /* Figure out the new size */
170 num_alloc
= st
->num
+ n
;
171 if (num_alloc
< min_nodes
)
172 num_alloc
= min_nodes
;
174 /* If |st->data| allocation was postponed */
175 if (st
->data
== NULL
) {
177 * At this point, |st->num_alloc| and |st->num| are 0;
178 * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
180 if ((st
->data
= OPENSSL_zalloc(sizeof(void *) * num_alloc
)) == NULL
) {
181 CRYPTOerr(CRYPTO_F_SK_RESERVE
, ERR_R_MALLOC_FAILURE
);
184 st
->num_alloc
= num_alloc
;
189 if (num_alloc
<= st
->num_alloc
)
191 num_alloc
= compute_growth(num_alloc
, st
->num_alloc
);
194 } else if (num_alloc
== st
->num_alloc
) {
198 tmpdata
= OPENSSL_realloc((void *)st
->data
, sizeof(void *) * num_alloc
);
203 st
->num_alloc
= num_alloc
;
207 OPENSSL_STACK
*OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c
, int n
)
209 OPENSSL_STACK
*st
= OPENSSL_zalloc(sizeof(OPENSSL_STACK
));
219 if (!sk_reserve(st
, n
, 1)) {
227 int OPENSSL_sk_reserve(OPENSSL_STACK
*st
, int n
)
234 return sk_reserve(st
, n
, 1);
237 int OPENSSL_sk_insert(OPENSSL_STACK
*st
, const void *data
, int loc
)
239 if (st
== NULL
|| st
->num
== max_nodes
)
242 if (!sk_reserve(st
, 1, 0))
245 if ((loc
>= st
->num
) || (loc
< 0)) {
246 st
->data
[st
->num
] = data
;
248 memmove(&st
->data
[loc
+ 1], &st
->data
[loc
],
249 sizeof(st
->data
[0]) * (st
->num
- loc
));
250 st
->data
[loc
] = data
;
257 static ossl_inline
void *internal_delete(OPENSSL_STACK
*st
, int loc
)
259 const void *ret
= st
->data
[loc
];
261 if (loc
!= st
->num
- 1)
262 memmove(&st
->data
[loc
], &st
->data
[loc
+ 1],
263 sizeof(st
->data
[0]) * (st
->num
- loc
- 1));
269 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK
*st
, const void *p
)
273 for (i
= 0; i
< st
->num
; i
++)
274 if (st
->data
[i
] == p
)
275 return internal_delete(st
, i
);
279 void *OPENSSL_sk_delete(OPENSSL_STACK
*st
, int loc
)
281 if (st
== NULL
|| loc
< 0 || loc
>= st
->num
)
284 return internal_delete(st
, loc
);
287 static int internal_find(OPENSSL_STACK
*st
, const void *data
,
293 if (st
== NULL
|| st
->num
== 0)
296 if (st
->comp
== NULL
) {
297 for (i
= 0; i
< st
->num
; i
++)
298 if (st
->data
[i
] == data
)
305 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
306 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
310 r
= OBJ_bsearch_ex_(&data
, st
->data
, st
->num
, sizeof(void *), st
->comp
,
313 return r
== NULL
? -1 : (int)((const void **)r
- st
->data
);
316 int OPENSSL_sk_find(OPENSSL_STACK
*st
, const void *data
)
318 return internal_find(st
, data
, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH
);
321 int OPENSSL_sk_find_ex(OPENSSL_STACK
*st
, const void *data
)
323 return internal_find(st
, data
, OBJ_BSEARCH_VALUE_ON_NOMATCH
);
326 int OPENSSL_sk_push(OPENSSL_STACK
*st
, const void *data
)
330 return OPENSSL_sk_insert(st
, data
, st
->num
);
333 int OPENSSL_sk_unshift(OPENSSL_STACK
*st
, const void *data
)
335 return OPENSSL_sk_insert(st
, data
, 0);
338 void *OPENSSL_sk_shift(OPENSSL_STACK
*st
)
340 if (st
== NULL
|| st
->num
== 0)
342 return internal_delete(st
, 0);
345 void *OPENSSL_sk_pop(OPENSSL_STACK
*st
)
347 if (st
== NULL
|| st
->num
== 0)
349 return internal_delete(st
, st
->num
- 1);
352 void OPENSSL_sk_zero(OPENSSL_STACK
*st
)
354 if (st
== NULL
|| st
->num
== 0)
356 memset(st
->data
, 0, sizeof(*st
->data
) * st
->num
);
360 void OPENSSL_sk_pop_free(OPENSSL_STACK
*st
, OPENSSL_sk_freefunc func
)
366 for (i
= 0; i
< st
->num
; i
++)
367 if (st
->data
[i
] != NULL
)
368 func((char *)st
->data
[i
]);
372 void OPENSSL_sk_free(OPENSSL_STACK
*st
)
376 OPENSSL_free(st
->data
);
380 int OPENSSL_sk_num(const OPENSSL_STACK
*st
)
382 return st
== NULL
? -1 : st
->num
;
385 void *OPENSSL_sk_value(const OPENSSL_STACK
*st
, int i
)
387 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
389 return (void *)st
->data
[i
];
392 void *OPENSSL_sk_set(OPENSSL_STACK
*st
, int i
, const void *data
)
394 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
398 return (void *)st
->data
[i
];
401 void OPENSSL_sk_sort(OPENSSL_STACK
*st
)
403 if (st
!= NULL
&& !st
->sorted
&& st
->comp
!= NULL
) {
405 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
406 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
410 int OPENSSL_sk_is_sorted(const OPENSSL_STACK
*st
)
412 return st
== NULL
? 1 : st
->sorted
;