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