/src/openssl40/crypto/stack/stack.c

Source
/*
 * Copyright 1995-2026 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;
    int (*cmp_thunk)(OPENSSL_sk_compfunc, const void *, const void *);
    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;
}

static ossl_inline int cmp_with_thunk(const OPENSSL_STACK *st, const void *a, const void *b)
{
    return (st->cmp_thunk == NULL) ? st->comp(a, b) : st->cmp_thunk(st->comp, a, b);
}

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;
}

OPENSSL_STACK *OPENSSL_sk_set_cmp_thunks(OPENSSL_STACK *st, int (*c_thunk)(int (*)(const void *, const void *), const void *, const void *))
{
    if (st != NULL)
        st->cmp_thunk = c_thunk;

    return st;
}

int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
{
    int cmp_ret;

    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) {
                cmp_ret = cmp_with_thunk(st, &st->data[loc - 1], &st->data[loc]);
                if (cmp_ret > 0)
                    st->sorted = 0;
            }
            if (loc < st->num - 1) {
                cmp_ret = cmp_with_thunk(st, &st->data[loc + 1], &st->data[loc]);
                if (cmp_ret < 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 cmp_ret;
    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++) {
            cmp_ret = cmp_with_thunk(st, &data, st->data + i);
            if (cmp_ret == 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, st->cmp_thunk,
        ret_val_options);

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

            while (p < st->data + st->num) {
                cmp_ret = cmp_with_thunk(st, &data, p);
                if (cmp_ret != 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: 2026-09-12 06:55

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