linked-list: Don't require an argument for the item when enumerating
[strongswan.git] / src / libstrongswan / collections / linked_list.c
1 /*
2 * Copyright (C) 2007-2011 Tobias Brunner
3 * Copyright (C) 2005-2006 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 #include <stdlib.h>
19 #include <stdarg.h>
20
21 #include "linked_list.h"
22
23 typedef struct element_t element_t;
24
25 /**
26 * This element holds a pointer to the value it represents.
27 */
28 struct element_t {
29
30 /**
31 * Value of a list item.
32 */
33 void *value;
34
35 /**
36 * Previous list element.
37 *
38 * NULL if first element in list.
39 */
40 element_t *previous;
41
42 /**
43 * Next list element.
44 *
45 * NULL if last element in list.
46 */
47 element_t *next;
48 };
49
50 /**
51 * Creates an empty linked list object.
52 */
53 element_t *element_create(void *value)
54 {
55 element_t *this;
56 INIT(this,
57 .value = value,
58 );
59 return this;
60 }
61
62
63 typedef struct private_linked_list_t private_linked_list_t;
64
65 /**
66 * Private data of a linked_list_t object.
67 *
68 */
69 struct private_linked_list_t {
70 /**
71 * Public part of linked list.
72 */
73 linked_list_t public;
74
75 /**
76 * Number of items in the list.
77 */
78 int count;
79
80 /**
81 * First element in list.
82 * NULL if no elements in list.
83 */
84 element_t *first;
85
86 /**
87 * Last element in list.
88 * NULL if no elements in list.
89 */
90 element_t *last;
91 };
92
93 typedef struct private_enumerator_t private_enumerator_t;
94
95 /**
96 * linked lists enumerator implementation
97 */
98 struct private_enumerator_t {
99
100 /**
101 * implements enumerator interface
102 */
103 enumerator_t enumerator;
104
105 /**
106 * associated linked list
107 */
108 private_linked_list_t *list;
109
110 /**
111 * current item
112 */
113 element_t *current;
114
115 /**
116 * enumerator has enumerated all items
117 */
118 bool finished;
119 };
120
121 METHOD(enumerator_t, enumerate, bool,
122 private_enumerator_t *this, void **item)
123 {
124 if (this->finished)
125 {
126 return FALSE;
127 }
128 if (!this->current)
129 {
130 this->current = this->list->first;
131 }
132 else
133 {
134 this->current = this->current->next;
135 }
136 if (!this->current)
137 {
138 this->finished = TRUE;
139 return FALSE;
140 }
141 if (item)
142 {
143 *item = this->current->value;
144 }
145 return TRUE;
146 }
147
148 METHOD(linked_list_t, create_enumerator, enumerator_t*,
149 private_linked_list_t *this)
150 {
151 private_enumerator_t *enumerator;
152
153 INIT(enumerator,
154 .enumerator = {
155 .enumerate = (void*)_enumerate,
156 .destroy = (void*)free,
157 },
158 .list = this,
159 );
160
161 return &enumerator->enumerator;
162 }
163
164 METHOD(linked_list_t, reset_enumerator, void,
165 private_linked_list_t *this, private_enumerator_t *enumerator)
166 {
167 enumerator->current = NULL;
168 enumerator->finished = FALSE;
169 }
170
171 METHOD(linked_list_t, has_more, bool,
172 private_linked_list_t *this, private_enumerator_t *enumerator)
173 {
174 if (enumerator->current)
175 {
176 return enumerator->current->next != NULL;
177 }
178 return !enumerator->finished && this->first != NULL;
179 }
180
181 METHOD(linked_list_t, get_count, int,
182 private_linked_list_t *this)
183 {
184 return this->count;
185 }
186
187 METHOD(linked_list_t, insert_first, void,
188 private_linked_list_t *this, void *item)
189 {
190 element_t *element;
191
192 element = element_create(item);
193 if (this->count == 0)
194 {
195 /* first entry in list */
196 this->first = element;
197 this->last = element;
198 }
199 else
200 {
201 element->next = this->first;
202 this->first->previous = element;
203 this->first = element;
204 }
205 this->count++;
206 }
207
208 /**
209 * unlink an element form the list, returns following element
210 */
211 static element_t* remove_element(private_linked_list_t *this,
212 element_t *element)
213 {
214 element_t *next, *previous;
215
216 next = element->next;
217 previous = element->previous;
218 free(element);
219 if (next)
220 {
221 next->previous = previous;
222 }
223 else
224 {
225 this->last = previous;
226 }
227 if (previous)
228 {
229 previous->next = next;
230 }
231 else
232 {
233 this->first = next;
234 }
235 if (--this->count == 0)
236 {
237 this->first = NULL;
238 this->last = NULL;
239 }
240 return next;
241 }
242
243 METHOD(linked_list_t, get_first, status_t,
244 private_linked_list_t *this, void **item)
245 {
246 if (this->count == 0)
247 {
248 return NOT_FOUND;
249 }
250 *item = this->first->value;
251 return SUCCESS;
252 }
253
254 METHOD(linked_list_t, remove_first, status_t,
255 private_linked_list_t *this, void **item)
256 {
257 if (get_first(this, item) == SUCCESS)
258 {
259 remove_element(this, this->first);
260 return SUCCESS;
261 }
262 return NOT_FOUND;
263 }
264
265 METHOD(linked_list_t, insert_last, void,
266 private_linked_list_t *this, void *item)
267 {
268 element_t *element;
269
270 element = element_create(item);
271 if (this->count == 0)
272 {
273 /* first entry in list */
274 this->first = element;
275 this->last = element;
276 }
277 else
278 {
279 element->previous = this->last;
280 this->last->next = element;
281 this->last = element;
282 }
283 this->count++;
284 }
285
286 METHOD(linked_list_t, insert_before, void,
287 private_linked_list_t *this, private_enumerator_t *enumerator,
288 void *item)
289 {
290 element_t *current, *element;
291
292 current = enumerator->current;
293 if (!current)
294 {
295 if (enumerator->finished)
296 {
297 this->public.insert_last(&this->public, item);
298 }
299 else
300 {
301 this->public.insert_first(&this->public, item);
302 }
303 return;
304 }
305 element = element_create(item);
306 if (current->previous)
307 {
308 current->previous->next = element;
309 element->previous = current->previous;
310 current->previous = element;
311 element->next = current;
312 }
313 else
314 {
315 current->previous = element;
316 element->next = current;
317 this->first = element;
318 }
319 this->count++;
320 }
321
322 METHOD(linked_list_t, get_last, status_t,
323 private_linked_list_t *this, void **item)
324 {
325 if (this->count == 0)
326 {
327 return NOT_FOUND;
328 }
329 *item = this->last->value;
330 return SUCCESS;
331 }
332
333 METHOD(linked_list_t, remove_last, status_t,
334 private_linked_list_t *this, void **item)
335 {
336 if (get_last(this, item) == SUCCESS)
337 {
338 remove_element(this, this->last);
339 return SUCCESS;
340 }
341 return NOT_FOUND;
342 }
343
344 METHOD(linked_list_t, remove_, int,
345 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
346 {
347 element_t *current = this->first;
348 int removed = 0;
349
350 while (current)
351 {
352 if ((compare && compare(current->value, item)) ||
353 (!compare && current->value == item))
354 {
355 removed++;
356 current = remove_element(this, current);
357 }
358 else
359 {
360 current = current->next;
361 }
362 }
363 return removed;
364 }
365
366 METHOD(linked_list_t, remove_at, void,
367 private_linked_list_t *this, private_enumerator_t *enumerator)
368 {
369 element_t *current;
370
371 if (enumerator->current)
372 {
373 current = enumerator->current;
374 enumerator->current = current->previous;
375 remove_element(this, current);
376 }
377 }
378
379 METHOD(linked_list_t, find_first, status_t,
380 private_linked_list_t *this, linked_list_match_t match,
381 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
382 {
383 element_t *current = this->first;
384
385 while (current)
386 {
387 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
388 (!match && item && current->value == *item))
389 {
390 if (item != NULL)
391 {
392 *item = current->value;
393 }
394 return SUCCESS;
395 }
396 current = current->next;
397 }
398 return NOT_FOUND;
399 }
400
401 METHOD(linked_list_t, invoke_offset, void,
402 private_linked_list_t *this, size_t offset,
403 void *d1, void *d2, void *d3, void *d4, void *d5)
404 {
405 element_t *current = this->first;
406 linked_list_invoke_t *method;
407
408 while (current)
409 {
410 method = current->value + offset;
411 (*method)(current->value, d1, d2, d3, d4, d5);
412 current = current->next;
413 }
414 }
415
416 METHOD(linked_list_t, invoke_function, void,
417 private_linked_list_t *this, linked_list_invoke_t fn,
418 void *d1, void *d2, void *d3, void *d4, void *d5)
419 {
420 element_t *current = this->first;
421
422 while (current)
423 {
424 fn(current->value, d1, d2, d3, d4, d5);
425 current = current->next;
426 }
427 }
428
429 METHOD(linked_list_t, clone_offset, linked_list_t*,
430 private_linked_list_t *this, size_t offset)
431 {
432 element_t *current = this->first;
433 linked_list_t *clone;
434
435 clone = linked_list_create();
436 while (current)
437 {
438 void* (**method)(void*) = current->value + offset;
439 clone->insert_last(clone, (*method)(current->value));
440 current = current->next;
441 }
442
443 return clone;
444 }
445
446 METHOD(linked_list_t, destroy, void,
447 private_linked_list_t *this)
448 {
449 void *value;
450
451 /* Remove all list items before destroying list */
452 while (remove_first(this, &value) == SUCCESS)
453 {
454 /* values are not destroyed so memory leaks are possible
455 * if list is not empty when deleting */
456 }
457 free(this);
458 }
459
460 METHOD(linked_list_t, destroy_offset, void,
461 private_linked_list_t *this, size_t offset)
462 {
463 element_t *current = this->first, *next;
464
465 while (current)
466 {
467 void (**method)(void*) = current->value + offset;
468 (*method)(current->value);
469 next = current->next;
470 free(current);
471 current = next;
472 }
473 free(this);
474 }
475
476 METHOD(linked_list_t, destroy_function, void,
477 private_linked_list_t *this, void (*fn)(void*))
478 {
479 element_t *current = this->first, *next;
480
481 while (current)
482 {
483 fn(current->value);
484 next = current->next;
485 free(current);
486 current = next;
487 }
488 free(this);
489 }
490
491 /*
492 * Described in header.
493 */
494 linked_list_t *linked_list_create()
495 {
496 private_linked_list_t *this;
497
498 INIT(this,
499 .public = {
500 .get_count = _get_count,
501 .create_enumerator = _create_enumerator,
502 .reset_enumerator = (void*)_reset_enumerator,
503 .has_more = (void*)_has_more,
504 .get_first = _get_first,
505 .get_last = _get_last,
506 .find_first = (void*)_find_first,
507 .insert_first = _insert_first,
508 .insert_last = _insert_last,
509 .insert_before = (void*)_insert_before,
510 .remove_first = _remove_first,
511 .remove_last = _remove_last,
512 .remove = _remove_,
513 .remove_at = (void*)_remove_at,
514 .invoke_offset = (void*)_invoke_offset,
515 .invoke_function = (void*)_invoke_function,
516 .clone_offset = _clone_offset,
517 .destroy = _destroy,
518 .destroy_offset = _destroy_offset,
519 .destroy_function = _destroy_function,
520 },
521 );
522
523 return &this->public;
524 }
525
526 /*
527 * See header.
528 */
529 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
530 {
531 linked_list_t *list;
532 void *item;
533
534 list = linked_list_create();
535
536 while (enumerator->enumerate(enumerator, &item))
537 {
538 list->insert_last(list, item);
539 }
540 enumerator->destroy(enumerator);
541
542 return list;
543 }
544
545 /*
546 * See header.
547 */
548 linked_list_t *linked_list_create_with_items(void *item, ...)
549 {
550 linked_list_t *list;
551 va_list args;
552
553 list = linked_list_create();
554
555 va_start(args, item);
556 while (item)
557 {
558 list->insert_last(list, item);
559 item = va_arg(args, void*);
560 }
561 va_end(args);
562
563 return list;
564 }