]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
28428130 | 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
d02b48c6 | 3 | * |
4f22f405 RS |
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 | |
d02b48c6 | 8 | */ |
4f22f405 | 9 | |
d02b48c6 | 10 | #include <stdio.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
9205ebeb | 12 | #include "internal/numbers.h" |
ec577822 | 13 | #include <openssl/stack.h> |
d584fd6b | 14 | #include <openssl/objects.h> |
1b3e2bbf P |
15 | #include <errno.h> |
16 | #include <openssl/e_os2.h> /* For ossl_inline */ | |
17 | ||
18 | /* | |
19 | * The initial number of nodes in the array. | |
20 | */ | |
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 *)) | |
24 | : INT_MAX; | |
d02b48c6 | 25 | |
31c2b6ee DSH |
26 | struct stack_st { |
27 | int num; | |
1b3e2bbf | 28 | const void **data; |
31c2b6ee | 29 | int sorted; |
1b3e2bbf | 30 | int num_alloc; |
739a1eb1 | 31 | OPENSSL_sk_compfunc comp; |
31c2b6ee DSH |
32 | }; |
33 | ||
739a1eb1 RS |
34 | OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c) |
35 | { | |
36 | OPENSSL_sk_compfunc old = sk->comp; | |
eb90a483 | 37 | |
0f113f3e MC |
38 | if (sk->comp != c) |
39 | sk->sorted = 0; | |
40 | sk->comp = c; | |
eb90a483 | 41 | |
0f113f3e MC |
42 | return old; |
43 | } | |
d02b48c6 | 44 | |
c0c9c0c0 | 45 | OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk) |
0f113f3e | 46 | { |
739a1eb1 | 47 | OPENSSL_STACK *ret; |
9205ebeb | 48 | |
7e1445b0 F |
49 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) |
50 | return NULL; | |
51 | ||
52 | /* direct structure assignment */ | |
53 | *ret = *sk; | |
0f113f3e | 54 | |
8e8e507e F |
55 | if (sk->num == 0) { |
56 | /* postpone |ret->data| allocation */ | |
57 | ret->data = NULL; | |
58 | ret->num_alloc = 0; | |
59 | return ret; | |
60 | } | |
61 | /* duplicate |sk->data| content */ | |
7e1445b0 F |
62 | if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL) |
63 | goto err; | |
1b3e2bbf | 64 | memcpy(ret->data, sk->data, sizeof(void *) * sk->num); |
7e1445b0 | 65 | return ret; |
0f113f3e | 66 | err: |
739a1eb1 | 67 | OPENSSL_sk_free(ret); |
7e1445b0 | 68 | return NULL; |
0f113f3e MC |
69 | } |
70 | ||
c0c9c0c0 F |
71 | OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk, |
72 | OPENSSL_sk_copyfunc copy_func, | |
739a1eb1 | 73 | OPENSSL_sk_freefunc free_func) |
0f113f3e | 74 | { |
739a1eb1 | 75 | OPENSSL_STACK *ret; |
0f113f3e MC |
76 | int i; |
77 | ||
739a1eb1 | 78 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) |
7e1445b0 F |
79 | return NULL; |
80 | ||
81 | /* direct structure assignment */ | |
82 | *ret = *sk; | |
83 | ||
8e8e507e F |
84 | if (sk->num == 0) { |
85 | /* postpone |ret| data allocation */ | |
86 | ret->data = NULL; | |
87 | ret->num_alloc = 0; | |
88 | return ret; | |
89 | } | |
90 | ||
1b3e2bbf | 91 | ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes; |
7e1445b0 | 92 | ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc); |
0f113f3e MC |
93 | if (ret->data == NULL) { |
94 | OPENSSL_free(ret); | |
95 | return NULL; | |
96 | } | |
0f113f3e MC |
97 | |
98 | for (i = 0; i < ret->num; ++i) { | |
99 | if (sk->data[i] == NULL) | |
100 | continue; | |
101 | if ((ret->data[i] = copy_func(sk->data[i])) == NULL) { | |
102 | while (--i >= 0) | |
103 | if (ret->data[i] != NULL) | |
36639907 | 104 | free_func((void *)ret->data[i]); |
739a1eb1 | 105 | OPENSSL_sk_free(ret); |
0f113f3e MC |
106 | return NULL; |
107 | } | |
108 | } | |
109 | return ret; | |
110 | } | |
66d884f0 | 111 | |
739a1eb1 | 112 | OPENSSL_STACK *OPENSSL_sk_new_null(void) |
0f113f3e | 113 | { |
3ceab379 | 114 | return OPENSSL_sk_new_reserve(NULL, 0); |
0f113f3e MC |
115 | } |
116 | ||
739a1eb1 | 117 | OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) |
0f113f3e | 118 | { |
3ceab379 | 119 | return OPENSSL_sk_new_reserve(c, 0); |
0f113f3e | 120 | } |
d02b48c6 | 121 | |
1b3e2bbf P |
122 | /* |
123 | * Calculate the array growth based on the target size. | |
124 | * | |
8e8e507e | 125 | * The growth fraction is a rational number and is defined by a numerator |
1b3e2bbf P |
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...). | |
129 | * | |
8e8e507e | 130 | * We use 3/2 = 1.5 for simplicity of calculation and overflow checking. |
1b3e2bbf P |
131 | * Another option 8/5 = 1.6 allows for slightly faster growth, although safe |
132 | * computation is more difficult. | |
133 | * | |
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. | |
8e8e507e F |
137 | * |
138 | * Do not call it with |current| lower than 2, or it will infinitely loop. | |
1b3e2bbf P |
139 | */ |
140 | static ossl_inline int compute_growth(int target, int current) | |
0f113f3e | 141 | { |
1b3e2bbf P |
142 | const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0); |
143 | ||
144 | while (current < target) { | |
145 | /* Check to see if we're at the hard limit */ | |
146 | if (current >= max_nodes) | |
147 | return 0; | |
148 | ||
149 | /* Expand the size by a factor of 3/2 if it is within range */ | |
150 | current = current < limit ? current + current / 2 : max_nodes; | |
9731a9ce | 151 | } |
1b3e2bbf P |
152 | return current; |
153 | } | |
9731a9ce | 154 | |
8e8e507e | 155 | /* internal STACK storage allocation */ |
1b3e2bbf P |
156 | static int sk_reserve(OPENSSL_STACK *st, int n, int exact) |
157 | { | |
158 | const void **tmpdata; | |
159 | int num_alloc; | |
9731a9ce | 160 | |
1b3e2bbf P |
161 | /* Check to see the reservation isn't exceeding the hard limit */ |
162 | if (n > max_nodes - st->num) | |
163 | return 0; | |
9731a9ce | 164 | |
1b3e2bbf P |
165 | /* Figure out the new size */ |
166 | num_alloc = st->num + n; | |
167 | if (num_alloc < min_nodes) | |
168 | num_alloc = min_nodes; | |
9731a9ce | 169 | |
8e8e507e F |
170 | /* If |st->data| allocation was postponed */ |
171 | if (st->data == NULL) { | |
172 | /* | |
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|. | |
175 | */ | |
cdb10bae RS |
176 | if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL) { |
177 | /* STACKerr(STACK_F_SK_RESERVE, ERR_R_MALLOC_FAILURE); */ | |
8e8e507e | 178 | return 0; |
cdb10bae | 179 | } |
8e8e507e F |
180 | st->num_alloc = num_alloc; |
181 | return 1; | |
182 | } | |
183 | ||
1b3e2bbf P |
184 | if (!exact) { |
185 | if (num_alloc <= st->num_alloc) | |
186 | return 1; | |
187 | num_alloc = compute_growth(num_alloc, st->num_alloc); | |
188 | if (num_alloc == 0) | |
9205ebeb | 189 | return 0; |
1b3e2bbf P |
190 | } else if (num_alloc == st->num_alloc) { |
191 | return 1; | |
0f113f3e | 192 | } |
1b3e2bbf P |
193 | |
194 | tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc); | |
195 | if (tmpdata == NULL) | |
196 | return 0; | |
197 | ||
198 | st->data = tmpdata; | |
199 | st->num_alloc = num_alloc; | |
200 | return 1; | |
201 | } | |
202 | ||
3ceab379 PY |
203 | OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n) |
204 | { | |
205 | OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK)); | |
206 | ||
207 | if (st == NULL) | |
208 | return NULL; | |
209 | ||
210 | st->comp = c; | |
211 | ||
212 | if (n <= 0) | |
213 | return st; | |
214 | ||
215 | if (!sk_reserve(st, n, 1)) { | |
216 | OPENSSL_sk_free(st); | |
217 | return NULL; | |
218 | } | |
219 | ||
220 | return st; | |
221 | } | |
222 | ||
1b3e2bbf P |
223 | int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n) |
224 | { | |
fbb7b33b | 225 | if (st == NULL) |
1b3e2bbf P |
226 | return 0; |
227 | ||
228 | if (n < 0) | |
229 | return 1; | |
230 | return sk_reserve(st, n, 1); | |
231 | } | |
232 | ||
233 | int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc) | |
234 | { | |
fbb7b33b | 235 | if (st == NULL || st->num == max_nodes) |
1b3e2bbf P |
236 | return 0; |
237 | ||
238 | if (!sk_reserve(st, 1, 0)) | |
239 | return 0; | |
240 | ||
9205ebeb | 241 | if ((loc >= st->num) || (loc < 0)) { |
0f113f3e | 242 | st->data[st->num] = data; |
9205ebeb | 243 | } else { |
36639907 RS |
244 | memmove(&st->data[loc + 1], &st->data[loc], |
245 | sizeof(st->data[0]) * (st->num - loc)); | |
0f113f3e MC |
246 | st->data[loc] = data; |
247 | } | |
248 | st->num++; | |
249 | st->sorted = 0; | |
9205ebeb | 250 | return st->num; |
0f113f3e | 251 | } |
d02b48c6 | 252 | |
8e8e507e F |
253 | static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc) |
254 | { | |
255 | const void *ret = st->data[loc]; | |
256 | ||
257 | if (loc != st->num - 1) | |
258 | memmove(&st->data[loc], &st->data[loc + 1], | |
259 | sizeof(st->data[0]) * (st->num - loc - 1)); | |
260 | st->num--; | |
261 | ||
262 | return (void *)ret; | |
263 | } | |
264 | ||
4591e5fb | 265 | void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p) |
0f113f3e MC |
266 | { |
267 | int i; | |
d02b48c6 | 268 | |
0f113f3e MC |
269 | for (i = 0; i < st->num; i++) |
270 | if (st->data[i] == p) | |
8e8e507e | 271 | return internal_delete(st, i); |
4591e5fb | 272 | return NULL; |
0f113f3e | 273 | } |
d02b48c6 | 274 | |
739a1eb1 | 275 | void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc) |
0f113f3e | 276 | { |
9205ebeb | 277 | if (st == NULL || loc < 0 || loc >= st->num) |
0f113f3e MC |
278 | return NULL; |
279 | ||
8e8e507e | 280 | return internal_delete(st, loc); |
0f113f3e | 281 | } |
d02b48c6 | 282 | |
4591e5fb DSH |
283 | static int internal_find(OPENSSL_STACK *st, const void *data, |
284 | int ret_val_options) | |
0f113f3e | 285 | { |
36639907 | 286 | const void *r; |
0f113f3e MC |
287 | int i; |
288 | ||
8e8e507e | 289 | if (st == NULL || st->num == 0) |
0f113f3e MC |
290 | return -1; |
291 | ||
292 | if (st->comp == NULL) { | |
293 | for (i = 0; i < st->num; i++) | |
294 | if (st->data[i] == data) | |
fbb7b33b AP |
295 | return i; |
296 | return -1; | |
297 | } | |
298 | ||
299 | if (!st->sorted) { | |
300 | if (st->num > 1) | |
301 | qsort(st->data, st->num, sizeof(void *), st->comp); | |
302 | st->sorted = 1; /* empty or single-element stack is considered sorted */ | |
0f113f3e | 303 | } |
0f113f3e | 304 | if (data == NULL) |
fbb7b33b | 305 | return -1; |
0f113f3e MC |
306 | r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp, |
307 | ret_val_options); | |
fbb7b33b AP |
308 | |
309 | return r == NULL ? -1 : (int)((const void **)r - st->data); | |
0f113f3e | 310 | } |
26851b6b | 311 | |
4591e5fb | 312 | int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data) |
0f113f3e MC |
313 | { |
314 | return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH); | |
315 | } | |
316 | ||
4591e5fb | 317 | int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data) |
0f113f3e MC |
318 | { |
319 | return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH); | |
320 | } | |
d02b48c6 | 321 | |
36639907 | 322 | int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data) |
0f113f3e | 323 | { |
8e8e507e F |
324 | if (st == NULL) |
325 | return -1; | |
326 | return OPENSSL_sk_insert(st, data, st->num); | |
0f113f3e | 327 | } |
d02b48c6 | 328 | |
36639907 | 329 | int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data) |
0f113f3e | 330 | { |
fbb7b33b | 331 | return OPENSSL_sk_insert(st, data, 0); |
0f113f3e | 332 | } |
d02b48c6 | 333 | |
739a1eb1 | 334 | void *OPENSSL_sk_shift(OPENSSL_STACK *st) |
0f113f3e | 335 | { |
fbb7b33b | 336 | if (st == NULL || st->num == 0) |
8e8e507e F |
337 | return NULL; |
338 | return internal_delete(st, 0); | |
0f113f3e | 339 | } |
d02b48c6 | 340 | |
739a1eb1 | 341 | void *OPENSSL_sk_pop(OPENSSL_STACK *st) |
0f113f3e | 342 | { |
fbb7b33b | 343 | if (st == NULL || st->num == 0) |
8e8e507e F |
344 | return NULL; |
345 | return internal_delete(st, st->num - 1); | |
0f113f3e | 346 | } |
d02b48c6 | 347 | |
739a1eb1 | 348 | void OPENSSL_sk_zero(OPENSSL_STACK *st) |
0f113f3e | 349 | { |
fbb7b33b | 350 | if (st == NULL || st->num == 0) |
0f113f3e | 351 | return; |
16f8d4eb | 352 | memset(st->data, 0, sizeof(*st->data) * st->num); |
0f113f3e MC |
353 | st->num = 0; |
354 | } | |
355 | ||
739a1eb1 | 356 | void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func) |
0f113f3e MC |
357 | { |
358 | int i; | |
359 | ||
360 | if (st == NULL) | |
361 | return; | |
362 | for (i = 0; i < st->num; i++) | |
363 | if (st->data[i] != NULL) | |
36639907 | 364 | func((char *)st->data[i]); |
739a1eb1 | 365 | OPENSSL_sk_free(st); |
0f113f3e | 366 | } |
d02b48c6 | 367 | |
739a1eb1 | 368 | void OPENSSL_sk_free(OPENSSL_STACK *st) |
0f113f3e MC |
369 | { |
370 | if (st == NULL) | |
371 | return; | |
b548a1f1 | 372 | OPENSSL_free(st->data); |
0f113f3e MC |
373 | OPENSSL_free(st); |
374 | } | |
d02b48c6 | 375 | |
739a1eb1 | 376 | int OPENSSL_sk_num(const OPENSSL_STACK *st) |
e84240d4 | 377 | { |
fbb7b33b | 378 | return st == NULL ? -1 : st->num; |
e84240d4 DSH |
379 | } |
380 | ||
739a1eb1 | 381 | void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i) |
e84240d4 | 382 | { |
739a1eb1 | 383 | if (st == NULL || i < 0 || i >= st->num) |
0f113f3e | 384 | return NULL; |
36639907 | 385 | return (void *)st->data[i]; |
e84240d4 DSH |
386 | } |
387 | ||
36639907 | 388 | void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data) |
e84240d4 | 389 | { |
739a1eb1 | 390 | if (st == NULL || i < 0 || i >= st->num) |
0f113f3e | 391 | return NULL; |
36639907 | 392 | st->data[i] = data; |
fbb7b33b | 393 | st->sorted = 0; |
36639907 | 394 | return (void *)st->data[i]; |
e84240d4 | 395 | } |
ee8ba0b2 | 396 | |
739a1eb1 | 397 | void OPENSSL_sk_sort(OPENSSL_STACK *st) |
0f113f3e | 398 | { |
fbb7b33b AP |
399 | if (st != NULL && !st->sorted && st->comp != NULL) { |
400 | if (st->num > 1) | |
8e8e507e | 401 | qsort(st->data, st->num, sizeof(void *), st->comp); |
fbb7b33b | 402 | st->sorted = 1; /* empty or single-element stack is considered sorted */ |
0f113f3e MC |
403 | } |
404 | } | |
2f605e8d | 405 | |
739a1eb1 | 406 | int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st) |
0f113f3e | 407 | { |
fbb7b33b | 408 | return st == NULL ? 1 : st->sorted; |
0f113f3e | 409 | } |