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     char **s;
  43
  44     if ((ret = OPENSSL_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     OPENSSL_sk_free(ret);
  60     return (NULL);
  61 }
  62
  63 OPENSSL_STACK *OPENSSL_sk_deep_copy(OPENSSL_STACK *sk, OPENSSL_sk_copyfunc copy_func,
  64                              OPENSSL_sk_freefunc free_func)
  65 {
  66     OPENSSL_STACK *ret;
  67     int i;
  68
  69     if ((ret = OPENSSL_malloc(sizeof(*ret))) == 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             OPENSSL_sk_free(ret);
  91             return NULL;
  92         }
  93     }
  94     return ret;
  95 }
  96
  97 OPENSSL_STACK *OPENSSL_sk_new_null(void)
  98 {
  99     return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL);
 100 }
 101
 102 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
 103 {
 104     OPENSSL_STACK *ret;
 105
 106     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == 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 OPENSSL_sk_insert(OPENSSL_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 *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
 146 {
 147     int i;
 148
 149     for (i = 0; i < st->num; i++)
 150         if (st->data[i] == p)
 151             return OPENSSL_sk_delete(st, i);
 152     return NULL;
 153 }
 154
 155 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 156 {
 157     char *ret;
 158     int i, j;
 159
 160     if (st == NULL || 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(OPENSSL_STACK *st, const void *data,
 178                          int ret_val_options)
 179 {
 180     const void *const *r;
 181     int i;
 182
 183     if (st == NULL)
 184         return -1;
 185
 186     if (st->comp == NULL) {
 187         for (i = 0; i < st->num; i++)
 188             if (st->data[i] == data)
 189                 return (i);
 190         return (-1);
 191     }
 192     OPENSSL_sk_sort(st);
 193     if (data == NULL)
 194         return (-1);
 195     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
 196                         ret_val_options);
 197     if (r == NULL)
 198         return (-1);
 199     return (int)((char **)r - st->data);
 200 }
 201
 202 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 203 {
 204     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 205 }
 206
 207 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 208 {
 209     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 210 }
 211
 212 int OPENSSL_sk_push(OPENSSL_STACK *st, void *data)
 213 {
 214     return (OPENSSL_sk_insert(st, data, st->num));
 215 }
 216
 217 int OPENSSL_sk_unshift(OPENSSL_STACK *st, void *data)
 218 {
 219     return (OPENSSL_sk_insert(st, data, 0));
 220 }
 221
 222 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 223 {
 224     if (st == NULL)
 225         return (NULL);
 226     if (st->num <= 0)
 227         return (NULL);
 228     return (OPENSSL_sk_delete(st, 0));
 229 }
 230
 231 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 232 {
 233     if (st == NULL)
 234         return (NULL);
 235     if (st->num <= 0)
 236         return (NULL);
 237     return (OPENSSL_sk_delete(st, st->num - 1));
 238 }
 239
 240 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 241 {
 242     if (st == NULL)
 243         return;
 244     if (st->num <= 0)
 245         return;
 246     memset(st->data, 0, sizeof(*st->data) * st->num);
 247     st->num = 0;
 248 }
 249
 250 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 251 {
 252     int i;
 253
 254     if (st == NULL)
 255         return;
 256     for (i = 0; i < st->num; i++)
 257         if (st->data[i] != NULL)
 258             func(st->data[i]);
 259     OPENSSL_sk_free(st);
 260 }
 261
 262 void OPENSSL_sk_free(OPENSSL_STACK *st)
 263 {
 264     if (st == NULL)
 265         return;
 266     OPENSSL_free(st->data);
 267     OPENSSL_free(st);
 268 }
 269
 270 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 271 {
 272     if (st == NULL)
 273         return -1;
 274     return st->num;
 275 }
 276
 277 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 278 {
 279     if (st == NULL || i < 0 || i >= st->num)
 280         return NULL;
 281     return st->data[i];
 282 }
 283
 284 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, void *value)
 285 {
 286     if (st == NULL || i < 0 || i >= st->num)
 287         return NULL;
 288     return (st->data[i] = value);
 289 }
 290
 291 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 292 {
 293     if (st && !st->sorted && st->comp != NULL) {
 294         qsort(st->data, st->num, sizeof(char *), st->comp);
 295         st->sorted = 1;
 296     }
 297 }
 298
 299 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 300 {
 301     if (st == NULL)
 302         return 1;
 303     return st->sorted;
 304 }