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