16913b934771971e875dac4217e944144a6cbe5e
[strongswan.git] / src / libstrongswan / utils / linked_list.c
1 /*
2 * Copyright (C) 2007 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 * next item to enumerate
153 */
154 element_t *next;
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->next == NULL)
168 {
169 return FALSE;
170 }
171 *item = this->next->value;
172 this->current = this->next;
173 this->next = this->next->next;
174 return TRUE;
175 }
176
177 /**
178 * Implementation of linked_list_t.create_enumerator.
179 */
180 static enumerator_t* create_enumerator(private_linked_list_t *this)
181 {
182 private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
183
184 enumerator->enumerator.enumerate = (void*)enumerate;
185 enumerator->enumerator.destroy = (void*)free;
186 enumerator->next = this->first;
187 enumerator->current = NULL;
188
189 return &enumerator->enumerator;
190 }
191
192 /**
193 * Implementation of iterator_t.get_count.
194 */
195 static int get_list_count(private_iterator_t *this)
196 {
197 return this->list->count;
198 }
199
200 /**
201 * default iterator hook which does nothing
202 */
203 static hook_result_t iterator_hook(void *param, void *in, void **out)
204 {
205 *out = in;
206 return HOOK_NEXT;
207 }
208
209 /**
210 * Implementation of iterator_t.set_iterator_hook.
211 */
212 static void set_iterator_hook(private_iterator_t *this, iterator_hook_t *hook,
213 void* param)
214 {
215 if (hook == NULL)
216 {
217 this->hook = iterator_hook;
218 this->hook_param = NULL;
219 }
220 else
221 {
222 this->hook = hook;
223 this->hook_param = param;
224 }
225 }
226
227 /**
228 * Implementation of iterator_t.iterate.
229 */
230 static bool iterate(private_iterator_t *this, void** value)
231 {
232 while (TRUE)
233 {
234 if (this->forward)
235 {
236 this->current = this->current ? this->current->next : this->list->first;
237 }
238 else
239 {
240 this->current = this->current ? this->current->previous : this->list->last;
241 }
242
243 if (this->current == NULL)
244 {
245 return FALSE;
246 }
247
248 switch (this->hook(this->hook_param, this->current->value, value))
249 {
250 case HOOK_AGAIN:
251 /* rewind */
252 if (this->forward)
253 {
254 this->current = this->current->previous;
255 }
256 else
257 {
258 this->current = this->current->next;
259 }
260 break;
261 case HOOK_NEXT:
262 /* normal iteration */
263 break;
264 case HOOK_SKIP:
265 /* advance */
266 continue;
267 }
268 break;
269 }
270 return TRUE;
271 }
272
273 /**
274 * Implementation of iterator_t.reset.
275 */
276 static void iterator_reset(private_iterator_t *this)
277 {
278 this->current = NULL;
279 }
280
281 /**
282 * Implementation of iterator_t.remove.
283 */
284 static status_t remove_(private_iterator_t *this)
285 {
286 element_t *new_current;
287
288 if (this->current == NULL)
289 {
290 return NOT_FOUND;
291 }
292
293 if (this->list->count == 0)
294 {
295 return NOT_FOUND;
296 }
297 /* find out the new iterator position, depending on iterator direction */
298 if (this->forward && this->current->previous != NULL)
299 {
300 new_current = this->current->previous;
301 }
302 else if (!this->forward && this->current->next != NULL)
303 {
304 new_current = this->current->next;
305 }
306 else
307 {
308 new_current = NULL;
309 }
310
311 /* now delete the entry :-) */
312 if (this->current->previous == NULL)
313 {
314 if (this->current->next == NULL)
315 {
316 this->list->first = NULL;
317 this->list->last = NULL;
318 }
319 else
320 {
321 this->current->next->previous = NULL;
322 this->list->first = this->current->next;
323 }
324 }
325 else if (this->current->next == NULL)
326 {
327 this->current->previous->next = NULL;
328 this->list->last = this->current->previous;
329 }
330 else
331 {
332 this->current->previous->next = this->current->next;
333 this->current->next->previous = this->current->previous;
334 }
335
336 this->list->count--;
337 free(this->current);
338 /* set the new iterator position */
339 this->current = new_current;
340 return SUCCESS;
341 }
342
343 /**
344 * Implementation of iterator_t.insert_before.
345 */
346 static void insert_before(private_iterator_t * iterator, void *item)
347 {
348 if (iterator->current == NULL)
349 {
350 iterator->list->public.insert_first(&(iterator->list->public), item);
351 }
352
353 element_t *element = element_create(item);
354 if (iterator->current->previous == NULL)
355 {
356 iterator->current->previous = element;
357 element->next = iterator->current;
358 iterator->list->first = element;
359 }
360 else
361 {
362 iterator->current->previous->next = element;
363 element->previous = iterator->current->previous;
364 iterator->current->previous = element;
365 element->next = iterator->current;
366 }
367 iterator->list->count++;
368 }
369
370 /**
371 * Implementation of iterator_t.replace.
372 */
373 static status_t replace(private_iterator_t *this, void **old_item, void *new_item)
374 {
375 if (this->current == NULL)
376 {
377 return NOT_FOUND;
378 }
379 if (old_item != NULL)
380 {
381 *old_item = this->current->value;
382 }
383 this->current->value = new_item;
384
385 return SUCCESS;
386 }
387
388 /**
389 * Implementation of iterator_t.insert_after.
390 */
391 static void insert_after(private_iterator_t *iterator, void *item)
392 {
393 if (iterator->current == NULL)
394 {
395 iterator->list->public.insert_first(&(iterator->list->public),item);
396 return;
397 }
398
399 element_t *element = element_create(item);
400 if (iterator->current->next == NULL)
401 {
402 iterator->current->next = element;
403 element->previous = iterator->current;
404 iterator->list->last = element;
405 }
406 else
407 {
408 iterator->current->next->previous = element;
409 element->next = iterator->current->next;
410 iterator->current->next = element;
411 element->previous = iterator->current;
412 }
413 iterator->list->count++;
414 }
415
416 /**
417 * Implementation of iterator_t.destroy.
418 */
419 static void iterator_destroy(private_iterator_t *this)
420 {
421 if (this->mutex)
422 {
423 pthread_mutex_unlock(this->mutex);
424 }
425 free(this);
426 }
427
428 /**
429 * Implementation of linked_list_t.get_count.
430 */
431 static int get_count(private_linked_list_t *this)
432 {
433 return this->count;
434 }
435
436 /**
437 * Implementation of linked_list_t.insert_first.
438 */
439 static void insert_first(private_linked_list_t *this, void *item)
440 {
441 element_t *element;
442
443 element = element_create(item);
444 if (this->count == 0)
445 {
446 /* first entry in list */
447 this->first = element;
448 this->last = element;
449 element->previous = NULL;
450 element->next = NULL;
451 }
452 else
453 {
454 element_t *old_first_element = this->first;
455 element->next = old_first_element;
456 element->previous = NULL;
457 old_first_element->previous = element;
458 this->first = element;
459 }
460 this->count++;
461 }
462
463 /**
464 * unlink an element form the list, returns following element
465 */
466 static element_t* remove_element(private_linked_list_t *this, element_t *element)
467 {
468 element_t *next, *previous;
469
470 next = element->next;
471 previous = element->previous;
472 free(element);
473 if (next)
474 {
475 next->previous = previous;
476 }
477 else
478 {
479 this->last = previous;
480 }
481 if (previous)
482 {
483 previous->next = next;
484 }
485 else
486 {
487 this->first = next;
488 }
489 if (--this->count == 0)
490 {
491 this->first = NULL;
492 this->last = NULL;
493 }
494 return next;
495 }
496
497 /**
498 * Implementation of linked_list_t.get_first.
499 */
500 static status_t get_first(private_linked_list_t *this, void **item)
501 {
502 if (this->count == 0)
503 {
504 return NOT_FOUND;
505 }
506 *item = this->first->value;
507 return SUCCESS;
508 }
509
510 /**
511 * Implementation of linked_list_t.remove_first.
512 */
513 static status_t remove_first(private_linked_list_t *this, void **item)
514 {
515 if (get_first(this, item) == SUCCESS)
516 {
517 remove_element(this, this->first);
518 return SUCCESS;
519 }
520 return NOT_FOUND;
521 }
522
523 /**
524 * Implementation of linked_list_t.insert_last.
525 */
526 static void insert_last(private_linked_list_t *this, void *item)
527 {
528 element_t *element = element_create(item);
529
530 if (this->count == 0)
531 {
532 /* first entry in list */
533 this->first = element;
534 this->last = element;
535 element->previous = NULL;
536 element->next = NULL;
537 }
538 else
539 {
540 element_t *old_last_element = this->last;
541 element->previous = old_last_element;
542 element->next = NULL;
543 old_last_element->next = element;
544 this->last = element;
545 }
546 this->count++;
547 }
548
549 /**
550 * Implementation of linked_list_t.get_last.
551 */
552 static status_t get_last(private_linked_list_t *this, void **item)
553 {
554 if (this->count == 0)
555 {
556 return NOT_FOUND;
557 }
558 *item = this->last->value;
559 return SUCCESS;
560 }
561
562 /**
563 * Implementation of linked_list_t.remove_last.
564 */
565 static status_t remove_last(private_linked_list_t *this, void **item)
566 {
567 if (get_last(this, item) == SUCCESS)
568 {
569 remove_element(this, this->last);
570 return SUCCESS;
571 }
572 return NOT_FOUND;
573 }
574
575 /**
576 * Implementation of linked_list_t.remove.
577 */
578 static int remove(private_linked_list_t *this, void *item,
579 bool (*compare)(void *,void*))
580 {
581 element_t *current = this->first;
582 int removed = 0;
583
584 while (current)
585 {
586 if ((compare && compare(current->value, item)) ||
587 (!compare && current->value == item))
588 {
589 removed++;
590 current = remove_element(this, current);
591 }
592 else
593 {
594 current = current->next;
595 }
596 }
597 return removed;
598 }
599
600 /**
601 * Implementation of linked_list_t.remove_at.
602 */
603 static void remove_at(private_linked_list_t *this, private_enumerator_t *enumerator)
604 {
605 if (enumerator->current)
606 {
607 remove_element(this, enumerator->current);
608 enumerator->current = NULL;
609 enumerator->next = this->first;
610 }
611 }
612
613 /**
614 * Implementation of linked_list_t.find_first.
615 */
616 static status_t find_first(private_linked_list_t *this, linked_list_match_t match,
617 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
618 {
619 element_t *current = this->first;
620
621 while (current)
622 {
623 if (match(current->value, d1, d2, d3, d4, d5))
624 {
625 if (item != NULL)
626 {
627 *item = current->value;
628 }
629 return SUCCESS;
630 }
631 current = current->next;
632 }
633 return NOT_FOUND;
634 }
635
636 /**
637 * Implementation of linked_list_t.find_last.
638 */
639 static status_t find_last(private_linked_list_t *this, linked_list_match_t match,
640 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
641 {
642 element_t *current = this->last;
643
644 while (current)
645 {
646 if (match(current->value, d1, d2, d3, d4, d5))
647 {
648 if (item != NULL)
649 {
650 *item = current->value;
651 }
652 return SUCCESS;
653 }
654 current = current->previous;
655 }
656 return NOT_FOUND;
657 }
658
659 /**
660 * Implementation of linked_list_t.invoke_offset.
661 */
662 static void invoke_offset(private_linked_list_t *this, size_t offset)
663 {
664 element_t *current = this->first;
665
666 while (current)
667 {
668 void (**method)(void*) = current->value + offset;
669 (*method)(current->value);
670 current = current->next;
671 }
672 }
673
674 /**
675 * Implementation of linked_list_t.invoke_function.
676 */
677 static void invoke_function(private_linked_list_t *this, void(*fn)(void*))
678 {
679 element_t *current = this->first;
680
681 while (current)
682 {
683 fn(current->value);
684 current = current->next;
685 }
686 }
687
688 /**
689 * Implementation of linked_list_t.clone_offset
690 */
691 static linked_list_t *clone_offset(private_linked_list_t *this, size_t offset)
692 {
693 linked_list_t *clone = linked_list_create();
694 element_t *current = this->first;
695
696 while (current)
697 {
698 void* (**method)(void*) = current->value + offset;
699 clone->insert_last(clone, (*method)(current->value));
700 current = current->next;
701 }
702
703 return clone;
704 }
705
706 /**
707 * Implementation of linked_list_t.clone_function
708 */
709 static linked_list_t *clone_function(private_linked_list_t *this, void* (*fn)(void*))
710 {
711 linked_list_t *clone = linked_list_create();
712 element_t *current = this->first;
713
714 while (current)
715 {
716 clone->insert_last(clone, fn(current->value));
717 current = current->next;
718 }
719
720 return clone;
721 }
722
723 /**
724 * Implementation of linked_list_t.destroy.
725 */
726 static void destroy(private_linked_list_t *this)
727 {
728 void *value;
729 /* Remove all list items before destroying list */
730 while (remove_first(this, &value) == SUCCESS)
731 {
732 /* values are not destroyed so memory leaks are possible
733 * if list is not empty when deleting */
734 }
735 free(this);
736 }
737
738 /**
739 * Implementation of linked_list_t.destroy_offset.
740 */
741 static void destroy_offset(private_linked_list_t *this, size_t offset)
742 {
743 element_t *current = this->first, *next;
744
745 while (current)
746 {
747 void (**method)(void*) = current->value + offset;
748 (*method)(current->value);
749 next = current->next;
750 free(current);
751 current = next;
752 }
753 free(this);
754 }
755
756 /**
757 * Implementation of linked_list_t.destroy_function.
758 */
759 static void destroy_function(private_linked_list_t *this, void (*fn)(void*))
760 {
761 element_t *current = this->first, *next;
762
763 while (current)
764 {
765 fn(current->value);
766 next = current->next;
767 free(current);
768 current = next;
769 }
770 free(this);
771 }
772
773 /**
774 * Implementation of linked_list_t.create_iterator.
775 */
776 static iterator_t *create_iterator(private_linked_list_t *linked_list, bool forward)
777 {
778 private_iterator_t *this = malloc_thing(private_iterator_t);
779
780 this->public.get_count = (int (*) (iterator_t*)) get_list_count;
781 this->public.iterate = (bool (*) (iterator_t*, void **value)) iterate;
782 this->public.set_iterator_hook = (void(*)(iterator_t*, iterator_hook_t*, void*))set_iterator_hook;
783 this->public.insert_before = (void (*) (iterator_t*, void *item)) insert_before;
784 this->public.insert_after = (void (*) (iterator_t*, void *item)) insert_after;
785 this->public.replace = (status_t (*) (iterator_t*, void **, void *)) replace;
786 this->public.remove = (status_t (*) (iterator_t*)) remove_;
787 this->public.reset = (void (*) (iterator_t*)) iterator_reset;
788 this->public.destroy = (void (*) (iterator_t*)) iterator_destroy;
789
790 this->forward = forward;
791 this->current = NULL;
792 this->list = linked_list;
793 this->mutex = NULL;
794 this->hook = iterator_hook;
795
796 return &this->public;
797 }
798
799 /**
800 * Implementation of linked_list_t.create_iterator_locked.
801 */
802 static iterator_t *create_iterator_locked(private_linked_list_t *linked_list,
803 pthread_mutex_t *mutex)
804 {
805 private_iterator_t *this = (private_iterator_t*)create_iterator(linked_list, TRUE);
806 this->mutex = mutex;
807
808 pthread_mutex_lock(mutex);
809
810 return &this->public;
811 }
812
813 /*
814 * Described in header.
815 */
816 linked_list_t *linked_list_create()
817 {
818 private_linked_list_t *this = malloc_thing(private_linked_list_t);
819
820 this->public.get_count = (int (*) (linked_list_t *)) get_count;
821 this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool))create_iterator;
822 this->public.create_iterator_locked = (iterator_t * (*) (linked_list_t *,pthread_mutex_t*))create_iterator_locked;
823 this->public.create_enumerator = (enumerator_t*(*)(linked_list_t*))create_enumerator;
824 this->public.get_first = (status_t (*) (linked_list_t *, void **item))get_first;
825 this->public.get_last = (status_t (*) (linked_list_t *, void **item))get_last;
826 this->public.find_first = (status_t (*) (linked_list_t *, linked_list_match_t,void**,...))find_first;
827 this->public.find_last = (status_t (*) (linked_list_t *, linked_list_match_t,void**,...))find_last;
828 this->public.insert_first = (void (*) (linked_list_t *, void *item))insert_first;
829 this->public.insert_last = (void (*) (linked_list_t *, void *item))insert_last;
830 this->public.remove_first = (status_t (*) (linked_list_t *, void **item))remove_first;
831 this->public.remove_last = (status_t (*) (linked_list_t *, void **item))remove_last;
832 this->public.remove = (int(*)(linked_list_t*, void *item, bool (*compare)(void *,void*)))remove;
833 this->public.remove_at = (void(*)(linked_list_t*, enumerator_t *enumerator))remove_at;
834 this->public.invoke_offset = (void (*)(linked_list_t*,size_t))invoke_offset;
835 this->public.invoke_function = (void (*)(linked_list_t*,void(*)(void*)))invoke_function;
836 this->public.clone_offset = (linked_list_t * (*)(linked_list_t*,size_t))clone_offset;
837 this->public.clone_function = (linked_list_t * (*)(linked_list_t*,void*(*)(void*)))clone_function;
838 this->public.destroy = (void (*) (linked_list_t *))destroy;
839 this->public.destroy_offset = (void (*) (linked_list_t *,size_t))destroy_offset;
840 this->public.destroy_function = (void (*)(linked_list_t*,void(*)(void*)))destroy_function;
841
842 this->count = 0;
843 this->first = NULL;
844 this->last = NULL;
845
846 return &this->public;
847 }