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 <string.h>
60
61 #include <openssl/mem.h>
62
63 #include "../internal.h"
64
65
66 // kMinSize is the number of pointers that will be initially allocated in a new
67 // stack.
68 static const size_t kMinSize = 4;
69
sk_new(stack_cmp_func comp)70 _STACK *sk_new(stack_cmp_func comp) {
71 _STACK *ret;
72
73 ret = OPENSSL_malloc(sizeof(_STACK));
74 if (ret == NULL) {
75 goto err;
76 }
77 OPENSSL_memset(ret, 0, sizeof(_STACK));
78
79 ret->data = OPENSSL_malloc(sizeof(void *) * kMinSize);
80 if (ret->data == NULL) {
81 goto err;
82 }
83
84 OPENSSL_memset(ret->data, 0, sizeof(void *) * kMinSize);
85
86 ret->comp = comp;
87 ret->num_alloc = kMinSize;
88
89 return ret;
90
91 err:
92 OPENSSL_free(ret);
93 return NULL;
94 }
95
sk_new_null(void)96 _STACK *sk_new_null(void) { return sk_new(NULL); }
97
sk_num(const _STACK * sk)98 size_t sk_num(const _STACK *sk) {
99 if (sk == NULL) {
100 return 0;
101 }
102 return sk->num;
103 }
104
sk_zero(_STACK * sk)105 void sk_zero(_STACK *sk) {
106 if (sk == NULL || sk->num == 0) {
107 return;
108 }
109 OPENSSL_memset(sk->data, 0, sizeof(void*) * sk->num);
110 sk->num = 0;
111 sk->sorted = 0;
112 }
113
sk_value(const _STACK * sk,size_t i)114 void *sk_value(const _STACK *sk, size_t i) {
115 if (!sk || i >= sk->num) {
116 return NULL;
117 }
118 return sk->data[i];
119 }
120
sk_set(_STACK * sk,size_t i,void * value)121 void *sk_set(_STACK *sk, size_t i, void *value) {
122 if (!sk || i >= sk->num) {
123 return NULL;
124 }
125 return sk->data[i] = value;
126 }
127
sk_free(_STACK * sk)128 void sk_free(_STACK *sk) {
129 if (sk == NULL) {
130 return;
131 }
132 OPENSSL_free(sk->data);
133 OPENSSL_free(sk);
134 }
135
sk_pop_free(_STACK * sk,void (* func)(void *))136 void sk_pop_free(_STACK *sk, void (*func)(void *)) {
137 if (sk == NULL) {
138 return;
139 }
140
141 for (size_t i = 0; i < sk->num; i++) {
142 if (sk->data[i] != NULL) {
143 func(sk->data[i]);
144 }
145 }
146 sk_free(sk);
147 }
148
sk_insert(_STACK * sk,void * p,size_t where)149 size_t sk_insert(_STACK *sk, void *p, size_t where) {
150 if (sk == NULL) {
151 return 0;
152 }
153
154 if (sk->num_alloc <= sk->num + 1) {
155 // Attempt to double the size of the array.
156 size_t new_alloc = sk->num_alloc << 1;
157 size_t alloc_size = new_alloc * sizeof(void *);
158 void **data;
159
160 // If the doubling overflowed, try to increment.
161 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) {
162 new_alloc = sk->num_alloc + 1;
163 alloc_size = new_alloc * sizeof(void *);
164 }
165
166 // If the increment also overflowed, fail.
167 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) {
168 return 0;
169 }
170
171 data = OPENSSL_realloc(sk->data, alloc_size);
172 if (data == NULL) {
173 return 0;
174 }
175
176 sk->data = data;
177 sk->num_alloc = new_alloc;
178 }
179
180 if (where >= sk->num) {
181 sk->data[sk->num] = p;
182 } else {
183 OPENSSL_memmove(&sk->data[where + 1], &sk->data[where],
184 sizeof(void *) * (sk->num - where));
185 sk->data[where] = p;
186 }
187
188 sk->num++;
189 sk->sorted = 0;
190
191 return sk->num;
192 }
193
sk_delete(_STACK * sk,size_t where)194 void *sk_delete(_STACK *sk, size_t where) {
195 void *ret;
196
197 if (!sk || where >= sk->num) {
198 return NULL;
199 }
200
201 ret = sk->data[where];
202
203 if (where != sk->num - 1) {
204 OPENSSL_memmove(&sk->data[where], &sk->data[where + 1],
205 sizeof(void *) * (sk->num - where - 1));
206 }
207
208 sk->num--;
209 return ret;
210 }
211
sk_delete_ptr(_STACK * sk,void * p)212 void *sk_delete_ptr(_STACK *sk, void *p) {
213 if (sk == NULL) {
214 return NULL;
215 }
216
217 for (size_t i = 0; i < sk->num; i++) {
218 if (sk->data[i] == p) {
219 return sk_delete(sk, i);
220 }
221 }
222
223 return NULL;
224 }
225
sk_find(_STACK * sk,size_t * out_index,void * p)226 int sk_find(_STACK *sk, size_t *out_index, void *p) {
227 if (sk == NULL) {
228 return 0;
229 }
230
231 if (sk->comp == NULL) {
232 // Use pointer equality when no comparison function has been set.
233 for (size_t i = 0; i < sk->num; i++) {
234 if (sk->data[i] == p) {
235 if (out_index) {
236 *out_index = i;
237 }
238 return 1;
239 }
240 }
241 return 0;
242 }
243
244 if (p == NULL) {
245 return 0;
246 }
247
248 sk_sort(sk);
249
250 // sk->comp is a function that takes pointers to pointers to elements, but
251 // qsort and bsearch take a comparison function that just takes pointers to
252 // elements. However, since we're passing an array of pointers to
253 // qsort/bsearch, we can just cast the comparison function and everything
254 // works.
255 const void *const *r = bsearch(&p, sk->data, sk->num, sizeof(void *),
256 (int (*)(const void *, const void *))sk->comp);
257 if (r == NULL) {
258 return 0;
259 }
260 size_t idx = ((void **)r) - sk->data;
261 // This function always returns the first result.
262 while (idx > 0 &&
263 sk->comp((const void **)&p, (const void **)&sk->data[idx - 1]) == 0) {
264 idx--;
265 }
266 if (out_index) {
267 *out_index = idx;
268 }
269 return 1;
270 }
271
sk_shift(_STACK * sk)272 void *sk_shift(_STACK *sk) {
273 if (sk == NULL) {
274 return NULL;
275 }
276 if (sk->num == 0) {
277 return NULL;
278 }
279 return sk_delete(sk, 0);
280 }
281
sk_push(_STACK * sk,void * p)282 size_t sk_push(_STACK *sk, void *p) { return (sk_insert(sk, p, sk->num)); }
283
sk_pop(_STACK * sk)284 void *sk_pop(_STACK *sk) {
285 if (sk == NULL) {
286 return NULL;
287 }
288 if (sk->num == 0) {
289 return NULL;
290 }
291 return sk_delete(sk, sk->num - 1);
292 }
293
sk_dup(const _STACK * sk)294 _STACK *sk_dup(const _STACK *sk) {
295 _STACK *ret;
296 void **s;
297
298 if (sk == NULL) {
299 return NULL;
300 }
301
302 ret = sk_new(sk->comp);
303 if (ret == NULL) {
304 goto err;
305 }
306
307 s = (void **)OPENSSL_realloc(ret->data, sizeof(void *) * sk->num_alloc);
308 if (s == NULL) {
309 goto err;
310 }
311 ret->data = s;
312
313 ret->num = sk->num;
314 OPENSSL_memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
315 ret->sorted = sk->sorted;
316 ret->num_alloc = sk->num_alloc;
317 ret->comp = sk->comp;
318 return ret;
319
320 err:
321 sk_free(ret);
322 return NULL;
323 }
324
sk_sort(_STACK * sk)325 void sk_sort(_STACK *sk) {
326 int (*comp_func)(const void *,const void *);
327
328 if (sk == NULL || sk->comp == NULL || sk->sorted) {
329 return;
330 }
331
332 // See the comment in sk_find about this cast.
333 comp_func = (int (*)(const void *, const void *))(sk->comp);
334 qsort(sk->data, sk->num, sizeof(void *), comp_func);
335 sk->sorted = 1;
336 }
337
sk_is_sorted(const _STACK * sk)338 int sk_is_sorted(const _STACK *sk) {
339 if (!sk) {
340 return 1;
341 }
342 return sk->sorted;
343 }
344
sk_set_cmp_func(_STACK * sk,stack_cmp_func comp)345 stack_cmp_func sk_set_cmp_func(_STACK *sk, stack_cmp_func comp) {
346 stack_cmp_func old = sk->comp;
347
348 if (sk->comp != comp) {
349 sk->sorted = 0;
350 }
351 sk->comp = comp;
352
353 return old;
354 }
355
sk_deep_copy(const _STACK * sk,void * (* copy_func)(void *),void (* free_func)(void *))356 _STACK *sk_deep_copy(const _STACK *sk, void *(*copy_func)(void *),
357 void (*free_func)(void *)) {
358 _STACK *ret = sk_dup(sk);
359 if (ret == NULL) {
360 return NULL;
361 }
362
363 for (size_t i = 0; i < ret->num; i++) {
364 if (ret->data[i] == NULL) {
365 continue;
366 }
367 ret->data[i] = copy_func(ret->data[i]);
368 if (ret->data[i] == NULL) {
369 for (size_t j = 0; j < i; j++) {
370 if (ret->data[j] != NULL) {
371 free_func(ret->data[j]);
372 }
373 }
374 sk_free(ret);
375 return NULL;
376 }
377 }
378
379 return ret;
380 }
381