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