1/*
2 * Copyright 1995-2018 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 */
20static const int min_nodes = 4;
21static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
22 ? (int)(SIZE_MAX / sizeof(void *))
23 : INT_MAX;
24
25struct stack_st {
26 int num;
27 const void **data;
28 int sorted;
29 int num_alloc;
30 OPENSSL_sk_compfunc comp;
31};
32
33OPENSSL_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
44OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
45{
46 OPENSSL_STACK *ret;
47
48 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
49 CRYPTOerr(CRYPTO_F_OPENSSL_SK_DUP, ERR_R_MALLOC_FAILURE);
50 return NULL;
51 }
52
53 /* direct structure assignment */
54 *ret = *sk;
55
56 if (sk->num == 0) {
57 /* postpone |ret->data| allocation */
58 ret->data = NULL;
59 ret->num_alloc = 0;
60 return ret;
61 }
62 /* duplicate |sk->data| content */
63 if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)
64 goto err;
65 memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
66 return ret;
67 err:
68 OPENSSL_sk_free(ret);
69 return NULL;
70}
71
72OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
73 OPENSSL_sk_copyfunc copy_func,
74 OPENSSL_sk_freefunc free_func)
75{
76 OPENSSL_STACK *ret;
77 int i;
78
79 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
80 CRYPTOerr(CRYPTO_F_OPENSSL_SK_DEEP_COPY, ERR_R_MALLOC_FAILURE);
81 return NULL;
82 }
83
84 /* direct structure assignment */
85 *ret = *sk;
86
87 if (sk->num == 0) {
88 /* postpone |ret| data allocation */
89 ret->data = NULL;
90 ret->num_alloc = 0;
91 return ret;
92 }
93
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) {
97 OPENSSL_free(ret);
98 return NULL;
99 }
100
101 for (i = 0; i < ret->num; ++i) {
102 if (sk->data[i] == NULL)
103 continue;
104 if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
105 while (--i >= 0)
106 if (ret->data[i] != NULL)
107 free_func((void *)ret->data[i]);
108 OPENSSL_sk_free(ret);
109 return NULL;
110 }
111 }
112 return ret;
113}
114
115OPENSSL_STACK *OPENSSL_sk_new_null(void)
116{
117 return OPENSSL_sk_new_reserve(NULL, 0);
118}
119
120OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
121{
122 return OPENSSL_sk_new_reserve(c, 0);
123}
124
125/*
126 * Calculate the array growth based on the target size.
127 *
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...).
132 *
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.
136 *
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.
140 *
141 * Do not call it with |current| lower than 2, or it will infinitely loop.
142 */
143static ossl_inline int compute_growth(int target, int current)
144{
145 const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0);
146
147 while (current < target) {
148 /* Check to see if we're at the hard limit */
149 if (current >= max_nodes)
150 return 0;
151
152 /* Expand the size by a factor of 3/2 if it is within range */
153 current = current < limit ? current + current / 2 : max_nodes;
154 }
155 return current;
156}
157
158/* internal STACK storage allocation */
159static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
160{
161 const void **tmpdata;
162 int num_alloc;
163
164 /* Check to see the reservation isn't exceeding the hard limit */
165 if (n > max_nodes - st->num)
166 return 0;
167
168 /* Figure out the new size */
169 num_alloc = st->num + n;
170 if (num_alloc < min_nodes)
171 num_alloc = min_nodes;
172
173 /* If |st->data| allocation was postponed */
174 if (st->data == NULL) {
175 /*
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|.
178 */
179 if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL) {
180 CRYPTOerr(CRYPTO_F_SK_RESERVE, ERR_R_MALLOC_FAILURE);
181 return 0;
182 }
183 st->num_alloc = num_alloc;
184 return 1;
185 }
186
187 if (!exact) {
188 if (num_alloc <= st->num_alloc)
189 return 1;
190 num_alloc = compute_growth(num_alloc, st->num_alloc);
191 if (num_alloc == 0)
192 return 0;
193 } else if (num_alloc == st->num_alloc) {
194 return 1;
195 }
196
197 tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc);
198 if (tmpdata == NULL)
199 return 0;
200
201 st->data = tmpdata;
202 st->num_alloc = num_alloc;
203 return 1;
204}
205
206OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
207{
208 OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
209
210 if (st == NULL)
211 return NULL;
212
213 st->comp = c;
214
215 if (n <= 0)
216 return st;
217
218 if (!sk_reserve(st, n, 1)) {
219 OPENSSL_sk_free(st);
220 return NULL;
221 }
222
223 return st;
224}
225
226int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
227{
228 if (st == NULL)
229 return 0;
230
231 if (n < 0)
232 return 1;
233 return sk_reserve(st, n, 1);
234}
235
236int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
237{
238 if (st == NULL || st->num == max_nodes)
239 return 0;
240
241 if (!sk_reserve(st, 1, 0))
242 return 0;
243
244 if ((loc >= st->num) || (loc < 0)) {
245 st->data[st->num] = data;
246 } else {
247 memmove(&st->data[loc + 1], &st->data[loc],
248 sizeof(st->data[0]) * (st->num - loc));
249 st->data[loc] = data;
250 }
251 st->num++;
252 st->sorted = 0;
253 return st->num;
254}
255
256static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc)
257{
258 const void *ret = st->data[loc];
259
260 if (loc != st->num - 1)
261 memmove(&st->data[loc], &st->data[loc + 1],
262 sizeof(st->data[0]) * (st->num - loc - 1));
263 st->num--;
264
265 return (void *)ret;
266}
267
268void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
269{
270 int i;
271
272 for (i = 0; i < st->num; i++)
273 if (st->data[i] == p)
274 return internal_delete(st, i);
275 return NULL;
276}
277
278void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
279{
280 if (st == NULL || loc < 0 || loc >= st->num)
281 return NULL;
282
283 return internal_delete(st, loc);
284}
285
286static int internal_find(OPENSSL_STACK *st, const void *data,
287 int ret_val_options)
288{
289 const void *r;
290 int i;
291
292 if (st == NULL || st->num == 0)
293 return -1;
294
295 if (st->comp == NULL) {
296 for (i = 0; i < st->num; i++)
297 if (st->data[i] == data)
298 return i;
299 return -1;
300 }
301
302 if (!st->sorted) {
303 if (st->num > 1)
304 qsort(st->data, st->num, sizeof(void *), st->comp);
305 st->sorted = 1; /* empty or single-element stack is considered sorted */
306 }
307 if (data == NULL)
308 return -1;
309 r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
310 ret_val_options);
311
312 return r == NULL ? -1 : (int)((const void **)r - st->data);
313}
314
315int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
316{
317 return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH);
318}
319
320int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
321{
322 return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH);
323}
324
325int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
326{
327 if (st == NULL)
328 return -1;
329 return OPENSSL_sk_insert(st, data, st->num);
330}
331
332int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
333{
334 return OPENSSL_sk_insert(st, data, 0);
335}
336
337void *OPENSSL_sk_shift(OPENSSL_STACK *st)
338{
339 if (st == NULL || st->num == 0)
340 return NULL;
341 return internal_delete(st, 0);
342}
343
344void *OPENSSL_sk_pop(OPENSSL_STACK *st)
345{
346 if (st == NULL || st->num == 0)
347 return NULL;
348 return internal_delete(st, st->num - 1);
349}
350
351void OPENSSL_sk_zero(OPENSSL_STACK *st)
352{
353 if (st == NULL || st->num == 0)
354 return;
355 memset(st->data, 0, sizeof(*st->data) * st->num);
356 st->num = 0;
357}
358
359void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
360{
361 int i;
362
363 if (st == NULL)
364 return;
365 for (i = 0; i < st->num; i++)
366 if (st->data[i] != NULL)
367 func((char *)st->data[i]);
368 OPENSSL_sk_free(st);
369}
370
371void OPENSSL_sk_free(OPENSSL_STACK *st)
372{
373 if (st == NULL)
374 return;
375 OPENSSL_free(st->data);
376 OPENSSL_free(st);
377}
378
379int OPENSSL_sk_num(const OPENSSL_STACK *st)
380{
381 return st == NULL ? -1 : st->num;
382}
383
384void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
385{
386 if (st == NULL || i < 0 || i >= st->num)
387 return NULL;
388 return (void *)st->data[i];
389}
390
391void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
392{
393 if (st == NULL || i < 0 || i >= st->num)
394 return NULL;
395 st->data[i] = data;
396 st->sorted = 0;
397 return (void *)st->data[i];
398}
399
400void OPENSSL_sk_sort(OPENSSL_STACK *st)
401{
402 if (st != NULL && !st->sorted && st->comp != NULL) {
403 if (st->num > 1)
404 qsort(st->data, st->num, sizeof(void *), st->comp);
405 st->sorted = 1; /* empty or single-element stack is considered sorted */
406 }
407}
408
409int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
410{
411 return st == NULL ? 1 : st->sorted;
412}
413