/src/openssl/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_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;
}

Coverage Report

Created: 2025-06-13 06:57

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		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	1.83k	{
39	1.83k	OPENSSL_sk_compfunc old = sk->comp;
40
41	1.83k	if (sk->comp != c)
42	1.83k	sk->sorted = 0;
43	1.83k	sk->comp = c;
44
45	1.83k	return old;
46	1.83k	}
47
48		OPENSSL_STACK OPENSSL_sk_dup(const OPENSSL_STACK sk)
49	18.0k	{
50	18.0k	OPENSSL_STACK *ret;
51
52	18.0k	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
53	0	goto err;
54
55	18.0k	if (sk == NULL) {
56	2	ret->num = 0;
57	2	ret->sorted = 0;
58	2	ret->comp = NULL;
59	18.0k	} else {
60		/* direct structure assignment */
61	18.0k	ret = sk;
62	18.0k	}
63
64	18.0k	if (sk == NULL \|\| sk->num == 0) {
65		/* postpone \|ret->data\| allocation */
66	2	ret->data = NULL;
67	2	ret->num_alloc = 0;
68	2	return ret;
69	2	}
70
71		/* duplicate \|sk->data\| content */
72	18.0k	ret->data = OPENSSL_malloc(sizeof(ret->data) sk->num_alloc);
73	18.0k	if (ret->data == NULL)
74	0	goto err;
75	18.0k	memcpy(ret->data, sk->data, sizeof(void ) sk->num);
76	18.0k	return ret;
77
78	0	err:
79	0	OPENSSL_sk_free(ret);
80	0	return NULL;
81	18.0k	}
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	75.2k	{
87	75.2k	OPENSSL_STACK *ret;
88	75.2k	int i;
89
90	75.2k	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
91	0	goto err;
92
93	75.2k	if (sk == NULL) {
94	3	ret->num = 0;
95	3	ret->sorted = 0;
96	3	ret->comp = NULL;
97	75.2k	} else {
98		/* direct structure assignment */
99	75.2k	ret = sk;
100	75.2k	}
101
102	75.2k	if (sk == NULL \|\| sk->num == 0) {
103		/* postpone \|ret\| data allocation */
104	3	ret->data = NULL;
105	3	ret->num_alloc = 0;
106	3	return ret;
107	3	}
108
109	75.2k	ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
110	75.2k	ret->data = OPENSSL_zalloc(sizeof(ret->data) ret->num_alloc);
111	75.2k	if (ret->data == NULL)
112	0	goto err;
113
114	1.21M	for (i = 0; i < ret->num; ++i) {
115	1.13M	if (sk->data[i] == NULL)
116	0	continue;
117	1.13M	if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
118	0	while (--i >= 0)
119	0	if (ret->data[i] != NULL)
120	0	free_func((void *)ret->data[i]);
121	0	goto err;
122	0	}
123	1.13M	}
124	75.2k	return ret;
125
126	0	err:
127	0	OPENSSL_sk_free(ret);
128	0	return NULL;
129	75.2k	}
130
131		OPENSSL_STACK *OPENSSL_sk_new_null(void)
132	2.75M	{
133	2.75M	return OPENSSL_sk_new_reserve(NULL, 0);
134	2.75M	}
135
136		OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
137	389	{
138	389	return OPENSSL_sk_new_reserve(c, 0);
139	389	}
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	66.4k	{
162	66.4k	int err = 0;
163
164	132k	while (current < target) {
165	66.4k	if (current >= max_nodes)
166	0	return 0;
167
168	66.4k	current = safe_muldiv_int(current, 8, 5, &err);
169	66.4k	if (err != 0)
170	0	return 0;
171	66.4k	if (current >= max_nodes)
172	0	current = max_nodes;
173	66.4k	}
174	66.4k	return current;
175	66.4k	}
176
177		/* internal STACK storage allocation */
178		static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
179	4.96M	{
180	4.96M	const void **tmpdata;
181	4.96M	int num_alloc;
182
183		/* Check to see the reservation isn't exceeding the hard limit */
184	4.96M	if (n > max_nodes - st->num) {
185	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
186	0	return 0;
187	0	}
188
189		/* Figure out the new size */
190	4.96M	num_alloc = st->num + n;
191	4.96M	if (num_alloc < min_nodes)
192	420k	num_alloc = min_nodes;
193
194		/* If \|st->data\| allocation was postponed */
195	4.96M	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	324k	if ((st->data = OPENSSL_zalloc(sizeof(void ) num_alloc)) == NULL)
201	0	return 0;
202	324k	st->num_alloc = num_alloc;
203	324k	return 1;
204	324k	}
205
206	4.64M	if (!exact) {
207	4.64M	if (num_alloc <= st->num_alloc)
208	4.57M	return 1;
209	66.4k	num_alloc = compute_growth(num_alloc, st->num_alloc);
210	66.4k	if (num_alloc == 0) {
211	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
212	0	return 0;
213	0	}
214	66.4k	} else if (num_alloc == st->num_alloc) {
215	0	return 1;
216	0	}
217
218	66.4k	tmpdata = OPENSSL_realloc((void )st->data, sizeof(void ) * num_alloc);
219	66.4k	if (tmpdata == NULL)
220	0	return 0;
221
222	66.4k	st->data = tmpdata;
223	66.4k	st->num_alloc = num_alloc;
224	66.4k	return 1;
225	66.4k	}
226
227		OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
228	2.76M	{
229	2.76M	OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
230
231	2.76M	if (st == NULL)
232	0	return NULL;
233
234	2.76M	st->comp = c;
235
236	2.76M	if (n <= 0)
237	2.76M	return st;
238
239	6.59k	if (!sk_reserve(st, n, 1)) {
240	0	OPENSSL_sk_free(st);
241	0	return NULL;
242	0	}
243
244	6.59k	return st;
245	6.59k	}
246
247		int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
248	0	{
249	0	if (st == NULL) {
250	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
251	0	return 0;
252	0	}
253
254	0	if (n < 0)
255	0	return 1;
256	0	return sk_reserve(st, n, 1);
257	0	}
258
259		OPENSSL_STACK OPENSSL_sk_set_thunks(OPENSSL_STACK st, OPENSSL_sk_freefunc_thunk f_thunk)
260	258k	{
261	258k	if (st != NULL)
262	164k	st->free_thunk = f_thunk;
263
264	258k	return st;
265	258k	}
266
267		int OPENSSL_sk_insert(OPENSSL_STACK st, const void data, int loc)
268	4.95M	{
269	4.95M	if (st == NULL) {
270	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
271	0	return 0;
272	0	}
273	4.95M	if (st->num == max_nodes) {
274	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
275	0	return 0;
276	0	}
277
278	4.95M	if (!sk_reserve(st, 1, 0))
279	0	return 0;
280
281	4.95M	if ((loc >= st->num) \|\| (loc < 0)) {
282	4.95M	st->data[st->num] = data;
283	4.95M	} else {
284	0	memmove(&st->data[loc + 1], &st->data[loc],
285	0	sizeof(st->data[0]) * (st->num - loc));
286	0	st->data[loc] = data;
287	0	}
288	4.95M	st->num++;
289	4.95M	st->sorted = 0;
290	4.95M	return st->num;
291	4.95M	}
292
293		static ossl_inline void internal_delete(OPENSSL_STACK st, int loc)
294	2	{
295	2	const void *ret = st->data[loc];
296
297	2	if (loc != st->num - 1)
298	0	memmove(&st->data[loc], &st->data[loc + 1],
299	0	sizeof(st->data[0]) * (st->num - loc - 1));
300	2	st->num--;
301
302	2	return (void *)ret;
303	2	}
304
305		void OPENSSL_sk_delete_ptr(OPENSSL_STACK st, const void *p)
306	0	{
307	0	int i;
308
309	0	if (st == NULL)
310	0	return NULL;
311
312	0	for (i = 0; i < st->num; i++)
313	0	if (st->data[i] == p)
314	0	return internal_delete(st, i);
315	0	return NULL;
316	0	}
317
318		void OPENSSL_sk_delete(OPENSSL_STACK st, int loc)
319	2	{
320	2	if (st == NULL \|\| loc < 0 \|\| loc >= st->num)
321	0	return NULL;
322
323	2	return internal_delete(st, loc);
324	2	}
325
326		static int internal_find(OPENSSL_STACK st, const void data,
327		int ret_val_options, int *pnum_matched)
328	5	{
329	5	const void *r;
330	5	int i, count = 0;
331	5	int *pnum = pnum_matched;
332
333	5	if (st == NULL \|\| st->num == 0)
334	5	return -1;
335
336	0	if (pnum == NULL)
337	0	pnum = &count;
338
339	0	if (st->comp == NULL) {
340	0	for (i = 0; i < st->num; i++)
341	0	if (st->data[i] == data) {
342	0	*pnum = 1;
343	0	return i;
344	0	}
345	0	*pnum = 0;
346	0	return -1;
347	0	}
348
349	0	if (data == NULL)
350	0	return -1;
351
352	0	if (!st->sorted) {
353	0	int res = -1;
354
355	0	for (i = 0; i < st->num; i++)
356	0	if (st->comp(&data, st->data + i) == 0) {
357	0	if (res == -1)
358	0	res = i;
359	0	++*pnum;
360		/* Check if only one result is wanted and exit if so */
361	0	if (pnum_matched == NULL)
362	0	return i;
363	0	}
364	0	if (res == -1)
365	0	*pnum = 0;
366	0	return res;
367	0	}
368
369	0	if (pnum_matched != NULL)
370	0	ret_val_options \|= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
371	0	r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
372	0	ret_val_options);
373
374	0	if (pnum_matched != NULL) {
375	0	*pnum = 0;
376	0	if (r != NULL) {
377	0	const void p = (const void )r;
378
379	0	while (p < st->data + st->num) {
380	0	if (st->comp(&data, p) != 0)
381	0	break;
382	0	++*pnum;
383	0	++p;
384	0	}
385	0	}
386	0	}
387
388	0	return r == NULL ? -1 : (int)((const void **)r - st->data);
389	0	}
390
391		int OPENSSL_sk_find(OPENSSL_STACK st, const void data)
392	5	{
393	5	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
394	5	}
395
396		int OPENSSL_sk_find_ex(OPENSSL_STACK st, const void data)
397	0	{
398	0	return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
399	0	}
400
401		int OPENSSL_sk_find_all(OPENSSL_STACK st, const void data, int *pnum)
402	0	{
403	0	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
404	0	}
405
406		int OPENSSL_sk_push(OPENSSL_STACK st, const void data)
407	4.95M	{
408	4.95M	if (st == NULL)
409	0	return 0;
410	4.95M	return OPENSSL_sk_insert(st, data, st->num);
411	4.95M	}
412
413		int OPENSSL_sk_unshift(OPENSSL_STACK st, const void data)
414	0	{
415	0	return OPENSSL_sk_insert(st, data, 0);
416	0	}
417
418		void OPENSSL_sk_shift(OPENSSL_STACK st)
419	0	{
420	0	if (st == NULL \|\| st->num == 0)
421	0	return NULL;
422	0	return internal_delete(st, 0);
423	0	}
424
425		void OPENSSL_sk_pop(OPENSSL_STACK st)
426	0	{
427	0	if (st == NULL \|\| st->num == 0)
428	0	return NULL;
429	0	return internal_delete(st, st->num - 1);
430	0	}
431
432		void OPENSSL_sk_zero(OPENSSL_STACK *st)
433	0	{
434	0	if (st == NULL \|\| st->num == 0)
435	0	return;
436	0	memset(st->data, 0, sizeof(st->data) st->num);
437	0	st->num = 0;
438	0	}
439
440		void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
441	762k	{
442	762k	int i;
443
444	762k	if (st == NULL)
445	279k	return;
446
447	3.46M	for (i = 0; i < st->num; i++) {
448	2.98M	if (st->data[i] != NULL) {
449	2.98M	if (st->free_thunk != NULL)
450	1.93M	st->free_thunk(func, (void *)st->data[i]);
451	1.05M	else
452	1.05M	func((void *)st->data[i]);
453	2.98M	}
454	2.98M	}
455	482k	OPENSSL_sk_free(st);
456	482k	}
457
458		void OPENSSL_sk_free(OPENSSL_STACK *st)
459	6.49M	{
460	6.49M	if (st == NULL)
461	3.63M	return;
462	2.85M	OPENSSL_free(st->data);
463	2.85M	OPENSSL_free(st);
464	2.85M	}
465
466		int OPENSSL_sk_num(const OPENSSL_STACK *st)
467	18.6M	{
468	18.6M	return st == NULL ? -1 : st->num;
469	18.6M	}
470
471		void OPENSSL_sk_value(const OPENSSL_STACK st, int i)
472	10.6M	{
473	10.6M	if (st == NULL \|\| i < 0 \|\| i >= st->num)
474	0	return NULL;
475	10.6M	return (void *)st->data[i];
476	10.6M	}
477
478		void OPENSSL_sk_set(OPENSSL_STACK st, int i, const void *data)
479	193k	{
480	193k	if (st == NULL) {
481	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
482	0	return NULL;
483	0	}
484	193k	if (i < 0 \|\| i >= st->num) {
485	0	ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
486	0	"i=%d", i);
487	0	return NULL;
488	0	}
489	193k	st->data[i] = data;
490	193k	st->sorted = 0;
491	193k	return (void *)st->data[i];
492	193k	}
493
494		void OPENSSL_sk_sort(OPENSSL_STACK *st)
495	383	{
496	383	if (st != NULL && !st->sorted && st->comp != NULL) {
497	383	if (st->num > 1)
498	372	qsort(st->data, st->num, sizeof(void *), st->comp);
499	383	st->sorted = 1; /* empty or single-element stack is considered sorted */
500	383	}
501	383	}
502
503		int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
504	0	{
505	0	return st == NULL ? 1 : st->sorted;
506	0	}