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