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(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(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, void *data, int loc)
 115 {
 116     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]),
 132                 &(st->data[loc]), sizeof(char *) * (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     char *ret;
 153     int i, j;
 154
 155     if (st == NULL || loc < 0 || loc >= st->num)
 156         return NULL;
 157
 158     ret = st->data[loc];
 159     if (loc != st->num - 1) {
 160         j = st->num - 1;
 161         for (i = loc; i < j; i++)
 162             st->data[i] = st->data[i + 1];
 163         /*
 164          * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
 165          * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
 166          */
 167     }
 168     st->num--;
 169     return (ret);
 170 }
 171
 172 static int internal_find(OPENSSL_STACK *st, const void *data,
 173                          int ret_val_options)
 174 {
 175     const void *const *r;
 176     int i;
 177
 178     if (st == NULL)
 179         return -1;
 180
 181     if (st->comp == NULL) {
 182         for (i = 0; i < st->num; i++)
 183             if (st->data[i] == data)
 184                 return (i);
 185         return (-1);
 186     }
 187     OPENSSL_sk_sort(st);
 188     if (data == NULL)
 189         return (-1);
 190     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 191                         ret_val_options);
 192     if (r == NULL)
 193         return (-1);
 194     return (int)((char **)r - st->data);
 195 }
 196
 197 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 198 {
 199     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 200 }
 201
 202 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 203 {
 204     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 205 }
 206
 207 int OPENSSL_sk_push(OPENSSL_STACK *st, void *data)
 208 {
 209     return (OPENSSL_sk_insert(st, data, st->num));
 210 }
 211
 212 int OPENSSL_sk_unshift(OPENSSL_STACK *st, void *data)
 213 {
 214     return (OPENSSL_sk_insert(st, data, 0));
 215 }
 216
 217 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 218 {
 219     if (st == NULL)
 220         return (NULL);
 221     if (st->num <= 0)
 222         return (NULL);
 223     return (OPENSSL_sk_delete(st, 0));
 224 }
 225
 226 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 227 {
 228     if (st == NULL)
 229         return (NULL);
 230     if (st->num <= 0)
 231         return (NULL);
 232     return (OPENSSL_sk_delete(st, st->num - 1));
 233 }
 234
 235 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 236 {
 237     if (st == NULL)
 238         return;
 239     if (st->num <= 0)
 240         return;
 241     memset(st->data, 0, sizeof(*st->data) * st->num);
 242     st->num = 0;
 243 }
 244
 245 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 246 {
 247     int i;
 248
 249     if (st == NULL)
 250         return;
 251     for (i = 0; i < st->num; i++)
 252         if (st->data[i] != NULL)
 253             func(st->data[i]);
 254     OPENSSL_sk_free(st);
 255 }
 256
 257 void OPENSSL_sk_free(OPENSSL_STACK *st)
 258 {
 259     if (st == NULL)
 260         return;
 261     OPENSSL_free(st->data);
 262     OPENSSL_free(st);
 263 }
 264
 265 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 266 {
 267     if (st == NULL)
 268         return -1;
 269     return st->num;
 270 }
 271
 272 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 273 {
 274     if (st == NULL || i < 0 || i >= st->num)
 275         return NULL;
 276     return st->data[i];
 277 }
 278
 279 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, void *value)
 280 {
 281     if (st == NULL || i < 0 || i >= st->num)
 282         return NULL;
 283     return (st->data[i] = value);
 284 }
 285
 286 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 287 {
 288     if (st && !st->sorted && st->comp != NULL) {
 289         qsort(st->data, st->num, sizeof(char *), st->comp);
 290         st->sorted = 1;
 291     }
 292 }
 293
 294 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 295 {
 296     if (st == NULL)
 297         return 1;
 298     return st->sorted;
 299 }