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