cc5590e9b37cf4d729964e8bdf9cb357d36a722b
[strongswan.git] / src / libstrongswan / utils / linked_list.c
1 /*
2 * Copyright (C) 2007-2011 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
18 #include <stdlib.h>
19
20 #include "linked_list.h"
21
22 typedef struct element_t element_t;
23
24 /**
25 * This element holds a pointer to the value it represents.
26 */
27 struct element_t {
28
29 /**
30 * Value of a list item.
31 */
32 void *value;
33
34 /**
35 * Previous list element.
36 *
37 * NULL if first element in list.
38 */
39 element_t *previous;
40
41 /**
42 * Next list element.
43 *
44 * NULL if last element in list.
45 */
46 element_t *next;
47 };
48
49 /**
50 * Creates an empty linked list object.
51 */
52 element_t *element_create(void *value)
53 {
54 element_t *this;
55 INIT(this,
56 .value = value,
57 );
58 return this;
59 }
60
61
62 typedef struct private_linked_list_t private_linked_list_t;
63
64 /**
65 * Private data of a linked_list_t object.
66 *
67 */
68 struct private_linked_list_t {
69 /**
70 * Public part of linked list.
71 */
72 linked_list_t public;
73
74 /**
75 * Number of items in the list.
76 */
77 int count;
78
79 /**
80 * First element in list.
81 * NULL if no elements in list.
82 */
83 element_t *first;
84
85 /**
86 * Last element in list.
87 * NULL if no elements in list.
88 */
89 element_t *last;
90 };
91
92
93 typedef struct private_iterator_t private_iterator_t;
94
95 /**
96 * Private variables and functions of linked list iterator.
97 */
98 struct private_iterator_t {
99 /**
100 * Public part of linked list iterator.
101 */
102 iterator_t public;
103
104 /**
105 * Associated linked list.
106 */
107 private_linked_list_t * list;
108
109 /**
110 * Current element of the iterator.
111 */
112 element_t *current;
113
114 /**
115 * Direction of iterator.
116 */
117 bool forward;
118 };
119
120 typedef struct private_enumerator_t private_enumerator_t;
121
122 /**
123 * linked lists enumerator implementation
124 */
125 struct private_enumerator_t {
126
127 /**
128 * implements enumerator interface
129 */
130 enumerator_t enumerator;
131
132 /**
133 * associated linked list
134 */
135 private_linked_list_t *list;
136
137 /**
138 * current item
139 */
140 element_t *current;
141 };
142
143 METHOD(enumerator_t, enumerate, bool,
144 private_enumerator_t *this, void **item)
145 {
146 if (!this->current)
147 {
148 this->current = this->list->first;
149 }
150 else
151 {
152 this->current = this->current->next;
153 }
154 if (!this->current)
155 {
156 return FALSE;
157 }
158 *item = this->current->value;
159 return TRUE;
160 }
161
162 METHOD(linked_list_t, create_enumerator, enumerator_t*,
163 private_linked_list_t *this)
164 {
165 private_enumerator_t *enumerator;
166
167 INIT(enumerator,
168 .enumerator = {
169 .enumerate = (void*)_enumerate,
170 .destroy = (void*)free,
171 },
172 .list = this,
173 );
174
175 return &enumerator->enumerator;
176 }
177
178 METHOD(iterator_t, iterator_get_count, int,
179 private_iterator_t *this)
180 {
181 return this->list->count;
182 }
183
184 METHOD(iterator_t, iterate, bool,
185 private_iterator_t *this, void** value)
186 {
187 if (this->forward)
188 {
189 this->current = this->current ? this->current->next : this->list->first;
190 }
191 else
192 {
193 this->current = this->current ? this->current->previous : this->list->last;
194 }
195 if (this->current == NULL)
196 {
197 return FALSE;
198 }
199 *value = this->current->value;
200 return TRUE;
201 }
202
203 METHOD(iterator_t, iterator_reset, void,
204 private_iterator_t *this)
205 {
206 this->current = NULL;
207 }
208
209 METHOD(iterator_t, iterator_remove, status_t,
210 private_iterator_t *this)
211 {
212 element_t *new_current;
213
214 if (this->current == NULL)
215 {
216 return NOT_FOUND;
217 }
218
219 if (this->list->count == 0)
220 {
221 return NOT_FOUND;
222 }
223 /* find out the new iterator position, depending on iterator direction */
224 if (this->forward && this->current->previous != NULL)
225 {
226 new_current = this->current->previous;
227 }
228 else if (!this->forward && this->current->next != NULL)
229 {
230 new_current = this->current->next;
231 }
232 else
233 {
234 new_current = NULL;
235 }
236
237 /* now delete the entry :-) */
238 if (this->current->previous == NULL)
239 {
240 if (this->current->next == NULL)
241 {
242 this->list->first = NULL;
243 this->list->last = NULL;
244 }
245 else
246 {
247 this->current->next->previous = NULL;
248 this->list->first = this->current->next;
249 }
250 }
251 else if (this->current->next == NULL)
252 {
253 this->current->previous->next = NULL;
254 this->list->last = this->current->previous;
255 }
256 else
257 {
258 this->current->previous->next = this->current->next;
259 this->current->next->previous = this->current->previous;
260 }
261
262 this->list->count--;
263 free(this->current);
264 /* set the new iterator position */
265 this->current = new_current;
266 return SUCCESS;
267 }
268
269 static void insert_item_before(private_linked_list_t *this, element_t *current,
270 void *item)
271 {
272 if (!current)
273 {
274 this->public.insert_last(&this->public, item);
275 return;
276 }
277 element_t *element = element_create(item);
278 if (current->previous)
279 {
280 current->previous->next = element;
281 element->previous = current->previous;
282 current->previous = element;
283 element->next = current;
284 }
285 else
286 {
287 current->previous = element;
288 element->next = current;
289 this->first = element;
290 }
291 this->count++;
292 }
293
294 static void insert_item_after(private_linked_list_t *this, element_t *current,
295 void *item)
296 {
297 if (!current)
298 {
299 this->public.insert_last(&this->public, item);
300 return;
301 }
302 element_t *element = element_create(item);
303 if (current->next)
304 {
305 current->next->previous = element;
306 element->next = current->next;
307 current->next = element;
308 element->previous = current;
309 }
310 else
311 {
312 current->next = element;
313 element->previous = current;
314 this->last = element;
315 }
316 this->count++;
317 }
318
319 METHOD(iterator_t, iterator_insert_before, void,
320 private_iterator_t * iterator, void *item)
321 {
322 insert_item_before(iterator->list, iterator->current, item);
323 }
324
325 METHOD(iterator_t, iterator_replace, status_t,
326 private_iterator_t *this, void **old_item, void *new_item)
327 {
328 if (this->current == NULL)
329 {
330 return NOT_FOUND;
331 }
332 if (old_item != NULL)
333 {
334 *old_item = this->current->value;
335 }
336 this->current->value = new_item;
337
338 return SUCCESS;
339 }
340
341 METHOD(iterator_t, iterator_insert_after, void,
342 private_iterator_t *iterator, void *item)
343 {
344 insert_item_after(iterator->list, iterator->current, item);
345 }
346
347 METHOD(iterator_t, iterator_destroy, void,
348 private_iterator_t *this)
349 {
350 free(this);
351 }
352
353 METHOD(linked_list_t, get_count, int,
354 private_linked_list_t *this)
355 {
356 return this->count;
357 }
358
359 METHOD(linked_list_t, insert_first, void,
360 private_linked_list_t *this, void *item)
361 {
362 element_t *element;
363
364 element = element_create(item);
365 if (this->count == 0)
366 {
367 /* first entry in list */
368 this->first = element;
369 this->last = element;
370 element->previous = NULL;
371 element->next = NULL;
372 }
373 else
374 {
375 element_t *old_first_element = this->first;
376 element->next = old_first_element;
377 element->previous = NULL;
378 old_first_element->previous = element;
379 this->first = element;
380 }
381 this->count++;
382 }
383
384 /**
385 * unlink an element form the list, returns following element
386 */
387 static element_t* remove_element(private_linked_list_t *this,
388 element_t *element)
389 {
390 element_t *next, *previous;
391
392 next = element->next;
393 previous = element->previous;
394 free(element);
395 if (next)
396 {
397 next->previous = previous;
398 }
399 else
400 {
401 this->last = previous;
402 }
403 if (previous)
404 {
405 previous->next = next;
406 }
407 else
408 {
409 this->first = next;
410 }
411 if (--this->count == 0)
412 {
413 this->first = NULL;
414 this->last = NULL;
415 }
416 return next;
417 }
418
419 METHOD(linked_list_t, get_first, status_t,
420 private_linked_list_t *this, void **item)
421 {
422 if (this->count == 0)
423 {
424 return NOT_FOUND;
425 }
426 *item = this->first->value;
427 return SUCCESS;
428 }
429
430 METHOD(linked_list_t, remove_first, status_t,
431 private_linked_list_t *this, void **item)
432 {
433 if (get_first(this, item) == SUCCESS)
434 {
435 remove_element(this, this->first);
436 return SUCCESS;
437 }
438 return NOT_FOUND;
439 }
440
441 METHOD(linked_list_t, insert_last, void,
442 private_linked_list_t *this, void *item)
443 {
444 element_t *element = element_create(item);
445
446 if (this->count == 0)
447 {
448 /* first entry in list */
449 this->first = element;
450 this->last = element;
451 element->previous = NULL;
452 element->next = NULL;
453 }
454 else
455 {
456 element_t *old_last_element = this->last;
457 element->previous = old_last_element;
458 element->next = NULL;
459 old_last_element->next = element;
460 this->last = element;
461 }
462 this->count++;
463 }
464
465 METHOD(linked_list_t, insert_before, void,
466 private_linked_list_t *this, private_enumerator_t *enumerator,
467 void *item)
468 {
469 insert_item_before(this, enumerator->current, item);
470 }
471
472 METHOD(linked_list_t, insert_after, void,
473 private_linked_list_t *this, private_enumerator_t *enumerator,
474 void *item)
475 {
476 insert_item_after(this, enumerator->current, item);
477 }
478
479 METHOD(linked_list_t, get_last, status_t,
480 private_linked_list_t *this, void **item)
481 {
482 if (this->count == 0)
483 {
484 return NOT_FOUND;
485 }
486 *item = this->last->value;
487 return SUCCESS;
488 }
489
490 METHOD(linked_list_t, remove_last, status_t,
491 private_linked_list_t *this, void **item)
492 {
493 if (get_last(this, item) == SUCCESS)
494 {
495 remove_element(this, this->last);
496 return SUCCESS;
497 }
498 return NOT_FOUND;
499 }
500
501 METHOD(linked_list_t, remove_, int,
502 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
503 {
504 element_t *current = this->first;
505 int removed = 0;
506
507 while (current)
508 {
509 if ((compare && compare(current->value, item)) ||
510 (!compare && current->value == item))
511 {
512 removed++;
513 current = remove_element(this, current);
514 }
515 else
516 {
517 current = current->next;
518 }
519 }
520 return removed;
521 }
522
523 METHOD(linked_list_t, remove_at, void,
524 private_linked_list_t *this, private_enumerator_t *enumerator)
525 {
526 element_t *current;
527
528 if (enumerator->current)
529 {
530 current = enumerator->current;
531 enumerator->current = current->previous;
532 remove_element(this, current);
533 }
534 }
535
536 METHOD(linked_list_t, find_first, status_t,
537 private_linked_list_t *this, linked_list_match_t match,
538 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
539 {
540 element_t *current = this->first;
541
542 while (current)
543 {
544 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
545 (!match && item && current->value == *item))
546 {
547 if (item != NULL)
548 {
549 *item = current->value;
550 }
551 return SUCCESS;
552 }
553 current = current->next;
554 }
555 return NOT_FOUND;
556 }
557
558 METHOD(linked_list_t, find_last, status_t,
559 private_linked_list_t *this, linked_list_match_t match,
560 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
561 {
562 element_t *current = this->last;
563
564 while (current)
565 {
566 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
567 (!match && item && current->value == *item))
568 {
569 if (item != NULL)
570 {
571 *item = current->value;
572 }
573 return SUCCESS;
574 }
575 current = current->previous;
576 }
577 return NOT_FOUND;
578 }
579
580 METHOD(linked_list_t, invoke_offset, void,
581 private_linked_list_t *this, size_t offset,
582 void *d1, void *d2, void *d3, void *d4, void *d5)
583 {
584 element_t *current = this->first;
585
586 while (current)
587 {
588 linked_list_invoke_t *method = current->value + offset;
589 (*method)(current->value, d1, d2, d3, d4, d5);
590 current = current->next;
591 }
592 }
593
594 METHOD(linked_list_t, invoke_function, void,
595 private_linked_list_t *this, linked_list_invoke_t fn,
596 void *d1, void *d2, void *d3, void *d4, void *d5)
597 {
598 element_t *current = this->first;
599
600 while (current)
601 {
602 fn(current->value, d1, d2, d3, d4, d5);
603 current = current->next;
604 }
605 }
606
607 METHOD(linked_list_t, clone_offset, linked_list_t*,
608 private_linked_list_t *this, size_t offset)
609 {
610 linked_list_t *clone = linked_list_create();
611 element_t *current = this->first;
612
613 while (current)
614 {
615 void* (**method)(void*) = current->value + offset;
616 clone->insert_last(clone, (*method)(current->value));
617 current = current->next;
618 }
619
620 return clone;
621 }
622
623 METHOD(linked_list_t, clone_function, linked_list_t*,
624 private_linked_list_t *this, void* (*fn)(void*))
625 {
626 linked_list_t *clone = linked_list_create();
627 element_t *current = this->first;
628
629 while (current)
630 {
631 clone->insert_last(clone, fn(current->value));
632 current = current->next;
633 }
634
635 return clone;
636 }
637
638 METHOD(linked_list_t, destroy, void,
639 private_linked_list_t *this)
640 {
641 void *value;
642 /* Remove all list items before destroying list */
643 while (remove_first(this, &value) == SUCCESS)
644 {
645 /* values are not destroyed so memory leaks are possible
646 * if list is not empty when deleting */
647 }
648 free(this);
649 }
650
651 METHOD(linked_list_t, destroy_offset, void,
652 private_linked_list_t *this, size_t offset)
653 {
654 element_t *current = this->first, *next;
655
656 while (current)
657 {
658 void (**method)(void*) = current->value + offset;
659 (*method)(current->value);
660 next = current->next;
661 free(current);
662 current = next;
663 }
664 free(this);
665 }
666
667 METHOD(linked_list_t, destroy_function, void,
668 private_linked_list_t *this, void (*fn)(void*))
669 {
670 element_t *current = this->first, *next;
671
672 while (current)
673 {
674 fn(current->value);
675 next = current->next;
676 free(current);
677 current = next;
678 }
679 free(this);
680 }
681
682 METHOD(linked_list_t, create_iterator, iterator_t*,
683 private_linked_list_t *linked_list, bool forward)
684 {
685 private_iterator_t *this;
686
687 INIT(this,
688 .public = {
689 .get_count = _iterator_get_count,
690 .iterate = _iterate,
691 .insert_before = _iterator_insert_before,
692 .insert_after = _iterator_insert_after,
693 .replace = _iterator_replace,
694 .remove = _iterator_remove,
695 .reset = _iterator_reset,
696 .destroy = _iterator_destroy,
697 },
698 .forward = forward,
699 .list = linked_list,
700 );
701
702 return &this->public;
703 }
704
705 /*
706 * Described in header.
707 */
708 linked_list_t *linked_list_create()
709 {
710 private_linked_list_t *this;
711
712 INIT(this,
713 .public = {
714 .get_count = _get_count,
715 .create_iterator = _create_iterator,
716 .create_enumerator = _create_enumerator,
717 .get_first = _get_first,
718 .get_last = _get_last,
719 .find_first = (void*)_find_first,
720 .find_last = (void*)_find_last,
721 .insert_first = _insert_first,
722 .insert_last = _insert_last,
723 .insert_after = (void*)_insert_after,
724 .insert_before = (void*)_insert_before,
725 .remove_first = _remove_first,
726 .remove_last = _remove_last,
727 .remove = _remove_,
728 .remove_at = (void*)_remove_at,
729 .invoke_offset = (void*)_invoke_offset,
730 .invoke_function = (void*)_invoke_function,
731 .clone_offset = _clone_offset,
732 .clone_function = _clone_function,
733 .destroy = _destroy,
734 .destroy_offset = _destroy_offset,
735 .destroy_function = _destroy_function,
736 },
737 );
738
739 return &this->public;
740 }