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