155714Skris/* crypto/stack/stack.c */
255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
355714Skris * All rights reserved.
455714Skris *
555714Skris * This package is an SSL implementation written
655714Skris * by Eric Young (eay@cryptsoft.com).
755714Skris * The implementation was written so as to conform with Netscapes SSL.
8280304Sjkim *
955714Skris * This library is free for commercial and non-commercial use as long as
1055714Skris * the following conditions are aheared to.  The following conditions
1155714Skris * apply to all code found in this distribution, be it the RC4, RSA,
1255714Skris * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
1355714Skris * included with this distribution is covered by the same copyright terms
1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15280304Sjkim *
1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in
1755714Skris * the code are not to be removed.
1855714Skris * If this package is used in a product, Eric Young should be given attribution
1955714Skris * as the author of the parts of the library used.
2055714Skris * This can be in the form of a textual message at program startup or
2155714Skris * in documentation (online or textual) provided with the package.
22280304Sjkim *
2355714Skris * Redistribution and use in source and binary forms, with or without
2455714Skris * modification, are permitted provided that the following conditions
2555714Skris * are met:
2655714Skris * 1. Redistributions of source code must retain the copyright
2755714Skris *    notice, this list of conditions and the following disclaimer.
2855714Skris * 2. Redistributions in binary form must reproduce the above copyright
2955714Skris *    notice, this list of conditions and the following disclaimer in the
3055714Skris *    documentation and/or other materials provided with the distribution.
3155714Skris * 3. All advertising materials mentioning features or use of this software
3255714Skris *    must display the following acknowledgement:
3355714Skris *    "This product includes cryptographic software written by
3455714Skris *     Eric Young (eay@cryptsoft.com)"
3555714Skris *    The word 'cryptographic' can be left out if the rouines from the library
3655714Skris *    being used are not cryptographic related :-).
37280304Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from
3855714Skris *    the apps directory (application code) you must include an acknowledgement:
3955714Skris *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40280304Sjkim *
4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4455714Skris * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
5155714Skris * SUCH DAMAGE.
52280304Sjkim *
5355714Skris * The licence and distribution terms for any publically available version or
5455714Skris * derivative of this code cannot be changed.  i.e. this code cannot simply be
5555714Skris * copied and put under another distribution licence
5655714Skris * [including the GNU Public Licence.]
5755714Skris */
5855714Skris
59280304Sjkim/*-
60280304Sjkim * Code for stacks
6155714Skris * Author - Eric Young v 1.0
62280304Sjkim * 1.2 eay 12-Mar-97 -  Modified sk_find so that it _DOES_ return the
63280304Sjkim *                      lowest index for the searched item.
6455714Skris *
6555714Skris * 1.1 eay - Take from netdb and added to SSLeay
6655714Skris *
6755714Skris * 1.0 eay - First version 29/07/92
6855714Skris */
6955714Skris#include <stdio.h>
7055714Skris#include "cryptlib.h"
7155714Skris#include <openssl/stack.h>
72160814Ssimon#include <openssl/objects.h>
7355714Skris
7455714Skris#undef MIN_NODES
75280304Sjkim#define MIN_NODES       4
7655714Skris
77280304Sjkimconst char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT;
7855714Skris
7955714Skris#include <errno.h>
8055714Skris
81280304Sjkimint (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *)))
82280304Sjkim (const void *, const void *) {
83280304Sjkim    int (*old) (const void *, const void *) = sk->comp;
8455714Skris
85280304Sjkim    if (sk->comp != c)
86280304Sjkim        sk->sorted = 0;
87280304Sjkim    sk->comp = c;
8855714Skris
89280304Sjkim    return old;
90280304Sjkim}
9155714Skris
92238405Sjkim_STACK *sk_dup(_STACK *sk)
93280304Sjkim{
94280304Sjkim    _STACK *ret;
95280304Sjkim    char **s;
9655714Skris
97280304Sjkim    if ((ret = sk_new(sk->comp)) == NULL)
98280304Sjkim        goto err;
99280304Sjkim    s = (char **)OPENSSL_realloc((char *)ret->data,
100280304Sjkim                                 (unsigned int)sizeof(char *) *
101280304Sjkim                                 sk->num_alloc);
102280304Sjkim    if (s == NULL)
103280304Sjkim        goto err;
104280304Sjkim    ret->data = s;
10555714Skris
106280304Sjkim    ret->num = sk->num;
107280304Sjkim    memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
108280304Sjkim    ret->sorted = sk->sorted;
109280304Sjkim    ret->num_alloc = sk->num_alloc;
110280304Sjkim    ret->comp = sk->comp;
111280304Sjkim    return (ret);
112280304Sjkim err:
113280304Sjkim    if (ret)
114280304Sjkim        sk_free(ret);
115280304Sjkim    return (NULL);
116280304Sjkim}
11755714Skris
118238405Sjkim_STACK *sk_new_null(void)
119280304Sjkim{
120280304Sjkim    return sk_new((int (*)(const void *, const void *))0);
121280304Sjkim}
12268651Skris
123280304Sjkim_STACK *sk_new(int (*c) (const void *, const void *))
124280304Sjkim{
125280304Sjkim    _STACK *ret;
126280304Sjkim    int i;
12755714Skris
128280304Sjkim    if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
129280304Sjkim        goto err;
130280304Sjkim    if ((ret->data = OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL)
131280304Sjkim        goto err;
132280304Sjkim    for (i = 0; i < MIN_NODES; i++)
133280304Sjkim        ret->data[i] = NULL;
134280304Sjkim    ret->comp = c;
135280304Sjkim    ret->num_alloc = MIN_NODES;
136280304Sjkim    ret->num = 0;
137280304Sjkim    ret->sorted = 0;
138280304Sjkim    return (ret);
139280304Sjkim err:
140280304Sjkim    if (ret)
141280304Sjkim        OPENSSL_free(ret);
142280304Sjkim    return (NULL);
143280304Sjkim}
14455714Skris
145238405Sjkimint sk_insert(_STACK *st, void *data, int loc)
146280304Sjkim{
147280304Sjkim    char **s;
14855714Skris
149280304Sjkim    if (st == NULL)
150280304Sjkim        return 0;
151280304Sjkim    if (st->num_alloc <= st->num + 1) {
152280304Sjkim        s = OPENSSL_realloc((char *)st->data,
153280304Sjkim                            (unsigned int)sizeof(char *) * st->num_alloc * 2);
154280304Sjkim        if (s == NULL)
155280304Sjkim            return (0);
156280304Sjkim        st->data = s;
157280304Sjkim        st->num_alloc *= 2;
158280304Sjkim    }
159280304Sjkim    if ((loc >= (int)st->num) || (loc < 0))
160280304Sjkim        st->data[st->num] = data;
161280304Sjkim    else {
162280304Sjkim        int i;
163280304Sjkim        char **f, **t;
16455714Skris
165280304Sjkim        f = st->data;
166280304Sjkim        t = &(st->data[1]);
167280304Sjkim        for (i = st->num; i >= loc; i--)
168280304Sjkim            t[i] = f[i];
169280304Sjkim
170280304Sjkim#ifdef undef                    /* no memmove on sunos :-( */
171280304Sjkim        memmove(&(st->data[loc + 1]),
172280304Sjkim                &(st->data[loc]), sizeof(char *) * (st->num - loc));
17355714Skris#endif
174280304Sjkim        st->data[loc] = data;
175280304Sjkim    }
176280304Sjkim    st->num++;
177280304Sjkim    st->sorted = 0;
178280304Sjkim    return (st->num);
179280304Sjkim}
18055714Skris
181238405Sjkimvoid *sk_delete_ptr(_STACK *st, void *p)
182280304Sjkim{
183280304Sjkim    int i;
18455714Skris
185280304Sjkim    for (i = 0; i < st->num; i++)
186280304Sjkim        if (st->data[i] == p)
187280304Sjkim            return (sk_delete(st, i));
188280304Sjkim    return (NULL);
189280304Sjkim}
19055714Skris
191238405Sjkimvoid *sk_delete(_STACK *st, int loc)
192280304Sjkim{
193280304Sjkim    char *ret;
194280304Sjkim    int i, j;
19555714Skris
196280304Sjkim    if (!st || (loc < 0) || (loc >= st->num))
197280304Sjkim        return NULL;
19855714Skris
199280304Sjkim    ret = st->data[loc];
200280304Sjkim    if (loc != st->num - 1) {
201280304Sjkim        j = st->num - 1;
202280304Sjkim        for (i = loc; i < j; i++)
203280304Sjkim            st->data[i] = st->data[i + 1];
204280304Sjkim        /*
205280304Sjkim         * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
206280304Sjkim         * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
207280304Sjkim         */
208280304Sjkim    }
209280304Sjkim    st->num--;
210280304Sjkim    return (ret);
211280304Sjkim}
21255714Skris
213238405Sjkimstatic int internal_find(_STACK *st, void *data, int ret_val_options)
214280304Sjkim{
215280304Sjkim    const void *const *r;
216280304Sjkim    int i;
217238405Sjkim
218280304Sjkim    if (st == NULL)
219280304Sjkim        return -1;
22055714Skris
221280304Sjkim    if (st->comp == NULL) {
222280304Sjkim        for (i = 0; i < st->num; i++)
223280304Sjkim            if (st->data[i] == data)
224280304Sjkim                return (i);
225280304Sjkim        return (-1);
226280304Sjkim    }
227280304Sjkim    sk_sort(st);
228280304Sjkim    if (data == NULL)
229280304Sjkim        return (-1);
230280304Sjkim    r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
231280304Sjkim                        ret_val_options);
232280304Sjkim    if (r == NULL)
233280304Sjkim        return (-1);
234280304Sjkim    return (int)((char **)r - st->data);
235280304Sjkim}
23655714Skris
237238405Sjkimint sk_find(_STACK *st, void *data)
238280304Sjkim{
239280304Sjkim    return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
240280304Sjkim}
241280304Sjkim
242238405Sjkimint sk_find_ex(_STACK *st, void *data)
243280304Sjkim{
244280304Sjkim    return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
245280304Sjkim}
246160814Ssimon
247238405Sjkimint sk_push(_STACK *st, void *data)
248280304Sjkim{
249280304Sjkim    return (sk_insert(st, data, st->num));
250280304Sjkim}
25155714Skris
252238405Sjkimint sk_unshift(_STACK *st, void *data)
253280304Sjkim{
254280304Sjkim    return (sk_insert(st, data, 0));
255280304Sjkim}
25655714Skris
257238405Sjkimvoid *sk_shift(_STACK *st)
258280304Sjkim{
259280304Sjkim    if (st == NULL)
260280304Sjkim        return (NULL);
261280304Sjkim    if (st->num <= 0)
262280304Sjkim        return (NULL);
263280304Sjkim    return (sk_delete(st, 0));
264280304Sjkim}
26555714Skris
266238405Sjkimvoid *sk_pop(_STACK *st)
267280304Sjkim{
268280304Sjkim    if (st == NULL)
269280304Sjkim        return (NULL);
270280304Sjkim    if (st->num <= 0)
271280304Sjkim        return (NULL);
272280304Sjkim    return (sk_delete(st, st->num - 1));
273280304Sjkim}
27455714Skris
275238405Sjkimvoid sk_zero(_STACK *st)
276280304Sjkim{
277280304Sjkim    if (st == NULL)
278280304Sjkim        return;
279280304Sjkim    if (st->num <= 0)
280280304Sjkim        return;
281280304Sjkim    memset((char *)st->data, 0, sizeof(*st->data) * st->num);
282280304Sjkim    st->num = 0;
283280304Sjkim}
28455714Skris
285280304Sjkimvoid sk_pop_free(_STACK *st, void (*func) (void *))
286280304Sjkim{
287280304Sjkim    int i;
28855714Skris
289280304Sjkim    if (st == NULL)
290280304Sjkim        return;
291280304Sjkim    for (i = 0; i < st->num; i++)
292280304Sjkim        if (st->data[i] != NULL)
293280304Sjkim            func(st->data[i]);
294280304Sjkim    sk_free(st);
295280304Sjkim}
29655714Skris
297238405Sjkimvoid sk_free(_STACK *st)
298280304Sjkim{
299280304Sjkim    if (st == NULL)
300280304Sjkim        return;
301280304Sjkim    if (st->data != NULL)
302280304Sjkim        OPENSSL_free(st->data);
303280304Sjkim    OPENSSL_free(st);
304280304Sjkim}
30555714Skris
306238405Sjkimint sk_num(const _STACK *st)
30755714Skris{
308280304Sjkim    if (st == NULL)
309280304Sjkim        return -1;
310280304Sjkim    return st->num;
31155714Skris}
31255714Skris
313238405Sjkimvoid *sk_value(const _STACK *st, int i)
31455714Skris{
315280304Sjkim    if (!st || (i < 0) || (i >= st->num))
316280304Sjkim        return NULL;
317280304Sjkim    return st->data[i];
31855714Skris}
31955714Skris
320238405Sjkimvoid *sk_set(_STACK *st, int i, void *value)
32155714Skris{
322280304Sjkim    if (!st || (i < 0) || (i >= st->num))
323280304Sjkim        return NULL;
324280304Sjkim    return (st->data[i] = value);
32555714Skris}
32655714Skris
327238405Sjkimvoid sk_sort(_STACK *st)
328280304Sjkim{
329280304Sjkim    if (st && !st->sorted) {
330280304Sjkim        int (*comp_func) (const void *, const void *);
33155714Skris
332280304Sjkim        /*
333280304Sjkim         * same comment as in sk_find ... previously st->comp was declared as
334280304Sjkim         * a (void*,void*) callback type, but this made the population of the
335280304Sjkim         * callback pointer illogical - our callbacks compare type** with
336280304Sjkim         * type**, so we leave the casting until absolutely necessary (ie.
337280304Sjkim         * "now").
338280304Sjkim         */
339280304Sjkim        comp_func = (int (*)(const void *, const void *))(st->comp);
340280304Sjkim        qsort(st->data, st->num, sizeof(char *), comp_func);
341280304Sjkim        st->sorted = 1;
342280304Sjkim    }
343280304Sjkim}
344142425Snectar
345238405Sjkimint sk_is_sorted(const _STACK *st)
346280304Sjkim{
347280304Sjkim    if (!st)
348280304Sjkim        return 1;
349280304Sjkim    return st->sorted;
350280304Sjkim}
351