[thirdparty/openssl.git] / crypto / stack / stack.c

/*
 * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include <stdio.h>
#include "internal/cryptlib.h"
#include "internal/numbers.h"
#include "internal/safe_math.h"
#include <openssl/stack.h>
#include <errno.h>
#include <openssl/e_os2.h>      /* For ossl_inline */

OSSL_SAFE_MATH_SIGNED(int, int)

/*
 * The initial number of nodes in the array.
 */
static const int min_nodes = 4;
static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
    ? (int)(SIZE_MAX / sizeof(void *)) : INT_MAX;

struct stack_st {
    int num;
    const void **data;
    int sorted;
    int num_alloc;
    OPENSSL_sk_compfunc comp;
    OPENSSL_sk_freefunc_thunk free_thunk;
};

OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk,
                                            OPENSSL_sk_compfunc c)
{
    OPENSSL_sk_compfunc old = sk->comp;

    if (sk->comp != c)
        sk->sorted = 0;
    sk->comp = c;

    return old;
}

OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
{
    OPENSSL_STACK *ret;

    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
        goto err;

    if (sk == NULL) {
        ret->num = 0;
        ret->sorted = 0;
        ret->comp = NULL;
    } else {
        /* direct structure assignment */
        *ret = *sk;
    }

    if (sk == NULL || sk->num == 0) {
        /* postpone |ret->data| allocation */
        ret->data = NULL;
        ret->num_alloc = 0;
        return ret;
    }

    /* duplicate |sk->data| content */
    ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc);
    if (ret->data == NULL)
        goto err;
    memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
    return ret;

 err:
    OPENSSL_sk_free(ret);
    return NULL;
}

OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
                                    OPENSSL_sk_copyfunc copy_func,
                                    OPENSSL_sk_freefunc free_func)
{
    OPENSSL_STACK *ret;
    int i;

    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
        goto err;

    if (sk == NULL) {
        ret->num = 0;
        ret->sorted = 0;
        ret->comp = NULL;
    } else {
        /* direct structure assignment */
        *ret = *sk;
    }

    if (sk == NULL || sk->num == 0) {
        /* postpone |ret| data allocation */
        ret->data = NULL;
        ret->num_alloc = 0;
        return ret;
    }

    ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
    ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);
    if (ret->data == NULL)
        goto err;

    for (i = 0; i < ret->num; ++i) {
        if (sk->data[i] == NULL)
            continue;
        if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
            while (--i >= 0)
                if (ret->data[i] != NULL)
                    free_func((void *)ret->data[i]);
            goto err;
        }
    }
    return ret;

 err:
    OPENSSL_sk_free(ret);
    return NULL;
}

OPENSSL_STACK *OPENSSL_sk_new_null(void)
{
    return OPENSSL_sk_new_reserve(NULL, 0);
}

OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
{
    return OPENSSL_sk_new_reserve(c, 0);
}

/*
 * Calculate the array growth based on the target size.
 *
 * The growth factor is a rational number and is defined by a numerator
 * and a denominator.  According to Andrew Koenig in his paper "Why Are
 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
 * than the golden ratio (1.618...).
 *
 * Considering only the Fibonacci ratios less than the golden ratio, the
 * number of steps from the minimum allocation to integer overflow is:
 *      factor  decimal    growths
 *       3/2     1.5          51
 *       8/5     1.6          45
 *      21/13    1.615...     44
 *
 * All larger factors have the same number of growths.
 *
 * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice.
 */
static ossl_inline int compute_growth(int target, int current)
{
    int err = 0;

    while (current < target) {
        if (current >= max_nodes)
            return 0;

        current = safe_muldiv_int(current, 8, 5, &err);
        if (err != 0)
            return 0;
        if (current >= max_nodes)
            current = max_nodes;
    }
    return current;
}

