functions invoked on all linked list items now support up to five additional arguments
[strongswan.git] / src / libstrongswan / utils / linked_list.c
1 /*
2 * Copyright (C) 2007-2008 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 * $Id$
18 */
19
20 #include <stdlib.h>
21
22 #include "linked_list.h"
23
24 typedef struct element_t element_t;
25
26 /**
27 * This element holds a pointer to the value it represents.
28 */
29 struct element_t {
30
31 /**
32 * Value of a list item.
33 */
34 void *value;
35
36 /**
37 * Previous list element.
38 *
39 * NULL if first element in list.
40 */
41 element_t *previous;
42
43 /**
44 * Next list element.
45 *
46 * NULL if last element in list.
47 */
48 element_t *next;
49 };
50
51 /**
52 * Creates an empty linked list object.
53 */
54 element_t *element_create(void *value)
55 {
56 element_t *this = malloc_thing(element_t);
57
58 this->previous = NULL;
59 this->next = NULL;
60 this->value = value;
61
62 return (this);
63 }
64
65
66 typedef struct private_linked_list_t private_linked_list_t;
67
68 /**
69 * Private data of a linked_list_t object.
70 *
71 */
72 struct private_linked_list_t {
73 /**
74 * Public part of linked list.
75 */
76 linked_list_t public;
77
78 /**
79 * Number of items in the list.
80 */
81 int count;
82
83 /**
84 * First element in list.
85 * NULL if no elements in list.
86 */
87 element_t *first;
88
89 /**
90 * Last element in list.
91 * NULL if no elements in list.
92 */
93 element_t *last;
94 };
95
96
97 typedef struct private_iterator_t private_iterator_t;
98
99 /**
100 * Private variables and functions of linked list iterator.
101 */
102 struct private_iterator_t {
103 /**
104 * Public part of linked list iterator.
105 */
106 iterator_t public;
107
108 /**
109 * Associated linked list.
110 */
111 private_linked_list_t * list;
112
113 /**
114 * Current element of the iterator.
115 */
116 element_t *current;
117
118 /**
119 * Direction of iterator.
120 */
121 bool forward;
122
123 /**
124 * Mutex to use to synchronize access
125 */
126 pthread_mutex_t *mutex;
127
128 /**
129 * iteration hook
130 */
131 iterator_hook_t *hook;
132
133 /**
134 * user parameter for iterator hook
135 */
136 void *hook_param;
137 };
138
139 typedef struct private_enumerator_t private_enumerator_t;
140
141 /**
142 * linked lists enumerator implementation
143 */
144 struct private_enumerator_t {
145
146 /**
147 * implements enumerator interface
148 */
149 enumerator_t enumerator;
150
151 /**
152 * associated linked list
153 */
154 private_linked_list_t *list;
155
156 /**
157 * current item
158 */
159 element_t *current;
160 };
161
162 /**
163 * Implementation of private_enumerator_t.enumerator.enumerate.
164 */
165 static bool enumerate(private_enumerator_t *this, void **item)
166 {
167 if (!this->current)
168 {
169 if (!this->list->first)
170 {
171 return FALSE;
172 }
173 this->current = this->list->first;
174 }
175 else
176 {
177 if (!this->current->next)
178 {
179 return FALSE;
180 }
181 this->current = this->current->next;
182 }
183 *item = this->current->value;
184 return TRUE;
185 }
186
187 /**
188 * Implementation of linked_list_t.create_enumerator.
189 */
190 static enumerator_t* create_enumerator(private_linked_list_t *this)
191 {
192 private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
193
194 enumerator->enumerator.enumerate = (void*)enumerate;
195 enumerator->enumerator.destroy = (void*)free;
196 enumerator->list = this;
197 enumerator->current = NULL;
198
199 return &enumerator->enumerator;
200 }
201
202 /**
203 * Implementation of iterator_t.get_count.
204 */
205 static int get_list_count(private_iterator_t *this)
206 {
207 return this->list->count;
208 }
209
210 /**
211 * default iterator hook which does nothing
212 */
213 static hook_result_t iterator_hook(void *param, void *in, void **out)
214 {
215 *out = in;
216 return HOOK_NEXT;
217 }
218
219 /**
220 * Implementation of iterator_t.set_iterator_hook.
221 */
222 static void set_iterator_hook(private_iterator_t *this, iterator_hook_t *hook,
223 void* param)
224 {
225 if (hook == NULL)
226 {
227 this->hook = iterator_hook;
228 this->hook_param = NULL;
229 }
230 else
231 {
232 this->hook = hook;
233 this->hook_param = param;
234 }
235 }
236
237 /**
238 * Implementation of iterator_t.iterate.
239 */
240 static bool iterate(private_iterator_t *this, void** value)
241 {
242 while (TRUE)
243 {
244 if (this->forward)
245 {
246 this->current = this->current ? this->current->next : this->list->first;
247 }
248 else
249 {
250 this->current = this->current ? this->current->previous : this->list->last;
251 }
252
253 if (this->current == NULL)
254 {
255 return FALSE;
256 }
257
258 switch (this->hook(this->hook_param, this->current->value, value))
259 {
260 case HOOK_AGAIN:
261 /* rewind */
262 if (this->forward)
263 {
264 this->current = this->current->previous;
265 }
266 else
267 {
268 this->current = this->current->next;
269 }
270 break;
271 case HOOK_NEXT:
272 /* normal iteration */
273 break;
274 case HOOK_SKIP:
275 /* advance */
276 continue;
277 }
278 break;
279 }
280 return TRUE;
281 }
282
283 /**
284 * Implementation of iterator_t.reset.
285 */
286 static void iterator_reset(private_iterator_t *this)
287 {
288 this->current = NULL;
289 }
290
291 /**
292 * Implementation of iterator_t.remove.
293 */
294 static status_t remove_(private_iterator_t *this)
295 {
296 element_t *new_current;
297
298 if (this->current == NULL)
299 {
300 return NOT_FOUND;
301 }
302
303 if (this->list->count == 0)
304 {
305 return NOT_FOUND;
306 }
307 /* find out the new iterator position, depending on iterator direction */
308 if (this->forward && this->current->previous != NULL)
309 {
310 new_current = this->current->previous;
311 }
312 else if (!this->forward && this->current->next != NULL)
313 {
314 new_current = this->current->next;
315 }
316 else
317 {
318 new_current = NULL;
319 }
320
321 /* now delete the entry :-) */
322 if (this->current->previous == NULL)
323 {
324 if (this->current->next == NULL)
325 {
326 this->list->first = NULL;
327 this->list->last = NULL;
328 }
329 else
330 {
331 this->current->next->previous = NULL;
332 this->list->first = this->current->next;
333 }
334 }
335 else if (this->current->next == NULL)
336 {
337 this->current->previous->next = NULL;
338 this->list->last = this->current->previous;
339 }
340 else
341 {
342 this->current->previous->next = this->current->next;
343 this->current->next->previous = this->current->previous;
344 }
345
346 this->list->count--;
347 free(this->current);
348 /* set the new iterator position */
349 this->current = new_current;
350 return SUCCESS;
351 }
352
353 /**
354 * Implementation of iterator_t.insert_before.
355 */
356 static void insert_before(private_iterator_t * iterator, void *item)
357 {
358 if (iterator->current == NULL)
359 {
360 iterator->list->public.insert_first(&(iterator->list->public), item);
361 }
362
363 element_t *element = element_create(item);
364 if (iterator->current->previous == NULL)
365 {
366 iterator->current->previous = element;
367 element->next = iterator->current;
368 iterator->list->first = element;
369 }
370 else
371 {
372 iterator->current->previous->next = element;
373 element->previous = iterator->current->previous;
374 iterator->current->previous = element;
375 element->next = iterator->current;
376 }
377 iterator->list->count++;
378 }
379
380 /**
381 * Implementation of iterator_t.replace.
382 */
383 static status_t replace(private_iterator_t *this, void **old_item, void *new_item)
384 {
385 if (this->current == NULL)
386 {
387 return NOT_FOUND;
388 }
389 if (old_item != NULL)
390 {
391 *old_item = this->current->value;
392 }
393 this->current->value = new_item;
394
395 return SUCCESS;
396 }
397
398 /**
399 * Implementation of iterator_t.insert_after.
400 */
401 static void insert_after(private_iterator_t *iterator, void *item)
402 {
403 if (iterator->current == NULL)
404 {
405 iterator->list->public.insert_first(&(iterator->list->public),item);
406 return;
407 }
408
409 element_t *element = element_create(item);
410 if (iterator->current->next == NULL)
411 {
412 iterator->current->next = element;
413 element->previous = iterator->current;
414 iterator->list->last = element;
415 }
416 else
417 {
418 iterator->current->next->previous = element;
419 element->next = iterator->current->next;
420 iterator->current->next = element;
421 element->previous = iterator->current;
422 }
423 iterator->list->count++;
424 }
425
426 /**
427 * Implementation of iterator_t.destroy.
428 */
429 static void iterator_destroy(private_iterator_t *this)
430 {
431 if (this->mutex)
432 {
433 pthread_mutex_unlock(this->mutex);
434 }
435 free(this);
436 }
437
438 /**
439 * Implementation of linked_list_t.get_count.
440 */
441 static int get_count(private_linked_list_t *this)
442 {
443 return this->count;
444 }
445
446 /**
447 * Implementation of linked_list_t.insert_first.
448 */
449 static void insert_first(private_linked_list_t *this, void *item)
450 {
451 element_t *element;
452
453 element = element_create(item);
454 if (this->count == 0)
455 {
456 /* first entry in list */
457 this->first = element;
458 this->last = element;
459 element->previous = NULL;
460 element->next = NULL;
461 }
462 else
463 {
464 element_t *old_first_element = this->first;
465 element->next = old_first_element;
466 element->previous = NULL;
467 old_first_element->previous = element;
468 this->first = element;
469 }
470 this->count++;
471 }
472
473 /**
474 * unlink an element form the list, returns following element
475 */
476 static element_t* remove_element(private_linked_list_t *this, element_t *element)
477 {
478 element_t *next, *previous;
479
480 next = element->next;
481 previous = element->previous;
482 free(element);
483 if (next)
484 {
485 next->previous = previous;
486 }
487 else
488 {
489 this->last = previous;
490 }
491 if (previous)
492 {
493 previous->next = next;
494 }
495 else
496 {
497 this->first = next;
498 }
499 if (--this->count == 0)
500 {
501 this->first = NULL;
502 this->last = NULL;
503 }
504 return next;
505 }
506
507 /**
508 * Implementation of linked_list_t.get_first.
509 */
510 static status_t get_first(private_linked_list_t *this, void **item)
511 {
512 if (this->count == 0)
513 {
514 return NOT_FOUND;
515 }
516 *item = this->first->value;
517 return SUCCESS;
518 }
519
520 /**
521 * Implementation of linked_list_t.remove_first.
522 */
523 static status_t remove_first(private_linked_list_t *this, void **item)
524 {
525 if (get_first(this, item) == SUCCESS)
526 {
527 remove_element(this, this->first);
528 return SUCCESS;
529 }
530 return NOT_FOUND;
531 }
532
533 /**
534 * Implementation of linked_list_t.insert_last.
535 */
536 static void insert_last(private_linked_list_t *this, void *item)
537 {
538 element_t *element = element_create(item);
539
540 if (this->count == 0)
541 {
542 /* first entry in list */
543 this->first = element;
544 this->last = element;
545 element->previous = NULL;
546 element->next = NULL;
547 }
548 else
549 {
550 element_t *old_last_element = this->last;
551 element->previous = old_last_element;
552 element->next = NULL;
553 old_last_element->next = element;
554 this->last = element;
555 }
556 this->count++;
557 }
558
559 /**
560 * Implementation of linked_list_t.get_last.
561 */
562 static status_t get_last(private_linked_list_t *this, void **item)
563 {
564 if (this->count == 0)
565 {
566 return NOT_FOUND;
567 }
568 *item = this->last->value;
569 return SUCCESS;
570 }
571
572 /**
573 * Implementation of linked_list_t.remove_last.
574 */
575 static status_t remove_last(private_linked_list_t *this, void **item)
576 {
577 if (get_last(this, item) == SUCCESS)
578 {
579 remove_element(this, this->last);
580 return SUCCESS;
581 }
582 return NOT_FOUND;
583 }
584
585 /**
586 * Implementation of linked_list_t.remove.
587 */
588 static int remove(private_linked_list_t *this, void *item,
589 bool (*compare)(void *,void*))
590 {
591 element_t *current = this->first;
592 int removed = 0;
593
594 while (current)
595 {
596 if ((compare && compare(current->value, item)) ||
597 (!compare && current->value == item))
598 {
599 removed++;
600 current = remove_element(this, current);
601 }
602 else
603 {
604 current = current->next;
605 }
606 }
607 return removed;
608 }
609
610 /**
611 * Implementation of linked_list_t.remove_at.
612 */
613 static void remove_at(private_linked_list_t *this, private_enumerator_t *enumerator)
614 {
615 element_t *current;
616
617 if (enumerator->current)
618 {
619 current = enumerator->current;
620 enumerator->current = current->previous;
621 remove_element(this, current);
622 }
623 }
624
625 /**
626 * Implementation of linked_list_t.find_first.
627 */
628 static status_t find_first(private_linked_list_t *this, linked_list_match_t match,
629 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
630 {
631 element_t *current = this->first;
632
633 while (current)
634 {
635 if (match(current->value, d1, d2, d3, d4, d5))
636 {
637 if (item != NULL)
638 {
639 *item = current->value;
640 }
641 return SUCCESS;
642 }
643 current = current->next;
644 }
645 return NOT_FOUND;
646 }
647
648 /**
649 * Implementation of linked_list_t.find_last.
650 */
651 static status_t find_last(private_linked_list_t *this, linked_list_match_t match,
652 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
653 {
654 element_t *current = this->last;
655
656 while (current)
657 {
658 if (match(current->value, d1, d2, d3, d4, d5))
659 {
660 if (item != NULL)
661 {
662 *item = current->value;
663 }
664 return SUCCESS;
665 }
666 current = current->previous;
667 }
668 return NOT_FOUND;
669 }
670
671 /**
672 * Implementation of linked_list_t.invoke_offset.
673 */
674 static void invoke_offset(private_linked_list_t *this, size_t offset,
675 void *d1, void *d2, void *d3, void *d4, void *d5)
676 {
677 element_t *current = this->first;
678
679 while (current)
680 {
681 linked_list_invoke_t *method = current->value + offset;
682 (*method)(current->value, d1, d2, d3, d4, d5);
683 current = current->next;
684 }
685 }
686
687 /**
688 * Implementation of linked_list_t.invoke_function.
689 */
690 static void invoke_function(private_linked_list_t *this, linked_list_invoke_t fn,
691 void *d1, void *d2, void *d3, void *d4, void *d5)
692 {
693 element_t *current = this->first;
694
695 while (current)
696 {
697 fn(current->value, d1, d2, d3, d4, d5);
698 current = current->next;
699 }
700 }
701
702 /**
703 * Implementation of linked_list_t.clone_offset
704 */
705 static linked_list_t *clone_offset(private_linked_list_t *this, size_t offset)
706 {
707 linked_list_t *clone = linked_list_create();
708 element_t *current = this->first;
709
710 while (current)
711 {
712 void* (**method)(void*) = current->value + offset;
713 clone->insert_last(clone, (*method)(current->value));
714 current = current->next;
715 }
716
717 return clone;
718 }
719
720 /**
721 * Implementation of linked_list_t.clone_function
722 */
723 static linked_list_t *clone_function(private_linked_list_t *this, void* (*fn)(void*))
724 {
725 linked_list_t *clone = linked_list_create();
726 element_t *current = this->first;
727
728 while (current)
729 {
730 clone->insert_last(clone, fn(current->value));
731 current = current->next;
732 }
733
734 return clone;
735 }
736
737 /**
738 * Implementation of linked_list_t.destroy.
739 */
740 static void destroy(private_linked_list_t *this)
741 {
742 void *value;
743 /* Remove all list items before destroying list */
744 while (remove_first(this, &value) == SUCCESS)
745 {
746 /* values are not destroyed so memory leaks are possible
747 * if list is not empty when deleting */
748 }
749 free(this);
750 }
751
752 /**
753 * Implementation of linked_list_t.destroy_offset.
754 */
755 static void destroy_offset(private_linked_list_t *this, size_t offset)
756 {
757 element_t *current = this->first, *next;
758
759 while (current)
760 {
761 void (**method)(void*) = current->value + offset;
762 (*method)(current->value);
763 next = current->next;
764 free(current);
765 current = next;
766 }
767 free(this);
768 }
769
770 /**
771 * Implementation of linked_list_t.destroy_function.
772 */
773 static void destroy_function(private_linked_list_t *this, void (*fn)(void*))
774 {
775 element_t *current = this->first, *next;
776
777 while (current)
778 {
779 fn(current->value);
780 next = current->next;
781 free(current);
782 current = next;
783 }
784 free(this);
785 }
786
787 /**
788 * Implementation of linked_list_t.create_iterator.
789 */
790 static iterator_t *create_iterator(private_linked_list_t *linked_list, bool forward)
791 {
792 private_iterator_t *this = malloc_thing(private_iterator_t);
793
794 this->public.get_count = (int (*) (iterator_t*)) get_list_count;
795 this->public.iterate = (bool (*) (iterator_t*, void **value)) iterate;
796 this->public.set_iterator_hook = (void(*)(iterator_t*, iterator_hook_t*, void*))set_iterator_hook;
797 this->public.insert_before = (void (*) (iterator_t*, void *item)) insert_before;
798 this->public.insert_after = (void (*) (iterator_t*, void *item)) insert_after;
799 this->public.replace = (status_t (*) (iterator_t*, void **, void *)) replace;
800 this->public.remove = (status_t (*) (iterator_t*)) remove_;
801 this->public.reset = (void (*) (iterator_t*)) iterator_reset;
802 this->public.destroy = (void (*) (iterator_t*)) iterator_destroy;
803
804 this->forward = forward;
805 this->current = NULL;
806 this->list = linked_list;
807 this->mutex = NULL;
808 this->hook = iterator_hook;
809
810 return &this->public;
811 }
812
813 /**
814 * Implementation of linked_list_t.create_iterator_locked.
815 */
816 static iterator_t *create_iterator_locked(private_linked_list_t *linked_list,
817 pthread_mutex_t *mutex)
818 {
819 private_iterator_t *this = (private_iterator_t*)create_iterator(linked_list, TRUE);
820 this->mutex = mutex;
821
822 pthread_mutex_lock(mutex);
823
824 return &this->public;
825 }
826
827 /*
828 * Described in header.
829 */
830 linked_list_t *linked_list_create()
831 {
832 private_linked_list_t *this = malloc_thing(private_linked_list_t);
833
834 this->public.get_count = (int (*) (linked_list_t *)) get_count;
835 this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool))create_iterator;
836 this->public.create_iterator_locked = (iterator_t * (*) (linked_list_t *,pthread_mutex_t*))create_iterator_locked;
837 this->public.create_enumerator = (enumerator_t*(*)(linked_list_t*))create_enumerator;
838 this->public.get_first = (status_t (*) (linked_list_t *, void **item))get_first;
839 this->public.get_last = (status_t (*) (linked_list_t *, void **item))get_last;
840 this->public.find_first = (status_t (*) (linked_list_t *, linked_list_match_t,void**,...))find_first;
841 this->public.find_last = (status_t (*) (linked_list_t *, linked_list_match_t,void**,...))find_last;
842 this->public.insert_first = (void (*) (linked_list_t *, void *item))insert_first;
843 this->public.insert_last = (void (*) (linked_list_t *, void *item))insert_last;
844 this->public.remove_first = (status_t (*) (linked_list_t *, void **item))remove_first;
845 this->public.remove_last = (status_t (*) (linked_list_t *, void **item))remove_last;
846 this->public.remove = (int(*)(linked_list_t*, void *item, bool (*compare)(void *,void*)))remove;
847 this->public.remove_at = (void(*)(linked_list_t*, enumerator_t *enumerator))remove_at;
848 this->public.invoke_offset = (void (*)(linked_list_t*,size_t,...))invoke_offset;
849 this->public.invoke_function = (void (*)(linked_list_t*,linked_list_invoke_t,...))invoke_function;
850 this->public.clone_offset = (linked_list_t * (*)(linked_list_t*,size_t))clone_offset;
851 this->public.clone_function = (linked_list_t * (*)(linked_list_t*,void*(*)(void*)))clone_function;
852 this->public.destroy = (void (*) (linked_list_t *))destroy;
853 this->public.destroy_offset = (void (*) (linked_list_t *,size_t))destroy_offset;
854 this->public.destroy_function = (void (*)(linked_list_t*,void(*)(void*)))destroy_function;
855
856 this->count = 0;
857 this->first = NULL;
858 this->last = NULL;
859
860 return &this->public;
861 }