1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
/**
\file
Typesafe dynamically sized arrays
*/
#include "vector.h"
#include <errno.h>
#include <stdint.h>
#include <string.h>
/** The minimum number of elements to allocate even when fewer elements are used */
#define MIN_VECTOR_ALLOC 4
/**
Multiplies two size_t values, checking for overflows
Both arguments are limited to the size of a uint32_t (to keep the check simple)
Returns SIZE_MAX and sets errno on failure.
*/
static inline size_t mul_check(size_t members, size_t size) {
uint64_t v = (uint64_t)members * size;
if (members > UINT32_MAX || size > UINT32_MAX || v > SIZE_MAX) {
errno = EOVERFLOW;
return SIZE_MAX;
}
return v;
}
/**
Reallocates a block of memory for an array on the heap
May fail with EOVERFLOW (when members or size does not fit into a uint32_t,
or their product does not fit into a size_t) or ENOMEM.
*/
static inline void * realloc_array(void *ptr, size_t members, size_t size) {
errno = 0;
size_t array_size = mul_check(members, size);
if (errno)
return NULL;
return realloc(ptr, array_size);
}
/**
Resizes a vector
Vector allocations are always powers of 2.
Internal function, use VECTOR_RESIZE() instead.
*/
bool _vector_resize(vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
desc->length = n;
size_t alloc = desc->allocated;
if (!alloc) {
alloc = MIN_VECTOR_ALLOC;
n = n*3/2;
}
while (alloc < n) {
alloc <<= 1;
if (!alloc) {
errno = ENOMEM;
return false;
}
}
if (alloc != desc->allocated) {
desc->allocated = alloc;
void *tmp = realloc_array(*data, alloc, elemsize);
if (!tmp)
return false;
*data = tmp;
}
return true;
}
/**
Inserts an element into a vector
Internal function, use VECTOR_INSERT() and VECTOR_ADD() instead.
*/
bool _vector_insert(vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize) {
if (!_vector_resize(desc, data, desc->length+1, elemsize))
return false;
void *p = *data + pos*elemsize;
memmove(p+elemsize, p, (desc->length-pos-1)*elemsize);
memcpy(p, element, elemsize);
return true;
}
/**
Deletes an element from a vector
Internal function, use VECTOR_DELETE() instead.
*/
void _vector_delete(vector_desc_t *desc, void **data, size_t pos, size_t elemsize) {
void *p = *data + pos*elemsize;
memmove(p, p+elemsize, (desc->length-pos-1)*elemsize);
desc->length--;
}
|
