Line data Source code
1 : /* crypto/stack/stack.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : * All rights reserved.
4 : *
5 : * This package is an SSL implementation written
6 : * by Eric Young (eay@cryptsoft.com).
7 : * The implementation was written so as to conform with Netscapes SSL.
8 : *
9 : * This library is free for commercial and non-commercial use as long as
10 : * the following conditions are aheared to. The following conditions
11 : * apply to all code found in this distribution, be it the RC4, RSA,
12 : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : * included with this distribution is covered by the same copyright terms
14 : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : *
16 : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : * the code are not to be removed.
18 : * If this package is used in a product, Eric Young should be given attribution
19 : * as the author of the parts of the library used.
20 : * This can be in the form of a textual message at program startup or
21 : * in documentation (online or textual) provided with the package.
22 : *
23 : * Redistribution and use in source and binary forms, with or without
24 : * modification, are permitted provided that the following conditions
25 : * are met:
26 : * 1. Redistributions of source code must retain the copyright
27 : * notice, this list of conditions and the following disclaimer.
28 : * 2. Redistributions in binary form must reproduce the above copyright
29 : * notice, this list of conditions and the following disclaimer in the
30 : * documentation and/or other materials provided with the distribution.
31 : * 3. All advertising materials mentioning features or use of this software
32 : * must display the following acknowledgement:
33 : * "This product includes cryptographic software written by
34 : * Eric Young (eay@cryptsoft.com)"
35 : * The word 'cryptographic' can be left out if the rouines from the library
36 : * being used are not cryptographic related :-).
37 : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : * the apps directory (application code) you must include an acknowledgement:
39 : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : * SUCH DAMAGE.
52 : *
53 : * The licence and distribution terms for any publically available version or
54 : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : * copied and put under another distribution licence
56 : * [including the GNU Public Licence.]
57 : */
58 :
59 : /*-
60 : * Code for stacks
61 : * Author - Eric Young v 1.0
62 : * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the
63 : * lowest index for the searched item.
64 : *
65 : * 1.1 eay - Take from netdb and added to SSLeay
66 : *
67 : * 1.0 eay - First version 29/07/92
68 : */
69 : #include <stdio.h>
70 : #include "cryptlib.h"
71 : #include <openssl/stack.h>
72 : #include <openssl/objects.h>
73 :
74 : #undef MIN_NODES
75 : #define MIN_NODES 4
76 :
77 : const char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT;
78 :
79 : #include <errno.h>
80 :
81 1744 : int (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *)))
82 : (const void *, const void *) {
83 1744 : int (*old) (const void *, const void *) = sk->comp;
84 :
85 1744 : if (sk->comp != c)
86 1744 : sk->sorted = 0;
87 1744 : sk->comp = c;
88 :
89 1744 : return old;
90 : }
91 :
92 2114 : _STACK *sk_dup(_STACK *sk)
93 : {
94 : _STACK *ret;
95 : char **s;
96 :
97 2114 : if ((ret = sk_new(sk->comp)) == NULL)
98 : goto err;
99 2114 : s = (char **)OPENSSL_realloc((char *)ret->data,
100 : (unsigned int)sizeof(char *) *
101 : sk->num_alloc);
102 2114 : if (s == NULL)
103 : goto err;
104 2114 : ret->data = s;
105 :
106 2114 : ret->num = sk->num;
107 2114 : memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
108 2114 : ret->sorted = sk->sorted;
109 2114 : ret->num_alloc = sk->num_alloc;
110 2114 : ret->comp = sk->comp;
111 2114 : return (ret);
112 : err:
113 0 : if (ret)
114 0 : sk_free(ret);
115 : return (NULL);
116 : }
117 :
118 0 : _STACK *sk_deep_copy(_STACK *sk, void *(*copy_func) (void *),
119 : void (*free_func) (void *))
120 : {
121 : _STACK *ret;
122 : int i;
123 :
124 0 : if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
125 : return ret;
126 0 : ret->comp = sk->comp;
127 0 : ret->sorted = sk->sorted;
128 0 : ret->num = sk->num;
129 0 : ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
130 0 : ret->data = OPENSSL_malloc(sizeof(char *) * ret->num_alloc);
131 0 : if (ret->data == NULL) {
132 0 : OPENSSL_free(ret);
133 0 : return NULL;
134 : }
135 0 : for (i = 0; i < ret->num_alloc; i++)
136 0 : ret->data[i] = NULL;
137 :
138 0 : for (i = 0; i < ret->num; ++i) {
139 0 : if (sk->data[i] == NULL)
140 0 : continue;
141 0 : if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
142 0 : while (--i >= 0)
143 0 : if (ret->data[i] != NULL)
144 0 : free_func(ret->data[i]);
145 0 : sk_free(ret);
146 0 : return NULL;
147 : }
148 : }
149 : return ret;
150 : }
151 :
152 51967 : _STACK *sk_new_null(void)
153 : {
154 51967 : return sk_new((int (*)(const void *, const void *))0);
155 : }
156 :
157 55074 : _STACK *sk_new(int (*c) (const void *, const void *))
158 : {
159 : _STACK *ret;
160 : int i;
161 :
162 55074 : if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
163 : goto err;
164 55074 : if ((ret->data = OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL)
165 : goto err;
166 220296 : for (i = 0; i < MIN_NODES; i++)
167 220296 : ret->data[i] = NULL;
168 55074 : ret->comp = c;
169 55074 : ret->num_alloc = MIN_NODES;
170 55074 : ret->num = 0;
171 55074 : ret->sorted = 0;
172 55074 : return (ret);
173 : err:
174 0 : if (ret)
175 0 : OPENSSL_free(ret);
176 : return (NULL);
177 : }
178 :
179 180442 : int sk_insert(_STACK *st, void *data, int loc)
180 : {
181 : char **s;
182 :
183 180442 : if (st == NULL)
184 : return 0;
185 180442 : if (st->num_alloc <= st->num + 1) {
186 17195 : s = OPENSSL_realloc((char *)st->data,
187 : (unsigned int)sizeof(char *) * st->num_alloc * 2);
188 17195 : if (s == NULL)
189 : return (0);
190 17195 : st->data = s;
191 17195 : st->num_alloc *= 2;
192 : }
193 180442 : if ((loc >= (int)st->num) || (loc < 0))
194 180442 : st->data[st->num] = data;
195 : else {
196 : int i;
197 : char **f, **t;
198 :
199 0 : f = st->data;
200 0 : t = &(st->data[1]);
201 0 : for (i = st->num; i >= loc; i--)
202 0 : t[i] = f[i];
203 :
204 : #ifdef undef /* no memmove on sunos :-( */
205 : memmove(&(st->data[loc + 1]),
206 : &(st->data[loc]), sizeof(char *) * (st->num - loc));
207 : #endif
208 0 : st->data[loc] = data;
209 : }
210 180442 : st->num++;
211 180442 : st->sorted = 0;
212 180442 : return (st->num);
213 : }
214 :
215 0 : void *sk_delete_ptr(_STACK *st, void *p)
216 : {
217 : int i;
218 :
219 0 : for (i = 0; i < st->num; i++)
220 0 : if (st->data[i] == p)
221 0 : return (sk_delete(st, i));
222 : return (NULL);
223 : }
224 :
225 0 : void *sk_delete(_STACK *st, int loc)
226 : {
227 : char *ret;
228 : int i, j;
229 :
230 0 : if (!st || (loc < 0) || (loc >= st->num))
231 : return NULL;
232 :
233 0 : ret = st->data[loc];
234 0 : if (loc != st->num - 1) {
235 : j = st->num - 1;
236 0 : for (i = loc; i < j; i++)
237 0 : st->data[i] = st->data[i + 1];
238 : /*
239 : * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
240 : * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
241 : */
242 : }
243 0 : st->num--;
244 0 : return (ret);
245 : }
246 :
247 2657 : static int internal_find(_STACK *st, void *data, int ret_val_options)
248 : {
249 : const void *const *r;
250 : int i;
251 :
252 2657 : if (st == NULL)
253 : return -1;
254 :
255 2657 : if (st->comp == NULL) {
256 0 : for (i = 0; i < st->num; i++)
257 373 : if (st->data[i] == data)
258 : return (i);
259 : return (-1);
260 : }
261 2284 : sk_sort(st);
262 2284 : if (data == NULL)
263 : return (-1);
264 2284 : r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
265 : ret_val_options);
266 2284 : if (r == NULL)
267 : return (-1);
268 740 : return (int)((char **)r - st->data);
269 : }
270 :
271 2657 : int sk_find(_STACK *st, void *data)
272 : {
273 2657 : return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
274 : }
275 :
276 0 : int sk_find_ex(_STACK *st, void *data)
277 : {
278 0 : return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
279 : }
280 :
281 180442 : int sk_push(_STACK *st, void *data)
282 : {
283 180442 : return (sk_insert(st, data, st->num));
284 : }
285 :
286 0 : int sk_unshift(_STACK *st, void *data)
287 : {
288 0 : return (sk_insert(st, data, 0));
289 : }
290 :
291 0 : void *sk_shift(_STACK *st)
292 : {
293 0 : if (st == NULL)
294 : return (NULL);
295 0 : if (st->num <= 0)
296 : return (NULL);
297 0 : return (sk_delete(st, 0));
298 : }
299 :
300 0 : void *sk_pop(_STACK *st)
301 : {
302 0 : if (st == NULL)
303 : return (NULL);
304 0 : if (st->num <= 0)
305 : return (NULL);
306 0 : return (sk_delete(st, st->num - 1));
307 : }
308 :
309 0 : void sk_zero(_STACK *st)
310 : {
311 0 : if (st == NULL)
312 : return;
313 0 : if (st->num <= 0)
314 : return;
315 0 : memset((char *)st->data, 0, sizeof(*st->data) * st->num);
316 0 : st->num = 0;
317 : }
318 :
319 28808 : void sk_pop_free(_STACK *st, void (*func) (void *))
320 : {
321 : int i;
322 :
323 28808 : if (st == NULL)
324 28807 : return;
325 49204 : for (i = 0; i < st->num; i++)
326 49205 : if (st->data[i] != NULL)
327 49205 : func(st->data[i]);
328 28438 : sk_free(st);
329 : }
330 :
331 57467 : void sk_free(_STACK *st)
332 : {
333 57467 : if (st == NULL)
334 57467 : return;
335 53918 : if (st->data != NULL)
336 53918 : OPENSSL_free(st->data);
337 53918 : OPENSSL_free(st);
338 : }
339 :
340 308903 : int sk_num(const _STACK *st)
341 : {
342 308903 : if (st == NULL)
343 : return -1;
344 303944 : return st->num;
345 : }
346 :
347 176610 : void *sk_value(const _STACK *st, int i)
348 : {
349 176610 : if (!st || (i < 0) || (i >= st->num))
350 : return NULL;
351 176610 : return st->data[i];
352 : }
353 :
354 491 : void *sk_set(_STACK *st, int i, void *value)
355 : {
356 491 : if (!st || (i < 0) || (i >= st->num))
357 : return NULL;
358 491 : return (st->data[i] = value);
359 : }
360 :
361 4149 : void sk_sort(_STACK *st)
362 : {
363 4149 : if (st && !st->sorted) {
364 : int (*comp_func) (const void *, const void *);
365 :
366 : /*
367 : * same comment as in sk_find ... previously st->comp was declared as
368 : * a (void*,void*) callback type, but this made the population of the
369 : * callback pointer illogical - our callbacks compare type** with
370 : * type**, so we leave the casting until absolutely necessary (ie.
371 : * "now").
372 : */
373 2966 : comp_func = (int (*)(const void *, const void *))(st->comp);
374 2966 : qsort(st->data, st->num, sizeof(char *), comp_func);
375 2966 : st->sorted = 1;
376 : }
377 4149 : }
378 :
379 0 : int sk_is_sorted(const _STACK *st)
380 : {
381 0 : if (!st)
382 : return 1;
383 0 : return st->sorted;
384 : }
|
