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