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 | */ |
25 | AWS_EXTERN_C_BEGIN |
26 | |
27 | AWS_STATIC_IMPL |
28 | int 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 | |
63 | error: |
64 | AWS_POSTCONDITION(AWS_IS_ZEROED(*list)); |
65 | return AWS_OP_ERR; |
66 | } |
67 | |
68 | AWS_STATIC_IMPL |
69 | void 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 | |
91 | AWS_STATIC_IMPL |
92 | bool 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 | |
106 | AWS_STATIC_IMPL |
107 | void 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 | |
118 | AWS_STATIC_IMPL |
119 | void 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 | |
128 | AWS_STATIC_IMPL |
129 | int 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 | |
146 | AWS_STATIC_IMPL |
147 | int 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 | |
163 | AWS_STATIC_IMPL |
164 | int 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 | |
176 | AWS_STATIC_IMPL |
177 | void 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 | |
198 | int 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 | |
229 | AWS_STATIC_IMPL |
230 | int 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 | |
247 | AWS_STATIC_IMPL |
248 | int 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 | |
266 | AWS_STATIC_IMPL |
267 | void 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 | |
278 | AWS_STATIC_IMPL |
279 | void 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 | |
296 | AWS_STATIC_IMPL |
297 | size_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 | |
305 | AWS_STATIC_IMPL |
306 | size_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 | |
318 | AWS_STATIC_IMPL |
319 | int 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 | |
333 | AWS_STATIC_IMPL |
334 | int 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 | |
346 | AWS_STATIC_IMPL |
347 | int 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 | |
377 | AWS_STATIC_IMPL |
378 | void 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 | |
386 | AWS_EXTERN_C_END |
387 | |
388 | #endif /* AWS_COMMON_ARRAY_LIST_INL */ |
389 | |