test/recipes/81-test_cmp_cli.t: use app() rather than cmd()
[openssl.git] / crypto / stack / stack.c
1 /*
2  * Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved.
3  *
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
8  */
9
10 #include <stdio.h>
11 #include "internal/cryptlib.h"
12 #include "internal/numbers.h"
13 #include <openssl/stack.h>
14 #include <errno.h>
15 #include <openssl/e_os2.h>      /* For ossl_inline */
16
17 /*
18  * The initial number of nodes in the array.
19  */
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 *))
23                              : INT_MAX;
24
25 struct stack_st {
26     int num;
27     const void **data;
28     int sorted;
29     int num_alloc;
30     OPENSSL_sk_compfunc comp;
31 };
32
33 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
34 {
35     OPENSSL_sk_compfunc old = sk->comp;
36
37     if (sk->comp != c)
38         sk->sorted = 0;
39     sk->comp = c;
40
41     return old;
42 }
43
44 OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
45 {
46     OPENSSL_STACK *ret;
47
48     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
49         goto err;
50
51     if (sk == NULL) {
52         ret->num = 0;
53         ret->sorted = 0;
54         ret->comp = NULL;
55     } else {
56         /* direct structure assignment */
57         *ret = *sk;
58     }
59
60     if (sk == NULL || sk->num == 0) {
61         /* postpone |ret->data| allocation */
62         ret->data = NULL;
63         ret->num_alloc = 0;
64         return ret;
65     }
66
67     /* duplicate |sk->data| content */
68     if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)
69         goto err;
70     memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
71     return ret;
72
73  err:
74     ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
75     OPENSSL_sk_free(ret);
76     return NULL;
77 }
78
79 OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
80                              OPENSSL_sk_copyfunc copy_func,
81                              OPENSSL_sk_freefunc free_func)
82 {
83     OPENSSL_STACK *ret;
84     int i;
85
86     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
87         goto err;
88
89     if (sk == NULL) {
90         ret->num = 0;
91         ret->sorted = 0;
92         ret->comp = NULL;
93     } else {
94         /* direct structure assignment */
95         *ret = *sk;
96     }
97
98     if (sk == NULL || sk->num == 0) {
99         /* postpone |ret| data allocation */
100         ret->data = NULL;
101         ret->num_alloc = 0;
102         return ret;
103     }
104
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)
108         goto err;
109
110     for (i = 0; i < ret->num; ++i) {
111         if (sk->data[i] == NULL)
112             continue;
113         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
114             while (--i >= 0)
115                 if (ret->data[i] != NULL)
116                     free_func((void *)ret->data[i]);
117             goto err;
118         }
119     }
120     return ret;
121
122  err:
123     ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
124     OPENSSL_sk_free(ret);
125     return NULL;
126 }
127
128 OPENSSL_STACK *OPENSSL_sk_new_null(void)
129 {
130     return OPENSSL_sk_new_reserve(NULL, 0);
131 }
132
133 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
134 {
135     return OPENSSL_sk_new_reserve(c, 0);
136 }
137
138 /*
139  * Calculate the array growth based on the target size.
140  *
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...).
145  *
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.
149  *
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.
153  *
154  * Do not call it with |current| lower than 2, or it will infinitely loop.
155  */
156 static ossl_inline int compute_growth(int target, int current)
157 {
158     const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0);
159
160     while (current < target) {
161         /* Check to see if we're at the hard limit */
162         if (current >= max_nodes)
163             return 0;
164
165         /* Expand the size by a factor of 3/2 if it is within range */
166         current = current < limit ? current + current / 2 : max_nodes;
167     }
168     return current;
169 }
170
171 /* internal STACK storage allocation */
172 static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
173 {
174     const void **tmpdata;
175     int num_alloc;
176
177     /* Check to see the reservation isn't exceeding the hard limit */
178     if (n > max_nodes - st->num)
179         return 0;
180
181     /* Figure out the new size */
182     num_alloc = st->num + n;
183     if (num_alloc < min_nodes)
184         num_alloc = min_nodes;
185
186     /* If |st->data| allocation was postponed */
187     if (st->data == NULL) {
188         /*
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|.
191          */
192         if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL) {
193             ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
194             return 0;
195         }
196         st->num_alloc = num_alloc;
197         return 1;
198     }
199
200     if (!exact) {
201         if (num_alloc <= st->num_alloc)
202             return 1;
203         num_alloc = compute_growth(num_alloc, st->num_alloc);
204         if (num_alloc == 0)
205             return 0;
206     } else if (num_alloc == st->num_alloc) {
207         return 1;
208     }
209
210     tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc);
211     if (tmpdata == NULL)
212         return 0;
213
214     st->data = tmpdata;
215     st->num_alloc = num_alloc;
216     return 1;
217 }
218
219 OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
220 {
221     OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
222
223     if (st == NULL)
224         return NULL;
225
226     st->comp = c;
227
228     if (n <= 0)
229         return st;
230
231     if (!sk_reserve(st, n, 1)) {
232         OPENSSL_sk_free(st);
233         return NULL;
234     }
235
236     return st;
237 }
238
239 int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
240 {
241     if (st == NULL)
242         return 0;
243
244     if (n < 0)
245         return 1;
246     return sk_reserve(st, n, 1);
247 }
248
249 int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
250 {
251     if (st == NULL || st->num == max_nodes)
252         return 0;
253
254     if (!sk_reserve(st, 1, 0))
255         return 0;
256
257     if ((loc >= st->num) || (loc < 0)) {
258         st->data[st->num] = data;
259     } else {
260         memmove(&st->data[loc + 1], &st->data[loc],
261                 sizeof(st->data[0]) * (st->num - loc));
262         st->data[loc] = data;
263     }
264     st->num++;
265     st->sorted = 0;
266     return st->num;
267 }
268
269 static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc)
270 {
271     const void *ret = st->data[loc];
272
273     if (loc != st->num - 1)
274          memmove(&st->data[loc], &st->data[loc + 1],
275                  sizeof(st->data[0]) * (st->num - loc - 1));
276     st->num--;
277
278     return (void *)ret;
279 }
280
281 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
282 {
283     int i;
284
285     for (i = 0; i < st->num; i++)
286         if (st->data[i] == p)
287             return internal_delete(st, i);
288     return NULL;
289 }
290
291 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
292 {
293     if (st == NULL || loc < 0 || loc >= st->num)
294         return NULL;
295
296     return internal_delete(st, loc);
297 }
298
299 static int internal_find(OPENSSL_STACK *st, const void *data,
300                          int ret_val_options, int *pnum)
301 {
302     const void *r;
303     int i;
304
305     if (st == NULL || st->num == 0)
306         return -1;
307
308     if (st->comp == NULL) {
309         for (i = 0; i < st->num; i++)
310             if (st->data[i] == data) {
311                 if (pnum != NULL)
312                     *pnum = 1;
313                 return i;
314             }
315         if (pnum != NULL)
316             *pnum = 0;
317         return -1;
318     }
319
320     if (!st->sorted) {
321         if (st->num > 1)
322             qsort(st->data, st->num, sizeof(void *), st->comp);
323         st->sorted = 1; /* empty or single-element stack is considered sorted */
324     }
325     if (data == NULL)
326         return -1;
327     if (pnum != NULL)
328         ret_val_options |= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
329     r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
330                      ret_val_options);
331
332     if (pnum != NULL) {
333         *pnum = 0;
334         if (r != NULL) {
335             const void **p = (const void **)r;
336
337             while (p < st->data + st->num) {
338                 if (st->comp(&data, p) != 0)
339                     break;
340                 ++*pnum;
341                 ++p;
342             }
343         }
344     }
345
346     return r == NULL ? -1 : (int)((const void **)r - st->data);
347 }
348
349 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
350 {
351     return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
352 }
353
354 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
355 {
356     return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
357 }
358
359 int OPENSSL_sk_find_all(OPENSSL_STACK *st, const void *data, int *pnum)
360 {
361     return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
362 }
363
364 int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
365 {
366     if (st == NULL)
367         return -1;
368     return OPENSSL_sk_insert(st, data, st->num);
369 }
370
371 int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
372 {
373     return OPENSSL_sk_insert(st, data, 0);
374 }
375
376 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
377 {
378     if (st == NULL || st->num == 0)
379         return NULL;
380     return internal_delete(st, 0);
381 }
382
383 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
384 {
385     if (st == NULL || st->num == 0)
386         return NULL;
387     return internal_delete(st, st->num - 1);
388 }
389
390 void OPENSSL_sk_zero(OPENSSL_STACK *st)
391 {
392     if (st == NULL || st->num == 0)
393         return;
394     memset(st->data, 0, sizeof(*st->data) * st->num);
395     st->num = 0;
396 }
397
398 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
399 {
400     int i;
401
402     if (st == NULL)
403         return;
404     for (i = 0; i < st->num; i++)
405         if (st->data[i] != NULL)
406             func((char *)st->data[i]);
407     OPENSSL_sk_free(st);
408 }
409
410 void OPENSSL_sk_free(OPENSSL_STACK *st)
411 {
412     if (st == NULL)
413         return;
414     OPENSSL_free(st->data);
415     OPENSSL_free(st);
416 }
417
418 int OPENSSL_sk_num(const OPENSSL_STACK *st)
419 {
420     return st == NULL ? -1 : st->num;
421 }
422
423 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
424 {
425     if (st == NULL || i < 0 || i >= st->num)
426         return NULL;
427     return (void *)st->data[i];
428 }
429
430 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
431 {
432     if (st == NULL || i < 0 || i >= st->num)
433         return NULL;
434     st->data[i] = data;
435     st->sorted = 0;
436     return (void *)st->data[i];
437 }
438
439 void OPENSSL_sk_sort(OPENSSL_STACK *st)
440 {
441     if (st != NULL && !st->sorted && st->comp != NULL) {
442         if (st->num > 1)
443             qsort(st->data, st->num, sizeof(void *), st->comp);
444         st->sorted = 1; /* empty or single-element stack is considered sorted */
445     }
446 }
447
448 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
449 {
450     return st == NULL ? 1 : st->sorted;
451 }