Added an insert_after and insert_before function to linked_list_t.
[strongswan.git] / src / libstrongswan / utils / 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 utils
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 <utils/iterator.h>
29 #include <utils/enumerator.h>
30
31 /**
32 * Method to match elements in a linked list (used in find_* functions)
33 *
34 * @param item current list item
35 * @param ... user supplied data (only pointers, at most 5)
36 * @return
37 * - TRUE, if the item matched
38 * - FALSE, otherwise
39 */
40 typedef bool (*linked_list_match_t)(void *item, ...);
41
42 /**
43 * Method to be invoked on elements in a linked list (used in invoke_* functions)
44 *
45 * @param item current list item
46 * @param ... user supplied data (only pointers, at most 5)
47 */
48 typedef void (*linked_list_invoke_t)(void *item, ...);
49
50 /**
51 * Class implementing a double linked list.
52 *
53 * General purpose linked list. This list is not synchronized.
54 */
55 struct linked_list_t {
56
57 /**
58 * Gets the count of items in the list.
59 *
60 * @return number of items in list
61 */
62 int (*get_count) (linked_list_t *this);
63
64 /**
65 * Creates a iterator for the given list.
66 *
67 * @warning Created iterator_t object has to get destroyed by the caller.
68 *
69 * @deprecated Iterator is obsolete and will disappear, it is too
70 * complicated to implement. Use enumerator instead.
71 *
72 * @param forward iterator direction (TRUE: front to end)
73 * @return new iterator_t object
74 */
75 iterator_t *(*create_iterator) (linked_list_t *this, bool forward);
76
77 /**
78 * Create an enumerator over the list.
79 *
80 * The enumerator is a "lightweight" iterator. It only has two methods
81 * and should therefore be much easier to implement.
82 *
83 * @return enumerator over list items
84 */
85 enumerator_t* (*create_enumerator)(linked_list_t *this);
86
87 /**
88 * Inserts a new item at the beginning of the list.
89 *
90 * @param item item value to insert in list
91 */
92 void (*insert_first) (linked_list_t *this, void *item);
93
94 /**
95 * Removes the first item in the list and returns its value.
96 *
97 * @param item returned value of first item, or NULL
98 * @return SUCCESS, or NOT_FOUND if list is empty
99 */
100 status_t (*remove_first) (linked_list_t *this, void **item);
101
102 /**
103 * Inserts a new item before the item the enumerator currently points to.
104 *
105 * @note The position of the enumerator is not changed.
106 * @note If the enumerator's position is invalid, the item is inserted last.
107 *
108 * @param enumerator enumerator with position
109 * @param item item value to insert in list
110 */
111 void (*insert_before)(linked_list_t *this, enumerator_t *enumerator,
112 void *item);
113
114 /**
115 * Inserts a new item after the item the enumerator currently points to.
116 *
117 * @note The position of the enumerator is not changed (thus the next item
118 * the enumerator returns will be the inserted item).
119 *
120 * @note If the enumerator's position is invalid, the item is inserted last.
121 *
122 * @param enumerator enumerator with position
123 * @param item item value to insert in list
124 */
125 void (*insert_after)(linked_list_t *this, enumerator_t *enumerator,
126 void *item);
127
128 /**
129 * Remove an item from the list where the enumerator points to.
130 *
131 * @param enumerator enumerator with position
132 */
133 void (*remove_at)(linked_list_t *this, enumerator_t *enumerator);
134
135 /**
136 * Remove items from the list matching the given item.
137 *
138 * If a compare function is given, it is called for each item, with the
139 * first parameter being the current list item and the second parameter
140 * being the supplied item. Return TRUE from the compare function to remove
141 * the item, return FALSE to keep it in the list.
142 *
143 * If compare is NULL, comparison is done by pointers.
144 *
145 * @param item item to remove/pass to comparator
146 * @param compare compare function, or NULL
147 * @return number of removed items
148 */
149 int (*remove)(linked_list_t *this, void *item, bool (*compare)(void*,void*));
150
151 /**
152 * Returns the value of the first list item without removing it.
153 *
154 * @param this calling object
155 * @param item returned value of first item
156 * @return SUCCESS, NOT_FOUND if list is empty
157 */
158 status_t (*get_first) (linked_list_t *this, void **item);
159
160 /**
161 * Inserts a new item at the end of the list.
162 *
163 * @param item value to insert into list
164 */
165 void (*insert_last) (linked_list_t *this, void *item);
166
167 /**
168 * Removes the last item in the list and returns its value.
169 *
170 * @param this calling object
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 this calling object
180 * @param item returned value of last item
181 * @return SUCCESS, NOT_FOUND if list is empty
182 */
183 status_t (*get_last) (linked_list_t *this, void **item);
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 /** Find the last matching element in the list.
206 *
207 * The first object passed to the match function is the current list item,
208 * followed by the user supplied data.
209 * If the supplied function returns TRUE this function returns SUCCESS, and
210 * the current object is returned in the third parameter, otherwise,
211 * the next item is checked.
212 *
213 * If match is NULL, *item and the current object are compared.
214 *
215 * @warning Only use pointers as user supplied data.
216 *
217 * @param match comparison function to call on each object, or NULL
218 * @param item the list item, if found
219 * @param ... user data to supply to match function (limited to 5 arguments)
220 * @return SUCCESS if found, NOT_FOUND otherwise
221 */
222 status_t (*find_last) (linked_list_t *this, linked_list_match_t match,
223 void **item, ...);
224
225 /**
226 * Invoke a method on all of the contained objects.
227 *
228 * If a linked list contains objects with function pointers,
229 * invoke() can call a method on each of the objects. The
230 * method is specified by an offset of the function pointer,
231 * which can be evalutated at compile time using the offsetof
232 * macro, e.g.: list->invoke(list, offsetof(object_t, method));
233 *
234 * @warning Only use pointers as user supplied data.
235 *
236 * @param offset offset of the method to invoke on objects
237 * @param ... user data to supply to called function (limited to 5 arguments)
238 */
239 void (*invoke_offset) (linked_list_t *this, size_t offset, ...);
240
241 /**
242 * Invoke a function on all of the contained objects.
243 *
244 * @warning Only use pointers as user supplied data.
245 *
246 * @param function offset of the method to invoke on objects
247 * @param ... user data to supply to called function (limited to 5 arguments)
248 */
249 void (*invoke_function) (linked_list_t *this, linked_list_invoke_t function, ...);
250
251 /**
252 * Clones a list and its objects using the objects' clone method.
253 *
254 * @param offset offset ot the objects clone function
255 * @return cloned list
256 */
257 linked_list_t *(*clone_offset) (linked_list_t *this, size_t offset);
258
259 /**
260 * Clones a list and its objects using a given function.
261 *
262 * @param function function that clones an object
263 * @return cloned list
264 */
265 linked_list_t *(*clone_function) (linked_list_t *this, void*(*)(void*));
266
267 /**
268 * Destroys a linked_list object.
269 */
270 void (*destroy) (linked_list_t *this);
271
272 /**
273 * Destroys a list and its objects using the destructor.
274 *
275 * If a linked list and the contained objects should be destroyed, use
276 * destroy_offset. The supplied offset specifies the destructor to
277 * call on each object. The offset may be calculated using the offsetof
278 * macro, e.g.: list->destroy_offset(list, offsetof(object_t, destroy));
279 *
280 * @param offset offset of the objects destructor
281 */
282 void (*destroy_offset) (linked_list_t *this, size_t offset);
283
284 /**
285 * Destroys a list and its contents using a a cleanup function.
286 *
287 * If a linked list and its contents should get destroyed using a specific
288 * cleanup function, use destroy_function. This is useful when the
289 * list contains malloc()-ed blocks which should get freed,
290 * e.g.: list->destroy_function(list, free);
291 *
292 * @param function function to call on each object
293 */
294 void (*destroy_function) (linked_list_t *this, void (*)(void*));
295 };
296
297 /**
298 * Creates an empty linked list object.
299 *
300 * @return linked_list_t object.
301 */
302 linked_list_t *linked_list_create(void);
303
304 #endif /** LINKED_LIST_H_ @}*/