stack.c revision 296465
1/* crypto/stack/stack.c */ 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59/*- 60 * Code for stacks 61 * Author - Eric Young v 1.0 62 * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the 63 * lowest index for the searched item. 64 * 65 * 1.1 eay - Take from netdb and added to SSLeay 66 * 67 * 1.0 eay - First version 29/07/92 68 */ 69#include <stdio.h> 70#include "cryptlib.h" 71#include <openssl/stack.h> 72#include <openssl/objects.h> 73 74#undef MIN_NODES 75#define MIN_NODES 4 76 77const char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT; 78 79#include <errno.h> 80 81int (*sk_set_cmp_func 82 (STACK * sk, int (*c) (const char *const *, const char *const *))) 83 (const char *const *, const char *const *) { 84 int (*old) (const char *const *, const char *const *) = sk->comp; 85 86 if (sk->comp != c) 87 sk->sorted = 0; 88 sk->comp = c; 89 90 return old; 91} 92 93STACK *sk_dup(STACK * sk) 94{ 95 STACK *ret; 96 char **s; 97 98 if ((ret = sk_new(sk->comp)) == NULL) 99 goto err; 100 s = (char **)OPENSSL_realloc((char *)ret->data, 101 (unsigned int)sizeof(char *) * 102 sk->num_alloc); 103 if (s == NULL) 104 goto err; 105 ret->data = s; 106 107 ret->num = sk->num; 108 memcpy(ret->data, sk->data, sizeof(char *) * sk->num); 109 ret->sorted = sk->sorted; 110 ret->num_alloc = sk->num_alloc; 111 ret->comp = sk->comp; 112 return (ret); 113 err: 114 if (ret) 115 sk_free(ret); 116 return (NULL); 117} 118 119STACK *sk_new_null(void) 120{ 121 return sk_new((int (*)(const char *const *, const char *const *))0); 122} 123 124STACK *sk_new(int (*c) (const char *const *, const char *const *)) 125{ 126 STACK *ret; 127 int i; 128 129 if ((ret = (STACK *) OPENSSL_malloc(sizeof(STACK))) == NULL) 130 goto err; 131 if ((ret->data = 132 (char **)OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL) 133 goto err; 134 for (i = 0; i < MIN_NODES; i++) 135 ret->data[i] = NULL; 136 ret->comp = c; 137 ret->num_alloc = MIN_NODES; 138 ret->num = 0; 139 ret->sorted = 0; 140 return (ret); 141 err: 142 if (ret) 143 OPENSSL_free(ret); 144 return (NULL); 145} 146 147int sk_insert(STACK * st, char *data, int loc) 148{ 149 char **s; 150 151 if (st == NULL) 152 return 0; 153 if (st->num_alloc <= st->num + 1) { 154 s = (char **)OPENSSL_realloc((char *)st->data, 155 (unsigned int)sizeof(char *) * 156 st->num_alloc * 2); 157 if (s == NULL) 158 return (0); 159 st->data = s; 160 st->num_alloc *= 2; 161 } 162 if ((loc >= (int)st->num) || (loc < 0)) 163 st->data[st->num] = data; 164 else { 165 int i; 166 char **f, **t; 167 168 f = (char **)st->data; 169 t = (char **)&(st->data[1]); 170 for (i = st->num; i >= loc; i--) 171 t[i] = f[i]; 172 173#ifdef undef /* no memmove on sunos :-( */ 174 memmove((char *)&(st->data[loc + 1]), 175 (char *)&(st->data[loc]), sizeof(char *) * (st->num - loc)); 176#endif 177 st->data[loc] = data; 178 } 179 st->num++; 180 st->sorted = 0; 181 return (st->num); 182} 183 184char *sk_delete_ptr(STACK * st, char *p) 185{ 186 int i; 187 188 for (i = 0; i < st->num; i++) 189 if (st->data[i] == p) 190 return (sk_delete(st, i)); 191 return (NULL); 192} 193 194char *sk_delete(STACK * st, int loc) 195{ 196 char *ret; 197 int i, j; 198 199 if (!st || (loc < 0) || (loc >= st->num)) 200 return NULL; 201 202 ret = st->data[loc]; 203 if (loc != st->num - 1) { 204 j = st->num - 1; 205 for (i = loc; i < j; i++) 206 st->data[i] = st->data[i + 1]; 207 /* 208 * In theory memcpy is not safe for this memcpy( &(st->data[loc]), 209 * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1)); 210 */ 211 } 212 st->num--; 213 return (ret); 214} 215 216static int internal_find(STACK * st, char *data, int ret_val_options) 217{ 218 char **r; 219 int i; 220 int (*comp_func) (const void *, const void *); 221 if (st == NULL) 222 return -1; 223 224 if (st->comp == NULL) { 225 for (i = 0; i < st->num; i++) 226 if (st->data[i] == data) 227 return (i); 228 return (-1); 229 } 230 sk_sort(st); 231 if (data == NULL) 232 return (-1); 233 /* 234 * This (and the "qsort" below) are the two places in OpenSSL where we 235 * need to convert from our standard (type **,type **) compare callback 236 * type to the (void *,void *) type required by bsearch. However, the 237 * "data" it is being called(back) with are not (type *) pointers, but 238 * the *pointers* to (type *) pointers, so we get our extra level of 239 * pointer dereferencing that way. 240 */ 241 comp_func = (int (*)(const void *, const void *))(st->comp); 242 r = (char **)OBJ_bsearch_ex((char *)&data, (char *)st->data, 243 st->num, sizeof(char *), comp_func, 244 ret_val_options); 245 if (r == NULL) 246 return (-1); 247 return ((int)(r - st->data)); 248} 249 250int sk_find(STACK * st, char *data) 251{ 252 return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH); 253} 254 255int sk_find_ex(STACK * st, char *data) 256{ 257 return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH); 258} 259 260int sk_push(STACK * st, char *data) 261{ 262 return (sk_insert(st, data, st->num)); 263} 264 265int sk_unshift(STACK * st, char *data) 266{ 267 return (sk_insert(st, data, 0)); 268} 269 270char *sk_shift(STACK * st) 271{ 272 if (st == NULL) 273 return (NULL); 274 if (st->num <= 0) 275 return (NULL); 276 return (sk_delete(st, 0)); 277} 278 279char *sk_pop(STACK * st) 280{ 281 if (st == NULL) 282 return (NULL); 283 if (st->num <= 0) 284 return (NULL); 285 return (sk_delete(st, st->num - 1)); 286} 287 288void sk_zero(STACK * st) 289{ 290 if (st == NULL) 291 return; 292 if (st->num <= 0) 293 return; 294 memset((char *)st->data, 0, sizeof(st->data) * st->num); 295 st->num = 0; 296} 297 298void sk_pop_free(STACK * st, void (*func) (void *)) 299{ 300 int i; 301 302 if (st == NULL) 303 return; 304 for (i = 0; i < st->num; i++) 305 if (st->data[i] != NULL) 306 func(st->data[i]); 307 sk_free(st); 308} 309 310void sk_free(STACK * st) 311{ 312 if (st == NULL) 313 return; 314 if (st->data != NULL) 315 OPENSSL_free(st->data); 316 OPENSSL_free(st); 317} 318 319int sk_num(const STACK * st) 320{ 321 if (st == NULL) 322 return -1; 323 return st->num; 324} 325 326char *sk_value(const STACK * st, int i) 327{ 328 if (!st || (i < 0) || (i >= st->num)) 329 return NULL; 330 return st->data[i]; 331} 332 333char *sk_set(STACK * st, int i, char *value) 334{ 335 if (!st || (i < 0) || (i >= st->num)) 336 return NULL; 337 return (st->data[i] = value); 338} 339 340void sk_sort(STACK * st) 341{ 342 if (st && !st->sorted) { 343 int (*comp_func) (const void *, const void *); 344 345 /* 346 * same comment as in sk_find ... previously st->comp was declared as 347 * a (void*,void*) callback type, but this made the population of the 348 * callback pointer illogical - our callbacks compare type** with 349 * type**, so we leave the casting until absolutely necessary (ie. 350 * "now"). 351 */ 352 comp_func = (int (*)(const void *, const void *))(st->comp); 353 qsort(st->data, st->num, sizeof(char *), comp_func); 354 st->sorted = 1; 355 } 356} 357 358int sk_is_sorted(const STACK * st) 359{ 360 if (!st) 361 return 1; 362 return st->sorted; 363} 364