/* internal STACK storage allocation */
static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
{
    const void **tmpdata;
    int num_alloc;

    /* Check to see the reservation isn't exceeding the hard limit */
    if (n > max_nodes - st->num) {
        ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
        return 0;
    }

    /* Figure out the new size */
    num_alloc = st->num + n;
    if (num_alloc < min_nodes)
        num_alloc = min_nodes;

    /* If |st->data| allocation was postponed */
    if (st->data == NULL) {
        /*
         * At this point, |st->num_alloc| and |st->num| are 0;
         * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
         */
        if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL)
            return 0;
        st->num_alloc = num_alloc;
        return 1;
    }

    if (!exact) {
        if (num_alloc <= st->num_alloc)
            return 1;
        num_alloc = compute_growth(num_alloc, st->num_alloc);
        if (num_alloc == 0) {
            ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
            return 0;
        }
    } else if (num_alloc == st->num_alloc) {
        return 1;
    }

    tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc);
    if (tmpdata == NULL)
        return 0;

    st->data = tmpdata;
    st->num_alloc = num_alloc;
    return 1;
}

OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
{
    OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));

    if (st == NULL)
        return NULL;

    st->comp = c;

    if (n <= 0)
        return st;

    if (!sk_reserve(st, n, 1)) {
        OPENSSL_sk_free(st);
        return NULL;
    }

    return st;
}

int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
{
    if (st == NULL) {
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
        return 0;
    }

    if (n < 0)
        return 1;
    return sk_reserve(st, n, 1);
}

OPENSSL_STACK *OPENSSL_sk_set_thunks(OPENSSL_STACK *st, OPENSSL_sk_freefunc_thunk f_thunk)
{
    if (st != NULL)
        st->free_thunk = f_thunk;

    return st;
}

int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
{
    if (st == NULL) {
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
        return 0;
    }
    if (st->num == max_nodes) {
        ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
        return 0;
    }

    if (!sk_reserve(st, 1, 0))
        return 0;

    if ((loc >= st->num) || (loc < 0)) {
        st->data[st->num] = data;
    } else {
        memmove(&st->data[loc + 1], &st->data[loc],
                sizeof(st->data[0]) * (st->num - loc));
        st->data[loc] = data;
    }
    st->num++;
    st->sorted = 0;
    return st->num;
}

static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc)
{
    const void *ret = st->data[loc];

    if (loc != st->num - 1)
        memmove(&st->data[loc], &st->data[loc + 1],
                sizeof(st->data[0]) * (st->num - loc - 1));
    st->num--;

    return (void *)ret;
}

void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
{
    int i;

    if (st == NULL)
        return NULL;

    for (i = 0; i < st->num; i++)
        if (st->data[i] == p)
            return internal_delete(st, i);
    return NULL;
}

void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
{
    if (st == NULL || loc < 0 || loc >= st->num)
        return NULL;

    return internal_delete(st, loc);
}

static int internal_find(OPENSSL_STACK *st, const void *data,
                         int ret_val_options, int *pnum_matched)
{
    const void *r;
    int i, count = 0;
    int *pnum = pnum_matched;

    if (st == NULL || st->num == 0)
        return -1;

    if (pnum == NULL)
        pnum = &count;

    if (st->comp == NULL) {
        for (i = 0; i < st->num; i++)
            if (st->data[i] == data) {
                *pnum = 1;
                return i;
            }
        *pnum = 0;
        return -1;
    }

    if (data == NULL)
        return -1;

    if (!st->sorted) {
        int res = -1;

        for (i = 0; i < st->num; i++)
            if (st->comp(&data, st->data + i) == 0) {
                if (res == -1)
                    res = i;
                ++*pnum;
                /* Check if only one result is wanted and exit if so */
                if (pnum_matched == NULL)
                    return i;
            }
        if (res == -1)
            *pnum = 0;
        return res;
    }

    if (pnum_matched != NULL)
        ret_val_options |= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
    r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
                     ret_val_options);

    if (pnum_matched != NULL) {
        *pnum = 0;
        if (r != NULL) {
            const void **p = (const void **)r;

            while (p < st->data + st->num) {
                if (st->comp(&data, p) != 0)
                    break;
                ++*pnum;
                ++p;
            }
        }
    }

    return r == NULL ? -1 : (int)((const void **)r - st->data);
}

int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
{
    return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
}

int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
{
    return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
}

int OPENSSL_sk_find_all(OPENSSL_STACK *st, const void *data, int *pnum)
{
    return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
}

int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
{
    if (st == NULL)
        return 0;
    return OPENSSL_sk_insert(st, data, st->num);
}

int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
{
    return OPENSSL_sk_insert(st, data, 0);
}

