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 EXPORT_C  int (*sk_set_cmp_func(STACK *sk, int (*c)(const char * const *,const char * const *)))

    81 		(const char * const *, const char * const *)

    82 	{

    83 	int (*old)(const char * const *,const char * const *)=sk->comp;

    84 

    85 	if (sk->comp != c)

    86 		sk->sorted=0;

    87 	sk->comp=c;

    88 

    89 	return old;

    90 	}

    91 

    92 EXPORT_C STACK *sk_dup(STACK *sk)

    93 	{

    94 	STACK *ret;

    95 	char **s;

    96 

    97 	if ((ret=sk_new(sk->comp)) == NULL) goto err;

    98 	s=(char **)OPENSSL_realloc((char *)ret->data,

    99 		(unsigned int)sizeof(char *)*sk->num_alloc);

   100 	if (s == NULL) goto err;

   101 	ret->data=s;

   102 

   103 	ret->num=sk->num;

   104 	memcpy(ret->data,sk->data,sizeof(char *)*sk->num);

   105 	ret->sorted=sk->sorted;

   106 	ret->num_alloc=sk->num_alloc;

   107 	ret->comp=sk->comp;

   108 	return(ret);

   109 err:

   110 	if(ret)

   111 		sk_free(ret);

   112 	return(NULL);

   113 	}

   114 

   115 EXPORT_C STACK *sk_new_null(void)

   116 	{

   117 	return sk_new((int (*)(const char * const *, const char * const *))0);

   118 	}

   119 

   120 EXPORT_C STACK *sk_new(int (*c)(const char * const *, const char * const *))

   121 	{

   122 	STACK *ret;

   123 	int i;

   124 

   125 	if ((ret=(STACK *)OPENSSL_malloc(sizeof(STACK))) == NULL)

   126 		goto err;

   127 	if ((ret->data=(char **)OPENSSL_malloc(sizeof(char *)*MIN_NODES)) == NULL)

   128 		goto err;

   129 	for (i=0; i<MIN_NODES; i++)

   130 		ret->data[i]=NULL;

   131 	ret->comp=c;

   132 	ret->num_alloc=MIN_NODES;

   133 	ret->num=0;

   134 	ret->sorted=0;

   135 	return(ret);

   136 err:

   137 	if(ret)

   138 		OPENSSL_free(ret);

   139 	return(NULL);

   140 	}

   141 

   142 EXPORT_C int sk_insert(STACK *st, char *data, int loc)

   143 	{

   144 	char **s;

   145 

   146 	if(st == NULL) return 0;

   147 	if (st->num_alloc <= st->num+1)

   148 		{

   149 		s=(char **)OPENSSL_realloc((char *)st->data,

   150 			(unsigned int)sizeof(char *)*st->num_alloc*2);

   151 		if (s == NULL)

   152 			return(0);

   153 		st->data=s;

   154 		st->num_alloc*=2;

   155 		}

   156 	if ((loc >= (int)st->num) || (loc < 0))

   157 		st->data[st->num]=data;

   158 	else

   159 		{

   160 		int i;

   161 		char **f,**t;

   162 

   163 		f=(char **)st->data;

   164 		t=(char **)&(st->data[1]);

   165 		for (i=st->num; i>=loc; i--)

   166 			t[i]=f[i];

   167 			

   168 #ifdef undef /* no memmove on sunos :-( */

   169 		memmove( (char *)&(st->data[loc+1]),

   170 			(char *)&(st->data[loc]),

   171 			sizeof(char *)*(st->num-loc));

   172 #endif

   173 		st->data[loc]=data;

   174 		}

   175 	st->num++;

   176 	st->sorted=0;

   177 	return(st->num);

   178 	}

   179 

   180 EXPORT_C char *sk_delete_ptr(STACK *st, char *p)

   181 	{

   182 	int i;

   183 

   184 	for (i=0; i<st->num; i++)

   185 		if (st->data[i] == p)

   186 			return(sk_delete(st,i));

   187 	return(NULL);

   188 	}

   189 

   190 EXPORT_C char *sk_delete(STACK *st, int loc)

   191 	{

   192 	char *ret;

   193 	int i,j;

   194 

   195 	if(!st || (loc < 0) || (loc >= st->num)) return NULL;

   196 

   197 	ret=st->data[loc];

   198 	if (loc != st->num-1)

   199 		{

   200 		j=st->num-1;

   201 		for (i=loc; i<j; i++)

   202 			st->data[i]=st->data[i+1];

   203 		/* In theory memcpy is not safe for this

   204 		 * memcpy( &(st->data[loc]),

   205 		 *	&(st->data[loc+1]),

   206 		 *	sizeof(char *)*(st->num-loc-1));

   207 		 */

   208 		}

   209 	st->num--;

   210 	return(ret);

   211 	}

   212 

   213 static int internal_find(STACK *st, char *data, int ret_val_options)

   214 	{

   215 	char **r;

   216 	int i;

   217 	int (*comp_func)(const void *,const void *);

   218 	if(st == NULL) return -1;

   219 

   220 	if (st->comp == NULL)

   221 		{

   222 		for (i=0; i<st->num; i++)

   223 			if (st->data[i] == data)

   224 				return(i);

   225 		return(-1);

   226 		}

   227 	sk_sort(st);

   228 	if (data == NULL) return(-1);

   229 	/* This (and the "qsort" below) are the two places in OpenSSL

   230 	 * where we need to convert from our standard (type **,type **)

   231 	 * compare callback type to the (void *,void *) type required by

   232 	 * bsearch. However, the "data" it is being called(back) with are

   233 	 * not (type *) pointers, but the *pointers* to (type *) pointers,

   234 	 * so we get our extra level of pointer dereferencing that way. */

   235 	comp_func=(int (*)(const void *,const void *))(st->comp);

   236 	r=(char **)OBJ_bsearch_ex((char *)&data,(char *)st->data,

   237 		st->num,sizeof(char *),comp_func,ret_val_options);

   238 	if (r == NULL) return(-1);

   239 	return((int)(r-st->data));

   240 	}

   241 

   242 EXPORT_C int sk_find(STACK *st, char *data)

   243 	{

   244 	return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);

   245 	}

   246 EXPORT_C int sk_find_ex(STACK *st, char *data)

   247 	{

   248 	return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);

   249 	}

   250 

   251 EXPORT_C int sk_push(STACK *st, char *data)

   252 	{

   253 	return(sk_insert(st,data,st->num));

   254 	}

   255 

   256 EXPORT_C int sk_unshift(STACK *st, char *data)

   257 	{

   258 	return(sk_insert(st,data,0));

   259 	}

   260 

   261 EXPORT_C char *sk_shift(STACK *st)

   262 	{

   263 	if (st == NULL) return(NULL);

   264 	if (st->num <= 0) return(NULL);

   265 	return(sk_delete(st,0));

   266 	}

   267 

   268 EXPORT_C char *sk_pop(STACK *st)

   269 	{

   270 	if (st == NULL) return(NULL);

   271 	if (st->num <= 0) return(NULL);

   272 	return(sk_delete(st,st->num-1));

   273 	}

   274 

   275 EXPORT_C void sk_zero(STACK *st)

   276 	{

   277 	if (st == NULL) return;

   278 	if (st->num <= 0) return;

   279 	memset((char *)st->data,0,sizeof(st->data)*st->num);

   280 	st->num=0;

   281 	}

   282 

   283 EXPORT_C void sk_pop_free(STACK *st, void (*func)(void *))

   284 	{

   285 	int i;

   286 

   287 	if (st == NULL) return;

   288 	for (i=0; i<st->num; i++)

   289 		if (st->data[i] != NULL)

   290 			func(st->data[i]);

   291 	sk_free(st);

   292 	}

   293 

   294 EXPORT_C void sk_free(STACK *st)

   295 	{

   296 	if (st == NULL) return;

   297 	if (st->data != NULL) OPENSSL_free(st->data);

   298 	OPENSSL_free(st);

   299 	}

   300 

   301 EXPORT_C int sk_num(const STACK *st)

   302 {

   303 	if(st == NULL) return -1;

   304 	return st->num;

   305 }

   306 

   307 EXPORT_C char *sk_value(const STACK *st, int i)

   308 {

   309 	if(!st || (i < 0) || (i >= st->num)) return NULL;

   310 	return st->data[i];

   311 }

   312 

   313 EXPORT_C char *sk_set(STACK *st, int i, char *value)

   314 {

   315 	if(!st || (i < 0) || (i >= st->num)) return NULL;

   316 	return (st->data[i] = value);

   317 }

   318 

   319 EXPORT_C void sk_sort(STACK *st)

   320 	{

   321 	if (st && !st->sorted)

   322 		{

   323 		int (*comp_func)(const void *,const void *);

   324 

   325 		/* same comment as in sk_find ... previously st->comp was declared

   326 		 * as a (void*,void*) callback type, but this made the population

   327 		 * of the callback pointer illogical - our callbacks compare

   328 		 * type** with type**, so we leave the casting until absolutely

   329 		 * necessary (ie. "now"). */

   330 		comp_func=(int (*)(const void *,const void *))(st->comp);

   331 		qsort(st->data,st->num,sizeof(char *), comp_func);

   332 		st->sorted=1;

   333 		}

   334 	}

   335 EXPORT_C int sk_is_sorted(const STACK *st)

   336 	{

   337 	if (!st)

   338 		return 1;

   339 	return st->sorted;

   340 	}