/src/openssl/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->num > 1)
        sk->sorted = 0;
    sk->comp = c;

    return old;
}

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

    if ((ret = OPENSSL_sk_new_null()) == NULL)
        goto err;

    if (sk == NULL)
        goto done;

    /* direct structure assignment */
    *ret = *sk;
    ret->data = NULL;
    ret->num_alloc = 0;

    if (ret->num == 0)
        goto done; /* nothing to copy */

    ret->num_alloc = ret->num > min_nodes ? ret->num : min_nodes;
    ret->data = OPENSSL_calloc(ret->num_alloc, sizeof(*ret->data));
    if (ret->data == NULL)
        goto err;
    if (copy_func == NULL) {
        memcpy(ret->data, sk->data, sizeof(*ret->data) * ret->num);
    } else {
        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;
            }
        }
    }

 done:
    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)
{
    return internal_copy(sk, copy_func, free_func);
}

OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
{
    return internal_copy(sk, NULL, 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;
    st->sorted = 1; /* empty or single-element stack is considered sorted */

    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)) {
        loc = st->num;
        st->data[loc] = data;
    } else {
        memmove(&st->data[loc + 1], &st->data[loc],
                sizeof(st->data[0]) * (st->num - loc));
        st->data[loc] = data;
    }
    st->num++;
    if (st->sorted && st->num > 1) {
        if (st->comp != NULL) {
            if (loc > 0 && (st->comp(&st->data[loc - 1], &st->data[loc]) > 0))
                st->sorted = 0;
            if (loc < st->num - 1
                && (st->comp(&st->data[loc + 1], &st->data[loc]) < 0))
                st->sorted = 0;
        } else {
            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--;
    st->sorted = st->sorted || st->num <= 1;

    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(const 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(const OPENSSL_STACK *st, const void *data)
{
    return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
}

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

int OPENSSL_sk_find_all(const 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 = st->num <= 1;
    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-10-28 06:56

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