void *OPENSSL_sk_shift(OPENSSL_STACK *st)
{
    if (st == NULL || st->num == 0)
        return NULL;
    return internal_delete(st, 0);
}

void *OPENSSL_sk_pop(OPENSSL_STACK *st)
{
    if (st == NULL || st->num == 0)
        return NULL;
    return internal_delete(st, st->num - 1);
}

void OPENSSL_sk_zero(OPENSSL_STACK *st)
{
    if (st == NULL || st->num == 0)
        return;
    memset(st->data, 0, sizeof(*st->data) * st->num);
    st->num = 0;
}

void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
{
    int i;

    if (st == NULL)
        return;

    for (i = 0; i < st->num; i++) {
        if (st->data[i] != NULL) {
            if (st->free_thunk != NULL)
                st->free_thunk(func, (void *)st->data[i]);
            else
                func((void *)st->data[i]);
        }
    }
    OPENSSL_sk_free(st);
}

void OPENSSL_sk_free(OPENSSL_STACK *st)
{
    if (st == NULL)
        return;
    OPENSSL_free(st->data);
    OPENSSL_free(st);
}

int OPENSSL_sk_num(const OPENSSL_STACK *st)
{
    return st == NULL ? -1 : st->num;
}

void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
{
    if (st == NULL || i < 0 || i >= st->num)
        return NULL;
    return (void *)st->data[i];
}

void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
{
    if (st == NULL) {
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
        return NULL;
    }
    if (i < 0 || i >= st->num) {
        ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
                       "i=%d", i);
        return NULL;
    }
    st->data[i] = data;
    st->sorted = 0;
    return (void *)st->data[i];
}

void OPENSSL_sk_sort(OPENSSL_STACK *st)
{
    if (st != NULL && !st->sorted && st->comp != NULL) {
        if (st->num > 1)
            qsort(st->data, st->num, sizeof(void *), st->comp);
        st->sorted = 1; /* empty or single-element stack is considered sorted */
    }
}

