155714Skris/* crypto/stack/stack.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 8280304Sjkim * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15280304Sjkim * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 22280304Sjkim * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 37280304Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40280304Sjkim * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 52280304Sjkim * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 5855714Skris 59280304Sjkim/*- 60280304Sjkim * Code for stacks 6155714Skris * Author - Eric Young v 1.0 62280304Sjkim * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the 63280304Sjkim * lowest index for the searched item. 6455714Skris * 6555714Skris * 1.1 eay - Take from netdb and added to SSLeay 6655714Skris * 6755714Skris * 1.0 eay - First version 29/07/92 6855714Skris */ 6955714Skris#include <stdio.h> 7055714Skris#include "cryptlib.h" 7155714Skris#include <openssl/stack.h> 72160814Ssimon#include <openssl/objects.h> 7355714Skris 7455714Skris#undef MIN_NODES 75280304Sjkim#define MIN_NODES 4 7655714Skris 77280304Sjkimconst char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT; 7855714Skris 7955714Skris#include <errno.h> 8055714Skris 81280304Sjkimint (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *))) 82280304Sjkim (const void *, const void *) { 83280304Sjkim int (*old) (const void *, const void *) = sk->comp; 8455714Skris 85280304Sjkim if (sk->comp != c) 86280304Sjkim sk->sorted = 0; 87280304Sjkim sk->comp = c; 8855714Skris 89280304Sjkim return old; 90280304Sjkim} 9155714Skris 92238405Sjkim_STACK *sk_dup(_STACK *sk) 93280304Sjkim{ 94280304Sjkim _STACK *ret; 95280304Sjkim char **s; 9655714Skris 97280304Sjkim if ((ret = sk_new(sk->comp)) == NULL) 98280304Sjkim goto err; 99280304Sjkim s = (char **)OPENSSL_realloc((char *)ret->data, 100280304Sjkim (unsigned int)sizeof(char *) * 101280304Sjkim sk->num_alloc); 102280304Sjkim if (s == NULL) 103280304Sjkim goto err; 104280304Sjkim ret->data = s; 10555714Skris 106280304Sjkim ret->num = sk->num; 107280304Sjkim memcpy(ret->data, sk->data, sizeof(char *) * sk->num); 108280304Sjkim ret->sorted = sk->sorted; 109280304Sjkim ret->num_alloc = sk->num_alloc; 110280304Sjkim ret->comp = sk->comp; 111280304Sjkim return (ret); 112280304Sjkim err: 113280304Sjkim if (ret) 114280304Sjkim sk_free(ret); 115280304Sjkim return (NULL); 116280304Sjkim} 11755714Skris 118238405Sjkim_STACK *sk_new_null(void) 119280304Sjkim{ 120280304Sjkim return sk_new((int (*)(const void *, const void *))0); 121280304Sjkim} 12268651Skris 123280304Sjkim_STACK *sk_new(int (*c) (const void *, const void *)) 124280304Sjkim{ 125280304Sjkim _STACK *ret; 126280304Sjkim int i; 12755714Skris 128280304Sjkim if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL) 129280304Sjkim goto err; 130280304Sjkim if ((ret->data = OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL) 131280304Sjkim goto err; 132280304Sjkim for (i = 0; i < MIN_NODES; i++) 133280304Sjkim ret->data[i] = NULL; 134280304Sjkim ret->comp = c; 135280304Sjkim ret->num_alloc = MIN_NODES; 136280304Sjkim ret->num = 0; 137280304Sjkim ret->sorted = 0; 138280304Sjkim return (ret); 139280304Sjkim err: 140280304Sjkim if (ret) 141280304Sjkim OPENSSL_free(ret); 142280304Sjkim return (NULL); 143280304Sjkim} 14455714Skris 145238405Sjkimint sk_insert(_STACK *st, void *data, int loc) 146280304Sjkim{ 147280304Sjkim char **s; 14855714Skris 149280304Sjkim if (st == NULL) 150280304Sjkim return 0; 151280304Sjkim if (st->num_alloc <= st->num + 1) { 152280304Sjkim s = OPENSSL_realloc((char *)st->data, 153280304Sjkim (unsigned int)sizeof(char *) * st->num_alloc * 2); 154280304Sjkim if (s == NULL) 155280304Sjkim return (0); 156280304Sjkim st->data = s; 157280304Sjkim st->num_alloc *= 2; 158280304Sjkim } 159280304Sjkim if ((loc >= (int)st->num) || (loc < 0)) 160280304Sjkim st->data[st->num] = data; 161280304Sjkim else { 162280304Sjkim int i; 163280304Sjkim char **f, **t; 16455714Skris 165280304Sjkim f = st->data; 166280304Sjkim t = &(st->data[1]); 167280304Sjkim for (i = st->num; i >= loc; i--) 168280304Sjkim t[i] = f[i]; 169280304Sjkim 170280304Sjkim#ifdef undef /* no memmove on sunos :-( */ 171280304Sjkim memmove(&(st->data[loc + 1]), 172280304Sjkim &(st->data[loc]), sizeof(char *) * (st->num - loc)); 17355714Skris#endif 174280304Sjkim st->data[loc] = data; 175280304Sjkim } 176280304Sjkim st->num++; 177280304Sjkim st->sorted = 0; 178280304Sjkim return (st->num); 179280304Sjkim} 18055714Skris 181238405Sjkimvoid *sk_delete_ptr(_STACK *st, void *p) 182280304Sjkim{ 183280304Sjkim int i; 18455714Skris 185280304Sjkim for (i = 0; i < st->num; i++) 186280304Sjkim if (st->data[i] == p) 187280304Sjkim return (sk_delete(st, i)); 188280304Sjkim return (NULL); 189280304Sjkim} 19055714Skris 191238405Sjkimvoid *sk_delete(_STACK *st, int loc) 192280304Sjkim{ 193280304Sjkim char *ret; 194280304Sjkim int i, j; 19555714Skris 196280304Sjkim if (!st || (loc < 0) || (loc >= st->num)) 197280304Sjkim return NULL; 19855714Skris 199280304Sjkim ret = st->data[loc]; 200280304Sjkim if (loc != st->num - 1) { 201280304Sjkim j = st->num - 1; 202280304Sjkim for (i = loc; i < j; i++) 203280304Sjkim st->data[i] = st->data[i + 1]; 204280304Sjkim /* 205280304Sjkim * In theory memcpy is not safe for this memcpy( &(st->data[loc]), 206280304Sjkim * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1)); 207280304Sjkim */ 208280304Sjkim } 209280304Sjkim st->num--; 210280304Sjkim return (ret); 211280304Sjkim} 21255714Skris 213238405Sjkimstatic int internal_find(_STACK *st, void *data, int ret_val_options) 214280304Sjkim{ 215280304Sjkim const void *const *r; 216280304Sjkim int i; 217238405Sjkim 218280304Sjkim if (st == NULL) 219280304Sjkim return -1; 22055714Skris 221280304Sjkim if (st->comp == NULL) { 222280304Sjkim for (i = 0; i < st->num; i++) 223280304Sjkim if (st->data[i] == data) 224280304Sjkim return (i); 225280304Sjkim return (-1); 226280304Sjkim } 227280304Sjkim sk_sort(st); 228280304Sjkim if (data == NULL) 229280304Sjkim return (-1); 230280304Sjkim r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp, 231280304Sjkim ret_val_options); 232280304Sjkim if (r == NULL) 233280304Sjkim return (-1); 234280304Sjkim return (int)((char **)r - st->data); 235280304Sjkim} 23655714Skris 237238405Sjkimint sk_find(_STACK *st, void *data) 238280304Sjkim{ 239280304Sjkim return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH); 240280304Sjkim} 241280304Sjkim 242238405Sjkimint sk_find_ex(_STACK *st, void *data) 243280304Sjkim{ 244280304Sjkim return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH); 245280304Sjkim} 246160814Ssimon 247238405Sjkimint sk_push(_STACK *st, void *data) 248280304Sjkim{ 249280304Sjkim return (sk_insert(st, data, st->num)); 250280304Sjkim} 25155714Skris 252238405Sjkimint sk_unshift(_STACK *st, void *data) 253280304Sjkim{ 254280304Sjkim return (sk_insert(st, data, 0)); 255280304Sjkim} 25655714Skris 257238405Sjkimvoid *sk_shift(_STACK *st) 258280304Sjkim{ 259280304Sjkim if (st == NULL) 260280304Sjkim return (NULL); 261280304Sjkim if (st->num <= 0) 262280304Sjkim return (NULL); 263280304Sjkim return (sk_delete(st, 0)); 264280304Sjkim} 26555714Skris 266238405Sjkimvoid *sk_pop(_STACK *st) 267280304Sjkim{ 268280304Sjkim if (st == NULL) 269280304Sjkim return (NULL); 270280304Sjkim if (st->num <= 0) 271280304Sjkim return (NULL); 272280304Sjkim return (sk_delete(st, st->num - 1)); 273280304Sjkim} 27455714Skris 275238405Sjkimvoid sk_zero(_STACK *st) 276280304Sjkim{ 277280304Sjkim if (st == NULL) 278280304Sjkim return; 279280304Sjkim if (st->num <= 0) 280280304Sjkim return; 281280304Sjkim memset((char *)st->data, 0, sizeof(*st->data) * st->num); 282280304Sjkim st->num = 0; 283280304Sjkim} 28455714Skris 285280304Sjkimvoid sk_pop_free(_STACK *st, void (*func) (void *)) 286280304Sjkim{ 287280304Sjkim int i; 28855714Skris 289280304Sjkim if (st == NULL) 290280304Sjkim return; 291280304Sjkim for (i = 0; i < st->num; i++) 292280304Sjkim if (st->data[i] != NULL) 293280304Sjkim func(st->data[i]); 294280304Sjkim sk_free(st); 295280304Sjkim} 29655714Skris 297238405Sjkimvoid sk_free(_STACK *st) 298280304Sjkim{ 299280304Sjkim if (st == NULL) 300280304Sjkim return; 301280304Sjkim if (st->data != NULL) 302280304Sjkim OPENSSL_free(st->data); 303280304Sjkim OPENSSL_free(st); 304280304Sjkim} 30555714Skris 306238405Sjkimint sk_num(const _STACK *st) 30755714Skris{ 308280304Sjkim if (st == NULL) 309280304Sjkim return -1; 310280304Sjkim return st->num; 31155714Skris} 31255714Skris 313238405Sjkimvoid *sk_value(const _STACK *st, int i) 31455714Skris{ 315280304Sjkim if (!st || (i < 0) || (i >= st->num)) 316280304Sjkim return NULL; 317280304Sjkim return st->data[i]; 31855714Skris} 31955714Skris 320238405Sjkimvoid *sk_set(_STACK *st, int i, void *value) 32155714Skris{ 322280304Sjkim if (!st || (i < 0) || (i >= st->num)) 323280304Sjkim return NULL; 324280304Sjkim return (st->data[i] = value); 32555714Skris} 32655714Skris 327238405Sjkimvoid sk_sort(_STACK *st) 328280304Sjkim{ 329280304Sjkim if (st && !st->sorted) { 330280304Sjkim int (*comp_func) (const void *, const void *); 33155714Skris 332280304Sjkim /* 333280304Sjkim * same comment as in sk_find ... previously st->comp was declared as 334280304Sjkim * a (void*,void*) callback type, but this made the population of the 335280304Sjkim * callback pointer illogical - our callbacks compare type** with 336280304Sjkim * type**, so we leave the casting until absolutely necessary (ie. 337280304Sjkim * "now"). 338280304Sjkim */ 339280304Sjkim comp_func = (int (*)(const void *, const void *))(st->comp); 340280304Sjkim qsort(st->data, st->num, sizeof(char *), comp_func); 341280304Sjkim st->sorted = 1; 342280304Sjkim } 343280304Sjkim} 344142425Snectar 345238405Sjkimint sk_is_sorted(const _STACK *st) 346280304Sjkim{ 347280304Sjkim if (!st) 348280304Sjkim return 1; 349280304Sjkim return st->sorted; 350280304Sjkim} 351