1 | #ifndef AWS_COMMON_ARRAY_LIST_H |
2 | #define AWS_COMMON_ARRAY_LIST_H |
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 | #include <aws/common/common.h> |
19 | #include <aws/common/math.h> |
20 | |
21 | #include <stdlib.h> |
22 | |
23 | #define AWS_ARRAY_LIST_DEBUG_FILL 0xDD |
24 | |
25 | struct aws_array_list { |
26 | struct aws_allocator *alloc; |
27 | size_t current_size; |
28 | size_t length; |
29 | size_t item_size; |
30 | void *data; |
31 | }; |
32 | |
33 | /** |
34 | * Prototype for a comparator function for sorting elements. |
35 | * |
36 | * a and b should be cast to pointers to the element type held in the list |
37 | * before being dereferenced. The function should compare the elements and |
38 | * return a positive number if a > b, zero if a = b, and a negative number |
39 | * if a < b. |
40 | */ |
41 | typedef int(aws_array_list_comparator_fn)(const void *a, const void *b); |
42 | |
43 | AWS_EXTERN_C_BEGIN |
44 | |
45 | /** |
46 | * Initializes an array list with an array of size initial_item_allocation * item_size. In this mode, the array size |
47 | * will grow by a factor of 2 upon insertion if space is not available. initial_item_allocation is the number of |
48 | * elements you want space allocated for. item_size is the size of each element in bytes. Mixing items types is not |
49 | * supported by this API. |
50 | */ |
51 | AWS_STATIC_IMPL |
52 | int aws_array_list_init_dynamic( |
53 | struct aws_array_list *AWS_RESTRICT list, |
54 | struct aws_allocator *alloc, |
55 | size_t initial_item_allocation, |
56 | size_t item_size); |
57 | |
58 | /** |
59 | * Initializes an array list with a preallocated array of void *. item_count is the number of elements in the array, |
60 | * and item_size is the size in bytes of each element. Mixing items types is not supported |
61 | * by this API. Once this list is full, new items will be rejected. |
62 | */ |
63 | AWS_STATIC_IMPL |
64 | void aws_array_list_init_static( |
65 | struct aws_array_list *AWS_RESTRICT list, |
66 | void *raw_array, |
67 | size_t item_count, |
68 | size_t item_size); |
69 | |
70 | /** |
71 | * Set of properties of a valid aws_array_list. |
72 | */ |
73 | AWS_STATIC_IMPL |
74 | bool aws_array_list_is_valid(const struct aws_array_list *AWS_RESTRICT list); |
75 | |
76 | /** |
77 | * Deallocates any memory that was allocated for this list, and resets list for reuse or deletion. |
78 | */ |
79 | AWS_STATIC_IMPL |
80 | void aws_array_list_clean_up(struct aws_array_list *AWS_RESTRICT list); |
81 | |
82 | /** |
83 | * Pushes the memory pointed to by val onto the end of internal list |
84 | */ |
85 | AWS_STATIC_IMPL |
86 | int aws_array_list_push_back(struct aws_array_list *AWS_RESTRICT list, const void *val); |
87 | |
88 | /** |
89 | * Copies the element at the front of the list if it exists. If list is empty, AWS_ERROR_LIST_EMPTY will be raised |
90 | */ |
91 | AWS_STATIC_IMPL |
92 | int aws_array_list_front(const struct aws_array_list *AWS_RESTRICT list, void *val); |
93 | |
94 | /** |
95 | * Deletes the element at the front of the list if it exists. If list is empty, AWS_ERROR_LIST_EMPTY will be raised. |
96 | * This call results in shifting all of the elements at the end of the array to the front. Avoid this call unless that |
97 | * is intended behavior. |
98 | */ |
99 | AWS_STATIC_IMPL |
100 | int aws_array_list_pop_front(struct aws_array_list *AWS_RESTRICT list); |
101 | |
102 | /** |
103 | * Delete N elements from the front of the list. |
104 | * Remaining elements are shifted to the front of the list. |
105 | * If the list has less than N elements, the list is cleared. |
106 | * This call is more efficient than calling aws_array_list_pop_front() N times. |
107 | */ |
108 | AWS_STATIC_IMPL |
109 | void aws_array_list_pop_front_n(struct aws_array_list *AWS_RESTRICT list, size_t n); |
110 | |
111 | /** |
112 | * Deletes the element this index in the list if it exists. |
113 | * If element does not exist, AWS_ERROR_INVALID_INDEX will be raised. |
114 | * This call results in shifting all remaining elements towards the front. |
115 | * Avoid this call unless that is intended behavior. |
116 | */ |
117 | AWS_STATIC_IMPL |
118 | int aws_array_list_erase(struct aws_array_list *AWS_RESTRICT list, size_t index); |
119 | |
120 | /** |
121 | * Copies the element at the end of the list if it exists. If list is empty, AWS_ERROR_LIST_EMPTY will be raised. |
122 | */ |
123 | AWS_STATIC_IMPL |
124 | int aws_array_list_back(const struct aws_array_list *AWS_RESTRICT list, void *val); |
125 | |
126 | /** |
127 | * Deletes the element at the end of the list if it exists. If list is empty, AWS_ERROR_LIST_EMPTY will be raised. |
128 | */ |
129 | AWS_STATIC_IMPL |
130 | int aws_array_list_pop_back(struct aws_array_list *AWS_RESTRICT list); |
131 | |
132 | /** |
133 | * Clears all elements in the array and resets length to zero. Size does not change in this operation. |
134 | */ |
135 | AWS_STATIC_IMPL |
136 | void aws_array_list_clear(struct aws_array_list *AWS_RESTRICT list); |
137 | |
138 | /** |
139 | * If in dynamic mode, shrinks the allocated array size to the minimum amount necessary to store its elements. |
140 | */ |
141 | AWS_COMMON_API |
142 | int aws_array_list_shrink_to_fit(struct aws_array_list *AWS_RESTRICT list); |
143 | |
144 | /** |
145 | * Copies the elements from from to to. If to is in static mode, it must at least be the same length as from. Any data |
146 | * in to will be overwritten in this copy. |
147 | */ |
148 | AWS_COMMON_API |
149 | int aws_array_list_copy(const struct aws_array_list *AWS_RESTRICT from, struct aws_array_list *AWS_RESTRICT to); |
150 | |
151 | /** |
152 | * Swap contents between two dynamic lists. Both lists must use the same allocator. |
153 | */ |
154 | AWS_STATIC_IMPL |
155 | void aws_array_list_swap_contents( |
156 | struct aws_array_list *AWS_RESTRICT list_a, |
157 | struct aws_array_list *AWS_RESTRICT list_b); |
158 | |
159 | /** |
160 | * Returns the number of elements that can fit in the internal array. If list is initialized in dynamic mode, |
161 | * the capacity changes over time. |
162 | */ |
163 | AWS_STATIC_IMPL |
164 | size_t aws_array_list_capacity(const struct aws_array_list *AWS_RESTRICT list); |
165 | |
166 | /** |
167 | * Returns the number of elements in the internal array. |
168 | */ |
169 | AWS_STATIC_IMPL |
170 | size_t aws_array_list_length(const struct aws_array_list *AWS_RESTRICT list); |
171 | |
172 | /** |
173 | * Copies the memory at index to val. If element does not exist, AWS_ERROR_INVALID_INDEX will be raised. |
174 | */ |
175 | AWS_STATIC_IMPL |
176 | int aws_array_list_get_at(const struct aws_array_list *AWS_RESTRICT list, void *val, size_t index); |
177 | |
178 | /** |
179 | * Copies the memory address of the element at index to *val. If element does not exist, AWS_ERROR_INVALID_INDEX will be |
180 | * raised. |
181 | */ |
182 | AWS_STATIC_IMPL |
183 | int aws_array_list_get_at_ptr(const struct aws_array_list *AWS_RESTRICT list, void **val, size_t index); |
184 | |
185 | /** |
186 | * Ensures that the array list has enough capacity to store a value at the specified index. If there is not already |
187 | * enough capacity, and the list is in dynamic mode, this function will attempt to allocate more memory, expanding the |
188 | * list. In static mode, if 'index' is beyond the maximum index, AWS_ERROR_INVALID_INDEX will be raised. |
189 | */ |
190 | AWS_COMMON_API |
191 | int aws_array_list_ensure_capacity(struct aws_array_list *AWS_RESTRICT list, size_t index); |
192 | |
193 | /** |
194 | * Copies the the memory pointed to by val into the array at index. If in dynamic mode, the size will grow by a factor |
195 | * of two when the array is full. In static mode, AWS_ERROR_INVALID_INDEX will be raised if the index is past the bounds |
196 | * of the array. |
197 | */ |
198 | AWS_STATIC_IMPL |
199 | int aws_array_list_set_at(struct aws_array_list *AWS_RESTRICT list, const void *val, size_t index); |
200 | |
201 | /** |
202 | * Swap elements at the specified indices, which must be within the bounds of the array. |
203 | */ |
204 | AWS_COMMON_API |
205 | void aws_array_list_swap(struct aws_array_list *AWS_RESTRICT list, size_t a, size_t b); |
206 | |
207 | /** |
208 | * Sort elements in the list in-place according to the comparator function. |
209 | */ |
210 | AWS_STATIC_IMPL |
211 | void aws_array_list_sort(struct aws_array_list *AWS_RESTRICT list, aws_array_list_comparator_fn *compare_fn); |
212 | |
213 | #ifndef AWS_NO_STATIC_IMPL |
214 | # include <aws/common/array_list.inl> |
215 | #endif /* AWS_NO_STATIC_IMPL */ |
216 | |
217 | AWS_EXTERN_C_END |
218 | |
219 | #endif /* AWS_COMMON_ARRAY_LIST_H */ |
220 | |