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