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 "internal/numbers.h"
  13 #include <openssl/stack.h>
  14 #include <openssl/objects.h>
  15
  16 struct stack_st {
  17     int num;
  18     const char **data;
  19     int sorted;
  20     size_t num_alloc;
  21     OPENSSL_sk_compfunc comp;
  22 };
  23
  24 #undef MIN_NODES
  25 #define MIN_NODES       4
  26
  27 #include <errno.h>
  28
  29 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
  30 {
  31     OPENSSL_sk_compfunc old = sk->comp;
  32
  33     if (sk->comp != c)
  34         sk->sorted = 0;
  35     sk->comp = c;
  36
  37     return old;
  38 }
  39
  40 OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
  41 {
  42     OPENSSL_STACK *ret;
  43
  44     if (sk->num < 0)
  45         return NULL;
  46
  47     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  48         return NULL;
  49
  50     /* direct structure assignment */
  51     *ret = *sk;
  52
  53     if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)
  54         goto err;
  55     memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
  56     return ret;
  57  err:
  58     OPENSSL_sk_free(ret);
  59     return NULL;
  60 }
  61
  62 OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
  63                              OPENSSL_sk_copyfunc copy_func,
  64                              OPENSSL_sk_freefunc free_func)
  65 {
  66     OPENSSL_STACK *ret;
  67     int i;
  68
  69     if (sk->num < 0)
  70         return NULL;
  71
  72     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  73         return NULL;
  74
  75     /* direct structure assignment */
  76     *ret = *sk;
  77
  78     ret->num_alloc = sk->num > MIN_NODES ? (size_t)sk->num : MIN_NODES;
  79     ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);
  80     if (ret->data == NULL) {
  81         OPENSSL_free(ret);
  82         return NULL;
  83     }
  84
  85     for (i = 0; i < ret->num; ++i) {
  86         if (sk->data[i] == NULL)
  87             continue;
  88         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
  89             while (--i >= 0)
  90                 if (ret->data[i] != NULL)
  91                     free_func((void *)ret->data[i]);
  92             OPENSSL_sk_free(ret);
  93             return NULL;
  94         }
  95     }
  96     return ret;
  97 }
  98
  99 OPENSSL_STACK *OPENSSL_sk_new_null(void)
 100 {
 101     return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL);
 102 }
 103
 104 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
 105 {
 106     OPENSSL_STACK *ret;
 107
 108     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
 109         goto err;
 110     if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL)
 111         goto err;
 112     ret->comp = c;
 113     ret->num_alloc = MIN_NODES;
 114     return (ret);
 115
 116  err:
 117     OPENSSL_free(ret);
 118     return (NULL);
 119 }
 120
 121 int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
 122 {
 123     if (st == NULL || st->num < 0 || st->num == INT_MAX) {
 124         return 0;
 125     }
 126
 127     if (st->num_alloc <= (size_t)(st->num + 1)) {
 128         size_t doub_num_alloc = st->num_alloc * 2;
 129         const char **tmpdata;
 130
 131         /* Overflow checks */
 132         if (doub_num_alloc < st->num_alloc)
 133             return 0;
 134
 135         /* Avoid overflow due to multiplication by sizeof(char *) */
 136         if (doub_num_alloc > SIZE_MAX / sizeof(char *))
 137             return 0;
 138
 139         tmpdata = OPENSSL_realloc((char *)st->data,
 140                                   sizeof(char *) * doub_num_alloc);
 141         if (tmpdata == NULL)
 142             return 0;
 143
 144         st->data = tmpdata;
 145         st->num_alloc = doub_num_alloc;
 146     }
 147     if ((loc >= st->num) || (loc < 0)) {
 148         st->data[st->num] = data;
 149     } else {
 150         memmove(&st->data[loc + 1], &st->data[loc],
 151                 sizeof(st->data[0]) * (st->num - loc));
 152         st->data[loc] = data;
 153     }
 154     st->num++;
 155     st->sorted = 0;
 156     return st->num;
 157 }
 158
 159 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
 160 {
 161     int i;
 162
 163     for (i = 0; i < st->num; i++)
 164         if (st->data[i] == p)
 165             return OPENSSL_sk_delete(st, i);
 166     return NULL;
 167 }
 168
 169 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 170 {
 171     const char *ret;
 172
 173     if (st == NULL || loc < 0 || loc >= st->num)
 174         return NULL;
 175
 176     ret = st->data[loc];
 177     if (loc != st->num - 1)
 178          memmove(&st->data[loc], &st->data[loc + 1],
 179                  sizeof(st->data[0]) * (st->num - loc - 1));
 180     st->num--;
 181     return (void *)ret;
 182 }
 183
 184 static int internal_find(OPENSSL_STACK *st, const void *data,
 185                          int ret_val_options)
 186 {
 187     const void *r;
 188     int i;
 189
 190     if (st == NULL)
 191         return -1;
 192
 193     if (st->comp == NULL) {
 194         for (i = 0; i < st->num; i++)
 195             if (st->data[i] == data)
 196                 return (i);
 197         return (-1);
 198     }
 199     OPENSSL_sk_sort(st);
 200     if (data == NULL)
 201         return (-1);
 202     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 203                         ret_val_options);
 204     if (r == NULL)
 205         return (-1);
 206     return (int)((const char **)r - st->data);
 207 }
 208
 209 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 210 {
 211     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 212 }
 213
 214 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 215 {
 216     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 217 }
 218
 219 int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
 220 {
 221     return (OPENSSL_sk_insert(st, data, st->num));
 222 }
 223
 224 int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
 225 {
 226     return (OPENSSL_sk_insert(st, data, 0));
 227 }
 228
 229 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 230 {
 231     if (st == NULL)
 232         return (NULL);
 233     if (st->num <= 0)
 234         return (NULL);
 235     return (OPENSSL_sk_delete(st, 0));
 236 }
 237
 238 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 239 {
 240     if (st == NULL)
 241         return (NULL);
 242     if (st->num <= 0)
 243         return (NULL);
 244     return (OPENSSL_sk_delete(st, st->num - 1));
 245 }
 246
 247 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 248 {
 249     if (st == NULL)
 250         return;
 251     if (st->num <= 0)
 252         return;
 253     memset(st->data, 0, sizeof(*st->data) * st->num);
 254     st->num = 0;
 255 }
 256
 257 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 258 {
 259     int i;
 260
 261     if (st == NULL)
 262         return;
 263     for (i = 0; i < st->num; i++)
 264         if (st->data[i] != NULL)
 265             func((char *)st->data[i]);
 266     OPENSSL_sk_free(st);
 267 }
 268
 269 void OPENSSL_sk_free(OPENSSL_STACK *st)
 270 {
 271     if (st == NULL)
 272         return;
 273     OPENSSL_free(st->data);
 274     OPENSSL_free(st);
 275 }
 276
 277 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 278 {
 279     if (st == NULL)
 280         return -1;
 281     return st->num;
 282 }
 283
 284 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 285 {
 286     if (st == NULL || i < 0 || i >= st->num)
 287         return NULL;
 288     return (void *)st->data[i];
 289 }
 290
 291 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
 292 {
 293     if (st == NULL || i < 0 || i >= st->num)
 294         return NULL;
 295     st->data[i] = data;
 296     return (void *)st->data[i];
 297 }
 298
 299 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 300 {
 301     if (st && !st->sorted && st->comp != NULL) {
 302         qsort(st->data, st->num, sizeof(char *), st->comp);
 303         st->sorted = 1;
 304     }
 305 }
 306
 307 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 308 {
 309     if (st == NULL)
 310         return 1;
 311     return st->sorted;
 312 }