/src/openssl33/crypto/stack/stack.c

Source (jump to first uncovered line)
/*
 * 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_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);
}

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)
            func((char *)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;
}

Coverage Report

Created: 2025-08-28 07:07

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