/src/openssl30/crypto/stack/stack.c

Source
/*
 * Copyright 1995-2022 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 <openssl/stack.h>
#include <errno.h>
#include <openssl/e_os2.h>      /* For ossl_inline */

/*
 * 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_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:
    ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
    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:
    ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
    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 fraction 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...).
 *
 * We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
 * Another option 8/5 = 1.6 allows for slightly faster growth, although safe
 * computation is more difficult.
 *
 * The limit to avoid overflow is spot on.  The modulo three correction term
 * ensures that the limit is the largest number than can be expanded by the
 * growth factor without exceeding the hard limit.
 *
 * Do not call it with |current| lower than 2, or it will infinitely loop.
 */
static ossl_inline int compute_growth(int target, int current)
{
    const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0);

    while (current < target) {
        /* Check to see if we're at the hard limit */
        if (current >= max_nodes)
            return 0;

        /* Expand the size by a factor of 3/2 if it is within range */
        current = current < limit ? current + current / 2 : 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) {
            ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
            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) {
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
        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) {
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
        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);
}

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)
{
    const void *r;
    int i;

    if (st == NULL || st->num == 0)
        return -1;

    if (st->comp == NULL) {
        for (i = 0; i < st->num; i++)
            if (st->data[i] == data) {
                if (pnum != NULL)
                    *pnum = 1;
                return i;
            }
        if (pnum != NULL)
            *pnum = 0;
        return -1;
    }

    if (!st->sorted) {
        if (st->num > 1)
            qsort(st->data, st->num, sizeof(void *), st->comp);
        st->sorted = 1; /* empty or single-element stack is considered sorted */
    }
    if (data == NULL)
        return -1;
    if (pnum != 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 != 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 -1;
    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)
            func((char *)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-11-16 06:40

Line	Count	Source
1		/*
2		* Copyright 1995-2022 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 <openssl/stack.h>
14		#include <errno.h>
15		#include <openssl/e_os2.h> /* For ossl_inline */
16
17		/*
18		* The initial number of nodes in the array.
19		*/
20		static const int min_nodes = 4;
21		static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
22		? (int)(SIZE_MAX / sizeof(void *)) : INT_MAX;
23
24		struct stack_st {
25		int num;
26		const void **data;
27		int sorted;
28		int num_alloc;
29		OPENSSL_sk_compfunc comp;
30		};
31
32		OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk,
33		OPENSSL_sk_compfunc c)
34	230k	{
35	230k	OPENSSL_sk_compfunc old = sk->comp;
36
37	230k	if (sk->comp != c)
38	230k	sk->sorted = 0;
39	230k	sk->comp = c;
40
41	230k	return old;
42	230k	}
43
44		OPENSSL_STACK OPENSSL_sk_dup(const OPENSSL_STACK sk)
45	37.7M	{
46	37.7M	OPENSSL_STACK *ret;
47
48	37.7M	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
49	0	goto err;
50
51	37.7M	if (sk == NULL) {
52	143	ret->num = 0;
53	143	ret->sorted = 0;
54	143	ret->comp = NULL;
55	37.7M	} else {
56		/* direct structure assignment */
57	37.7M	ret = sk;
58	37.7M	}
59
60	37.7M	if (sk == NULL \|\| sk->num == 0) {
61		/* postpone \|ret->data\| allocation */
62	160	ret->data = NULL;
63	160	ret->num_alloc = 0;
64	160	return ret;
65	160	}
66
67		/* duplicate \|sk->data\| content */
68	37.7M	ret->data = OPENSSL_malloc(sizeof(ret->data) sk->num_alloc);
69	37.7M	if (ret->data == NULL)
70	0	goto err;
71	37.7M	memcpy(ret->data, sk->data, sizeof(void ) sk->num);
72	37.7M	return ret;
73
74	0	err:
75	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
76	0	OPENSSL_sk_free(ret);
77	0	return NULL;
78	37.7M	}
79
80		OPENSSL_STACK OPENSSL_sk_deep_copy(const OPENSSL_STACK sk,
81		OPENSSL_sk_copyfunc copy_func,
82		OPENSSL_sk_freefunc free_func)
83	1.52M	{
84	1.52M	OPENSSL_STACK *ret;
85	1.52M	int i;
86
87	1.52M	if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
88	0	goto err;
89
90	1.52M	if (sk == NULL) {
91	165	ret->num = 0;
92	165	ret->sorted = 0;
93	165	ret->comp = NULL;
94	1.52M	} else {
95		/* direct structure assignment */
96	1.52M	ret = sk;
97	1.52M	}
98
99	1.52M	if (sk == NULL \|\| sk->num == 0) {
100		/* postpone \|ret\| data allocation */
101	165	ret->data = NULL;
102	165	ret->num_alloc = 0;
103	165	return ret;
104	165	}
105
106	1.52M	ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
107	1.52M	ret->data = OPENSSL_zalloc(sizeof(ret->data) ret->num_alloc);
108	1.52M	if (ret->data == NULL)
109	0	goto err;
110
111	14.2M	for (i = 0; i < ret->num; ++i) {
112	12.7M	if (sk->data[i] == NULL)
113	0	continue;
114	12.7M	if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
115	0	while (--i >= 0)
116	0	if (ret->data[i] != NULL)
117	0	free_func((void *)ret->data[i]);
118	0	goto err;
119	0	}
120	12.7M	}
121	1.52M	return ret;
122
123	0	err:
124	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
125	0	OPENSSL_sk_free(ret);
126	0	return NULL;
127	1.52M	}
128
129		OPENSSL_STACK *OPENSSL_sk_new_null(void)
130	155M	{
131	155M	return OPENSSL_sk_new_reserve(NULL, 0);
132	155M	}
133
134		OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
135	15.3M	{
136	15.3M	return OPENSSL_sk_new_reserve(c, 0);
137	15.3M	}
138
139		/*
140		* Calculate the array growth based on the target size.
141		*
142		* The growth fraction is a rational number and is defined by a numerator
143		* and a denominator. According to Andrew Koenig in his paper "Why Are
144		* Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
145		* than the golden ratio (1.618...).
146		*
147		* We use 3/2 = 1.5 for simplicity of calculation and overflow checking.
148		* Another option 8/5 = 1.6 allows for slightly faster growth, although safe
149		* computation is more difficult.
150		*
151		* The limit to avoid overflow is spot on. The modulo three correction term
152		* ensures that the limit is the largest number than can be expanded by the
153		* growth factor without exceeding the hard limit.
154		*
155		* Do not call it with \|current\| lower than 2, or it will infinitely loop.
156		*/
157		static ossl_inline int compute_growth(int target, int current)
158	3.93M	{
159	3.93M	const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0);
160
161	7.87M	while (current < target) {
162		/* Check to see if we're at the hard limit */
163	3.93M	if (current >= max_nodes)
164	0	return 0;
165
166		/* Expand the size by a factor of 3/2 if it is within range */
167	3.93M	current = current < limit ? current + current / 2 : max_nodes;
168	3.93M	}
169	3.93M	return current;
170	3.93M	}
171
172		/* internal STACK storage allocation */
173		static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
174	381M	{
175	381M	const void **tmpdata;
176	381M	int num_alloc;
177
178		/* Check to see the reservation isn't exceeding the hard limit */
179	381M	if (n > max_nodes - st->num) {
180	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
181	0	return 0;
182	0	}
183
184		/* Figure out the new size */
185	381M	num_alloc = st->num + n;
186	381M	if (num_alloc < min_nodes)
187	31.9M	num_alloc = min_nodes;
188
189		/* If \|st->data\| allocation was postponed */
190	381M	if (st->data == NULL) {
191		/*
192		* At this point, \|st->num_alloc\| and \|st->num\| are 0;
193		* so \|num_alloc\| value is \|n\| or \|min_nodes\| if greater than \|n\|.
194		*/
195	21.2M	if ((st->data = OPENSSL_zalloc(sizeof(void ) num_alloc)) == NULL) {
196	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
197	0	return 0;
198	0	}
199	21.2M	st->num_alloc = num_alloc;
200	21.2M	return 1;
201	21.2M	}
202
203	360M	if (!exact) {
204	360M	if (num_alloc <= st->num_alloc)
205	351M	return 1;
206	8.62M	num_alloc = compute_growth(num_alloc, st->num_alloc);
207	8.62M	if (num_alloc == 0) {
208	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
209	0	return 0;
210	0	}
211	8.62M	} else if (num_alloc == st->num_alloc) {
212	0	return 1;
213	0	}
214
215	8.62M	tmpdata = OPENSSL_realloc((void )st->data, sizeof(void ) * num_alloc);
216	8.62M	if (tmpdata == NULL) {
217	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
218	0	return 0;
219	0	}
220
221	8.62M	st->data = tmpdata;
222	8.62M	st->num_alloc = num_alloc;
223	8.62M	return 1;
224	8.62M	}
225
226		OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
227	171M	{
228	171M	OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
229
230	171M	if (st == NULL) {
231	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);
232	0	return NULL;
233	0	}
234
235	171M	st->comp = c;
236
237	171M	if (n <= 0)
238	170M	return st;
239
240	949k	if (!sk_reserve(st, n, 1)) {
241	0	OPENSSL_sk_free(st);
242	0	return NULL;
243	0	}
244
245	949k	return st;
246	949k	}
247
248		int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
249	0	{
250	0	if (st == NULL) {
251	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
252	0	return 0;
253	0	}
254
255	0	if (n < 0)
256	0	return 1;
257	0	return sk_reserve(st, n, 1);
258	0	}
259
260		int OPENSSL_sk_insert(OPENSSL_STACK st, const void data, int loc)
261	309M	{
262	309M	if (st == NULL) {
263	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
264	0	return 0;
265	0	}
266	309M	if (st->num == max_nodes) {
267	0	ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
268	0	return 0;
269	0	}
270
271	309M	if (!sk_reserve(st, 1, 0))
272	0	return 0;
273
274	309M	if ((loc >= st->num) \|\| (loc < 0)) {
275	309M	st->data[st->num] = data;
276	309M	} else {
277	5.12k	memmove(&st->data[loc + 1], &st->data[loc],
278	5.12k	sizeof(st->data[0]) * (st->num - loc));
279	5.12k	st->data[loc] = data;
280	5.12k	}
281	309M	st->num++;
282	309M	st->sorted = 0;
283	309M	return st->num;
284	309M	}
285
286		static ossl_inline void internal_delete(OPENSSL_STACK st, int loc)
287	1.99M	{
288	1.99M	const void *ret = st->data[loc];
289
290	1.99M	if (loc != st->num - 1)
291	274k	memmove(&st->data[loc], &st->data[loc + 1],
292	274k	sizeof(st->data[0]) * (st->num - loc - 1));
293	1.99M	st->num--;
294
295	1.99M	return (void *)ret;
296	1.99M	}
297
298		void OPENSSL_sk_delete_ptr(OPENSSL_STACK st, const void *p)
299	216k	{
300	216k	int i;
301
302	216k	if (st == NULL)
303	0	return NULL;
304
305	688k	for (i = 0; i < st->num; i++)
306	688k	if (st->data[i] == p)
307	216k	return internal_delete(st, i);
308	0	return NULL;
309	216k	}
310
311		void OPENSSL_sk_delete(OPENSSL_STACK st, int loc)
312	263k	{
313	263k	if (st == NULL \|\| loc < 0 \|\| loc >= st->num)
314	0	return NULL;
315
316	263k	return internal_delete(st, loc);
317	263k	}
318
319		static int internal_find(OPENSSL_STACK st, const void data,
320		int ret_val_options, int *pnum)
321	21.9k	{
322	21.9k	const void *r;
323	21.9k	int i;
324
325	21.9k	if (st == NULL \|\| st->num == 0)
326	8.80k	return -1;
327
328	13.1k	if (st->comp == NULL) {
329	256k	for (i = 0; i < st->num; i++)
330	255k	if (st->data[i] == data) {
331	3.01k	if (pnum != NULL)
332	0	*pnum = 1;
333	3.01k	return i;
334	3.01k	}
335	251	if (pnum != NULL)
336	0	*pnum = 0;
337	251	return -1;
338	3.26k	}
339
340	9.86k	if (!st->sorted) {
341	1.55k	if (st->num > 1)
342	0	qsort(st->data, st->num, sizeof(void *), st->comp);
343	1.55k	st->sorted = 1; /* empty or single-element stack is considered sorted */
344	1.55k	}
345	9.86k	if (data == NULL)
346	0	return -1;
347	9.86k	if (pnum != NULL)
348	1.96k	ret_val_options \|= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
349	9.86k	r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
350	9.86k	ret_val_options);
351
352	9.86k	if (pnum != NULL) {
353	1.96k	*pnum = 0;
354	1.96k	if (r != NULL) {
355	1.46k	const void p = (const void )r;
356
357	2.93k	while (p < st->data + st->num) {
358	1.46k	if (st->comp(&data, p) != 0)
359	0	break;
360	1.46k	++*pnum;
361	1.46k	++p;
362	1.46k	}
363	1.46k	}
364	1.96k	}
365
366	9.86k	return r == NULL ? -1 : (int)((const void **)r - st->data);
367	9.86k	}
368
369		int OPENSSL_sk_find(OPENSSL_STACK st, const void data)
370	160k	{
371	160k	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
372	160k	}
373
374		int OPENSSL_sk_find_ex(OPENSSL_STACK st, const void data)
375	0	{
376	0	return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
377	0	}
378
379		int OPENSSL_sk_find_all(OPENSSL_STACK st, const void data, int *pnum)
380	93.6k	{
381	93.6k	return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
382	93.6k	}
383
384		int OPENSSL_sk_push(OPENSSL_STACK st, const void data)
385	380M	{
386	380M	if (st == NULL)
387	0	return -1;
388	380M	return OPENSSL_sk_insert(st, data, st->num);
389	380M	}
390
391		int OPENSSL_sk_unshift(OPENSSL_STACK st, const void data)
392	0	{
393	0	return OPENSSL_sk_insert(st, data, 0);
394	0	}
395
396		void OPENSSL_sk_shift(OPENSSL_STACK st)
397	0	{
398	0	if (st == NULL \|\| st->num == 0)
399	0	return NULL;
400	0	return internal_delete(st, 0);
401	0	}
402
403		void OPENSSL_sk_pop(OPENSSL_STACK st)
404	2.06M	{
405	2.06M	if (st == NULL \|\| st->num == 0)
406	10.0k	return NULL;
407	2.05M	return internal_delete(st, st->num - 1);
408	2.06M	}
409
410		void OPENSSL_sk_zero(OPENSSL_STACK *st)
411	0	{
412	0	if (st == NULL \|\| st->num == 0)
413	0	return;
414	0	memset(st->data, 0, sizeof(st->data) st->num);
415	0	st->num = 0;
416	0	}
417
418		void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
419	50.4M	{
420	50.4M	int i;
421
422	50.4M	if (st == NULL)
423	12.7M	return;
424	227M	for (i = 0; i < st->num; i++)
425	190M	if (st->data[i] != NULL)
426	189M	func((char *)st->data[i]);
427	37.6M	OPENSSL_sk_free(st);
428	37.6M	}
429
430		void OPENSSL_sk_free(OPENSSL_STACK *st)
431	260M	{
432	260M	if (st == NULL)
433	49.4M	return;
434	210M	OPENSSL_free(st->data);
435	210M	OPENSSL_free(st);
436	210M	}
437
438		int OPENSSL_sk_num(const OPENSSL_STACK *st)
439	1.14G	{
440	1.14G	return st == NULL ? -1 : st->num;
441	1.14G	}
442
443		void OPENSSL_sk_value(const OPENSSL_STACK st, int i)
444	1.30G	{
445	1.30G	if (st == NULL \|\| i < 0 \|\| i >= st->num)
446	4.82k	return NULL;
447	1.30G	return (void *)st->data[i];
448	1.30G	}
449
450		void OPENSSL_sk_set(OPENSSL_STACK st, int i, const void *data)
451	13.0M	{
452	13.0M	if (st == NULL) {
453	0	ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
454	0	return NULL;
455	0	}
456	13.0M	if (i < 0 \|\| i >= st->num) {
457	0	ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
458	0	"i=%d", i);
459	0	return NULL;
460	0	}
461	13.0M	st->data[i] = data;
462	13.0M	st->sorted = 0;
463	13.0M	return (void *)st->data[i];
464	13.0M	}
465
466		void OPENSSL_sk_sort(OPENSSL_STACK *st)
467	15.5M	{
468	15.5M	if (st != NULL && !st->sorted && st->comp != NULL) {
469	13.1M	if (st->num > 1)
470	269k	qsort(st->data, st->num, sizeof(void *), st->comp);
471	13.1M	st->sorted = 1; /* empty or single-element stack is considered sorted */
472	13.1M	}
473	15.5M	}
474
475		int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
476	75.6k	{
477	75.6k	return st == NULL ? 1 : st->sorted;
478	75.6k	}