/src/openssl36/crypto/stack/stack.c

Source
/*
 * Copyright 1995-2025 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_array(sk->num_alloc, sizeof(*ret->data));
    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_calloc(ret->num_alloc, sizeof(*ret->data));
    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_calloc(num_alloc, sizeof(void *))) == 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_array((void *)st->data, num_alloc, sizeof(void *));
    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;
}

Coverage Report

Created: 2026-09-12 06:55

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