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 | |
21 | int 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 | |
37 | int 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 | |
70 | int 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, ©_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 | |
118 | int 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 | |
179 | static 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 | |
202 | void 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 | |