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