Further comment amendments to preserve formatting prior to source reformat
[openssl.git] / crypto / stack / stack.c
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 int (*sk_set_cmp_func(_STACK *sk, int (*c)(const void *, const void *)))
82                 (const void *, const void *)
83         {
84         int (*old)(const void *,const void *)=sk->comp;
85
86         if (sk->comp != c)
87                 sk->sorted=0;
88         sk->comp=c;
89
90         return old;
91         }
92
93 _STACK *sk_dup(_STACK *sk)
94         {
95         _STACK *ret;
96         char **s;
97
98         if ((ret=sk_new(sk->comp)) == NULL) goto err;
99         s=(char **)OPENSSL_realloc((char *)ret->data,
100                 (unsigned int)sizeof(char *)*sk->num_alloc);
101         if (s == NULL) goto err;
102         ret->data=s;
103
104         ret->num=sk->num;
105         memcpy(ret->data,sk->data,sizeof(char *)*sk->num);
106         ret->sorted=sk->sorted;
107         ret->num_alloc=sk->num_alloc;
108         ret->comp=sk->comp;
109         return(ret);
110 err:
111         if(ret)
112                 sk_free(ret);
113         return(NULL);
114         }
115
116 _STACK *sk_deep_copy(_STACK *sk, void *(*copy_func)(void *),
117                          void (*free_func)(void *))
118         {
119         _STACK *ret;
120         int i;
121
122         if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
123                 return ret;
124         ret->comp = sk->comp;
125         ret->sorted = sk->sorted;
126         ret->num = sk->num;
127         ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
128         ret->data = OPENSSL_malloc(sizeof(char *) * ret->num_alloc);
129         if (ret->data == NULL)
130                 {
131                 OPENSSL_free(ret);
132                 return NULL;
133                 }
134         for (i = 0; i < ret->num_alloc; i++)
135                 ret->data[i] = NULL;
136
137         for (i = 0; i < ret->num; ++i)
138                 {
139                 if (sk->data[i] == NULL)
140                         continue;
141                 if ((ret->data[i] = copy_func(sk->data[i])) == NULL)
142                         {
143                         while (--i >= 0)
144                                 if (ret->data[i] != NULL)
145                                         free_func(ret->data[i]);
146                         sk_free(ret);
147                         return NULL;
148                         }
149                 }
150         return ret;
151         }
152
153 _STACK *sk_new_null(void)
154         {
155         return sk_new((int (*)(const void *, const void *))0);
156         }
157
158 _STACK *sk_new(int (*c)(const void *, const void *))
159         {
160         _STACK *ret;
161         int i;
162
163         if ((ret=OPENSSL_malloc(sizeof(_STACK))) == NULL)
164                 goto err;
165         if ((ret->data=OPENSSL_malloc(sizeof(char *)*MIN_NODES)) == NULL)
166                 goto err;
167         for (i=0; i<MIN_NODES; i++)
168                 ret->data[i]=NULL;
169         ret->comp=c;
170         ret->num_alloc=MIN_NODES;
171         ret->num=0;
172         ret->sorted=0;
173         return(ret);
174 err:
175         if(ret)
176                 OPENSSL_free(ret);
177         return(NULL);
178         }
179
180 int sk_insert(_STACK *st, void *data, int loc)
181         {
182         char **s;
183
184         if(st == NULL) return 0;
185         if (st->num_alloc <= st->num+1)
186                 {
187                 s=OPENSSL_realloc((char *)st->data,
188                         (unsigned int)sizeof(char *)*st->num_alloc*2);
189                 if (s == NULL)
190                         return(0);
191                 st->data=s;
192                 st->num_alloc*=2;
193                 }
194         if ((loc >= (int)st->num) || (loc < 0))
195                 st->data[st->num]=data;
196         else
197                 {
198                 int i;
199                 char **f,**t;
200
201                 f=st->data;
202                 t=&(st->data[1]);
203                 for (i=st->num; i>=loc; i--)
204                         t[i]=f[i];
205                         
206 #ifdef undef /* no memmove on sunos :-( */
207                 memmove(&(st->data[loc+1]),
208                         &(st->data[loc]),
209                         sizeof(char *)*(st->num-loc));
210 #endif
211                 st->data[loc]=data;
212                 }
213         st->num++;
214         st->sorted=0;
215         return(st->num);
216         }
217
218 void *sk_delete_ptr(_STACK *st, void *p)
219         {
220         int i;
221
222         for (i=0; i<st->num; i++)
223                 if (st->data[i] == p)
224                         return(sk_delete(st,i));
225         return(NULL);
226         }
227
228 void *sk_delete(_STACK *st, int loc)
229         {
230         char *ret;
231         int i,j;
232
233         if(!st || (loc < 0) || (loc >= st->num)) return NULL;
234
235         ret=st->data[loc];
236         if (loc != st->num-1)
237                 {
238                 j=st->num-1;
239                 for (i=loc; i<j; i++)
240                         st->data[i]=st->data[i+1];
241                 /* In theory memcpy is not safe for this
242                  * memcpy( &(st->data[loc]),
243                  *      &(st->data[loc+1]),
244                  *      sizeof(char *)*(st->num-loc-1));
245                  */
246                 }
247         st->num--;
248         return(ret);
249         }
250
251 static int internal_find(_STACK *st, void *data, int ret_val_options)
252         {
253         const void * const *r;
254         int i;
255
256         if(st == NULL) return -1;
257
258         if (st->comp == NULL)
259                 {
260                 for (i=0; i<st->num; i++)
261                         if (st->data[i] == data)
262                                 return(i);
263                 return(-1);
264                 }
265         sk_sort(st);
266         if (data == NULL) return(-1);
267         r=OBJ_bsearch_ex_(&data,st->data,st->num,sizeof(void *),st->comp,
268                           ret_val_options);
269         if (r == NULL) return(-1);
270         return (int)((char **)r-st->data);
271         }
272
273 int sk_find(_STACK *st, void *data)
274         {
275         return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
276         }
277 int sk_find_ex(_STACK *st, void *data)
278         {
279         return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
280         }
281
282 int sk_push(_STACK *st, void *data)
283         {
284         return(sk_insert(st,data,st->num));
285         }
286
287 int sk_unshift(_STACK *st, void *data)
288         {
289         return(sk_insert(st,data,0));
290         }
291
292 void *sk_shift(_STACK *st)
293         {
294         if (st == NULL) return(NULL);
295         if (st->num <= 0) return(NULL);
296         return(sk_delete(st,0));
297         }
298
299 void *sk_pop(_STACK *st)
300         {
301         if (st == NULL) return(NULL);
302         if (st->num <= 0) return(NULL);
303         return(sk_delete(st,st->num-1));
304         }
305
306 void sk_zero(_STACK *st)
307         {
308         if (st == NULL) return;
309         if (st->num <= 0) return;
310         memset((char *)st->data,0,sizeof(st->data)*st->num);
311         st->num=0;
312         }
313
314 void sk_pop_free(_STACK *st, void (*func)(void *))
315         {
316         int i;
317
318         if (st == NULL) return;
319         for (i=0; i<st->num; i++)
320                 if (st->data[i] != NULL)
321                         func(st->data[i]);
322         sk_free(st);
323         }
324
325 void sk_free(_STACK *st)
326         {
327         if (st == NULL) return;
328         if (st->data != NULL) OPENSSL_free(st->data);
329         OPENSSL_free(st);
330         }
331
332 int sk_num(const _STACK *st)
333 {
334         if(st == NULL) return -1;
335         return st->num;
336 }
337
338 void *sk_value(const _STACK *st, int i)
339 {
340         if(!st || (i < 0) || (i >= st->num)) return NULL;
341         return st->data[i];
342 }
343
344 void *sk_set(_STACK *st, int i, void *value)
345 {
346         if(!st || (i < 0) || (i >= st->num)) return NULL;
347         return (st->data[i] = value);
348 }
349
350 void sk_sort(_STACK *st)
351         {
352         if (st && !st->sorted)
353                 {
354                 int (*comp_func)(const void *,const void *);
355
356                 /* same comment as in sk_find ... previously st->comp was declared
357                  * as a (void*,void*) callback type, but this made the population
358                  * of the callback pointer illogical - our callbacks compare
359                  * type** with type**, so we leave the casting until absolutely
360                  * necessary (ie. "now"). */
361                 comp_func=(int (*)(const void *,const void *))(st->comp);
362                 qsort(st->data,st->num,sizeof(char *), comp_func);
363                 st->sorted=1;
364                 }
365         }
366
367 int sk_is_sorted(const _STACK *st)
368         {
369         if (!st)
370                 return 1;
371         return st->sorted;
372         }