Line data Source code
1 : #ifndef AWS_COMMON_ARRAY_LIST_INL
2 : #define AWS_COMMON_ARRAY_LIST_INL
3 :
4 : /**
5 : * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
6 : * SPDX-License-Identifier: Apache-2.0.
7 : */
8 :
9 : /* This is implicitly included, but helps with editor highlighting */
10 : #include <aws/common/array_list.h>
11 : /*
12 : * Do not add system headers here; add them to array_list.h. This file is included under extern "C" guards,
13 : * which might break system headers.
14 : */
15 : AWS_EXTERN_C_BEGIN
16 :
17 : AWS_STATIC_IMPL
18 : int aws_array_list_init_dynamic(
19 : struct aws_array_list *AWS_RESTRICT list,
20 : struct aws_allocator *alloc,
21 : size_t initial_item_allocation,
22 1520 : size_t item_size) {
23 1520 :
24 1520 : AWS_FATAL_PRECONDITION(list != NULL);
25 1520 : AWS_FATAL_PRECONDITION(alloc != NULL);
26 1520 : AWS_FATAL_PRECONDITION(item_size > 0);
27 1520 :
28 1520 : AWS_ZERO_STRUCT(*list);
29 1520 :
30 1520 : size_t allocation_size;
31 1520 : if (aws_mul_size_checked(initial_item_allocation, item_size, &allocation_size)) {
32 0 : goto error;
33 0 : }
34 1520 :
35 1520 : if (allocation_size > 0) {
36 652 : list->data = aws_mem_acquire(alloc, allocation_size);
37 652 : if (!list->data) {
38 0 : goto error;
39 0 : }
40 330 : #ifdef DEBUG_BUILD
41 330 : memset(list->data, AWS_ARRAY_LIST_DEBUG_FILL, allocation_size);
42 330 :
43 330 : #endif
44 652 : list->current_size = allocation_size;
45 652 : }
46 1520 : list->item_size = item_size;
47 1520 : list->alloc = alloc;
48 1520 :
49 1520 : AWS_FATAL_POSTCONDITION(list->current_size == 0 || list->data);
50 1520 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
51 1520 : return AWS_OP_SUCCESS;
52 792 :
53 792 : error:
54 0 : AWS_POSTCONDITION(AWS_IS_ZEROED(*list));
55 0 : return AWS_OP_ERR;
56 0 : }
57 :
58 : AWS_STATIC_IMPL
59 : void aws_array_list_init_static(
60 : struct aws_array_list *AWS_RESTRICT list,
61 : void *raw_array,
62 : size_t item_count,
63 27899 : size_t item_size) {
64 27899 :
65 27899 : AWS_FATAL_PRECONDITION(list != NULL);
66 27899 : AWS_FATAL_PRECONDITION(raw_array != NULL);
67 27899 : AWS_FATAL_PRECONDITION(item_count > 0);
68 27899 : AWS_FATAL_PRECONDITION(item_size > 0);
69 27899 :
70 27899 : list->alloc = NULL;
71 27899 :
72 27899 : int no_overflow = !aws_mul_size_checked(item_count, item_size, &list->current_size);
73 27899 : AWS_FATAL_PRECONDITION(no_overflow);
74 27899 :
75 27899 : list->item_size = item_size;
76 27899 : list->length = 0;
77 27899 : list->data = raw_array;
78 27899 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
79 27899 : }
80 :
81 : AWS_STATIC_IMPL
82 5646168 : bool aws_array_list_is_valid(const struct aws_array_list *AWS_RESTRICT list) {
83 5646168 : if (!list) {
84 0 : return false;
85 0 : }
86 5646168 : size_t required_size = 0;
87 5646168 : bool required_size_is_valid =
88 5646168 : (aws_mul_size_checked(list->length, list->item_size, &required_size) == AWS_OP_SUCCESS);
89 5646168 : bool current_size_is_valid = (list->current_size >= required_size);
90 5646168 : bool data_is_valid = AWS_IMPLIES(list->current_size == 0, list->data == NULL) &&
91 5646168 : AWS_IMPLIES(list->current_size != 0, AWS_MEM_IS_WRITABLE(list->data, list->current_size));
92 5646168 : bool item_size_is_valid = (list->item_size != 0);
93 5646168 : return required_size_is_valid && current_size_is_valid && data_is_valid && item_size_is_valid;
94 5646168 : }
95 :
96 : AWS_STATIC_IMPL
97 0 : void aws_array_list_debug_print(const struct aws_array_list *list) {
98 0 : printf(
99 0 : "arraylist %p. Alloc %p. current_size %zu. length %zu. item_size %zu. data %p\n",
100 0 : (void *)list,
101 0 : (void *)list->alloc,
102 0 : list->current_size,
103 0 : list->length,
104 0 : list->item_size,
105 0 : (void *)list->data);
106 0 : }
107 :
108 : AWS_STATIC_IMPL
109 123879 : void aws_array_list_clean_up(struct aws_array_list *AWS_RESTRICT list) {
110 123879 : AWS_PRECONDITION(AWS_IS_ZEROED(*list) || aws_array_list_is_valid(list));
111 123879 : if (list->alloc && list->data) {
112 97082 : aws_mem_release(list->alloc, list->data);
113 97082 : }
114 634 :
115 123879 : AWS_ZERO_STRUCT(*list);
116 634 : }
117 :
118 : AWS_STATIC_IMPL
119 0 : void aws_array_list_clean_up_secure(struct aws_array_list *AWS_RESTRICT list) {
120 0 : AWS_PRECONDITION(AWS_IS_ZEROED(*list) || aws_array_list_is_valid(list));
121 0 : if (list->alloc && list->data) {
122 0 : aws_secure_zero((void *)list->data, list->current_size);
123 0 : aws_mem_release(list->alloc, list->data);
124 0 : }
125 0 :
126 0 : AWS_ZERO_STRUCT(*list);
127 0 : }
128 :
129 : AWS_STATIC_IMPL
130 22615 : int aws_array_list_push_back(struct aws_array_list *AWS_RESTRICT list, const void *val) {
131 22615 : AWS_PRECONDITION(aws_array_list_is_valid(list));
132 0 : AWS_PRECONDITION(
133 0 : val && AWS_MEM_IS_READABLE(val, list->item_size),
134 0 : "Input pointer [val] must point writable memory of [list->item_size] bytes.");
135 0 :
136 0 : int err_code = aws_array_list_set_at(list, val, aws_array_list_length(list));
137 0 :
138 22615 : if (err_code && aws_last_error() == AWS_ERROR_INVALID_INDEX && !list->alloc) {
139 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
140 0 : return aws_raise_error(AWS_ERROR_LIST_EXCEEDS_MAX_SIZE);
141 0 : }
142 22615 :
143 22615 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
144 0 : return err_code;
145 22615 : }
146 :
147 : AWS_STATIC_IMPL
148 40368 : int aws_array_list_front(const struct aws_array_list *AWS_RESTRICT list, void *val) {
149 40368 : AWS_PRECONDITION(aws_array_list_is_valid(list));
150 40368 : AWS_PRECONDITION(
151 40368 : val && AWS_MEM_IS_WRITABLE(val, list->item_size),
152 40368 : "Input pointer [val] must point writable memory of [list->item_size] bytes.");
153 40368 : if (aws_array_list_length(list) > 0) {
154 9247 : memcpy(val, list->data, list->item_size);
155 9247 : AWS_POSTCONDITION(AWS_BYTES_EQ(val, list->data, list->item_size));
156 9247 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
157 9247 : return AWS_OP_SUCCESS;
158 9247 : }
159 31121 :
160 31121 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
161 31121 : return aws_raise_error(AWS_ERROR_LIST_EMPTY);
162 31121 : }
163 :
164 : AWS_STATIC_IMPL
165 53734 : int aws_array_list_pop_front(struct aws_array_list *AWS_RESTRICT list) {
166 53734 : AWS_PRECONDITION(aws_array_list_is_valid(list));
167 53734 : if (aws_array_list_length(list) > 0) {
168 23381 : aws_array_list_pop_front_n(list, 1);
169 23381 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
170 23381 : return AWS_OP_SUCCESS;
171 23381 : }
172 30353 :
173 30353 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
174 30353 : return aws_raise_error(AWS_ERROR_LIST_EMPTY);
175 30353 : }
176 :
177 : AWS_STATIC_IMPL
178 221518 : void aws_array_list_pop_front_n(struct aws_array_list *AWS_RESTRICT list, size_t n) {
179 221518 : AWS_PRECONDITION(aws_array_list_is_valid(list));
180 221518 : if (n >= aws_array_list_length(list)) {
181 176073 : aws_array_list_clear(list);
182 176073 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
183 176073 : return;
184 176073 : }
185 45445 :
186 45445 : if (n > 0) {
187 35575 : size_t popping_bytes = list->item_size * n;
188 35575 : size_t remaining_items = aws_array_list_length(list) - n;
189 35575 : size_t remaining_bytes = remaining_items * list->item_size;
190 35575 : memmove(list->data, (uint8_t *)list->data + popping_bytes, remaining_bytes);
191 35575 : list->length = remaining_items;
192 0 : #ifdef DEBUG_BUILD
193 0 : memset((uint8_t *)list->data + remaining_bytes, AWS_ARRAY_LIST_DEBUG_FILL, popping_bytes);
194 0 : #endif
195 0 : }
196 45445 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
197 45445 : }
198 :
199 59869 : int aws_array_list_erase(struct aws_array_list *AWS_RESTRICT list, size_t index) {
200 59869 : AWS_PRECONDITION(aws_array_list_is_valid(list));
201 59869 :
202 59869 : const size_t length = aws_array_list_length(list);
203 59869 :
204 59869 : if (index >= length) {
205 43524 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
206 43524 : return aws_raise_error(AWS_ERROR_INVALID_INDEX);
207 43524 : }
208 16345 :
209 16345 : if (index == 0) {
210 5090 : /* Removing front element */
211 5090 : aws_array_list_pop_front(list);
212 11255 : } else if (index == (length - 1)) {
213 366 : /* Removing back element */
214 366 : aws_array_list_pop_back(list);
215 10889 : } else {
216 10889 : /* Removing middle element */
217 10889 : uint8_t *item_ptr = (uint8_t *)list->data + (index * list->item_size);
218 10889 : uint8_t *next_item_ptr = item_ptr + list->item_size;
219 10889 : size_t trailing_items = (length - index) - 1;
220 10889 : size_t trailing_bytes = trailing_items * list->item_size;
221 10889 : memmove(item_ptr, next_item_ptr, trailing_bytes);
222 10889 :
223 10889 : aws_array_list_pop_back(list);
224 10889 : }
225 16345 :
226 16345 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
227 16345 : return AWS_OP_SUCCESS;
228 16345 : }
229 :
230 : AWS_STATIC_IMPL
231 53077 : int aws_array_list_back(const struct aws_array_list *AWS_RESTRICT list, void *val) {
232 53077 : AWS_PRECONDITION(aws_array_list_is_valid(list));
233 53077 : AWS_PRECONDITION(
234 53077 : val && AWS_MEM_IS_WRITABLE(val, list->item_size),
235 53077 : "Input pointer [val] must point writable memory of [list->item_size] bytes.");
236 53077 : if (aws_array_list_length(list) > 0) {
237 21119 : size_t last_item_offset = list->item_size * (aws_array_list_length(list) - 1);
238 21119 :
239 21119 : memcpy(val, (void *)((uint8_t *)list->data + last_item_offset), list->item_size);
240 21119 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
241 21119 : return AWS_OP_SUCCESS;
242 21119 : }
243 31958 :
244 31958 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
245 31958 : return aws_raise_error(AWS_ERROR_LIST_EMPTY);
246 31958 : }
247 :
248 : AWS_STATIC_IMPL
249 59752 : int aws_array_list_pop_back(struct aws_array_list *AWS_RESTRICT list) {
250 59752 : AWS_PRECONDITION(aws_array_list_is_valid(list));
251 59752 : if (aws_array_list_length(list) > 0) {
252 30529 :
253 30529 : AWS_FATAL_PRECONDITION(list->data);
254 30529 :
255 30529 : size_t last_item_offset = list->item_size * (aws_array_list_length(list) - 1);
256 30529 :
257 30529 : memset((void *)((uint8_t *)list->data + last_item_offset), 0, list->item_size);
258 30529 : list->length--;
259 30529 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
260 30529 : return AWS_OP_SUCCESS;
261 29223 : }
262 29223 :
263 29223 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
264 29223 : return aws_raise_error(AWS_ERROR_LIST_EMPTY);
265 29223 : }
266 :
267 : AWS_STATIC_IMPL
268 299492 : void aws_array_list_clear(struct aws_array_list *AWS_RESTRICT list) {
269 299492 : AWS_PRECONDITION(aws_array_list_is_valid(list));
270 299492 : if (list->data) {
271 0 : #ifdef DEBUG_BUILD
272 0 : memset(list->data, AWS_ARRAY_LIST_DEBUG_FILL, list->current_size);
273 0 : #endif
274 0 : list->length = 0;
275 223589 : }
276 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
277 0 : }
278 :
279 : AWS_STATIC_IMPL
280 : void aws_array_list_swap_contents(
281 : struct aws_array_list *AWS_RESTRICT list_a,
282 15280 : struct aws_array_list *AWS_RESTRICT list_b) {
283 15280 : AWS_FATAL_PRECONDITION(list_a->alloc);
284 15280 : AWS_FATAL_PRECONDITION(list_a->alloc == list_b->alloc);
285 15280 : AWS_FATAL_PRECONDITION(list_a->item_size == list_b->item_size);
286 15280 : AWS_FATAL_PRECONDITION(list_a != list_b);
287 15280 : AWS_PRECONDITION(aws_array_list_is_valid(list_a));
288 0 : AWS_PRECONDITION(aws_array_list_is_valid(list_b));
289 0 :
290 0 : struct aws_array_list tmp = *list_a;
291 0 : *list_a = *list_b;
292 0 : *list_b = tmp;
293 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list_a));
294 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list_b));
295 0 : }
296 :
297 : AWS_STATIC_IMPL
298 48661 : size_t aws_array_list_capacity(const struct aws_array_list *AWS_RESTRICT list) {
299 48661 : AWS_FATAL_PRECONDITION(list->item_size);
300 48661 : AWS_PRECONDITION(aws_array_list_is_valid(list));
301 48661 : size_t capacity = list->current_size / list->item_size;
302 48661 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
303 48661 : return capacity;
304 48661 : }
305 :
306 : AWS_STATIC_IMPL
307 1036848 : size_t aws_array_list_length(const struct aws_array_list *AWS_RESTRICT list) {
308 1036848 : /*
309 1036848 : * This assert teaches clang-tidy and friends that list->data cannot be null in a non-empty
310 1036848 : * list.
311 1036848 : */
312 1036848 : AWS_FATAL_PRECONDITION(!list->length || list->data);
313 1004726 : AWS_PRECONDITION(aws_array_list_is_valid(list));
314 49250 : size_t len = list->length;
315 49250 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
316 49250 : return len;
317 49250 : }
318 :
319 : AWS_STATIC_IMPL
320 48457 : int aws_array_list_get_at(const struct aws_array_list *AWS_RESTRICT list, void *val, size_t index) {
321 48457 : AWS_PRECONDITION(aws_array_list_is_valid(list));
322 0 : AWS_PRECONDITION(
323 0 : val && AWS_MEM_IS_WRITABLE(val, list->item_size),
324 0 : "Input pointer [val] must point writable memory of [list->item_size] bytes.");
325 48457 : if (aws_array_list_length(list) > index) {
326 9115 : memcpy(val, (void *)((uint8_t *)list->data + (list->item_size * index)), list->item_size);
327 9115 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
328 9115 : return AWS_OP_SUCCESS;
329 0 : }
330 39342 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
331 0 : return aws_raise_error(AWS_ERROR_INVALID_INDEX);
332 39342 : }
333 :
334 : AWS_STATIC_IMPL
335 91357 : int aws_array_list_get_at_ptr(const struct aws_array_list *AWS_RESTRICT list, void **val, size_t index) {
336 91357 : AWS_PRECONDITION(aws_array_list_is_valid(list));
337 38740 : AWS_PRECONDITION(val != NULL);
338 91357 : if (aws_array_list_length(list) > index) {
339 44464 : *val = (void *)((uint8_t *)list->data + (list->item_size * index));
340 44464 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
341 44464 : return AWS_OP_SUCCESS;
342 0 : }
343 46893 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
344 0 : return aws_raise_error(AWS_ERROR_INVALID_INDEX);
345 46893 : }
346 :
347 : AWS_STATIC_IMPL
348 39866 : int aws_array_list_set_at(struct aws_array_list *AWS_RESTRICT list, const void *val, size_t index) {
349 39866 : AWS_PRECONDITION(aws_array_list_is_valid(list));
350 0 : AWS_PRECONDITION(
351 0 : val && AWS_MEM_IS_READABLE(val, list->item_size),
352 0 : "Input pointer [val] must point readable memory of [list->item_size] bytes.");
353 0 :
354 39866 : if (aws_array_list_ensure_capacity(list, index)) {
355 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
356 0 : return AWS_OP_ERR;
357 0 : }
358 39866 :
359 39866 : AWS_FATAL_PRECONDITION(list->data);
360 39866 :
361 39866 : memcpy((void *)((uint8_t *)list->data + (list->item_size * index)), val, list->item_size);
362 39866 :
363 39866 : /*
364 39866 : * This isn't perfect, but its the best I can come up with for detecting
365 39866 : * length changes.
366 39866 : */
367 39866 : if (index >= aws_array_list_length(list)) {
368 30998 : if (aws_add_size_checked(index, 1, &list->length)) {
369 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
370 0 : return AWS_OP_ERR;
371 0 : }
372 39866 : }
373 0 :
374 0 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
375 39866 : return AWS_OP_SUCCESS;
376 39866 : }
377 :
378 : AWS_STATIC_IMPL
379 57984 : void aws_array_list_sort(struct aws_array_list *AWS_RESTRICT list, aws_array_list_comparator_fn *compare_fn) {
380 57984 : AWS_PRECONDITION(aws_array_list_is_valid(list));
381 57984 : if (list->data) {
382 32017 : qsort(list->data, aws_array_list_length(list), list->item_size, compare_fn);
383 32017 : }
384 57984 : AWS_POSTCONDITION(aws_array_list_is_valid(list));
385 57984 : }
386 :
387 : AWS_EXTERN_C_END
388 :
389 : #endif /* AWS_COMMON_ARRAY_LIST_INL */
|
