1/*
2 * Copyright 2010-2018 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 <aws/common/array_list.h>
17#include <aws/common/private/array_list.h>
18
19#include <stdlib.h> /* qsort */
20
21int aws_array_list_calc_necessary_size(struct aws_array_list *AWS_RESTRICT list, size_t index, size_t *necessary_size) {
22 AWS_PRECONDITION(aws_array_list_is_valid(list));
23 size_t index_inc;
24 if (aws_add_size_checked(index, 1, &index_inc)) {
25 AWS_POSTCONDITION(aws_array_list_is_valid(list));
26 return AWS_OP_ERR;
27 }
28
29 if (aws_mul_size_checked(index_inc, list->item_size, necessary_size)) {
30 AWS_POSTCONDITION(aws_array_list_is_valid(list));
31 return AWS_OP_ERR;
32 }
33 AWS_POSTCONDITION(aws_array_list_is_valid(list));
34 return AWS_OP_SUCCESS;
35}
36
37int aws_array_list_shrink_to_fit(struct aws_array_list *AWS_RESTRICT list) {
38 AWS_PRECONDITION(aws_array_list_is_valid(list));
39 if (list->alloc) {
40 size_t ideal_size;
41 if (aws_mul_size_checked(list->length, list->item_size, &ideal_size)) {
42 AWS_POSTCONDITION(aws_array_list_is_valid(list));
43 return AWS_OP_ERR;
44 }
45
46 if (ideal_size < list->current_size) {
47 void *raw_data = NULL;
48
49 if (ideal_size > 0) {
50 raw_data = aws_mem_acquire(list->alloc, ideal_size);
51 if (!raw_data) {
52 AWS_POSTCONDITION(aws_array_list_is_valid(list));
53 return AWS_OP_ERR;
54 }
55
56 memcpy(raw_data, list->data, ideal_size);
57 aws_mem_release(list->alloc, list->data);
58 }
59 list->data = raw_data;
60 list->current_size = ideal_size;
61 }
62 AWS_POSTCONDITION(aws_array_list_is_valid(list));
63 return AWS_OP_SUCCESS;
64 }
65
66 AWS_POSTCONDITION(aws_array_list_is_valid(list));
67 return aws_raise_error(AWS_ERROR_LIST_STATIC_MODE_CANT_SHRINK);
68}
69
70int aws_array_list_copy(const struct aws_array_list *AWS_RESTRICT from, struct aws_array_list *AWS_RESTRICT to) {
71 AWS_FATAL_PRECONDITION(from->item_size == to->item_size);
72 AWS_FATAL_PRECONDITION(from->data);
73 AWS_PRECONDITION(aws_array_list_is_valid(from));
74 AWS_PRECONDITION(aws_array_list_is_valid(to));
75
76 size_t copy_size;
77 if (aws_mul_size_checked(from->length, from->item_size, &copy_size)) {
78 AWS_POSTCONDITION(aws_array_list_is_valid(from));
79 AWS_POSTCONDITION(aws_array_list_is_valid(to));
80 return AWS_OP_ERR;
81 }
82
83 if (to->current_size >= copy_size) {
84 if (copy_size > 0) {
85 memcpy(to->data, from->data, copy_size);
86 }
87 to->length = from->length;
88 AWS_POSTCONDITION(aws_array_list_is_valid(from));
89 AWS_POSTCONDITION(aws_array_list_is_valid(to));
90 return AWS_OP_SUCCESS;
91 }
92 /* if to is in dynamic mode, we can just reallocate it and copy */
93 if (to->alloc != NULL) {
94 void *tmp = aws_mem_acquire(to->alloc, copy_size);
95
96 if (!tmp) {
97 AWS_POSTCONDITION(aws_array_list_is_valid(from));
98 AWS_POSTCONDITION(aws_array_list_is_valid(to));
99 return AWS_OP_ERR;
100 }
101
102 memcpy(tmp, from->data, copy_size);
103 if (to->data) {
104 aws_mem_release(to->alloc, to->data);
105 }
106
107 to->data = tmp;
108 to->length = from->length;
109 to->current_size = copy_size;
110 AWS_POSTCONDITION(aws_array_list_is_valid(from));
111 AWS_POSTCONDITION(aws_array_list_is_valid(to));
112 return AWS_OP_SUCCESS;
113 }
114
115 return aws_raise_error(AWS_ERROR_DEST_COPY_TOO_SMALL);
116}
117
118int aws_array_list_ensure_capacity(struct aws_array_list *AWS_RESTRICT list, size_t index) {
119 AWS_PRECONDITION(aws_array_list_is_valid(list));
120 size_t necessary_size;
121 if (aws_array_list_calc_necessary_size(list, index, &necessary_size)) {
122 AWS_POSTCONDITION(aws_array_list_is_valid(list));
123 return AWS_OP_ERR;
124 }
125
126 if (list->current_size < necessary_size) {
127 if (!list->alloc) {
128 AWS_POSTCONDITION(aws_array_list_is_valid(list));
129 return aws_raise_error(AWS_ERROR_INVALID_INDEX);
130 }
131
132 /* this will double capacity if the index isn't bigger than what the
133 * next allocation would be, but allocates the exact requested size if
134 * it is. This is largely because we don't have a good way to predict
135 * the usage pattern to make a smart decision about it. However, if the
136 * user
137 * is doing this in an iterative fashion, necessary_size will never be
138 * used.*/
139 size_t next_allocation_size = list->current_size << 1;
140 size_t new_size = next_allocation_size > necessary_size ? next_allocation_size : necessary_size;
141
142 if (new_size < list->current_size) {
143 /* this means new_size overflowed. The only way this happens is on a
144 * 32-bit system where size_t is 32 bits, in which case we're out of
145 * addressable memory anyways, or we're on a 64 bit system and we're
146 * most certainly out of addressable memory. But since we're simply
147 * going to fail fast and say, sorry can't do it, we'll just tell
148 * the user they can't grow the list anymore. */
149 AWS_POSTCONDITION(aws_array_list_is_valid(list));
150 return aws_raise_error(AWS_ERROR_LIST_EXCEEDS_MAX_SIZE);
151 }
152
153 void *temp = aws_mem_acquire(list->alloc, new_size);
154
155 if (!temp) {
156 AWS_POSTCONDITION(aws_array_list_is_valid(list));
157 return AWS_OP_ERR;
158 }
159
160 if (list->data) {
161 memcpy(temp, list->data, list->current_size);
162
163#ifdef DEBUG_BUILD
164 memset(
165 (void *)((uint8_t *)temp + list->current_size),
166 AWS_ARRAY_LIST_DEBUG_FILL,
167 new_size - list->current_size);
168#endif
169 aws_mem_release(list->alloc, list->data);
170 }
171 list->data = temp;
172 list->current_size = new_size;
173 }
174
175 AWS_POSTCONDITION(aws_array_list_is_valid(list));
176 return AWS_OP_SUCCESS;
177}
178
179static void aws_array_list_mem_swap(void *AWS_RESTRICT item1, void *AWS_RESTRICT item2, size_t item_size) {
180 enum { SLICE = 128 };
181
182 AWS_FATAL_PRECONDITION(item1);
183 AWS_FATAL_PRECONDITION(item2);
184
185 /* copy SLICE sized bytes at a time */
186 size_t slice_count = item_size / SLICE;
187 uint8_t temp[SLICE];
188 for (size_t i = 0; i < slice_count; i++) {
189 memcpy((void *)temp, (void *)item1, SLICE);
190 memcpy((void *)item1, (void *)item2, SLICE);
191 memcpy((void *)item2, (void *)temp, SLICE);
192 item1 = (uint8_t *)item1 + SLICE;
193 item2 = (uint8_t *)item2 + SLICE;
194 }
195
196 size_t remainder = item_size & (SLICE - 1); /* item_size % SLICE */
197 memcpy((void *)temp, (void *)item1, remainder);
198 memcpy((void *)item1, (void *)item2, remainder);
199 memcpy((void *)item2, (void *)temp, remainder);
200}
201
202void aws_array_list_swap(struct aws_array_list *AWS_RESTRICT list, size_t a, size_t b) {
203 AWS_FATAL_PRECONDITION(a < list->length);
204 AWS_FATAL_PRECONDITION(b < list->length);
205 AWS_PRECONDITION(aws_array_list_is_valid(list));
206
207 if (a == b) {
208 AWS_POSTCONDITION(aws_array_list_is_valid(list));
209 return;
210 }
211
212 void *item1 = NULL, *item2 = NULL;
213 aws_array_list_get_at_ptr(list, &item1, a);
214 aws_array_list_get_at_ptr(list, &item2, b);
215 aws_array_list_mem_swap(item1, item2, list->item_size);
216 AWS_POSTCONDITION(aws_array_list_is_valid(list));
217}
218