0076db139d78023c2a6e37f94fd43d8b3e7903f6
[openssl.git] / crypto / stack / stack.c
1 /*
2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (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 <openssl/stack.h>
13 #include <openssl/objects.h>
14
15 struct stack_st {
16     int num;
17     char **data;
18     int sorted;
19     int num_alloc;
20     OPENSSL_sk_compfunc comp;
21 };
22
23 #undef MIN_NODES
24 #define MIN_NODES       4
25
26 #include <errno.h>
27
28 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
29 {
30     OPENSSL_sk_compfunc old = sk->comp;
31
32     if (sk->comp != c)
33         sk->sorted = 0;
34     sk->comp = c;
35
36     return old;
37 }
38
39 OPENSSL_STACK *OPENSSL_sk_dup(OPENSSL_STACK *sk)
40 {
41     OPENSSL_STACK *ret;
42     char **s;
43
44     if ((ret = OPENSSL_sk_new(sk->comp)) == NULL)
45         goto err;
46     s = OPENSSL_realloc((char *)ret->data,
47                         (unsigned int)sizeof(char *) * sk->num_alloc);
48     if (s == NULL)
49         goto err;
50     ret->data = s;
51
52     ret->num = sk->num;
53     memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
54     ret->sorted = sk->sorted;
55     ret->num_alloc = sk->num_alloc;
56     ret->comp = sk->comp;
57     return (ret);
58  err:
59     OPENSSL_sk_free(ret);
60     return (NULL);
61 }
62
63 OPENSSL_STACK *OPENSSL_sk_deep_copy(OPENSSL_STACK *sk, OPENSSL_sk_copyfunc copy_func,
64                              OPENSSL_sk_freefunc free_func)
65 {
66     OPENSSL_STACK *ret;
67     int i;
68
69     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
70         return ret;
71     ret->comp = sk->comp;
72     ret->sorted = sk->sorted;
73     ret->num = sk->num;
74     ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
75     ret->data = OPENSSL_malloc(sizeof(*ret->data) * ret->num_alloc);
76     if (ret->data == NULL) {
77         OPENSSL_free(ret);
78         return NULL;
79     }
80     for (i = 0; i < ret->num_alloc; i++)
81         ret->data[i] = NULL;
82
83     for (i = 0; i < ret->num; ++i) {
84         if (sk->data[i] == NULL)
85             continue;
86         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
87             while (--i >= 0)
88                 if (ret->data[i] != NULL)
89                     free_func(ret->data[i]);
90             OPENSSL_sk_free(ret);
91             return NULL;
92         }
93     }
94     return ret;
95 }
96
97 OPENSSL_STACK *OPENSSL_sk_new_null(void)
98 {
99     return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL);
100 }
101
102 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
103 {
104     OPENSSL_STACK *ret;
105
106     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
107         goto err;
108     if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL)
109         goto err;
110     ret->comp = c;
111     ret->num_alloc = MIN_NODES;
112     return (ret);
113
114  err:
115     OPENSSL_free(ret);
116     return (NULL);
117 }
118
119 int OPENSSL_sk_insert(OPENSSL_STACK *st, void *data, int loc)
120 {
121     char **s;
122
123     if (st == NULL)
124         return 0;
125     if (st->num_alloc <= st->num + 1) {
126         s = OPENSSL_realloc((char *)st->data,
127                             (unsigned int)sizeof(char *) * st->num_alloc * 2);
128         if (s == NULL)
129             return (0);
130         st->data = s;
131         st->num_alloc *= 2;
132     }
133     if ((loc >= (int)st->num) || (loc < 0))
134         st->data[st->num] = data;
135     else {
136         memmove(&(st->data[loc + 1]),
137                 &(st->data[loc]), sizeof(char *) * (st->num - loc));
138         st->data[loc] = data;
139     }
140     st->num++;
141     st->sorted = 0;
142     return (st->num);
143 }
144
145 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
146 {
147     int i;
148
149     for (i = 0; i < st->num; i++)
150         if (st->data[i] == p)
151             return OPENSSL_sk_delete(st, i);
152     return NULL;
153 }
154
155 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
156 {
157     char *ret;
158     int i, j;
159
160     if (st == NULL || loc < 0 || loc >= st->num)
161         return NULL;
162
163     ret = st->data[loc];
164     if (loc != st->num - 1) {
165         j = st->num - 1;
166         for (i = loc; i < j; i++)
167             st->data[i] = st->data[i + 1];
168         /*
169          * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
170          * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
171          */
172     }
173     st->num--;
174     return (ret);
175 }
176
177 static int internal_find(OPENSSL_STACK *st, const void *data,
178                          int ret_val_options)
179 {
180     const void *const *r;
181     int i;
182
183     if (st == NULL)
184         return -1;
185
186     if (st->comp == NULL) {
187         for (i = 0; i < st->num; i++)
188             if (st->data[i] == data)
189                 return (i);
190         return (-1);
191     }
192     OPENSSL_sk_sort(st);
193     if (data == NULL)
194         return (-1);
195     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
196                         ret_val_options);
197     if (r == NULL)
198         return (-1);
199     return (int)((char **)r - st->data);
200 }
201
202 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
203 {
204     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
205 }
206
207 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
208 {
209     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
210 }
211
212 int OPENSSL_sk_push(OPENSSL_STACK *st, void *data)
213 {
214     return (OPENSSL_sk_insert(st, data, st->num));
215 }
216
217 int OPENSSL_sk_unshift(OPENSSL_STACK *st, void *data)
218 {
219     return (OPENSSL_sk_insert(st, data, 0));
220 }
221
222 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
223 {
224     if (st == NULL)
225         return (NULL);
226     if (st->num <= 0)
227         return (NULL);
228     return (OPENSSL_sk_delete(st, 0));
229 }
230
231 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
232 {
233     if (st == NULL)
234         return (NULL);
235     if (st->num <= 0)
236         return (NULL);
237     return (OPENSSL_sk_delete(st, st->num - 1));
238 }
239
240 void OPENSSL_sk_zero(OPENSSL_STACK *st)
241 {
242     if (st == NULL)
243         return;
244     if (st->num <= 0)
245         return;
246     memset(st->data, 0, sizeof(*st->data) * st->num);
247     st->num = 0;
248 }
249
250 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
251 {
252     int i;
253
254     if (st == NULL)
255         return;
256     for (i = 0; i < st->num; i++)
257         if (st->data[i] != NULL)
258             func(st->data[i]);
259     OPENSSL_sk_free(st);
260 }
261
262 void OPENSSL_sk_free(OPENSSL_STACK *st)
263 {
264     if (st == NULL)
265         return;
266     OPENSSL_free(st->data);
267     OPENSSL_free(st);
268 }
269
270 int OPENSSL_sk_num(const OPENSSL_STACK *st)
271 {
272     if (st == NULL)
273         return -1;
274     return st->num;
275 }
276
277 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
278 {
279     if (st == NULL || i < 0 || i >= st->num)
280         return NULL;
281     return st->data[i];
282 }
283
284 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, void *value)
285 {
286     if (st == NULL || i < 0 || i >= st->num)
287         return NULL;
288     return (st->data[i] = value);
289 }
290
291 void OPENSSL_sk_sort(OPENSSL_STACK *st)
292 {
293     if (st && !st->sorted && st->comp != NULL) {
294         qsort(st->data, st->num, sizeof(char *), st->comp);
295         st->sorted = 1;
296     }
297 }
298
299 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
300 {
301     if (st == NULL)
302         return 1;
303     return st->sorted;
304 }