OSX/libsecurity_apple_csp/open_ssl/stack/stack.c

   1 /*
   2  * Copyright (c) 2000-2001,2011,2014 Apple Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 /* crypto/stack/stack.c */
  20 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  21  * All rights reserved.
  22  *
  23  * This package is an SSL implementation written
  24  * by Eric Young (eay@cryptsoft.com).
  25  * The implementation was written so as to conform with Netscapes SSL.
  26  *
  27  * This library is free for commercial and non-commercial use as long as
  28  * the following conditions are aheared to.  The following conditions
  29  * apply to all code found in this distribution, be it the RC4, RSA,
  30  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  31  * included with this distribution is covered by the same copyright terms
  32  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  33  *
  34  * Copyright remains Eric Young's, and as such any Copyright notices in
  35  * the code are not to be removed.
  36  * If this package is used in a product, Eric Young should be given attribution
  37  * as the author of the parts of the library used.
  38  * This can be in the form of a textual message at program startup or
  39  * in documentation (online or textual) provided with the package.
  40  *
  41  * Redistribution and use in source and binary forms, with or without
  42  * modification, are permitted provided that the following conditions
  43  * are met:
  44  * 1. Redistributions of source code must retain the copyright
  45  *    notice, this list of conditions and the following disclaimer.
  46  * 2. Redistributions in binary form must reproduce the above copyright
  47  *    notice, this list of conditions and the following disclaimer in the
  48  *    documentation and/or other materials provided with the distribution.
  49  * 3. All advertising materials mentioning features or use of this software
  50  *    must display the following acknowledgement:
  51  *    "This product includes cryptographic software written by
  52  *     Eric Young (eay@cryptsoft.com)"
  53  *    The word 'cryptographic' can be left out if the rouines from the library
  54  *    being used are not cryptographic related :-).
  55  * 4. If you include any Windows specific code (or a derivative thereof) from
  56  *    the apps directory (application code) you must include an acknowledgement:
  57  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  69  * SUCH DAMAGE.
  70  *
  71  * The licence and distribution terms for any publically available version or
  72  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  73  * copied and put under another distribution licence
  74  * [including the GNU Public Licence.]
  75  */
  76
  77 /* Code for stacks
  78  * Author - Eric Young v 1.0
  79  * 1.2 eay 12-Mar-97 -  Modified sk_find so that it _DOES_ return the
  80  *                      lowest index for the searched item.
  81  *
  82  * 1.1 eay - Take from netdb and added to SSLeay
  83  *
  84  * 1.0 eay - First version 29/07/92
  85  */
  86 #include <stdio.h>
  87 #include "cryptlib.h"
  88 #include <openssl/stack_legacy.h>
  89
  90 #undef MIN_NODES
  91 #define MIN_NODES       4
  92
  93 const char *STACK_version="Stack" OPENSSL_VERSION_PTEXT;
  94
  95 #define FP_ICC  (int (*)(const void *,const void *))
  96 #include <errno.h>
  97
  98 int (*sk_set_cmp_func(STACK *sk, int (*c)()))(void)
  99         {
 100         int (*old)()=sk->comp;
 101
 102         if (sk->comp != c)
 103                 sk->sorted=0;
 104         sk->comp=c;
 105
 106         return old;
 107         }
 108
 109 STACK *sk_dup(STACK *sk)
 110         {
 111         STACK *ret;
 112         char **s;
 113
 114         if ((ret=sk_new(sk->comp)) == NULL) goto err;
 115         s=(char **)Realloc((char *)ret->data,
 116                 (unsigned int)sizeof(char *)*sk->num_alloc);
 117         if (s == NULL) goto err;
 118         ret->data=s;
 119
 120         ret->num=sk->num;
 121         memcpy(ret->data,sk->data,sizeof(char *)*sk->num);
 122         ret->sorted=sk->sorted;
 123         ret->num_alloc=sk->num_alloc;
 124         ret->comp=sk->comp;
 125         return(ret);
 126 err:
 127         return(NULL);
 128         }
 129
 130 STACK *sk_new(int (*c)())
 131         {
 132         STACK *ret;
 133         int i;
 134
 135         if ((ret=(STACK *)Malloc(sizeof(STACK))) == NULL)
 136                 goto err0;
 137         if ((ret->data=(char **)Malloc(sizeof(char *)*MIN_NODES)) == NULL)
 138                 goto err1;
 139         for (i=0; i<MIN_NODES; i++)
 140                 ret->data[i]=NULL;
 141         ret->comp=c;
 142         ret->num_alloc=MIN_NODES;
 143         ret->num=0;
 144         ret->sorted=0;
 145         return(ret);
 146 err1:
 147         Free(ret);
 148 err0:
 149         return(NULL);
 150         }
 151
 152 int sk_insert(STACK *st, char *data, int loc)
 153         {
 154         char **s;
 155
 156         if(st == NULL) return 0;
 157         if (st->num_alloc <= st->num+1)
 158                 {
 159                 s=(char **)Realloc((char *)st->data,
 160                         (unsigned int)sizeof(char *)*st->num_alloc*2);
 161                 if (s == NULL)
 162                         return(0);
 163                 st->data=s;
 164                 st->num_alloc*=2;
 165                 }
 166         if ((loc >= (int)st->num) || (loc < 0))
 167                 st->data[st->num]=data;
 168         else
 169                 {
 170                 int i;
 171                 char **f,**t;
 172
 173                 f=(char **)st->data;
 174                 t=(char **)&(st->data[1]);
 175                 for (i=st->num; i>=loc; i--)
 176                         t[i]=f[i];
 177
 178 #ifdef undef /* no memmove on sunos :-( */
 179                 memmove( (char *)&(st->data[loc+1]),
 180                         (char *)&(st->data[loc]),
 181                         sizeof(char *)*(st->num-loc));
 182 #endif
 183                 st->data[loc]=data;
 184                 }
 185         st->num++;
 186         st->sorted=0;
 187         return(st->num);
 188         }
 189
 190 char *sk_delete_ptr(STACK *st, char *p)
 191         {
 192         int i;
 193
 194         for (i=0; i<st->num; i++)
 195                 if (st->data[i] == p)
 196                         return(sk_delete(st,i));
 197         return(NULL);
 198         }
 199
 200 char *sk_delete(STACK *st, int loc)
 201         {
 202         char *ret;
 203         int i,j;
 204
 205         if ((st == NULL) || (st->num == 0) || (loc < 0)
 206                                          || (loc >= st->num)) return(NULL);
 207
 208         ret=st->data[loc];
 209         if (loc != st->num-1)
 210                 {
 211                 j=st->num-1;
 212                 for (i=loc; i<j; i++)
 213                         st->data[i]=st->data[i+1];
 214                 /* In theory memcpy is not safe for this
 215                  * memcpy( &(st->data[loc]),
 216                  *      &(st->data[loc+1]),
 217                  *      sizeof(char *)*(st->num-loc-1));
 218                  */
 219                 }
 220         st->num--;
 221         return(ret);
 222         }
 223
 224 int sk_find(STACK *st, char *data)
 225         {
 226         char **r;
 227         int i;
 228         int (*comp_func)();
 229         if(st == NULL) return -1;
 230
 231         if (st->comp == NULL)
 232                 {
 233                 for (i=0; i<st->num; i++)
 234                         if (st->data[i] == data)
 235                                 return(i);
 236                 return(-1);
 237                 }
 238         sk_sort(st);
 239         if (data == NULL) return(-1);
 240         comp_func=(int (*)())st->comp;
 241         r=(char **)bsearch(&data,(char *)st->data,
 242                 st->num,sizeof(char *),FP_ICC comp_func);
 243         if (r == NULL) return(-1);
 244         i=(int)(r-st->data);
 245         for ( ; i>0; i--)
 246                 if ((*st->comp)(&(st->data[i-1]),&data) < 0)
 247                         break;
 248         return(i);
 249         }
 250
 251 int sk_push(STACK *st, char *data)
 252         {
 253         return(sk_insert(st,data,st->num));
 254         }
 255
 256 int sk_unshift(STACK *st, char *data)
 257         {
 258         return(sk_insert(st,data,0));
 259         }
 260
 261 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 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 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 void sk_pop_free(STACK *st, void (*func)())
 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 void sk_free(STACK *st)
 295         {
 296         if (st == NULL) return;
 297         if (st->data != NULL) Free(st->data);
 298         Free(st);
 299         }
 300
 301 int sk_num(STACK *st)
 302 {
 303         if(st == NULL) return -1;
 304         return st->num;
 305 }
 306
 307 char *sk_value(STACK *st, int i)
 308 {
 309         if(st == NULL) return NULL;
 310         return st->data[i];
 311 }
 312
 313 char *sk_set(STACK *st, int i, char *value)
 314 {
 315         if(st == NULL) return NULL;
 316         return (st->data[i] = value);
 317 }
 318
 319 void sk_sort(STACK *st)
 320     {
 321     if (!st->sorted)
 322         {
 323         int (*comp_func)();
 324
 325         comp_func=(int (*)())st->comp;
 326         qsort(st->data,st->num,sizeof(char *),FP_ICC comp_func);
 327         st->sorted=1;
 328         }
 329     }