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
)
52 /* direct structure assignment */
56 /* postpone |ret->data| allocation */
61 /* duplicate |sk->data| content */
62 if ((ret
->data
= OPENSSL_malloc(sizeof(*ret
->data
) * sk
->num_alloc
)) == NULL
)
64 memcpy(ret
->data
, sk
->data
, sizeof(void *) * sk
->num
);
71 OPENSSL_STACK
*OPENSSL_sk_deep_copy(const OPENSSL_STACK
*sk
,
72 OPENSSL_sk_copyfunc copy_func
,
73 OPENSSL_sk_freefunc free_func
)
78 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
)
81 /* direct structure assignment */
85 /* postpone |ret| data allocation */
91 ret
->num_alloc
= sk
->num
> min_nodes
? sk
->num
: min_nodes
;
92 ret
->data
= OPENSSL_zalloc(sizeof(*ret
->data
) * ret
->num_alloc
);
93 if (ret
->data
== NULL
) {
98 for (i
= 0; i
< ret
->num
; ++i
) {
99 if (sk
->data
[i
] == NULL
)
101 if ((ret
->data
[i
] = copy_func(sk
->data
[i
])) == NULL
) {
103 if (ret
->data
[i
] != NULL
)
104 free_func((void *)ret
->data
[i
]);
105 OPENSSL_sk_free(ret
);
112 OPENSSL_STACK
*OPENSSL_sk_new_null(void)
114 return OPENSSL_sk_new_reserve(NULL
, 0);
117 OPENSSL_STACK
*OPENSSL_sk_new(OPENSSL_sk_compfunc c
)
119 return OPENSSL_sk_new_reserve(c
, 0);
123 * Calculate the array growth based on the target size.
125 * The growth fraction is a rational number and is defined by a numerator
126 * and a denominator. According to Andrew Koenig in his paper "Why Are
127 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
128 * than the golden ratio (1.618...).
130 * We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
131 * Another option 8/5 = 1.6 allows for slightly faster growth, although safe
132 * computation is more difficult.
134 * The limit to avoid overflow is spot on. The modulo three correction term
135 * ensures that the limit is the largest number than can be expanded by the
136 * growth factor without exceeding the hard limit.
138 * Do not call it with |current| lower than 2, or it will infinitely loop.
140 static ossl_inline
int compute_growth(int target
, int current
)
142 const int limit
= (max_nodes
/ 3) * 2 + (max_nodes
% 3 ? 1 : 0);
144 while (current
< target
) {
145 /* Check to see if we're at the hard limit */
146 if (current
>= max_nodes
)
149 /* Expand the size by a factor of 3/2 if it is within range */
150 current
= current
< limit
? current
+ current
/ 2 : max_nodes
;
155 /* internal STACK storage allocation */
156 static int sk_reserve(OPENSSL_STACK
*st
, int n
, int exact
)
158 const void **tmpdata
;
161 /* Check to see the reservation isn't exceeding the hard limit */
162 if (n
> max_nodes
- st
->num
)
165 /* Figure out the new size */
166 num_alloc
= st
->num
+ n
;
167 if (num_alloc
< min_nodes
)
168 num_alloc
= min_nodes
;
170 /* If |st->data| allocation was postponed */
171 if (st
->data
== NULL
) {
173 * At this point, |st->num_alloc| and |st->num| are 0;
174 * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
176 if ((st
->data
= OPENSSL_zalloc(sizeof(void *) * num_alloc
)) == NULL
) {
177 /* STACKerr(STACK_F_SK_RESERVE, ERR_R_MALLOC_FAILURE); */
180 st
->num_alloc
= num_alloc
;
185 if (num_alloc
<= st
->num_alloc
)
187 num_alloc
= compute_growth(num_alloc
, st
->num_alloc
);
190 } else if (num_alloc
== st
->num_alloc
) {
194 tmpdata
= OPENSSL_realloc((void *)st
->data
, sizeof(void *) * num_alloc
);
199 st
->num_alloc
= num_alloc
;
203 OPENSSL_STACK
*OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c
, int n
)
205 OPENSSL_STACK
*st
= OPENSSL_zalloc(sizeof(OPENSSL_STACK
));
215 if (!sk_reserve(st
, n
, 1)) {
223 int OPENSSL_sk_reserve(OPENSSL_STACK
*st
, int n
)
230 return sk_reserve(st
, n
, 1);
233 int OPENSSL_sk_insert(OPENSSL_STACK
*st
, const void *data
, int loc
)
235 if (st
== NULL
|| st
->num
== max_nodes
)
238 if (!sk_reserve(st
, 1, 0))
241 if ((loc
>= st
->num
) || (loc
< 0)) {
242 st
->data
[st
->num
] = data
;
244 memmove(&st
->data
[loc
+ 1], &st
->data
[loc
],
245 sizeof(st
->data
[0]) * (st
->num
- loc
));
246 st
->data
[loc
] = data
;
253 static ossl_inline
void *internal_delete(OPENSSL_STACK
*st
, int loc
)
255 const void *ret
= st
->data
[loc
];
257 if (loc
!= st
->num
- 1)
258 memmove(&st
->data
[loc
], &st
->data
[loc
+ 1],
259 sizeof(st
->data
[0]) * (st
->num
- loc
- 1));
265 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK
*st
, const void *p
)
269 for (i
= 0; i
< st
->num
; i
++)
270 if (st
->data
[i
] == p
)
271 return internal_delete(st
, i
);
275 void *OPENSSL_sk_delete(OPENSSL_STACK
*st
, int loc
)
277 if (st
== NULL
|| loc
< 0 || loc
>= st
->num
)
280 return internal_delete(st
, loc
);
283 static int internal_find(OPENSSL_STACK
*st
, const void *data
,
289 if (st
== NULL
|| st
->num
== 0)
292 if (st
->comp
== NULL
) {
293 for (i
= 0; i
< st
->num
; i
++)
294 if (st
->data
[i
] == data
)
301 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
302 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
306 r
= OBJ_bsearch_ex_(&data
, st
->data
, st
->num
, sizeof(void *), st
->comp
,
309 return r
== NULL
? -1 : (int)((const void **)r
- st
->data
);
312 int OPENSSL_sk_find(OPENSSL_STACK
*st
, const void *data
)
314 return internal_find(st
, data
, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH
);
317 int OPENSSL_sk_find_ex(OPENSSL_STACK
*st
, const void *data
)
319 return internal_find(st
, data
, OBJ_BSEARCH_VALUE_ON_NOMATCH
);
322 int OPENSSL_sk_push(OPENSSL_STACK
*st
, const void *data
)
326 return OPENSSL_sk_insert(st
, data
, st
->num
);
329 int OPENSSL_sk_unshift(OPENSSL_STACK
*st
, const void *data
)
331 return OPENSSL_sk_insert(st
, data
, 0);
334 void *OPENSSL_sk_shift(OPENSSL_STACK
*st
)
336 if (st
== NULL
|| st
->num
== 0)
338 return internal_delete(st
, 0);
341 void *OPENSSL_sk_pop(OPENSSL_STACK
*st
)
343 if (st
== NULL
|| st
->num
== 0)
345 return internal_delete(st
, st
->num
- 1);
348 void OPENSSL_sk_zero(OPENSSL_STACK
*st
)
350 if (st
== NULL
|| st
->num
== 0)
352 memset(st
->data
, 0, sizeof(*st
->data
) * st
->num
);
356 void OPENSSL_sk_pop_free(OPENSSL_STACK
*st
, OPENSSL_sk_freefunc func
)
362 for (i
= 0; i
< st
->num
; i
++)
363 if (st
->data
[i
] != NULL
)
364 func((char *)st
->data
[i
]);
368 void OPENSSL_sk_free(OPENSSL_STACK
*st
)
372 OPENSSL_free(st
->data
);
376 int OPENSSL_sk_num(const OPENSSL_STACK
*st
)
378 return st
== NULL
? -1 : st
->num
;
381 void *OPENSSL_sk_value(const OPENSSL_STACK
*st
, int i
)
383 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
385 return (void *)st
->data
[i
];
388 void *OPENSSL_sk_set(OPENSSL_STACK
*st
, int i
, const void *data
)
390 if (st
== NULL
|| i
< 0 || i
>= st
->num
)
394 return (void *)st
->data
[i
];
397 void OPENSSL_sk_sort(OPENSSL_STACK
*st
)
399 if (st
!= NULL
&& !st
->sorted
&& st
->comp
!= NULL
) {
401 qsort(st
->data
, st
->num
, sizeof(void *), st
->comp
);
402 st
->sorted
= 1; /* empty or single-element stack is considered sorted */
406 int OPENSSL_sk_is_sorted(const OPENSSL_STACK
*st
)
408 return st
== NULL
? 1 : st
->sorted
;