1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.] */
56
57#include <openssl/stack.h>
58
59#include <assert.h>
60#include <string.h>
61
62#include <openssl/mem.h>
63
64#include "../internal.h"
65
66
67// kMinSize is the number of pointers that will be initially allocated in a new
68// stack.
69static const size_t kMinSize = 4;
70
71_STACK *sk_new(stack_cmp_func comp) {
72 _STACK *ret;
73
74 ret = OPENSSL_malloc(sizeof(_STACK));
75 if (ret == NULL) {
76 goto err;
77 }
78 OPENSSL_memset(ret, 0, sizeof(_STACK));
79
80 ret->data = OPENSSL_malloc(sizeof(void *) * kMinSize);
81 if (ret->data == NULL) {
82 goto err;
83 }
84
85 OPENSSL_memset(ret->data, 0, sizeof(void *) * kMinSize);
86
87 ret->comp = comp;
88 ret->num_alloc = kMinSize;
89
90 return ret;
91
92err:
93 OPENSSL_free(ret);
94 return NULL;
95}
96
97_STACK *sk_new_null(void) { return sk_new(NULL); }
98
99size_t sk_num(const _STACK *sk) {
100 if (sk == NULL) {
101 return 0;
102 }
103 return sk->num;
104}
105
106void sk_zero(_STACK *sk) {
107 if (sk == NULL || sk->num == 0) {
108 return;
109 }
110 OPENSSL_memset(sk->data, 0, sizeof(void*) * sk->num);
111 sk->num = 0;
112 sk->sorted = 0;
113}
114
115void *sk_value(const _STACK *sk, size_t i) {
116 if (!sk || i >= sk->num) {
117 return NULL;
118 }
119 return sk->data[i];
120}
121
122void *sk_set(_STACK *sk, size_t i, void *value) {
123 if (!sk || i >= sk->num) {
124 return NULL;
125 }
126 return sk->data[i] = value;
127}
128
129void sk_free(_STACK *sk) {
130 if (sk == NULL) {
131 return;
132 }
133 OPENSSL_free(sk->data);
134 OPENSSL_free(sk);
135}
136
137void sk_pop_free_ex(_STACK *sk, void (*call_free_func)(stack_free_func, void *),
138 stack_free_func free_func) {
139 if (sk == NULL) {
140 return;
141 }
142
143 for (size_t i = 0; i < sk->num; i++) {
144 if (sk->data[i] != NULL) {
145 call_free_func(free_func, sk->data[i]);
146 }
147 }
148 sk_free(sk);
149}
150
151// Historically, |sk_pop_free| called the function as |stack_free_func|
152// directly. This is undefined in C. Some callers called |sk_pop_free| directly,
153// so we must maintain a compatibility version for now.
154static void call_free_func_legacy(stack_free_func func, void *ptr) {
155 func(ptr);
156}
157
158void sk_pop_free(_STACK *sk, stack_free_func free_func) {
159 sk_pop_free_ex(sk, call_free_func_legacy, free_func);
160}
161
162size_t sk_insert(_STACK *sk, void *p, size_t where) {
163 if (sk == NULL) {
164 return 0;
165 }
166
167 if (sk->num_alloc <= sk->num + 1) {
168 // Attempt to double the size of the array.
169 size_t new_alloc = sk->num_alloc << 1;
170 size_t alloc_size = new_alloc * sizeof(void *);
171 void **data;
172
173 // If the doubling overflowed, try to increment.
174 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) {
175 new_alloc = sk->num_alloc + 1;
176 alloc_size = new_alloc * sizeof(void *);
177 }
178
179 // If the increment also overflowed, fail.
180 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) {
181 return 0;
182 }
183
184 data = OPENSSL_realloc(sk->data, alloc_size);
185 if (data == NULL) {
186 return 0;
187 }
188
189 sk->data = data;
190 sk->num_alloc = new_alloc;
191 }
192
193 if (where >= sk->num) {
194 sk->data[sk->num] = p;
195 } else {
196 OPENSSL_memmove(&sk->data[where + 1], &sk->data[where],
197 sizeof(void *) * (sk->num - where));
198 sk->data[where] = p;
199 }
200
201 sk->num++;
202 sk->sorted = 0;
203
204 return sk->num;
205}
206
207void *sk_delete(_STACK *sk, size_t where) {
208 void *ret;
209
210 if (!sk || where >= sk->num) {
211 return NULL;
212 }
213
214 ret = sk->data[where];
215
216 if (where != sk->num - 1) {
217 OPENSSL_memmove(&sk->data[where], &sk->data[where + 1],
218 sizeof(void *) * (sk->num - where - 1));
219 }
220
221 sk->num--;
222 return ret;
223}
224
225void *sk_delete_ptr(_STACK *sk, const void *p) {
226 if (sk == NULL) {
227 return NULL;
228 }
229
230 for (size_t i = 0; i < sk->num; i++) {
231 if (sk->data[i] == p) {
232 return sk_delete(sk, i);
233 }
234 }
235
236 return NULL;
237}
238
239int sk_find(const _STACK *sk, size_t *out_index, const void *p,
240 int (*call_cmp_func)(stack_cmp_func, const void **,
241 const void **)) {
242 if (sk == NULL) {
243 return 0;
244 }
245
246 if (sk->comp == NULL) {
247 // Use pointer equality when no comparison function has been set.
248 for (size_t i = 0; i < sk->num; i++) {
249 if (sk->data[i] == p) {
250 if (out_index) {
251 *out_index = i;
252 }
253 return 1;
254 }
255 }
256 return 0;
257 }
258
259 if (p == NULL) {
260 return 0;
261 }
262
263 if (!sk_is_sorted(sk)) {
264 for (size_t i = 0; i < sk->num; i++) {
265 const void *elem = sk->data[i];
266 if (call_cmp_func(sk->comp, &p, &elem) == 0) {
267 if (out_index) {
268 *out_index = i;
269 }
270 return 1;
271 }
272 }
273 return 0;
274 }
275
276 // The stack is sorted, so binary search to find the element.
277 //
278 // |lo| and |hi| maintain a half-open interval of where the answer may be. All
279 // indices such that |lo <= idx < hi| are candidates.
280 size_t lo = 0, hi = sk->num;
281 while (lo < hi) {
282 // Bias |mid| towards |lo|. See the |r == 0| case below.
283 size_t mid = lo + (hi - lo - 1) / 2;
284 assert(lo <= mid && mid < hi);
285 const void *elem = sk->data[mid];
286 int r = call_cmp_func(sk->comp, &p, &elem);
287 if (r > 0) {
288 lo = mid + 1; // |mid| is too low.
289 } else if (r < 0) {
290 hi = mid; // |mid| is too high.
291 } else {
292 // |mid| matches. However, this function returns the earliest match, so we
293 // can only return if the range has size one.
294 if (hi - lo == 1) {
295 if (out_index != NULL) {
296 *out_index = mid;
297 }
298 return 1;
299 }
300 // The sample is biased towards |lo|. |mid| can only be |hi - 1| if
301 // |hi - lo| was one, so this makes forward progress.
302 assert(mid + 1 < hi);
303 hi = mid + 1;
304 }
305 }
306
307 assert(lo == hi);
308 return 0; // Not found.
309}
310
311void *sk_shift(_STACK *sk) {
312 if (sk == NULL) {
313 return NULL;
314 }
315 if (sk->num == 0) {
316 return NULL;
317 }
318 return sk_delete(sk, 0);
319}
320
321size_t sk_push(_STACK *sk, void *p) { return (sk_insert(sk, p, sk->num)); }
322
323void *sk_pop(_STACK *sk) {
324 if (sk == NULL) {
325 return NULL;
326 }
327 if (sk->num == 0) {
328 return NULL;
329 }
330 return sk_delete(sk, sk->num - 1);
331}
332
333_STACK *sk_dup(const _STACK *sk) {
334 _STACK *ret;
335 void **s;
336
337 if (sk == NULL) {
338 return NULL;
339 }
340
341 ret = sk_new(sk->comp);
342 if (ret == NULL) {
343 goto err;
344 }
345
346 s = (void **)OPENSSL_realloc(ret->data, sizeof(void *) * sk->num_alloc);
347 if (s == NULL) {
348 goto err;
349 }
350 ret->data = s;
351
352 ret->num = sk->num;
353 OPENSSL_memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
354 ret->sorted = sk->sorted;
355 ret->num_alloc = sk->num_alloc;
356 ret->comp = sk->comp;
357 return ret;
358
359err:
360 sk_free(ret);
361 return NULL;
362}
363
364void sk_sort(_STACK *sk) {
365 if (sk == NULL || sk->comp == NULL || sk->sorted) {
366 return;
367 }
368
369 // sk->comp is a function that takes pointers to pointers to elements, but
370 // qsort take a comparison function that just takes pointers to elements.
371 // However, since we're passing an array of pointers to qsort, we can just
372 // cast the comparison function and everything works.
373 //
374 // TODO(davidben): This is undefined behavior, but the call is in libc so,
375 // e.g., CFI does not notice. Unfortunately, |qsort| is missing a void*
376 // parameter in its callback and |qsort_s| / |qsort_r| are a mess of
377 // incompatibility.
378 if (sk->num >= 2) {
379 int (*comp_func)(const void *, const void *) =
380 (int (*)(const void *, const void *))(sk->comp);
381 qsort(sk->data, sk->num, sizeof(void *), comp_func);
382 }
383 sk->sorted = 1;
384}
385
386int sk_is_sorted(const _STACK *sk) {
387 if (!sk) {
388 return 1;
389 }
390 return sk->sorted;
391}
392
393stack_cmp_func sk_set_cmp_func(_STACK *sk, stack_cmp_func comp) {
394 stack_cmp_func old = sk->comp;
395
396 if (sk->comp != comp) {
397 sk->sorted = 0;
398 }
399 sk->comp = comp;
400
401 return old;
402}
403
404_STACK *sk_deep_copy(const _STACK *sk,
405 void *(*call_copy_func)(stack_copy_func, void *),
406 stack_copy_func copy_func,
407 void (*call_free_func)(stack_free_func, void *),
408 stack_free_func free_func) {
409 _STACK *ret = sk_dup(sk);
410 if (ret == NULL) {
411 return NULL;
412 }
413
414 for (size_t i = 0; i < ret->num; i++) {
415 if (ret->data[i] == NULL) {
416 continue;
417 }
418 ret->data[i] = call_copy_func(copy_func, ret->data[i]);
419 if (ret->data[i] == NULL) {
420 for (size_t j = 0; j < i; j++) {
421 if (ret->data[j] != NULL) {
422 call_free_func(free_func, ret->data[j]);
423 }
424 }
425 sk_free(ret);
426 return NULL;
427 }
428 }
429
430 return ret;
431}
432