/src/openssl/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_copyfunc_thunk copy_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 void free_with_thunk(OPENSSL_STACK *sk, OPENSSL_sk_freefunc free_func, const void *data)
{
    if (data == NULL)
        return;
    if (sk->free_thunk != NULL)
        sk->free_thunk(free_func, (void *)data);
    else
        free_func((void *)data);
}

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->copy_thunk != NULL)
                ret->data[i] = ret->copy_thunk(copy_func, sk->data[i]);
            else
                ret->data[i] = copy_func(sk->data[i]);

            if (ret->data[i] == NULL) {
                while (--i >= 0)
                    free_with_thunk(ret, free_func, 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;
}

OPENSSL_STACK *OPENSSL_sk_set_copy_thunks(OPENSSL_STACK *st, OPENSSL_sk_copyfunc_thunk cp_thunk)
{
    if (st != NULL)
        st->copy_thunk = cp_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++)
        free_with_thunk(st, func, 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-05-30 06:06

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