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