stack.c revision 296341
1218887Sdim/* crypto/stack/stack.c */ 2218887Sdim/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3218887Sdim * All rights reserved. 4218887Sdim * 5218887Sdim * This package is an SSL implementation written 6218887Sdim * by Eric Young (eay@cryptsoft.com). 7218887Sdim * The implementation was written so as to conform with Netscapes SSL. 8218887Sdim * 9218887Sdim * This library is free for commercial and non-commercial use as long as 10218887Sdim * the following conditions are aheared to. The following conditions 11218887Sdim * apply to all code found in this distribution, be it the RC4, RSA, 12218887Sdim * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13218887Sdim * included with this distribution is covered by the same copyright terms 14218887Sdim * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15218887Sdim * 16218887Sdim * Copyright remains Eric Young's, and as such any Copyright notices in 17218887Sdim * the code are not to be removed. 18218887Sdim * If this package is used in a product, Eric Young should be given attribution 19218887Sdim * as the author of the parts of the library used. 20263508Sdim * This can be in the form of a textual message at program startup or 21218887Sdim * in documentation (online or textual) provided with the package. 22218887Sdim * 23218887Sdim * Redistribution and use in source and binary forms, with or without 24218887Sdim * modification, are permitted provided that the following conditions 25218887Sdim * are met: 26218887Sdim * 1. Redistributions of source code must retain the copyright 27218887Sdim * notice, this list of conditions and the following disclaimer. 28218887Sdim * 2. Redistributions in binary form must reproduce the above copyright 29218887Sdim * notice, this list of conditions and the following disclaimer in the 30218887Sdim * documentation and/or other materials provided with the distribution. 31218887Sdim * 3. All advertising materials mentioning features or use of this software 32218887Sdim * must display the following acknowledgement: 33218887Sdim * "This product includes cryptographic software written by 34218887Sdim * Eric Young (eay@cryptsoft.com)" 35218887Sdim * The word 'cryptographic' can be left out if the rouines from the library 36218887Sdim * being used are not cryptographic related :-). 37218887Sdim * 4. If you include any Windows specific code (or a derivative thereof) from 38218887Sdim * the apps directory (application code) you must include an acknowledgement: 39218887Sdim * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40218887Sdim * 41218887Sdim * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42218887Sdim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43218887Sdim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44218887Sdim * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45218887Sdim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46218887Sdim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47218887Sdim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48218887Sdim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49218887Sdim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50218887Sdim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51226633Sdim * SUCH DAMAGE. 52224145Sdim * 53218887Sdim * The licence and distribution terms for any publically available version or 54218887Sdim * derivative of this code cannot be changed. i.e. this code cannot simply be 55249423Sdim * copied and put under another distribution licence 56249423Sdim * [including the GNU Public Licence.] 57218887Sdim */ 58218887Sdim 59218887Sdim/*- 60218887Sdim * Code for stacks 61218887Sdim * Author - Eric Young v 1.0 62218887Sdim * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the 63218887Sdim * lowest index for the searched item. 64218887Sdim * 65218887Sdim * 1.1 eay - Take from netdb and added to SSLeay 66218887Sdim * 67218887Sdim * 1.0 eay - First version 29/07/92 68218887Sdim */ 69218887Sdim#include <stdio.h> 70218887Sdim#include "cryptlib.h" 71218887Sdim#include <openssl/stack.h> 72218887Sdim#include <openssl/objects.h> 73218887Sdim 74218887Sdim#undef MIN_NODES 75218887Sdim#define MIN_NODES 4 76218887Sdim 77218887Sdimconst char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT; 78218887Sdim 79218887Sdim#include <errno.h> 80218887Sdim 81218887Sdimint (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *))) 82218887Sdim (const void *, const void *) { 83249423Sdim int (*old) (const void *, const void *) = sk->comp; 84249423Sdim 85249423Sdim if (sk->comp != c) 86249423Sdim sk->sorted = 0; 87249423Sdim sk->comp = c; 88249423Sdim 89218887Sdim return old; 90249423Sdim} 91218887Sdim 92218887Sdim_STACK *sk_dup(_STACK *sk) 93218887Sdim{ 94218887Sdim _STACK *ret; 95218887Sdim char **s; 96218887Sdim 97218887Sdim if ((ret = sk_new(sk->comp)) == NULL) 98218887Sdim goto err; 99218887Sdim s = (char **)OPENSSL_realloc((char *)ret->data, 100218887Sdim (unsigned int)sizeof(char *) * 101218887Sdim sk->num_alloc); 102218887Sdim if (s == NULL) 103218887Sdim goto err; 104218887Sdim ret->data = s; 105218887Sdim 106218887Sdim ret->num = sk->num; 107218887Sdim memcpy(ret->data, sk->data, sizeof(char *) * sk->num); 108218887Sdim ret->sorted = sk->sorted; 109218887Sdim ret->num_alloc = sk->num_alloc; 110218887Sdim ret->comp = sk->comp; 111218887Sdim return (ret); 112218887Sdim err: 113218887Sdim if (ret) 114218887Sdim sk_free(ret); 115218887Sdim return (NULL); 116218887Sdim} 117218887Sdim 118218887Sdim_STACK *sk_new_null(void) 119218887Sdim{ 120218887Sdim return sk_new((int (*)(const void *, const void *))0); 121218887Sdim} 122218887Sdim 123218887Sdim_STACK *sk_new(int (*c) (const void *, const void *)) 124218887Sdim{ 125218887Sdim _STACK *ret; 126218887Sdim int i; 127226633Sdim 128226633Sdim if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL) 129226633Sdim goto err; 130226633Sdim if ((ret->data = OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL) 131226633Sdim goto err; 132226633Sdim for (i = 0; i < MIN_NODES; i++) 133226633Sdim ret->data[i] = NULL; 134226633Sdim ret->comp = c; 135226633Sdim ret->num_alloc = MIN_NODES; 136226633Sdim ret->num = 0; 137226633Sdim ret->sorted = 0; 138226633Sdim return (ret); 139226633Sdim err: 140226633Sdim if (ret) 141226633Sdim OPENSSL_free(ret); 142226633Sdim return (NULL); 143226633Sdim} 144226633Sdim 145218887Sdimint sk_insert(_STACK *st, void *data, int loc) 146226633Sdim{ 147226633Sdim char **s; 148226633Sdim 149226633Sdim if (st == NULL) 150226633Sdim return 0; 151218887Sdim if (st->num_alloc <= st->num + 1) { 152218887Sdim s = OPENSSL_realloc((char *)st->data, 153218887Sdim (unsigned int)sizeof(char *) * st->num_alloc * 2); 154218887Sdim if (s == NULL) 155218887Sdim return (0); 156218887Sdim st->data = s; 157218887Sdim st->num_alloc *= 2; 158218887Sdim } 159218887Sdim if ((loc >= (int)st->num) || (loc < 0)) 160218887Sdim st->data[st->num] = data; 161218887Sdim else { 162218887Sdim int i; 163218887Sdim char **f, **t; 164218887Sdim 165218887Sdim f = st->data; 166218887Sdim t = &(st->data[1]); 167218887Sdim for (i = st->num; i >= loc; i--) 168226633Sdim t[i] = f[i]; 169218887Sdim 170218887Sdim#ifdef undef /* no memmove on sunos :-( */ 171218887Sdim memmove(&(st->data[loc + 1]), 172226633Sdim &(st->data[loc]), sizeof(char *) * (st->num - loc)); 173218887Sdim#endif 174218887Sdim st->data[loc] = data; 175218887Sdim } 176218887Sdim st->num++; 177218887Sdim st->sorted = 0; 178218887Sdim return (st->num); 179218887Sdim} 180218887Sdim 181218887Sdimvoid *sk_delete_ptr(_STACK *st, void *p) 182218887Sdim{ 183226633Sdim int i; 184218887Sdim 185218887Sdim for (i = 0; i < st->num; i++) 186218887Sdim if (st->data[i] == p) 187218887Sdim return (sk_delete(st, i)); 188218887Sdim return (NULL); 189218887Sdim} 190218887Sdim 191218887Sdimvoid *sk_delete(_STACK *st, int loc) 192218887Sdim{ 193218887Sdim char *ret; 194218887Sdim int i, j; 195218887Sdim 196218887Sdim if (!st || (loc < 0) || (loc >= st->num)) 197218887Sdim return NULL; 198218887Sdim 199218887Sdim ret = st->data[loc]; 200218887Sdim if (loc != st->num - 1) { 201218887Sdim j = st->num - 1; 202226633Sdim for (i = loc; i < j; i++) 203226633Sdim st->data[i] = st->data[i + 1]; 204226633Sdim /* 205226633Sdim * In theory memcpy is not safe for this memcpy( &(st->data[loc]), 206226633Sdim * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1)); 207226633Sdim */ 208218887Sdim } 209218887Sdim st->num--; 210218887Sdim return (ret); 211218887Sdim} 212218887Sdim 213226633Sdimstatic int internal_find(_STACK *st, void *data, int ret_val_options) 214226633Sdim{ 215218887Sdim const void *const *r; 216226633Sdim int i; 217218887Sdim 218218887Sdim if (st == NULL) 219226633Sdim return -1; 220226633Sdim 221226633Sdim if (st->comp == NULL) { 222226633Sdim for (i = 0; i < st->num; i++) 223226633Sdim if (st->data[i] == data) 224226633Sdim return (i); 225218887Sdim return (-1); 226218887Sdim } 227218887Sdim sk_sort(st); 228218887Sdim if (data == NULL) 229226633Sdim return (-1); 230226633Sdim r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp, 231218887Sdim ret_val_options); 232218887Sdim if (r == NULL) 233218887Sdim return (-1); 234218887Sdim return (int)((char **)r - st->data); 235218887Sdim} 236218887Sdim 237218887Sdimint sk_find(_STACK *st, void *data) 238218887Sdim{ 239218887Sdim return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH); 240218887Sdim} 241218887Sdim 242218887Sdimint sk_find_ex(_STACK *st, void *data) 243218887Sdim{ 244218887Sdim return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH); 245218887Sdim} 246218887Sdim 247218887Sdimint sk_push(_STACK *st, void *data) 248218887Sdim{ 249218887Sdim return (sk_insert(st, data, st->num)); 250218887Sdim} 251218887Sdim 252218887Sdimint sk_unshift(_STACK *st, void *data) 253218887Sdim{ 254218887Sdim return (sk_insert(st, data, 0)); 255218887Sdim} 256218887Sdim 257218887Sdimvoid *sk_shift(_STACK *st) 258218887Sdim{ 259234353Sdim if (st == NULL) 260218887Sdim return (NULL); 261218887Sdim if (st->num <= 0) 262218887Sdim return (NULL); 263218887Sdim return (sk_delete(st, 0)); 264218887Sdim} 265218887Sdim 266218887Sdimvoid *sk_pop(_STACK *st) 267218887Sdim{ 268218887Sdim if (st == NULL) 269218887Sdim return (NULL); 270218887Sdim if (st->num <= 0) 271218887Sdim return (NULL); 272218887Sdim return (sk_delete(st, st->num - 1)); 273224145Sdim} 274218887Sdim 275218887Sdimvoid sk_zero(_STACK *st) 276218887Sdim{ 277218887Sdim if (st == NULL) 278218887Sdim return; 279218887Sdim if (st->num <= 0) 280218887Sdim return; 281218887Sdim memset((char *)st->data, 0, sizeof(*st->data) * st->num); 282218887Sdim st->num = 0; 283218887Sdim} 284218887Sdim 285218887Sdimvoid sk_pop_free(_STACK *st, void (*func) (void *)) 286218887Sdim{ 287218887Sdim int i; 288218887Sdim 289218887Sdim if (st == NULL) 290218887Sdim return; 291218887Sdim for (i = 0; i < st->num; i++) 292218887Sdim if (st->data[i] != NULL) 293218887Sdim func(st->data[i]); 294218887Sdim sk_free(st); 295218887Sdim} 296218887Sdim 297218887Sdimvoid sk_free(_STACK *st) 298218887Sdim{ 299218887Sdim if (st == NULL) 300218887Sdim return; 301218887Sdim if (st->data != NULL) 302218887Sdim OPENSSL_free(st->data); 303218887Sdim OPENSSL_free(st); 304218887Sdim} 305218887Sdim 306218887Sdimint sk_num(const _STACK *st) 307218887Sdim{ 308218887Sdim if (st == NULL) 309218887Sdim return -1; 310218887Sdim return st->num; 311218887Sdim} 312218887Sdim 313218887Sdimvoid *sk_value(const _STACK *st, int i) 314218887Sdim{ 315218887Sdim if (!st || (i < 0) || (i >= st->num)) 316218887Sdim return NULL; 317218887Sdim return st->data[i]; 318218887Sdim} 319218887Sdim 320218887Sdimvoid *sk_set(_STACK *st, int i, void *value) 321218887Sdim{ 322218887Sdim if (!st || (i < 0) || (i >= st->num)) 323218887Sdim return NULL; 324218887Sdim return (st->data[i] = value); 325218887Sdim} 326218887Sdim 327218887Sdimvoid sk_sort(_STACK *st) 328218887Sdim{ 329218887Sdim if (st && !st->sorted) { 330218887Sdim int (*comp_func) (const void *, const void *); 331218887Sdim 332218887Sdim /* 333218887Sdim * same comment as in sk_find ... previously st->comp was declared as 334218887Sdim * a (void*,void*) callback type, but this made the population of the 335218887Sdim * callback pointer illogical - our callbacks compare type** with 336218887Sdim * type**, so we leave the casting until absolutely necessary (ie. 337218887Sdim * "now"). 338218887Sdim */ 339218887Sdim comp_func = (int (*)(const void *, const void *))(st->comp); 340218887Sdim qsort(st->data, st->num, sizeof(char *), comp_func); 341218887Sdim st->sorted = 1; 342218887Sdim } 343218887Sdim} 344218887Sdim 345218887Sdimint sk_is_sorted(const _STACK *st) 346218887Sdim{ 347218887Sdim if (!st) 348218887Sdim return 1; 349218887Sdim return st->sorted; 350218887Sdim} 351218887Sdim