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