crypto/stack/stack.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <stdio.h>
  11 #include "internal/cryptlib.h"
  12 #include <openssl/stack.h>
  13 #include <openssl/objects.h>
  14
  15 struct stack_st {
  16     int num;
  17     char **data;
  18     int sorted;
  19     int num_alloc;
  20     int (*comp) (const void *, const void *);
  21 };
  22
  23 #undef MIN_NODES
  24 #define MIN_NODES       4
  25
  26 #include <errno.h>
  27
  28 int (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *)))
  29  (const void *, const void *) {
  30     int (*old) (const void *, const void *) = sk->comp;
  31
  32     if (sk->comp != c)
  33         sk->sorted = 0;
  34     sk->comp = c;
  35
  36     return old;
  37 }
  38
  39 _STACK *sk_dup(_STACK *sk)
  40 {
  41     _STACK *ret;
  42     char **s;
  43
  44     if ((ret = sk_new(sk->comp)) == NULL)
  45         goto err;
  46     s = OPENSSL_realloc((char *)ret->data,
  47                         (unsigned int)sizeof(char *) * sk->num_alloc);
  48     if (s == NULL)
  49         goto err;
  50     ret->data = s;
  51
  52     ret->num = sk->num;
  53     memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
  54     ret->sorted = sk->sorted;
  55     ret->num_alloc = sk->num_alloc;
  56     ret->comp = sk->comp;
  57     return (ret);
  58  err:
  59     sk_free(ret);
  60     return (NULL);
  61 }
  62
  63 _STACK *sk_deep_copy(_STACK *sk, void *(*copy_func) (void *),
  64                      void (*free_func) (void *))
  65 {
  66     _STACK *ret;
  67     int i;
  68
  69     if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
  70         return ret;
  71     ret->comp = sk->comp;
  72     ret->sorted = sk->sorted;
  73     ret->num = sk->num;
  74     ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
  75     ret->data = OPENSSL_malloc(sizeof(*ret->data) * ret->num_alloc);
  76     if (ret->data == NULL) {
  77         OPENSSL_free(ret);
  78         return NULL;
  79     }
  80     for (i = 0; i < ret->num_alloc; i++)
  81         ret->data[i] = NULL;
  82
  83     for (i = 0; i < ret->num; ++i) {
  84         if (sk->data[i] == NULL)
  85             continue;
  86         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
  87             while (--i >= 0)
  88                 if (ret->data[i] != NULL)
  89                     free_func(ret->data[i]);
  90             sk_free(ret);
  91             return NULL;
  92         }
  93     }
  94     return ret;
  95 }
  96
  97 _STACK *sk_new_null(void)
  98 {
  99     return sk_new((int (*)(const void *, const void *))0);
 100 }
 101
 102 _STACK *sk_new(int (*c) (const void *, const void *))
 103 {
 104     _STACK *ret;
 105
 106     if ((ret = OPENSSL_zalloc(sizeof(_STACK))) == NULL)
 107         goto err;
 108     if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL)
 109         goto err;
 110     ret->comp = c;
 111     ret->num_alloc = MIN_NODES;
 112     return (ret);
 113
 114  err:
 115     OPENSSL_free(ret);
 116     return (NULL);
 117 }
 118
 119 int sk_insert(_STACK *st, void *data, int loc)
 120 {
 121     char **s;
 122
 123     if (st == NULL)
 124         return 0;
 125     if (st->num_alloc <= st->num + 1) {
 126         s = OPENSSL_realloc((char *)st->data,
 127                             (unsigned int)sizeof(char *) * st->num_alloc * 2);
 128         if (s == NULL)
 129             return (0);
 130         st->data = s;
 131         st->num_alloc *= 2;
 132     }
 133     if ((loc >= (int)st->num) || (loc < 0))
 134         st->data[st->num] = data;
 135     else {
 136         memmove(&(st->data[loc + 1]),
 137                 &(st->data[loc]), sizeof(char *) * (st->num - loc));
 138         st->data[loc] = data;
 139     }
 140     st->num++;
 141     st->sorted = 0;
 142     return (st->num);
 143 }
 144
 145 void *sk_delete_ptr(_STACK *st, void *p)
 146 {
 147     int i;
 148
 149     for (i = 0; i < st->num; i++)
 150         if (st->data[i] == p)
 151             return (sk_delete(st, i));
 152     return (NULL);
 153 }
 154
 155 void *sk_delete(_STACK *st, int loc)
 156 {
 157     char *ret;
 158     int i, j;
 159
 160     if (!st || (loc < 0) || (loc >= st->num))
 161         return NULL;
 162
 163     ret = st->data[loc];
 164     if (loc != st->num - 1) {
 165         j = st->num - 1;
 166         for (i = loc; i < j; i++)
 167             st->data[i] = st->data[i + 1];
 168         /*
 169          * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
 170          * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
 171          */
 172     }
 173     st->num--;
 174     return (ret);
 175 }
 176
 177 static int internal_find(_STACK *st, void *data, int ret_val_options)
 178 {
 179     const void *const *r;
 180     int i;
 181
 182     if (st == NULL)
 183         return -1;
 184
 185     if (st->comp == NULL) {
 186         for (i = 0; i < st->num; i++)
 187             if (st->data[i] == data)
 188                 return (i);
 189         return (-1);
 190     }
 191     sk_sort(st);
 192     if (data == NULL)
 193         return (-1);
 194     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 195                         ret_val_options);
 196     if (r == NULL)
 197         return (-1);
 198     return (int)((char **)r - st->data);
 199 }
 200
 201 int sk_find(_STACK *st, void *data)
 202 {
 203     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 204 }
 205
 206 int sk_find_ex(_STACK *st, void *data)
 207 {
 208     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 209 }
 210
 211 int sk_push(_STACK *st, void *data)
 212 {
 213     return (sk_insert(st, data, st->num));
 214 }
 215
 216 int sk_unshift(_STACK *st, void *data)
 217 {
 218     return (sk_insert(st, data, 0));
 219 }
 220
 221 void *sk_shift(_STACK *st)
 222 {
 223     if (st == NULL)
 224         return (NULL);
 225     if (st->num <= 0)
 226         return (NULL);
 227     return (sk_delete(st, 0));
 228 }
 229
 230 void *sk_pop(_STACK *st)
 231 {
 232     if (st == NULL)
 233         return (NULL);
 234     if (st->num <= 0)
 235         return (NULL);
 236     return (sk_delete(st, st->num - 1));
 237 }
 238
 239 void sk_zero(_STACK *st)
 240 {
 241     if (st == NULL)
 242         return;
 243     if (st->num <= 0)
 244         return;
 245     memset(st->data, 0, sizeof(*st->data) * st->num);
 246     st->num = 0;
 247 }
 248
 249 void sk_pop_free(_STACK *st, void (*func) (void *))
 250 {
 251     int i;
 252
 253     if (st == NULL)
 254         return;
 255     for (i = 0; i < st->num; i++)
 256         if (st->data[i] != NULL)
 257             func(st->data[i]);
 258     sk_free(st);
 259 }
 260
 261 void sk_free(_STACK *st)
 262 {
 263     if (st == NULL)
 264         return;
 265     OPENSSL_free(st->data);
 266     OPENSSL_free(st);
 267 }
 268
 269 int sk_num(const _STACK *st)
 270 {
 271     if (st == NULL)
 272         return -1;
 273     return st->num;
 274 }
 275
 276 void *sk_value(const _STACK *st, int i)
 277 {
 278     if (!st || (i < 0) || (i >= st->num))
 279         return NULL;
 280     return st->data[i];
 281 }
 282
 283 void *sk_set(_STACK *st, int i, void *value)
 284 {
 285     if (!st || (i < 0) || (i >= st->num))
 286         return NULL;
 287     return (st->data[i] = value);
 288 }
 289
 290 void sk_sort(_STACK *st)
 291 {
 292     if (st && !st->sorted && st->comp != NULL) {
 293         int (*comp_func) (const void *, const void *);
 294
 295         /*
 296          * same comment as in sk_find ... previously st->comp was declared as
 297          * a (void*,void*) callback type, but this made the population of the
 298          * callback pointer illogical - our callbacks compare type** with
 299          * type**, so we leave the casting until absolutely necessary (ie.
 300          * "now").
 301          */
 302         comp_func = (int (*)(const void *, const void *))(st->comp);
 303         qsort(st->data, st->num, sizeof(char *), comp_func);
 304         st->sorted = 1;
 305     }
 306 }
 307
 308 int sk_is_sorted(const _STACK *st)
 309 {
 310     if (!st)
 311         return 1;
 312     return st->sorted;
 313 }