lib/libcrypto/stack/stack.c

   1 /* $OpenBSD: stack.c,v 1.20 2018/04/01 00:36:28 schwarze Exp $ */
   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 #include <stdio.h>
  60 #include <string.h>
  61
  62 #include <openssl/objects.h>
  63 #include <openssl/stack.h>
  64
  65 #undef MIN_NODES
  66 #define MIN_NODES       4
  67
  68 #include <errno.h>
  69
  70 int
  71 (*sk_set_cmp_func(_STACK *sk, int (*c)(const void *, const void *)))(
  72     const void *, const void *)
  73 {
  74         int (*old)(const void *, const void *) = sk->comp;
  75
  76         if (sk->comp != c)
  77                 sk->sorted = 0;
  78         sk->comp = c;
  79
  80         return old;
  81 }
  82
  83 _STACK *
  84 sk_dup(_STACK *sk)
  85 {
  86         _STACK *ret;
  87         char **s;
  88
  89         if ((ret = sk_new(sk->comp)) == NULL)
  90                 goto err;
  91         s = reallocarray(ret->data, sk->num_alloc, sizeof(char *));
  92         if (s == NULL)
  93                 goto err;
  94         ret->data = s;
  95
  96         ret->num = sk->num;
  97         memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
  98         ret->sorted = sk->sorted;
  99         ret->num_alloc = sk->num_alloc;
 100         ret->comp = sk->comp;
 101         return (ret);
 102
 103 err:
 104         if (ret)
 105                 sk_free(ret);
 106         return (NULL);
 107 }
 108
 109 _STACK *
 110 sk_new_null(void)
 111 {
 112         return sk_new((int (*)(const void *, const void *))0);
 113 }
 114
 115 _STACK *
 116 sk_new(int (*c)(const void *, const void *))
 117 {
 118         _STACK *ret;
 119         int i;
 120
 121         if ((ret = malloc(sizeof(_STACK))) == NULL)
 122                 goto err;
 123         if ((ret->data = reallocarray(NULL, MIN_NODES, sizeof(char *))) == NULL)
 124                 goto err;
 125         for (i = 0; i < MIN_NODES; i++)
 126                 ret->data[i] = NULL;
 127         ret->comp = c;
 128         ret->num_alloc = MIN_NODES;
 129         ret->num = 0;
 130         ret->sorted = 0;
 131         return (ret);
 132
 133 err:
 134         free(ret);
 135         return (NULL);
 136 }
 137
 138 int
 139 sk_insert(_STACK *st, void *data, int loc)
 140 {
 141         char **s;
 142
 143         if (st == NULL)
 144                 return 0;
 145         if (st->num_alloc <= st->num + 1) {
 146                 s = reallocarray(st->data, st->num_alloc, 2 * sizeof(char *));
 147                 if (s == NULL)
 148                         return (0);
 149                 st->data = s;
 150                 st->num_alloc *= 2;
 151         }
 152         if ((loc >= (int)st->num) || (loc < 0))
 153                 st->data[st->num] = data;
 154         else {
 155                 memmove(&(st->data[loc + 1]), &(st->data[loc]),
 156                     sizeof(char *)*(st->num - loc));
 157                 st->data[loc] = data;
 158         }
 159         st->num++;
 160         st->sorted = 0;
 161         return (st->num);
 162 }
 163
 164 void *
 165 sk_delete_ptr(_STACK *st, void *p)
 166 {
 167         int i;
 168
 169         for (i = 0; i < st->num; i++)
 170                 if (st->data[i] == p)
 171                         return (sk_delete(st, i));
 172         return (NULL);
 173 }
 174
 175 void *
 176 sk_delete(_STACK *st, int loc)
 177 {
 178         char *ret;
 179
 180         if (!st || (loc < 0) || (loc >= st->num))
 181                 return NULL;
 182
 183         ret = st->data[loc];
 184         if (loc != st->num - 1) {
 185                 memmove(&(st->data[loc]), &(st->data[loc + 1]),
 186                     sizeof(char *)*(st->num - 1 - loc));
 187         }
 188         st->num--;
 189         return (ret);
 190 }
 191
 192 static int
 193 internal_find(_STACK *st, void *data, int ret_val_options)
 194 {
 195         const void * const *r;
 196         int i;
 197
 198         if (st == NULL)
 199                 return -1;
 200
 201         if (st->comp == NULL) {
 202                 for (i = 0; i < st->num; i++)
 203                         if (st->data[i] == data)
 204                                 return (i);
 205                 return (-1);
 206         }
 207         sk_sort(st);
 208         if (data == NULL)
 209                 return (-1);
 210         r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 211             ret_val_options);
 212         if (r == NULL)
 213                 return (-1);
 214         return (int)((char **)r - st->data);
 215 }
 216
 217 int
 218 sk_find(_STACK *st, void *data)
 219 {
 220         return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 221 }
 222
 223 int
 224 sk_find_ex(_STACK *st, void *data)
 225 {
 226         return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 227 }
 228
 229 int
 230 sk_push(_STACK *st, void *data)
 231 {
 232         return (sk_insert(st, data, st->num));
 233 }
 234
 235 int
 236 sk_unshift(_STACK *st, void *data)
 237 {
 238         return (sk_insert(st, data, 0));
 239 }
 240
 241 void *
 242 sk_shift(_STACK *st)
 243 {
 244         if (st == NULL)
 245                 return (NULL);
 246         if (st->num <= 0)
 247                 return (NULL);
 248         return (sk_delete(st, 0));
 249 }
 250
 251 void *
 252 sk_pop(_STACK *st)
 253 {
 254         if (st == NULL)
 255                 return (NULL);
 256         if (st->num <= 0)
 257                 return (NULL);
 258         return (sk_delete(st, st->num - 1));
 259 }
 260
 261 void
 262 sk_zero(_STACK *st)
 263 {
 264         if (st == NULL)
 265                 return;
 266         if (st->num <= 0)
 267                 return;
 268         memset(st->data, 0, sizeof(st->data)*st->num);
 269         st->num = 0;
 270 }
 271
 272 void
 273 sk_pop_free(_STACK *st, void (*func)(void *))
 274 {
 275         int i;
 276
 277         if (st == NULL)
 278                 return;
 279         for (i = 0; i < st->num; i++)
 280                 if (st->data[i] != NULL)
 281                         func(st->data[i]);
 282         sk_free(st);
 283 }
 284
 285 void
 286 sk_free(_STACK *st)
 287 {
 288         if (st == NULL)
 289                 return;
 290         free(st->data);
 291         free(st);
 292 }
 293
 294 int
 295 sk_num(const _STACK *st)
 296 {
 297         if (st == NULL)
 298                 return -1;
 299         return st->num;
 300 }
 301
 302 void *
 303 sk_value(const _STACK *st, int i)
 304 {
 305         if (!st || (i < 0) || (i >= st->num))
 306                 return NULL;
 307         return st->data[i];
 308 }
 309
 310 void *
 311 sk_set(_STACK *st, int i, void *value)
 312 {
 313         if (!st || (i < 0) || (i >= st->num))
 314                 return NULL;
 315         st->sorted = 0;
 316         return (st->data[i] = value);
 317 }
 318
 319 void
 320 sk_sort(_STACK *st)
 321 {
 322         if (st && !st->sorted) {
 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
 336 int
 337 sk_is_sorted(const _STACK *st)
 338 {
 339         if (!st)
 340                 return 1;
 341         return st->sorted;
 342 }