GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/stack/stack.c Lines: 102 132 77.3 %
Date: 2017-11-07 Branches: 49 80 61.3 %

Line Branch Exec Source
1
/* $OpenBSD: stack.c,v 1.19 2015/02/07 13:19:15 doug Exp $ */
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3
 * All rights reserved.
4
 *
5
 * This package is an SSL implementation written
6
 * by Eric Young (eay@cryptsoft.com).
7
 * The implementation was written so as to conform with Netscapes SSL.
8
 *
9
 * This library is free for commercial and non-commercial use as long as
10
 * the following conditions are aheared to.  The following conditions
11
 * apply to all code found in this distribution, be it the RC4, RSA,
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13
 * included with this distribution is covered by the same copyright terms
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15
 *
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
17
 * the code are not to be removed.
18
 * If this package is used in a product, Eric Young should be given attribution
19
 * as the author of the parts of the library used.
20
 * This can be in the form of a textual message at program startup or
21
 * in documentation (online or textual) provided with the package.
22
 *
23
 * Redistribution and use in source and binary forms, with or without
24
 * modification, are permitted provided that the following conditions
25
 * are met:
26
 * 1. Redistributions of source code must retain the copyright
27
 *    notice, this list of conditions and the following disclaimer.
28
 * 2. Redistributions in binary form must reproduce the above copyright
29
 *    notice, this list of conditions and the following disclaimer in the
30
 *    documentation and/or other materials provided with the distribution.
31
 * 3. All advertising materials mentioning features or use of this software
32
 *    must display the following acknowledgement:
33
 *    "This product includes cryptographic software written by
34
 *     Eric Young (eay@cryptsoft.com)"
35
 *    The word 'cryptographic' can be left out if the rouines from the library
36
 *    being used are not cryptographic related :-).
37
 * 4. If you include any Windows specific code (or a derivative thereof) from
38
 *    the apps directory (application code) you must include an acknowledgement:
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40
 *
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51
 * SUCH DAMAGE.
52
 *
53
 * The licence and distribution terms for any publically available version or
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
55
 * copied and put under another distribution licence
56
 * [including the GNU Public Licence.]
57
 */
58
59
#include <stdio.h>
60
#include <string.h>
61
62
#include <openssl/objects.h>
63
#include <openssl/stack.h>
64
65
#undef MIN_NODES
66
#define MIN_NODES	4
67
68
#include <errno.h>
69
70
int
71
(*sk_set_cmp_func(_STACK *sk, int (*c)(const void *, const void *)))(
72
    const void *, const void *)
73
{
74
2524
	int (*old)(const void *, const void *) = sk->comp;
75
76
1262
	if (sk->comp != c)
77
1262
		sk->sorted = 0;
78
1262
	sk->comp = c;
79
80
1262
	return old;
81
}
82
83
_STACK *
84
sk_dup(_STACK *sk)
85
{
86
	_STACK *ret;
87
	char **s;
88
89
4814
	if ((ret = sk_new(sk->comp)) == NULL)
90
		goto err;
91
2407
	s = reallocarray(ret->data, sk->num_alloc, sizeof(char *));
92
2407
	if (s == NULL)
93
		goto err;
94
2407
	ret->data = s;
95
96
2407
	ret->num = sk->num;
97
2407
	memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
98
2407
	ret->sorted = sk->sorted;
99
2407
	ret->num_alloc = sk->num_alloc;
100
2407
	ret->comp = sk->comp;
101
2407
	return (ret);
102
103
err:
104
	if (ret)
105
		sk_free(ret);
106
	return (NULL);
107
2407
}
108
109
_STACK *
110
sk_new_null(void)
111
{
112
811124
	return sk_new((int (*)(const void *, const void *))0);
113
}
114
115
_STACK *
116
sk_new(int (*c)(const void *, const void *))
117
{
118
	_STACK *ret;
119
	int i;
120
121
818026
	if ((ret = malloc(sizeof(_STACK))) == NULL)
122
		goto err;
123
409013
	if ((ret->data = reallocarray(NULL, MIN_NODES, sizeof(char *))) == NULL)
124
		goto err;
125
4090130
	for (i = 0; i < MIN_NODES; i++)
126
1636052
		ret->data[i] = NULL;
127
409013
	ret->comp = c;
128
409013
	ret->num_alloc = MIN_NODES;
129
409013
	ret->num = 0;
130
409013
	ret->sorted = 0;
131
409013
	return (ret);
132
133
err:
134
	free(ret);
135
	return (NULL);
136
409013
}
137
138
int
139
sk_insert(_STACK *st, void *data, int loc)
140
{
141
	char **s;
142
143
1513626
	if (st == NULL)
144
		return 0;
145
756813
	if (st->num_alloc <= st->num + 1) {
146
78172
		s = reallocarray(st->data, st->num_alloc, 2 * sizeof(char *));
147
78172
		if (s == NULL)
148
			return (0);
149
78172
		st->data = s;
150
78172
		st->num_alloc *= 2;
151
78172
	}
152
756813
	if ((loc >= (int)st->num) || (loc < 0))
153
756813
		st->data[st->num] = data;
154
	else {
155
		memmove(&(st->data[loc + 1]), &(st->data[loc]),
156
		    sizeof(char *)*(st->num - loc));
157
		st->data[loc] = data;
158
	}
159
756813
	st->num++;
160
756813
	st->sorted = 0;
161
756813
	return (st->num);
162
756813
}
163
164
void *
165
sk_delete_ptr(_STACK *st, void *p)
166
{
167
	int i;
168
169
4997
	for (i = 0; i < st->num; i++)
170
1998
		if (st->data[i] == p)
171
1001
			return (sk_delete(st, i));
172
	return (NULL);
173
1001
}
174
175
void *
176
sk_delete(_STACK *st, int loc)
177
{
178
	char *ret;
179
180

14622
	if (!st || (loc < 0) || (loc >= st->num))
181
		return NULL;
182
183
4874
	ret = st->data[loc];
184
4874
	if (loc != st->num - 1) {
185
180
		memmove(&(st->data[loc]), &(st->data[loc + 1]),
186
90
		    sizeof(char *)*(st->num - 1 - loc));
187
90
	}
188
4874
	st->num--;
189
4874
	return (ret);
190
4874
}
191
192
static int
193
internal_find(_STACK *st, void *data, int ret_val_options)
194
{
195
	const void * const *r;
196
	int i;
197
198
22658
	if (st == NULL)
199
		return -1;
200
201
22658
	if (st->comp == NULL) {
202
1312
		for (i = 0; i < st->num; i++)
203
656
			if (st->data[i] == data)
204
264
				return (i);
205
		return (-1);
206
	}
207
22394
	sk_sort(st);
208
22394
	if (data == NULL)
209
		return (-1);
210
22394
	r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
211
	    ret_val_options);
