Merge branch 'unit-tests'
[strongswan.git] / src / libstrongswan / collections / linked_list.h
1 /*
2 * Copyright (C) 2007-2011 Tobias Brunner
3 * Copyright (C) 2005-2008 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * Hochschule fuer Technik Rapperswil
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 /**
19 * @defgroup linked_list linked_list
20 * @{ @ingroup collections
21 */
22
23 #ifndef LINKED_LIST_H_
24 #define LINKED_LIST_H_
25
26 typedef struct linked_list_t linked_list_t;
27
28 #include <collections/enumerator.h>
29
30 /**
31 * Method to match elements in a linked list (used in find_* functions)
32 *
33 * @param item current list item
34 * @param ... user supplied data (only pointers, at most 5)
35 * @return
36 * - TRUE, if the item matched
37 * - FALSE, otherwise
38 */
39 typedef bool (*linked_list_match_t)(void *item, ...);
40
41 /**
42 * Method to be invoked on elements in a linked list (used in invoke_* functions)
43 *
44 * @param item current list item
45 * @param ... user supplied data (only pointers, at most 5)
46 */
47 typedef void (*linked_list_invoke_t)(void *item, ...);
48
49 /**
50 * Class implementing a double linked list.
51 *
52 * General purpose linked list. This list is not synchronized.
53 */
54 struct linked_list_t {
55
56 /**
57 * Gets the count of items in the list.
58 *
59 * @return number of items in list
60 */
61 int (*get_count) (linked_list_t *this);
62
63 /**
64 * Create an enumerator over the list.
65 *
66 * @note The enumerator's position is invalid before the first call
67 * to enumerate().
68 *
69 * @return enumerator over list items
70 */
71 enumerator_t* (*create_enumerator)(linked_list_t *this);
72
73 /**
74 * Resets the enumerator's current position to the beginning of the list.
75 *
76 * @param enumerator enumerator to reset
77 */
78 void (*reset_enumerator)(linked_list_t *this, enumerator_t *enumerator);
79
80 /**
81 * Checks if there are more elements following after the enumerator's
82 * current position.
83 *
84 * @param enumerator enumerator to check
85 * @return TRUE if more elements follow after the current item
86 */
87 bool (*has_more)(linked_list_t *this, enumerator_t *enumerator);
88
89 /**
90 * Inserts a new item at the beginning of the list.
91 *
92 * @param item item value to insert in list
93 */
94 void (*insert_first) (linked_list_t *this, void *item);
95
96 /**
97 * Removes the first item in the list and returns its value.
98 *
99 * @param item returned value of first item, or NULL
100 * @return SUCCESS, or NOT_FOUND if list is empty
101 */
102 status_t (*remove_first) (linked_list_t *this, void **item);
103
104 /**
105 * Inserts a new item before the item the enumerator currently points to.
106 *
107 * If this method is called before starting the enumeration the item is
108 * inserted first. If it is called after all items have been enumerated
109 * the item is inserted last. This is helpful when inserting items into
110 * a sorted list.
111 *
112 * @note The position of the enumerator is not changed.
113 *
114 * @param enumerator enumerator with position
115 * @param item item value to insert in list
116 */
117 void (*insert_before)(linked_list_t *this, enumerator_t *enumerator,
118 void *item);
119
120 /**
121 * Replaces the item the enumerator currently points to with the given item.
122 *
123 * @param enumerator enumerator with position
124 * @param item item value to replace current item with
125 * @return current item or NULL if the enumerator is at an
126 * invalid position
127 */
128 void *(*replace)(linked_list_t *this, enumerator_t *enumerator, void *item);
129
130 /**
131 * Remove an item from the list where the enumerator points to.
132 *
133 * @param enumerator enumerator with position
134 */
135 void (*remove_at)(linked_list_t *this, enumerator_t *enumerator);
136
137 /**
138 * Remove items from the list matching the given item.
139 *
140 * If a compare function is given, it is called for each item, with the
141 * first parameter being the current list item and the second parameter
142 * being the supplied item. Return TRUE from the compare function to remove
143 * the item, return FALSE to keep it in the list.
144 *
145 * If compare is NULL, comparison is done by pointers.
146 *
147 * @param item item to remove/pass to comparator
148 * @param compare compare function, or NULL
149 * @return number of removed items
150 */
151 int (*remove)(linked_list_t *this, void *item, bool (*compare)(void*,void*));
152
153 /**
154 * Returns the value of the first list item without removing it.
155 *
156 * @param item returned value of first item
157 * @return SUCCESS, NOT_FOUND if list is empty
158 */
159 status_t (*get_first) (linked_list_t *this, void **item);
160
161 /**
162 * Inserts a new item at the end of the list.
163 *
164 * @param item value to insert into list
165 */
166 void (*insert_last) (linked_list_t *this, void *item);
167
168 /**
169 * Removes the last item in the list and returns its value.
170 *
171 * @param item returned value of last item, or NULL
172 * @return SUCCESS, NOT_FOUND if list is empty
173 */
174 status_t (*remove_last) (linked_list_t *this, void **item);
175
176 /**
177 * Returns the value of the last list item without removing it.
178 *
179 * @param item returned value of last item
180 * @return SUCCESS, NOT_FOUND if list is empty
181 */
182 status_t (*get_last) (linked_list_t *this, void **item);
183
184 /**
185 * Find the first matching element in the list.
186 *
187 * The first object passed to the match function is the current list item,
188 * followed by the user supplied data.
189 * If the supplied function returns TRUE this function returns SUCCESS, and
190 * the current object is returned in the third parameter, otherwise,
191 * the next item is checked.
192 *
193 * If match is NULL, *item and the current object are compared.
194 *
195 * @warning Only use pointers as user supplied data.
196 *
197 * @param match comparison function to call on each object, or NULL
198 * @param item the list item, if found
199 * @param ... user data to supply to match function (limited to 5 arguments)
200 * @return SUCCESS if found, NOT_FOUND otherwise
201 */
202 status_t (*find_first) (linked_list_t *this, linked_list_match_t match,
203 void **item, ...);
204
205 /**
206 * Find the last matching element in the list.
207 *
208 * The first object passed to the match function is the current list item,
209 * followed by the user supplied data.
210 * If the supplied function returns TRUE this function returns SUCCESS, and
211 * the current object is returned in the third parameter, otherwise,
212 * the next item is checked.
213 *
214 * If match is NULL, *item and the current object are compared.
215 *
216 * @warning Only use pointers as user supplied data.
217 *
218 * @param match comparison function to call on each object, or NULL
219 * @param item the list item, if found
220 * @param ... user data to supply to match function (limited to 5 arguments)
221 * @return SUCCESS if found, NOT_FOUND otherwise
222 */
223 status_t (*find_last) (linked_list_t *this, linked_list_match_t match,
224 void **item, ...);
225
226 /**
227 * Invoke a method on all of the contained objects.
228 *
229 * If a linked list contains objects with function pointers,
230 * invoke() can call a method on each of the objects. The
231 * method is specified by an offset of the function pointer,
232 * which can be evalutated at compile time using the offsetof
233 * macro, e.g.: list->invoke(list, offsetof(object_t, method));
234 *
235 * @warning Only use pointers as user supplied data.
236 *
237 * @param offset offset of the method to invoke on objects
238 * @param ... user data to supply to called function (limited to 5 arguments)
239 */
240 void (*invoke_offset) (linked_list_t *this, size_t offset, ...);
241
242 /**
243 * Invoke a function on all of the contained objects.
244 *
245 * @warning Only use pointers as user supplied data.
246 *
247 * @param function offset of the method to invoke on objects
248 * @param ... user data to supply to called function (limited to 5 arguments)
249 */
250 void (*invoke_function) (linked_list_t *this, linked_list_invoke_t function, ...);
251
252 /**
253 * Clones a list and its objects using the objects' clone method.
254 *
255 * @param offset offset ot the objects clone function
256 * @return cloned list
257 */
258 linked_list_t *(*clone_offset) (linked_list_t *this, size_t offset);
259
260 /**
261 * Clones a list and its objects using a given function.
262 *
263 * @param function function that clones an object
264 * @return cloned list
265 */
266 linked_list_t *(*clone_function) (linked_list_t *this, void*(*)(void*));
267
268 /**
269 * Destroys a linked_list object.
270 */
271 void (*destroy) (linked_list_t *this);
272
273 /**
274 * Destroys a list and its objects using the destructor.
275 *
276 * If a linked list and the contained objects should be destroyed, use
277 * destroy_offset. The supplied offset specifies the destructor to
278 * call on each object. The offset may be calculated using the offsetof
279 * macro, e.g.: list->destroy_offset(list, offsetof(object_t, destroy));
280 *
281 * @param offset offset of the objects destructor
282 */
283 void (*destroy_offset) (linked_list_t *this, size_t offset);
284
285 /**
286 * Destroys a list and its contents using a a cleanup function.
287 *
288 * If a linked list and its contents should get destroyed using a specific
289 * cleanup function, use destroy_function. This is useful when the
290 * list contains malloc()-ed blocks which should get freed,
291 * e.g.: list->destroy_function(list, free);
292 *
293 * @param function function to call on each object
294 */
295 void (*destroy_function) (linked_list_t *this, void (*)(void*));
296 };
297
298 /**
299 * Creates an empty linked list object.
300 *
301 * @return linked_list_t object.
302 */
303 linked_list_t *linked_list_create(void);
304
305 /**
306 * Creates a linked list from an enumerator.
307 *
308 * @param enumerator enumerator over void*, gets destroyed
309 * @return linked_list_t object, containing enumerated values
310 */
311 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator);
312
313 /**
314 * Creates a linked list from a NULL terminated vararg list of items.
315 *
316 * @param first first item
317 * @param ... subsequent items, terminated by NULL
318 * @return linked_list_t object, containing passed items
319 */
320 linked_list_t *linked_list_create_with_items(void *first, ...);
321
322 #endif /** LINKED_LIST_H_ @}*/