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