Branch data 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 : : /* Code for stacks
60 : : * Author - Eric Young v 1.0
61 : : * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the
62 : : * lowest index for the searched item.
63 : : *
64 : : * 1.1 eay - Take from netdb and added to SSLeay
65 : : *
66 : : * 1.0 eay - First version 29/07/92
67 : : */
68 : : #include <stdio.h>
69 : : #include "cryptlib.h"
70 : : #include <openssl/stack.h>
71 : : #include <openssl/objects.h>
72 : :
73 : : #undef MIN_NODES
74 : : #define MIN_NODES 4
75 : :
76 : : const char STACK_version[]="Stack" OPENSSL_VERSION_PTEXT;
77 : :
78 : : #include <errno.h>
79 : :
80 : 2654 : int (*sk_set_cmp_func(_STACK *sk, int (*c)(const void *, const void *)))
81 : : (const void *, const void *)
82 : : {
83 : 2654 : int (*old)(const void *,const void *)=sk->comp;
84 : :
85 [ + - ]: 2654 : if (sk->comp != c)
86 : 2654 : sk->sorted=0;
87 : 2654 : sk->comp=c;
88 : :
89 : 2654 : return old;
90 : : }
91 : :
92 : 3765 : _STACK *sk_dup(_STACK *sk)
93 : : {
94 : : _STACK *ret;
95 : : char **s;
96 : :
97 [ + - ]: 3765 : if ((ret=sk_new(sk->comp)) == NULL) goto err;
98 : 3765 : s=(char **)OPENSSL_realloc((char *)ret->data,
99 : : (unsigned int)sizeof(char *)*sk->num_alloc);
100 [ + - ]: 3765 : if (s == NULL) goto err;
101 : 3765 : ret->data=s;
102 : :
103 : 3765 : ret->num=sk->num;
104 : 3765 : memcpy(ret->data,sk->data,sizeof(char *)*sk->num);
105 : 3765 : ret->sorted=sk->sorted;
106 : 3765 : ret->num_alloc=sk->num_alloc;
107 : 3765 : ret->comp=sk->comp;
108 : 3765 : return(ret);
109 : : err:
110 [ # # ]: 0 : if(ret)
111 : 0 : sk_free(ret);
112 : : return(NULL);
113 : : }
114 : :
115 : 0 : _STACK *sk_deep_copy(_STACK *sk, void *(*copy_func)(void *),
116 : : void (*free_func)(void *))
117 : : {
118 : : _STACK *ret;
119 : : int i;
120 : :
121 [ # # ]: 0 : if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
122 : : return ret;
123 : 0 : ret->comp = sk->comp;
124 : 0 : ret->sorted = sk->sorted;
125 : 0 : ret->num = sk->num;
126 : 0 : ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
127 : 0 : ret->data = OPENSSL_malloc(sizeof(char *) * ret->num_alloc);
128 [ # # ]: 0 : if (ret->data == NULL)
129 : : {
130 : 0 : OPENSSL_free(ret);
131 : 0 : return NULL;
132 : : }
133 [ # # ]: 0 : for (i = 0; i < ret->num_alloc; i++)
134 : 0 : ret->data[i] = NULL;
135 : :
136 [ # # ]: 0 : for (i = 0; i < ret->num; ++i)
137 : : {
138 [ # # ]: 0 : if (sk->data[i] == NULL)
139 : 0 : continue;
140 [ # # ]: 0 : if ((ret->data[i] = copy_func(sk->data[i])) == NULL)
141 : : {
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 : 222753 : _STACK *sk_new_null(void)
153 : : {
154 : 222753 : return sk_new((int (*)(const void *, const void *))0);
155 : : }
156 : :
157 : 230382 : _STACK *sk_new(int (*c)(const void *, const void *))
158 : : {
159 : : _STACK *ret;
160 : : int i;
161 : :
162 [ + - ]: 230382 : if ((ret=OPENSSL_malloc(sizeof(_STACK))) == NULL)
163 : : goto err;
164 [ + - ]: 230382 : if ((ret->data=OPENSSL_malloc(sizeof(char *)*MIN_NODES)) == NULL)
165 : : goto err;
166 [ + + ]: 1151910 : for (i=0; i<MIN_NODES; i++)
167 : 921528 : ret->data[i]=NULL;
168 : 230382 : ret->comp=c;
169 : 230382 : ret->num_alloc=MIN_NODES;
170 : 230382 : ret->num=0;
171 : 230382 : ret->sorted=0;
172 : 230382 : return(ret);
173 : : err:
174 [ # # ]: 0 : if(ret)
175 : 0 : OPENSSL_free(ret);
176 : : return(NULL);
177 : : }
178 : :
179 : 654762 : int sk_insert(_STACK *st, void *data, int loc)
180 : : {
181 : : char **s;
182 : :
183 [ + - ]: 654762 : if(st == NULL) return 0;
184 [ + + ]: 654762 : if (st->num_alloc <= st->num+1)
185 : : {
186 : 53643 : s=OPENSSL_realloc((char *)st->data,
187 : : (unsigned int)sizeof(char *)*st->num_alloc*2);
188 [ + - ]: 53643 : if (s == NULL)
189 : : return(0);
190 : 53643 : st->data=s;
191 : 53643 : st->num_alloc*=2;
192 : : }
193 [ + + ][ - + ]: 654762 : if ((loc >= (int)st->num) || (loc < 0))
194 : 649665 : st->data[st->num]=data;
195 : : else
196 : : {
197 : : int i;
198 : : char **f,**t;
199 : :
200 : 5097 : f=st->data;
201 : 5097 : t=&(st->data[1]);
202 [ + + ]: 30586 : for (i=st->num; i>=loc; i--)
203 : 25489 : t[i]=f[i];
204 : :
205 : : #ifdef undef /* no memmove on sunos :-( */
206 : : memmove(&(st->data[loc+1]),
207 : : &(st->data[loc]),
208 : : sizeof(char *)*(st->num-loc));
209 : : #endif
210 : 5097 : st->data[loc]=data;
211 : : }
212 : 654762 : st->num++;
213 : 654762 : st->sorted=0;
214 : 654762 : return(st->num);
215 : : }
216 : :
217 : 28914 : void *sk_delete_ptr(_STACK *st, void *p)
218 : : {
219 : : int i;
220 : :
221 [ + + ]: 80377 : for (i=0; i<st->num; i++)
222 [ + + ]: 57078 : if (st->data[i] == p)
223 : 5615 : return(sk_delete(st,i));
224 : : return(NULL);
225 : : }
226 : :
227 : 8585 : void *sk_delete(_STACK *st, int loc)
228 : : {
229 : : char *ret;
230 : : int i,j;
231 : :
232 [ + - ][ + - ]: 8585 : if(!st || (loc < 0) || (loc >= st->num)) return NULL;
233 : :
234 : 8585 : ret=st->data[loc];
235 [ + + ]: 8585 : if (loc != st->num-1)
236 : : {
237 : : j=st->num-1;
238 [ + + ]: 966 : for (i=loc; i<j; i++)
239 : 586 : st->data[i]=st->data[i+1];
240 : : /* In theory memcpy is not safe for this
241 : : * memcpy( &(st->data[loc]),
242 : : * &(st->data[loc+1]),
243 : : * sizeof(char *)*(st->num-loc-1));
244 : : */
245 : : }
246 : 8585 : st->num--;
247 : 8585 : return(ret);
248 : : }
249 : :
250 : 9428 : static int internal_find(_STACK *st, void *data, int ret_val_options)
251 : : {
252 : : const void * const *r;
253 : : int i;
254 : :
255 [ + - ]: 9428 : if(st == NULL) return -1;
256 : :
257 [ + + ]: 9428 : if (st->comp == NULL)
258 : : {
259 [ + - ]: 12366 : for (i=0; i<st->num; i++)
260 [ + + ]: 12366 : if (st->data[i] == data)
261 : : return(i);
262 : : return(-1);
263 : : }
264 : 7435 : sk_sort(st);
265 [ + - ]: 7435 : if (data == NULL) return(-1);
266 : 7435 : r=OBJ_bsearch_ex_(&data,st->data,st->num,sizeof(void *),st->comp,
267 : : ret_val_options);
268 [ + + ]: 7435 : if (r == NULL) return(-1);
269 : 2429 : return (int)((char **)r-st->data);
270 : : }
271 : :
272 : 9428 : int sk_find(_STACK *st, void *data)
273 : : {
274 : 9428 : return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
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 : 648970 : int sk_push(_STACK *st, void *data)
282 : : {
283 : 648970 : 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 : 99 : void *sk_shift(_STACK *st)
292 : : {
293 [ + - ]: 99 : if (st == NULL) return(NULL);
294 [ + - ]: 99 : if (st->num <= 0) return(NULL);
295 : 99 : return(sk_delete(st,0));
296 : : }
297 : :
298 : 223 : void *sk_pop(_STACK *st)
299 : : {
300 [ + - ]: 223 : if (st == NULL) return(NULL);
301 [ + - ]: 223 : if (st->num <= 0) return(NULL);
302 : 223 : return(sk_delete(st,st->num-1));
303 : : }
304 : :
305 : 0 : void sk_zero(_STACK *st)
306 : : {
307 [ # # ]: 0 : if (st == NULL) return;
308 [ # # ]: 0 : if (st->num <= 0) return;
309 : 0 : memset((char *)st->data,0,sizeof(st->data)*st->num);
310 : 0 : st->num=0;
311 : : }
312 : :
313 : 113674 : void sk_pop_free(_STACK *st, void (*func)(void *))
314 : : {
315 : : int i;
316 : :
317 [ + + ]: 113674 : if (st == NULL) return;
318 [ + + ]: 276995 : for (i=0; i<st->num; i++)
319 [ + - ]: 168123 : if (st->data[i] != NULL)
320 : 168123 : func(st->data[i]);
321 : 108872 : sk_free(st);
322 : : }
323 : :
324 : 243628 : void sk_free(_STACK *st)
325 : : {
326 [ + + ]: 243628 : if (st == NULL) return;
327 [ + - ]: 227756 : if (st->data != NULL) OPENSSL_free(st->data);
328 : 227756 : OPENSSL_free(st);
329 : : }
330 : :
331 : 1618950 : int sk_num(const _STACK *st)
332 : : {
333 [ + + ]: 1618950 : if(st == NULL) return -1;
334 : 1597968 : return st->num;
335 : : }
336 : :
337 : 1094146 : void *sk_value(const _STACK *st, int i)
338 : : {
339 [ + - ][ + + ]: 1094146 : if(!st || (i < 0) || (i >= st->num)) return NULL;
340 : 1093613 : return st->data[i];
341 : : }
342 : :
343 : 2890 : void *sk_set(_STACK *st, int i, void *value)
344 : : {
345 [ + - ][ + - ]: 2890 : if(!st || (i < 0) || (i >= st->num)) return NULL;
346 : 2890 : return (st->data[i] = value);
347 : : }
348 : :
349 : 10832 : void sk_sort(_STACK *st)
350 : : {
351 [ + - ][ + + ]: 10832 : if (st && !st->sorted)
352 : : {
353 : : int (*comp_func)(const void *,const void *);
354 : :
355 : : /* same comment as in sk_find ... previously st->comp was declared
356 : : * as a (void*,void*) callback type, but this made the population
357 : : * of the callback pointer illogical - our callbacks compare
358 : : * type** with type**, so we leave the casting until absolutely
359 : : * necessary (ie. "now"). */
360 : 6432 : comp_func=(int (*)(const void *,const void *))(st->comp);
361 : 6432 : qsort(st->data,st->num,sizeof(char *), comp_func);
362 : 6432 : st->sorted=1;
363 : : }
364 : 10832 : }
365 : :
366 : 0 : int sk_is_sorted(const _STACK *st)
367 : : {
368 [ # # ]: 0 : if (!st)
369 : : return 1;
370 : 0 : return st->sorted;
371 : : }
|