212
22394
	if (r == NULL)
213
13092
		return (-1);
214
9302
	return (int)((char **)r - st->data);
215
22658
}
216
217
int
218
sk_find(_STACK *st, void *data)
219
{
220
45316
	return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
221
}
222
223
int
224
sk_find_ex(_STACK *st, void *data)
225
{
226
	return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
227
}
228
229
int
230
sk_push(_STACK *st, void *data)
231
{
232
1513014
	return (sk_insert(st, data, st->num));
233
}
234
235
int
236
sk_unshift(_STACK *st, void *data)
237
{
238
	return (sk_insert(st, data, 0));
239
}
240
241
void *
242
sk_shift(_STACK *st)
243
{
244
64
	if (st == NULL)
245
		return (NULL);
246
32
	if (st->num <= 0)
247
		return (NULL);
248
32
	return (sk_delete(st, 0));
249
32
}
250
251
void *
252
sk_pop(_STACK *st)
253
{
254
1878
	if (st == NULL)
255
		return (NULL);
256
939
	if (st->num <= 0)
257
		return (NULL);
258
939
	return (sk_delete(st, st->num - 1));
259
939
}
260
261
void
262
sk_zero(_STACK *st)
263
{
264
	if (st == NULL)
265
		return;
266
	if (st->num <= 0)
267
		return;
268
	memset(st->data, 0, sizeof(st->data)*st->num);
269
	st->num = 0;
270
}
271
272
void
273
sk_pop_free(_STACK *st, void (*func)(void *))
274
{
275
	int i;
276
277
500190
	if (st == NULL)
278
25115
		return;
279
1245496
	for (i = 0; i < st->num; i++)
280
397768
		if (st->data[i] != NULL)
281
397768
			func(st->data[i]);
282
224980
	sk_free(st);
283
475075
}
284
285
void
286
sk_free(_STACK *st)
287
{
288
838660
	if (st == NULL)
289
		return;
290
403655
	free(st->data);
291
403655
	free(st);
292
822985
}
293
294
int
295
sk_num(const _STACK *st)
296
{
297
5071876
	if (st == NULL)
298
10570
		return -1;
299
2525368
	return st->num;
300
2535938
}
301
302
void *
303
sk_value(const _STACK *st, int i)
304
{
305

4726134
	if (!st || (i < 0) || (i >= st->num))
306
		return NULL;
307
1575378
	return st->data[i];
308
1575378
}
309
310
void *
311
sk_set(_STACK *st, int i, void *value)
312
{
313

4809
	if (!st || (i < 0) || (i >= st->num))
314
		return NULL;
315
1603
	return (st->data[i] = value);
316
1603
}
317
318
void
319
sk_sort(_STACK *st)
320
{
321

70972
	if (st && !st->sorted) {
322
		int (*comp_func)(const void *, const void *);
323
324
		/* same comment as in sk_find ... previously st->comp was declared
325
		 * as a (void*,void*) callback type, but this made the population
326
		 * of the callback pointer illogical - our callbacks compare
327
		 * type** with type**, so we leave the casting until absolutely
328
		 * necessary (ie. "now"). */
329
14466
		comp_func = (int (*)(const void *, const void *))(st->comp);
330
14466
		qsort(st->data, st->num, sizeof(char *), comp_func);
331
14466
		st->sorted = 1;
332
14466
	}
333
23658
}
334
335
int
336
sk_is_sorted(const _STACK *st)
337
{
338
	if (!st)
339
		return 1;
340
	return st->sorted;
341
}