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