int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
{
    return st == NULL ? 1 : st->sorted;
}
Commit	Line	Data
	1	/*
	2	* Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
	3	*
	4	* Licensed under the Apache License 2.0 (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 "internal/numbers.h"
	13	#include "internal/safe_math.h"
	14	#include <openssl/stack.h>
	15	#include <errno.h>
	16	#include <openssl/e_os2.h> /* For ossl_inline */
	17
	18	OSSL_SAFE_MATH_SIGNED(int, int)
	19
	20	/*
	21	* The initial number of nodes in the array.
	22	*/
	23	static const int min_nodes = 4;
	24	static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
	25	? (int)(SIZE_MAX / sizeof(void *)) : INT_MAX;
	26
	27	struct stack_st {
	28	int num;
	29	const void **data;
	30	int sorted;
	31	int num_alloc;
	32	OPENSSL_sk_compfunc comp;
	33	OPENSSL_sk_freefunc_thunk free_thunk;
	34	};
	35
	36	OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk,
	37	OPENSSL_sk_compfunc c)
	38	{
	39	OPENSSL_sk_compfunc old = sk->comp;
	40
	41	if (sk->comp != c)
	42	sk->sorted = 0;
	43	sk->comp = c;
	44
	45	return old;
	46	}
	47
	48	OPENSSL_STACK OPENSSL_sk_dup(const OPENSSL_STACK sk)
	49	{
	50	OPENSSL_STACK *ret;
	51
	52	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
	53	goto err;
	54
	55	if (sk == NULL) {
	56	ret->num = 0;
	57	ret->sorted = 0;
	58	ret->comp = NULL;
	59	} else {
	60	/* direct structure assignment */
	61	ret = sk;
	62	}
	63
	64	if (sk == NULL \|\| sk->num == 0) {
	65	/* postpone \|ret->data\| allocation */
	66	ret->data = NULL;
	67	ret->num_alloc = 0;
	68	return ret;
	69	}
	70
	71	/* duplicate \|sk->data\| content */
	72	ret->data = OPENSSL_malloc(sizeof(ret->data) sk->num_alloc);
	73	if (ret->data == NULL)
	74	goto err;
	75	memcpy(ret->data, sk->data, sizeof(void ) sk->num);
	76	return ret;
	77
	78	err:
	79	OPENSSL_sk_free(ret);
	80	return NULL;
	81	}
	82
	83	OPENSSL_STACK OPENSSL_sk_deep_copy(const OPENSSL_STACK sk,
	84	OPENSSL_sk_copyfunc copy_func,
	85	OPENSSL_sk_freefunc free_func)
	86	{
	87	OPENSSL_STACK *ret;
	88	int i;
	89
	90	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
	91	goto err;
	92
	93	if (sk == NULL) {
	94	ret->num = 0;
	95	ret->sorted = 0;
	96	ret->comp = NULL;
	97	} else {
	98	/* direct structure assignment */
	99	ret = sk;
	100	}
	101
	102	if (sk == NULL \|\| sk->num == 0) {
	103	/* postpone \|ret\| data allocation */
	104	ret->data = NULL;
	105	ret->num_alloc = 0;
	106	return ret;
	107	}
	108
	109	ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
	110	ret->data = OPENSSL_zalloc(sizeof(ret->data) ret->num_alloc);
	111	if (ret->data == NULL)
	112	goto err;
	113
	114	for (i = 0; i < ret->num; ++i) {
	115	if (sk->data[i] == NULL)
	116	continue;
	117	if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
	118	while (--i >= 0)
	119	if (ret->data[i] != NULL)
	120	free_func((void *)ret->data[i]);
	121	goto err;
	122	}
	123	}
	124	return ret;
	125
	126	err:
	127	OPENSSL_sk_free(ret);
	128	return NULL;
	129	}
	130
	131	OPENSSL_STACK *OPENSSL_sk_new_null(void)
	132	{
	133	return OPENSSL_sk_new_reserve(NULL, 0);
	134	}
	135
	136	OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
	137	{
	138	return OPENSSL_sk_new_reserve(c, 0);
	139	}
	140
	141	/*
	142	* Calculate the array growth based on the target size.
	143	*
	144	* The growth factor is a rational number and is defined by a numerator
	145	* and a denominator. According to Andrew Koenig in his paper "Why Are
	146	* Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
	147	* than the golden ratio (1.618...).
	148	*
	149	* Considering only the Fibonacci ratios less than the golden ratio, the
	150	* number of steps from the minimum allocation to integer overflow is:
	151	* factor decimal growths
	152	* 3/2 1.5 51
	153	* 8/5 1.6 45
	154	* 21/13 1.615... 44
	155	*
	156	* All larger factors have the same number of growths.
	157	*
	158	* 3/2 and 8/5 have nice power of two shifts, so seem like a good choice.
	159	*/
	160	static ossl_inline int compute_growth(int target, int current)
	161	{
	162	int err = 0;
	163
	164	while (current < target) {
	165	if (current >= max_nodes)
	166	return 0;
	167
	168	current = safe_muldiv_int(current, 8, 5, &err);
	169	if (err != 0)
	170	return 0;
	171	if (current >= max_nodes)
	172	current = max_nodes;
	173	}
	174	return current;
	175	}
	176
	177	/* internal STACK storage allocation */
	178	static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
	179	{
	180	const void **tmpdata;
	181	int num_alloc;
	182
	183	/* Check to see the reservation isn't exceeding the hard limit */
	184	if (n > max_nodes - st->num) {
	185	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
	186	return 0;
	187	}
	188
	189	/* Figure out the new size */
	190	num_alloc = st->num + n;
	191	if (num_alloc < min_nodes)
	192	num_alloc = min_nodes;
	193
	194	/* If \|st->data\| allocation was postponed */
	195	if (st->data == NULL) {
	196	/*
	197	* At this point, \|st->num_alloc\| and \|st->num\| are 0;
	198	* so \|num_alloc\| value is \|n\| or \|min_nodes\| if greater than \|n\|.
	199	*/
	200	if ((st->data = OPENSSL_zalloc(sizeof(void ) num_alloc)) == NULL)
	201	return 0;
	202	st->num_alloc = num_alloc;
	203	return 1;
	204	}
	205
	206	if (!exact) {
	207	if (num_alloc <= st->num_alloc)
	208	return 1;
	209	num_alloc = compute_growth(num_alloc, st->num_alloc);
	210	if (num_alloc == 0) {
	211	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
	212	return 0;
	213	}
	214	} else if (num_alloc == st->num_alloc) {
	215	return 1;
	216	}
	217
	218	tmpdata = OPENSSL_realloc((void )st->data, sizeof(void ) * num_alloc);
	219	if (tmpdata == NULL)
	220	return 0;
	221
	222	st->data = tmpdata;
	223	st->num_alloc = num_alloc;
	224	return 1;
	225	}
	226
	227	OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
	228	{
	229	OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
	230
	231	if (st == NULL)
	232	return NULL;
	233
	234	st->comp = c;
	235
	236	if (n <= 0)
	237	return st;
	238
	239	if (!sk_reserve(st, n, 1)) {
	240	OPENSSL_sk_free(st);
	241	return NULL;
	242	}
	243
	244	return st;
	245	}
	246
	247	int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
	248	{
	249	if (st == NULL) {
	250	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
	251	return 0;
	252	}
	253
	254	if (n < 0)
	255	return 1;
	256	return sk_reserve(st, n, 1);
	257	}
	258
	259	OPENSSL_STACK OPENSSL_sk_set_thunks(OPENSSL_STACK st, OPENSSL_sk_freefunc_thunk f_thunk)
	260	{
	261	if (st != NULL)
	262	st->free_thunk = f_thunk;
	263
	264	return st;
	265	}
	266
	267	int OPENSSL_sk_insert(OPENSSL_STACK st, const void data, int loc)
	268	{
	269	if (st == NULL) {
	270	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
	271	return 0;
	272	}
	273	if (st->num == max_nodes) {
	274	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
	275	return 0;
	276	}
	277
	278	if (!sk_reserve(st, 1, 0))
	279	return 0;
	280
	281	if ((loc >= st->num) \|\| (loc < 0)) {
	282	st->data[st->num] = data;
	283	} else {
	284	memmove(&st->data[loc + 1], &st->data[loc],
	285	sizeof(st->data[0]) * (st->num - loc));
	286	st->data[loc] = data;
	287	}
	288	st->num++;
	289	st->sorted = 0;
	290	return st->num;
	291	}
	292
	293	static ossl_inline void internal_delete(OPENSSL_STACK st, int loc)
	294	{
	295	const void *ret = st->data[loc];
	296
	297	if (loc != st->num - 1)
	298	memmove(&st->data[loc], &st->data[loc + 1],
	299	sizeof(st->data[0]) * (st->num - loc - 1));
	300	st->num--;
	301
	302	return (void *)ret;
	303	}
	304
	305	void OPENSSL_sk_delete_ptr(OPENSSL_STACK st, const void *p)
	306	{
	307	int i;
	308
	309	if (st == NULL)
	310	return NULL;
	311
	312	for (i = 0; i < st->num; i++)
	313	if (st->data[i] == p)
	314	return internal_delete(st, i);
	315	return NULL;
	316	}
	317
	318	void OPENSSL_sk_delete(OPENSSL_STACK st, int loc)
	319	{
	320	if (st == NULL \|\| loc < 0 \|\| loc >= st->num)
	321	return NULL;
	322
	323	return internal_delete(st, loc);
	324	}
	325
	326	static int internal_find(OPENSSL_STACK st, const void data,
	327	int ret_val_options, int *pnum_matched)
	328	{
	329	const void *r;
	330	int i, count = 0;
	331	int *pnum = pnum_matched;
	332
	333	if (st == NULL \|\| st->num == 0)
	334	return -1;
	335
	336	if (pnum == NULL)
	337	pnum = &count;
	338
	339	if (st->comp == NULL) {
	340	for (i = 0; i < st->num; i++)
	341	if (st->data[i] == data) {
	342	*pnum = 1;
	343	return i;
	344	}
	345	*pnum = 0;
	346	return -1;
	347	}
	348
	349	if (data == NULL)
	350	return -1;
	351
	352	if (!st->sorted) {
	353	int res = -1;
	354
	355	for (i = 0; i < st->num; i++)
	356	if (st->comp(&data, st->data + i) == 0) {
	357	if (res == -1)
	358	res = i;
	359	++*pnum;
	360	/* Check if only one result is wanted and exit if so */
	361	if (pnum_matched == NULL)
	362	return i;
	363	}
	364	if (res == -1)
	365	*pnum = 0;
	366	return res;
	367	}
	368
	369	if (pnum_matched != NULL)
	370	ret_val_options \|= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
	371	r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
	372	ret_val_options);
	373
	374	if (pnum_matched != NULL) {
	375	*pnum = 0;
	376	if (r != NULL) {
	377	const void p = (const void )r;
	378
	379	while (p < st->data + st->num) {
	380	if (st->comp(&data, p) != 0)
	381	break;
	382	++*pnum;
	383	++p;
	384	}
	385	}
	386	}
	387
	388	return r == NULL ? -1 : (int)((const void **)r - st->data);
	389	}
	390
	391	int OPENSSL_sk_find(OPENSSL_STACK st, const void data)
	392	{
	393	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
	394	}
	395
	396	int OPENSSL_sk_find_ex(OPENSSL_STACK st, const void data)
	397	{
	398	return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
	399	}
	400
	401	int OPENSSL_sk_find_all(OPENSSL_STACK st, const void data, int *pnum)
	402	{
	403	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
	404	}
	405
	406	int OPENSSL_sk_push(OPENSSL_STACK st, const void data)
	407	{
	408	if (st == NULL)
	409	return 0;
	410	return OPENSSL_sk_insert(st, data, st->num);
	411	}
	412
	413	int OPENSSL_sk_unshift(OPENSSL_STACK st, const void data)
	414	{
	415	return OPENSSL_sk_insert(st, data, 0);
	416	}
	417
	418	void OPENSSL_sk_shift(OPENSSL_STACK st)
	419	{
	420	if (st == NULL \|\| st->num == 0)
	421	return NULL;
	422	return internal_delete(st, 0);
	423	}
	424
	425	void OPENSSL_sk_pop(OPENSSL_STACK st)
	426	{
	427	if (st == NULL \|\| st->num == 0)
	428	return NULL;
	429	return internal_delete(st, st->num - 1);
	430	}
	431
	432	void OPENSSL_sk_zero(OPENSSL_STACK *st)
	433	{
	434	if (st == NULL \|\| st->num == 0)
	435	return;
	436	memset(st->data, 0, sizeof(st->data) st->num);
	437	st->num = 0;
	438	}
	439
	440	void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
	441	{
	442	int i;
	443
	444	if (st == NULL)
	445	return;
	446
	447	for (i = 0; i < st->num; i++) {
	448	if (st->data[i] != NULL) {
	449	if (st->free_thunk != NULL)
	450	st->free_thunk(func, (void *)st->data[i]);
	451	else
	452	func((void *)st->data[i]);
	453	}
	454	}
	455	OPENSSL_sk_free(st);
	456	}
	457
	458	void OPENSSL_sk_free(OPENSSL_STACK *st)
	459	{
	460	if (st == NULL)
	461	return;
	462	OPENSSL_free(st->data);
	463	OPENSSL_free(st);
	464	}
	465
	466	int OPENSSL_sk_num(const OPENSSL_STACK *st)
	467	{
	468	return st == NULL ? -1 : st->num;
	469	}
	470
	471	void OPENSSL_sk_value(const OPENSSL_STACK st, int i)
	472	{
	473	if (st == NULL \|\| i < 0 \|\| i >= st->num)
	474	return NULL;
	475	return (void *)st->data[i];
	476	}
	477
	478	void OPENSSL_sk_set(OPENSSL_STACK st, int i, const void *data)
	479	{
	480	if (st == NULL) {
	481	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
	482	return NULL;
	483	}
	484	if (i < 0 \|\| i >= st->num) {
	485	ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
	486	"i=%d", i);
	487	return NULL;
	488	}
	489	st->data[i] = data;
	490	st->sorted = 0;
	491	return (void *)st->data[i];
	492	}
	493
	494	void OPENSSL_sk_sort(OPENSSL_STACK *st)
	495	{
	496	if (st != NULL && !st->sorted && st->comp != NULL) {
	497	if (st->num > 1)
	498	qsort(st->data, st->num, sizeof(void *), st->comp);
	499	st->sorted = 1; /* empty or single-element stack is considered sorted */
	500	}
	501	}
	502
	503	int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
	504	{
	505	return st == NULL ? 1 : st->sorted;
	506	}