vector: Update API to be more flexible.
[asterisk/asterisk.git] / include / asterisk / vector.h
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2013, Digium, Inc.
5  *
6  * David M. Lee, II <dlee@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 #ifndef _ASTERISK_VECTOR_H
20 #define _ASTERISK_VECTOR_H
21
22 /*! \file
23  *
24  * \brief Vector container support.
25  *
26  * A vector is a variable length array, with properties that can be useful when
27  * order doesn't matter.
28  *  - Appends are asymptotically constant time.
29  *  - Unordered removes are constant time.
30  *  - Search is linear time
31  *
32  * \author David M. Lee, II <dlee@digium.com>
33  * \since 12
34  */
35
36 /*!
37  * \brief Define a vector structure
38  *
39  * \param name Optional vector struct name.
40  * \param type Vector element type.
41  */
42 #define ast_vector(name, type)                  \
43         struct name {                           \
44                 type *elems;                    \
45                 size_t max;                     \
46                 size_t current;                 \
47         }
48
49 /*!
50  * \brief Initialize a vector
51  *
52  * If \a size is 0, then no space will be allocated until the vector is
53  * appended to.
54  *
55  * \param vec Vector to initialize.
56  * \param size Initial size of the vector.
57  *
58  * \return 0 on success.
59  * \return Non-zero on failure.
60  */
61 #define ast_vector_init(vec, size) ({                                   \
62         size_t __size = (size);                                         \
63         size_t alloc_size = __size * sizeof(*((vec)->elems));           \
64         (vec)->elems = alloc_size ? ast_malloc(alloc_size) : NULL;      \
65         (vec)->current = 0;                                             \
66         if ((vec)->elems) {                                             \
67                 (vec)->max = __size;                                    \
68         } else {                                                        \
69                 (vec)->max = 0;                                         \
70         }                                                               \
71         (alloc_size == 0 || (vec)->elems != NULL) ? 0 : -1;             \
72 })
73
74 /*!
75  * \brief Deallocates this vector.
76  *
77  * If any code to free the elements of this vector need to be run, that should
78  * be done prior to this call.
79  *
80  * \param vec Vector to deallocate.
81  */
82 #define ast_vector_free(vec) do {               \
83         ast_free((vec)->elems);                 \
84         (vec)->elems = NULL;                    \
85         (vec)->max = 0;                         \
86         (vec)->current = 0;                     \
87 } while (0)
88
89 /*!
90  * \brief Append an element to a vector, growing the vector if needed.
91  *
92  * \param vec Vector to append to.
93  * \param elem Element to append.
94  *
95  * \return 0 on success.
96  * \return Non-zero on failure.
97  */
98 #define ast_vector_append(vec, elem) ({                                         \
99         int res = 0;                                                            \
100         do {                                                                    \
101                 if ((vec)->current + 1 > (vec)->max) {                          \
102                         size_t new_max = (vec)->max ? 2 * (vec)->max : 1;       \
103                         typeof((vec)->elems) new_elems = ast_realloc(           \
104                                 (vec)->elems, new_max * sizeof(*new_elems));    \
105                         if (new_elems) {                                        \
106                                 (vec)->elems = new_elems;                       \
107                                 (vec)->max = new_max;                           \
108                         } else {                                                \
109                                 res = -1;                                       \
110                                 break;                                          \
111                         }                                                       \
112                 }                                                               \
113                 (vec)->elems[(vec)->current++] = (elem);                        \
114         } while (0);                                                            \
115         res;                                                                    \
116 })
117
118 /*!
119  * \brief Remove an element from a vector by index.
120  *
121  * Note that elements in the vector may be reordered, so that the remove can
122  * happen in constant time.
123  *
124  * \param vec Vector to remove from.
125  * \param idx Index of the element to remove.
126  * \return The element that was removed.
127  */
128 #define ast_vector_remove_unordered(vec, idx) ({                \
129         typeof((vec)->elems[0]) res;                            \
130         size_t __idx = (idx);                                   \
131         ast_assert(__idx < (vec)->current);                     \
132         res = (vec)->elems[__idx];                              \
133         (vec)->elems[__idx] = (vec)->elems[--(vec)->current];   \
134         res;                                                    \
135 })
136
137
138 /*!
139  * \brief Remove an element from a vector that matches the given comparison
140  *
141  * \param vec Vector to remove from.
142  * \param value Value to pass into comparator.
143  * \param cmp Comparator function/macros (called as \c cmp(elem, value))
144  * \param cleanup How to cleanup a removed element macro/function.
145  *
146  * \return 0 if element was removed.
147  * \return Non-zero if element was not in the vector.
148  */
149 #define ast_vector_remove_cmp_unordered(vec, value, cmp, cleanup) ({    \
150         int res = -1;                                                   \
151         size_t idx;                                                     \
152         typeof(value) __value = (value);                                \
153         for (idx = 0; idx < (vec)->current; ++idx) {                    \
154                 if (cmp((vec)->elems[idx], __value)) {                  \
155                         cleanup((vec)->elems[idx]);                     \
156                         ast_vector_remove_unordered((vec), idx);        \
157                         res = 0;                                        \
158                         break;                                          \
159                 }                                                       \
160         }                                                               \
161         res;                                                            \
162 })
163
164 /*!
165  * \brief Default comparator for ast_vector_remove_elem_unordered()
166  *
167  * \param elem Element to compare against
168  * \param value Value to compare with the vector element.
169  *
170  * \return 0 if element does not match.
171  * \return Non-zero if element matches.
172  */
173 #define AST_VECTOR_ELEM_DEFAULT_CMP(elem, value) ((elem) == (value))
174
175 /*!
176  * \brief Vector element cleanup that does nothing.
177  *
178  * \param elem Element to cleanup
179  *
180  * \return Nothing
181  */
182 #define AST_VECTOR_ELEM_CLEANUP_NOOP(elem)
183
184 /*!
185  * \brief Remove an element from a vector.
186  *
187  * \param vec Vector to remove from.
188  * \param elem Element to remove
189  * \param cleanup How to cleanup a removed element macro/function.
190  *
191  * \return 0 if element was removed.
192  * \return Non-zero if element was not in the vector.
193  */
194 #define ast_vector_remove_elem_unordered(vec, elem, cleanup) ({ \
195         ast_vector_remove_cmp_unordered((vec), (elem),          \
196                 AST_VECTOR_ELEM_DEFAULT_CMP, cleanup);          \
197 })
198
199 /*!
200  * \brief Get the number of elements in a vector.
201  *
202  * \param vec Vector to query.
203  * \return Number of elements in the vector.
204  */
205 #define ast_vector_size(vec) (vec)->current
206
207 /*!
208  * \brief Get an address of element in a vector.
209  *
210  * \param vec Vector to query.
211  * \param idx Index of the element to get address of.
212  */
213 #define ast_vector_get_addr(vec, idx) ({        \
214         size_t __idx = (idx);                   \
215         ast_assert(__idx < (vec)->current);     \
216         &(vec)->elems[__idx];                   \
217 })
218
219 /*!
220  * \brief Get an element from a vector.
221  *
222  * \param vec Vector to query.
223  * \param idx Index of the element to get.
224  */
225 #define ast_vector_get(vec, idx) ({             \
226         size_t __idx = (idx);                   \
227         ast_assert(__idx < (vec)->current);     \
228         (vec)->elems[__idx];                    \
229 })
230
231 #endif /* _ASTERISK_VECTOR_H */