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
25struct 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 */
41typedef int(aws_array_list_comparator_fn)(const void *a, const void *b);
42
43AWS_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 */
51AWS_STATIC_IMPL
52int 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 */
63AWS_STATIC_IMPL
64void 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 */
73AWS_STATIC_IMPL
74bool 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 */
79AWS_STATIC_IMPL
80void 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 */
85AWS_STATIC_IMPL
86int 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 */
91AWS_STATIC_IMPL
92int 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 */
99AWS_STATIC_IMPL
100int 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 */
108AWS_STATIC_IMPL
109void 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 */
117AWS_STATIC_IMPL
118int 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 */
123AWS_STATIC_IMPL
124int 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 */
129AWS_STATIC_IMPL
130int 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 */
135AWS_STATIC_IMPL
136void 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 */
141AWS_COMMON_API
142int 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 */
148AWS_COMMON_API
149int 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 */
154AWS_STATIC_IMPL
155void 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 */
163AWS_STATIC_IMPL
164size_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 */
169AWS_STATIC_IMPL
170size_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 */
175AWS_STATIC_IMPL
176int 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 */
182AWS_STATIC_IMPL
183int 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 */
190AWS_COMMON_API
191int 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 */
198AWS_STATIC_IMPL
199int 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 */
204AWS_COMMON_API
205void 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 */
210AWS_STATIC_IMPL
211void 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
217AWS_EXTERN_C_END
218
219#endif /* AWS_COMMON_ARRAY_LIST_H */
220