botan: Add support for Ed25519 keys
[strongswan.git] / src / libstrongswan / collections / array.h
1 /*
2 * Copyright (C) 2014 Tobias Brunner
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * Copyright (C) 2013 Martin Willi
6 * Copyright (C) 2013 revosec AG
7 *
8 * This program is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2 of the License, or (at your
11 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * for more details.
17 */
18
19 /**
20 * @defgroup array array
21 * @{ @ingroup collections
22 */
23
24 #ifndef ARRAY_H_
25 #define ARRAY_H_
26
27 #include <collections/enumerator.h>
28
29 /**
30 * Variable sized array with fixed size elements.
31 *
32 * An array is a primitive object with associated functions to avoid the
33 * overhead of an object with methods. It is efficient in memory usage, but
34 * less efficient than a linked list in manipulating elements.
35 */
36 typedef struct array_t array_t;
37
38 typedef enum array_idx_t array_idx_t;
39
40 /**
41 * Special array index values for insert/remove.
42 */
43 enum array_idx_t {
44 ARRAY_HEAD = 0,
45 ARRAY_TAIL = -1,
46 };
47
48 /**
49 * Callback function invoked for each array element.
50 *
51 * Data is a pointer to the array element. If this is a pointer based array,
52 * (esize is zero), data is the pointer itself.
53 *
54 * @param data pointer to array data, or the pointer itself
55 * @param idx array index
56 * @param user user data passed with callback
57 */
58 typedef void (*array_callback_t)(void *data, int idx, void *user);
59
60 /**
61 * Create a array instance.
62 *
63 * Elements get tight packed to each other. If any alignment is required, pass
64 * appropriate padding to each element. The reserved space does not affect
65 * array_count(), but just preallocates buffer space.
66 *
67 * @param esize element size for this array, use 0 for a pointer array
68 * @param reserve number of items to allocate space for
69 * @return array instance
70 */
71 array_t *array_create(u_int esize, uint8_t reserve);
72
73 /**
74 * Get the number of elements currently in the array.
75 *
76 * @return number of elements
77 */
78 int array_count(array_t *array);
79
80 /**
81 * Compress an array, remove unused head/tail space.
82 *
83 * @param array array to compress, or NULL
84 */
85 void array_compress(array_t *array);
86
87 /**
88 * Create an enumerator over an array.
89 *
90 * The enumerater enumerates directly over the array element (pass a pointer to
91 * element types), unless the array is pointer based. If zero is passed as
92 * element size during construction, the enumerator enumerates over the
93 * dereferenced pointer values.
94 *
95 * @param array array to create enumerator for, or NULL
96 * @return enumerator, over elements or pointers
97 */
98 enumerator_t* array_create_enumerator(array_t *array);
99
100 /**
101 * Remove an element at enumerator position.
102 *
103 * @warning For **value based** arrays don't use the pointer returned by
104 * enumerate() anymore after calling this function. For performance reasons
105 * that pointer will point to internal data structures that get modified when
106 * this function is called.
107 *
108 * @param array array to remove element in
109 * @param enumerator enumerator position, from array_create_enumerator()
110 */
111 void array_remove_at(array_t *array, enumerator_t *enumerator);
112
113 /**
114 * Insert an element to an array.
115 *
116 * If the array is pointer based (esize = 0), the pointer itself is appended.
117 * Otherwise the element gets copied from the pointer.
118 * The idx must be either within array_count() or one above to append the item.
119 * Passing -1 has the same effect as passing array_count(), i.e. appends the
120 * item. It is always valid to pass idx 0 to prepend the item.
121 *
122 * @param array array to append element to
123 * @param idx index to insert item at
124 * @param data pointer to array element to copy
125 */
126 void array_insert(array_t *array, int idx, void *data);
127
128 /**
129 * Create an pointer based array if it does not exist, insert pointer.
130 *
131 * This is a convenience function for insert a pointer and implicitly
132 * create a pointer based array if array is NULL. Array is set the the newly
133 * created array, if any.
134 *
135 * @param array pointer to array reference, potentially NULL
136 * @param idx index to insert item at
137 * @param ptr pointer to append
138 */
139 void array_insert_create(array_t **array, int idx, void *ptr);
140
141 /**
142 * Create a value based array if it does not exist, insert value.
143 *
144 * This is a convenience function to insert a value and implicitly
145 * create a value based array if array is NULL. Array is set the the newly
146 * created array, if any.
147 *
148 * @param array pointer to array reference, potentially NULL
149 * @param esize element size of this array
150 * @param idx index to insert item at
151 * @param val pointer to value to insert
152 */
153 void array_insert_create_value(array_t **array, u_int esize,
154 int idx, void *val);
155
156 /**
157 * Insert all items from an enumerator to an array.
158 *
159 * @param array array to add items to
160 * @param idx index to insert each item with
161 * @param enumerator enumerator over void*, gets destroyed
162 */
163 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator);
164
165 /**
166 * Get an element from the array.
167 *
168 * If data is given, the element is copied to that position.
169 *
170 * @param array array to get element from, or NULL
171 * @param idx index of the item to get
172 * @param data data to copy element to, or NULL
173 * @return TRUE if idx valid and item returned
174 */
175 bool array_get(array_t *array, int idx, void *data);
176
177 /**
178 * Remove an element from the array.
179 *
180 * If data is given, the element is copied to that position.
181 *
182 * @param array array to remove element from, or NULL
183 * @param idx index of the item to remove
184 * @param data data to copy element to, or NULL
185 * @return TRUE if idx existed and item removed
186 */
187 bool array_remove(array_t *array, int idx, void *data);
188
189 /**
190 * Sort the array.
191 *
192 * The comparison function must return an integer less than, equal to, or
193 * greater than zero if the first argument is considered to be respectively less
194 * than, equal to, or greater than the second. If two elements compare as
195 * equal, their order in the sorted array is undefined.
196 *
197 * The comparison function receives pointers to the array elements (esize != 0)
198 * or the actual pointers (esize = 0). The third argument is the user data
199 * supplied to this function.
200 *
201 * @param array array to sort, or NULL
202 * @param cmp comparison function
203 * @param user user data to pass to comparison function
204 */
205 void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
206 void *user);
207
208 /**
209 * Binary search of a sorted array.
210 *
211 * The array should be sorted in ascending order according to the given
212 * comparison function.
213 *
214 * The comparison function must return an integer less than, equal to, or
215 * greater than zero if the first argument (the key) is considered to be
216 * respectively less than, equal to, or greater than the second.
217 *
218 * If there are multiple elements that match the key it is not specified which
219 * element is returned.
220 *
221 * The comparison function receives the key object and a pointer to an array
222 * element (esize != 0) or an actual pointer (esize = 0).
223 *
224 * @param array array to search, or NULL
225 * @param key key to search for
226 * @param cmp comparison function
227 * @param data data to copy element to, or NULL
228 * @return index of the element if found, -1 if not
229 */
230 int array_bsearch(array_t *array, const void *key,
231 int (*cmp)(const void*,const void*), void *data);
232
233 /**
234 * Invoke a callback for all array members.
235 *
236 * @param array array to traverse, or NULL
237 * @param cb callback function to invoke each element with
238 * @param user user data to pass to callback
239 */
240 void array_invoke(array_t *array, array_callback_t cb, void *user);
241
242 /**
243 * Invoke a method of each element defined with offset.
244 *
245 * @param array array to traverse, or NULL
246 * @param offset offset of element method, use offsetof()
247 */
248 void array_invoke_offset(array_t *array, size_t offset);
249
250 /**
251 * Destroy an array.
252 *
253 * @param array array to destroy, or NULL
254 */
255 void array_destroy(array_t *array);
256
257 /**
258 * Destroy an array, call a function to clean up all elements.
259 *
260 * @param array array to destroy, or NULL
261 * @param cb callback function to free element data
262 * @param user user data to pass to callback
263 */
264 void array_destroy_function(array_t *array, array_callback_t cb, void *user);
265
266 /**
267 * Destroy an array, call element method defined with offset.
268 *
269 * @param array array to destroy, or NULL
270 * @param offset offset of element method, use offsetof()
271 */
272 void array_destroy_offset(array_t *array, size_t offset);
273
274
275 /**
276 * Required on some platforms to initialize thread local value to implement
277 * array_sort().
278 */
279 void arrays_init();
280
281 /**
282 * Destroys the thread local value if required.
283 */
284 void arrays_deinit();
285
286 #endif /** ARRAY_H_ @}*/