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