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