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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
/*
* Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License").
* You may not use this file except in compliance with the License.
* A copy of the License is located at
*
* http://aws.amazon.com/apache2.0
*
* or in the "license" file accompanying this file. This file is distributed
* on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
* express or implied. See the License for the specific language governing
* permissions and limitations under the License.
*/
#include "utils/s2n_array.h"
#include <sys/param.h>
#include "utils/s2n_blob.h"
#include "utils/s2n_mem.h"
#include "utils/s2n_safety.h"
S2N_RESULT s2n_array_validate(const struct s2n_array *array)
{
uint32_t mem_size = 0;
RESULT_ENSURE_REF(array);
RESULT_GUARD(s2n_blob_validate(&array->mem));
RESULT_ENSURE_NE(array->element_size, 0);
RESULT_GUARD_POSIX(s2n_mul_overflow(array->len, array->element_size, &mem_size));
RESULT_ENSURE_GTE(array->mem.size, mem_size);
RESULT_ENSURE(S2N_IMPLIES(array->mem.size, array->mem.growable), S2N_ERR_SAFETY);
return S2N_RESULT_OK;
}
static S2N_RESULT s2n_array_enlarge(struct s2n_array *array, uint32_t capacity)
{
RESULT_ENSURE_REF(array);
/* Acquire the memory */
uint32_t mem_needed;
RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, capacity, &mem_needed));
RESULT_GUARD_POSIX(s2n_realloc(&array->mem, mem_needed));
/* Zero the extened part */
uint32_t array_elements_size;
RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, array->len, &array_elements_size));
RESULT_CHECKED_MEMSET(array->mem.data + array_elements_size, 0, array->mem.size - array_elements_size);
RESULT_POSTCONDITION(s2n_array_validate(array));
return S2N_RESULT_OK;
}
struct s2n_array *s2n_array_new(uint32_t element_size)
{
struct s2n_array *array = s2n_array_new_with_capacity(element_size, S2N_INITIAL_ARRAY_SIZE);
PTR_ENSURE_REF(array);
return array;
}
struct s2n_array *s2n_array_new_with_capacity(uint32_t element_size, uint32_t capacity)
{
DEFER_CLEANUP(struct s2n_blob mem = { 0 }, s2n_free);
PTR_GUARD_POSIX(s2n_alloc(&mem, sizeof(struct s2n_array)));
DEFER_CLEANUP(struct s2n_array *array = (void *) mem.data, s2n_array_free_p);
ZERO_TO_DISABLE_DEFER_CLEANUP(mem);
PTR_GUARD_RESULT(s2n_array_init_with_capacity(array, element_size, capacity));
struct s2n_array *array_ret = array;
ZERO_TO_DISABLE_DEFER_CLEANUP(array);
return array_ret;
}
S2N_RESULT s2n_array_init(struct s2n_array *array, uint32_t element_size)
{
RESULT_ENSURE_REF(array);
RESULT_GUARD(s2n_array_init_with_capacity(array, element_size, 0));
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_init_with_capacity(struct s2n_array *array, uint32_t element_size, uint32_t capacity)
{
RESULT_ENSURE_REF(array);
*array = (struct s2n_array){ .element_size = element_size };
RESULT_GUARD(s2n_array_enlarge(array, capacity));
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_pushback(struct s2n_array *array, void **element)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE_REF(element);
return s2n_array_insert(array, array->len, element);
}
S2N_RESULT s2n_array_get(struct s2n_array *array, uint32_t idx, void **element)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE_REF(element);
RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
*element = array->mem.data + (array->element_size * idx);
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_insert_and_copy(struct s2n_array *array, uint32_t idx, void *element)
{
void *insert_location = NULL;
RESULT_GUARD(s2n_array_insert(array, idx, &insert_location));
RESULT_CHECKED_MEMCPY(insert_location, element, array->element_size);
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_insert(struct s2n_array *array, uint32_t idx, void **element)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE_REF(element);
/* index == len is ok since we're about to add one element */
RESULT_ENSURE(idx <= array->len, S2N_ERR_ARRAY_INDEX_OOB);
/* We are about to add one more element to the array. Add capacity if necessary */
uint32_t current_capacity = 0;
RESULT_GUARD(s2n_array_capacity(array, ¤t_capacity));
if (array->len >= current_capacity) {
/* Enlarge the array */
uint32_t new_capacity = 0;
RESULT_GUARD_POSIX(s2n_mul_overflow(current_capacity, 2, &new_capacity));
new_capacity = MAX(new_capacity, S2N_INITIAL_ARRAY_SIZE);
RESULT_GUARD(s2n_array_enlarge(array, new_capacity));
}
/* If we are adding at an existing index, slide everything down. */
if (idx < array->len) {
uint32_t size = 0;
RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx, array->element_size, &size));
memmove(array->mem.data + array->element_size * (idx + 1),
array->mem.data + array->element_size * idx,
size);
}
*element = array->mem.data + array->element_size * idx;
array->len++;
RESULT_POSTCONDITION(s2n_array_validate(array));
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_remove(struct s2n_array *array, uint32_t idx)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
/* If the removed element is the last one, no need to move anything.
* Otherwise, shift everything down */
if (idx != array->len - 1) {
uint32_t size = 0;
RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx - 1, array->element_size, &size));
memmove(array->mem.data + array->element_size * idx,
array->mem.data + array->element_size * (idx + 1),
size);
}
array->len--;
/* After shifting, zero the last element */
RESULT_CHECKED_MEMSET(array->mem.data + array->element_size * array->len,
0,
array->element_size);
RESULT_POSTCONDITION(s2n_array_validate(array));
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_num_elements(struct s2n_array *array, uint32_t *len)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE_MUT(len);
*len = array->len;
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_capacity(struct s2n_array *array, uint32_t *capacity)
{
RESULT_PRECONDITION(s2n_array_validate(array));
RESULT_ENSURE_MUT(capacity);
*capacity = array->mem.size / array->element_size;
return S2N_RESULT_OK;
}
S2N_CLEANUP_RESULT s2n_array_free_p(struct s2n_array **parray)
{
RESULT_ENSURE_REF(parray);
struct s2n_array *array = *parray;
if (array == NULL) {
return S2N_RESULT_OK;
}
/* Free the elements */
RESULT_GUARD_POSIX(s2n_free(&array->mem));
/* And finally the array */
RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) parray, sizeof(struct s2n_array)));
return S2N_RESULT_OK;
}
S2N_RESULT s2n_array_free(struct s2n_array *array)
{
RESULT_ENSURE_REF(array);
return s2n_array_free_p(&array);
}
|
