Branch data Line data Source code
1 : : /*
2 : : * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License").
5 : : * You may not use this file except in compliance with the License.
6 : : * A copy of the License is located at
7 : : *
8 : : * http://aws.amazon.com/apache2.0
9 : : *
10 : : * or in the "license" file accompanying this file. This file is distributed
11 : : * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
12 : : * express or implied. See the License for the specific language governing
13 : : * permissions and limitations under the License.
14 : : */
15 : :
16 : : #include "utils/s2n_array.h"
17 : :
18 : : #include "utils/s2n_blob.h"
19 : : #include "utils/s2n_mem.h"
20 : : #include "utils/s2n_safety.h"
21 : :
22 : : S2N_RESULT s2n_array_validate(const struct s2n_array *array)
23 : 7899089 : {
24 : 7899089 : uint32_t mem_size = 0;
25 [ + + ][ + - ]: 7899089 : RESULT_ENSURE_REF(array);
26 [ - + ]: 7899087 : RESULT_GUARD(s2n_blob_validate(&array->mem));
27 [ # # ][ - + ]: 7899087 : RESULT_ENSURE_NE(array->element_size, 0);
28 [ - + ]: 7899087 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len, array->element_size, &mem_size));
29 [ - + ][ # # ]: 7899087 : RESULT_ENSURE_GTE(array->mem.size, mem_size);
30 [ # # ][ + - ]: 7899087 : RESULT_ENSURE(S2N_IMPLIES(array->mem.size, array->mem.growable), S2N_ERR_SAFETY);
[ + + ]
31 : 7899087 : return S2N_RESULT_OK;
32 : 7899087 : }
33 : :
34 : : static S2N_RESULT s2n_array_enlarge(struct s2n_array *array, uint32_t capacity)
35 : 6974374 : {
36 [ - + ][ # # ]: 6974374 : RESULT_ENSURE_REF(array);
37 : :
38 : : /* Acquire the memory */
39 : 6974374 : uint32_t mem_needed = 0;
40 [ + + ]: 6974374 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, capacity, &mem_needed));
41 [ - + ]: 6974373 : RESULT_GUARD_POSIX(s2n_realloc(&array->mem, mem_needed));
42 : :
43 : : /* Zero the extened part */
44 : 6974373 : uint32_t array_elements_size = 0;
45 [ - + ]: 6974373 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, array->len, &array_elements_size));
46 [ - + ][ # # ]: 6974373 : RESULT_CHECKED_MEMSET(array->mem.data + array_elements_size, 0, array->mem.size - array_elements_size);
[ + + ]
47 [ - + ][ + - ]: 6974373 : RESULT_POSTCONDITION(s2n_array_validate(array));
48 : 6974373 : return S2N_RESULT_OK;
49 : 6974373 : }
50 : :
51 : : struct s2n_array *s2n_array_new(uint32_t element_size)
52 : 1880 : {
53 : 1880 : struct s2n_array *array = s2n_array_new_with_capacity(element_size, S2N_INITIAL_ARRAY_SIZE);
54 [ + + ][ + - ]: 1880 : PTR_ENSURE_REF(array);
55 : :
56 : 1879 : return array;
57 : 1880 : }
58 : :
59 : : struct s2n_array *s2n_array_new_with_capacity(uint32_t element_size, uint32_t capacity)
60 : 2042 : {
61 : 2042 : DEFER_CLEANUP(struct s2n_blob mem = { 0 }, s2n_free);
62 [ - + ]: 2042 : PTR_GUARD_POSIX(s2n_alloc(&mem, sizeof(struct s2n_array)));
63 : :
64 : 2042 : DEFER_CLEANUP(struct s2n_array *array = (void *) mem.data, s2n_array_free_p);
65 : 2042 : ZERO_TO_DISABLE_DEFER_CLEANUP(mem);
66 : :
67 [ + + ]: 2042 : PTR_GUARD_RESULT(s2n_array_init_with_capacity(array, element_size, capacity));
68 : :
69 : 2041 : struct s2n_array *array_ret = array;
70 : 2041 : ZERO_TO_DISABLE_DEFER_CLEANUP(array);
71 : :
72 : 2041 : return array_ret;
73 : 2042 : }
74 : :
75 : : S2N_RESULT s2n_array_init(struct s2n_array *array, uint32_t element_size)
76 : 6970932 : {
77 [ - + ][ # # ]: 6970932 : RESULT_ENSURE_REF(array);
78 : :
79 [ - + ]: 6970932 : RESULT_GUARD(s2n_array_init_with_capacity(array, element_size, 0));
80 : :
81 : 6970932 : return S2N_RESULT_OK;
82 : 6970932 : }
83 : :
84 : : S2N_RESULT s2n_array_init_with_capacity(struct s2n_array *array, uint32_t element_size, uint32_t capacity)
85 : 6972974 : {
86 [ - + ][ # # ]: 6972974 : RESULT_ENSURE_REF(array);
87 : :
88 : 6972974 : *array = (struct s2n_array){ .element_size = element_size };
89 : :
90 [ + + ]: 6972974 : RESULT_GUARD(s2n_array_enlarge(array, capacity));
91 : :
92 : 6972973 : return S2N_RESULT_OK;
93 : 6972974 : }
94 : :
95 : : S2N_RESULT s2n_array_pushback(struct s2n_array *array, void **element)
96 : 3362 : {
97 [ + + ][ + + ]: 3362 : RESULT_PRECONDITION(s2n_array_validate(array));
98 [ - + ][ # # ]: 3361 : RESULT_ENSURE_REF(element);
99 : 3361 : return s2n_array_insert(array, array->len, element);
100 : 3361 : }
101 : :
102 : : S2N_RESULT s2n_array_get(struct s2n_array *array, uint32_t idx, void **element)
103 : 900584 : {
104 [ + + ][ + + ]: 900584 : RESULT_PRECONDITION(s2n_array_validate(array));
105 [ - + ][ # # ]: 900583 : RESULT_ENSURE_REF(element);
106 [ + - ][ + + ]: 900583 : RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
107 : 893950 : *element = array->mem.data + (array->element_size * idx);
108 : 893950 : return S2N_RESULT_OK;
109 : 900583 : }
110 : :
111 : : S2N_RESULT s2n_array_insert_and_copy(struct s2n_array *array, uint32_t idx, void *element)
112 : 1467 : {
113 : 1467 : void *insert_location = NULL;
114 [ - + ]: 1467 : RESULT_GUARD(s2n_array_insert(array, idx, &insert_location));
115 [ # # ][ - + ]: 1467 : RESULT_CHECKED_MEMCPY(insert_location, element, array->element_size);
[ + - ]
116 : 1467 : return S2N_RESULT_OK;
117 : 1467 : }
118 : :
119 : : S2N_RESULT s2n_array_insert(struct s2n_array *array, uint32_t idx, void **element)
120 : 4829 : {
121 [ - + ][ + - ]: 4829 : RESULT_PRECONDITION(s2n_array_validate(array));
122 [ - + ][ # # ]: 4829 : RESULT_ENSURE_REF(element);
123 : : /* index == len is ok since we're about to add one element */
124 [ - + ][ # # ]: 4829 : RESULT_ENSURE(idx <= array->len, S2N_ERR_ARRAY_INDEX_OOB);
125 : :
126 : : /* We are about to add one more element to the array. Add capacity if necessary */
127 : 4829 : uint32_t current_capacity = 0;
128 [ - + ]: 4829 : RESULT_GUARD(s2n_array_capacity(array, ¤t_capacity));
129 : :
130 [ + + ]: 4829 : if (array->len >= current_capacity) {
131 : : /* Enlarge the array */
132 : 1400 : uint32_t new_capacity = 0;
133 [ - + ]: 1400 : RESULT_GUARD_POSIX(s2n_mul_overflow(current_capacity, 2, &new_capacity));
134 [ + + ]: 1400 : new_capacity = S2N_MAX(new_capacity, S2N_INITIAL_ARRAY_SIZE);
135 [ - + ]: 1400 : RESULT_GUARD(s2n_array_enlarge(array, new_capacity));
136 : 1400 : }
137 : :
138 : : /* If we are adding at an existing index, slide everything down. */
139 [ + + ]: 4829 : if (idx < array->len) {
140 : 1 : uint32_t size = 0;
141 [ - + ]: 1 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx, array->element_size, &size));
142 : 1 : memmove(array->mem.data + array->element_size * (idx + 1),
143 : 1 : array->mem.data + array->element_size * idx,
144 : 1 : size);
145 : 1 : }
146 : :
147 : 4829 : *element = array->mem.data + array->element_size * idx;
148 : 4829 : array->len++;
149 : :
150 [ - + ][ + - ]: 4829 : RESULT_POSTCONDITION(s2n_array_validate(array));
151 : 4829 : return S2N_RESULT_OK;
152 : 4829 : }
153 : :
154 : : S2N_RESULT s2n_array_remove(struct s2n_array *array, uint32_t idx)
155 : 5 : {
156 [ - + ][ + - ]: 5 : RESULT_PRECONDITION(s2n_array_validate(array));
157 [ - + ][ # # ]: 5 : RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
158 : :
159 : : /* If the removed element is the last one, no need to move anything.
160 : : * Otherwise, shift everything down */
161 [ + + ]: 5 : if (idx != array->len - 1) {
162 : 2 : uint32_t size = 0;
163 [ - + ]: 2 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx - 1, array->element_size, &size));
164 : 2 : memmove(array->mem.data + array->element_size * idx,
165 : 2 : array->mem.data + array->element_size * (idx + 1),
166 : 2 : size);
167 : 2 : }
168 : 5 : array->len--;
169 : :
170 : : /* After shifting, zero the last element */
171 [ # # ][ - + ]: 5 : RESULT_CHECKED_MEMSET(array->mem.data + array->element_size * array->len,
[ + - ]
172 : 5 : 0,
173 : 5 : array->element_size);
174 : :
175 [ - + ][ + - ]: 5 : RESULT_POSTCONDITION(s2n_array_validate(array));
176 : 5 : return S2N_RESULT_OK;
177 : 5 : }
178 : :
179 : : S2N_RESULT s2n_array_num_elements(struct s2n_array *array, uint32_t *len)
180 : 5962 : {
181 [ - + ][ + - ]: 5962 : RESULT_PRECONDITION(s2n_array_validate(array));
182 [ - + ][ # # ]: 5962 : RESULT_ENSURE_MUT(len);
183 : :
184 : 5962 : *len = array->len;
185 : :
186 : 5962 : return S2N_RESULT_OK;
187 : 5962 : }
188 : :
189 : : S2N_RESULT s2n_array_capacity(struct s2n_array *array, uint32_t *capacity)
190 : 5140 : {
191 [ - + ][ + - ]: 5140 : RESULT_PRECONDITION(s2n_array_validate(array));
192 [ - + ][ # # ]: 5140 : RESULT_ENSURE_MUT(capacity);
193 : :
194 : 5140 : *capacity = array->mem.size / array->element_size;
195 : :
196 : 5140 : return S2N_RESULT_OK;
197 : 5140 : }
198 : :
199 : : S2N_CLEANUP_RESULT s2n_array_free_p(struct s2n_array **parray)
200 : 5976 : {
201 [ - + ][ # # ]: 5976 : RESULT_ENSURE_REF(parray);
202 : :
203 : 5976 : struct s2n_array *array = *parray;
204 [ + + ]: 5976 : if (array == NULL) {
205 : 3934 : return S2N_RESULT_OK;
206 : 3934 : }
207 : :
208 : : /* Free the elements */
209 [ - + ]: 2042 : RESULT_GUARD_POSIX(s2n_free(&array->mem));
210 : :
211 : : /* And finally the array */
212 [ - + ]: 2042 : RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) parray, sizeof(struct s2n_array)));
213 : :
214 : 2042 : return S2N_RESULT_OK;
215 : 2042 : }
216 : :
217 : : S2N_RESULT s2n_array_free(struct s2n_array *array)
218 : 1896 : {
219 [ + - ][ + + ]: 1896 : RESULT_ENSURE_REF(array);
220 : 1895 : return s2n_array_free_p(&array);
221 : 1896 : }
|
