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