removed deprecated iterator methods (has_next & current)
[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->hook(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 if (this->count == 0)
396 {
397 return NOT_FOUND;
398 }
399
400 element_t *element = this->first;
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 this->count--;
412 free(element);
413 return SUCCESS;
414 }
415
416 /**
417 * Implementation of linked_list_t.get_first.
418 */
419 static status_t get_first(private_linked_list_t *this, void **item)
420 {
421 if (this->count == 0)
422 {
423 return NOT_FOUND;
424 }
425 *item = this->first->value;
426 return SUCCESS;
427 }
428
429 /**
430 * Implementation of linked_list_t.insert_last.
431 */
432 static void insert_last(private_linked_list_t *this, void *item)
433 {
434 element_t *element = element_create(item);
435
436 if (this->count == 0)
437 {
438 /* first entry in list */
439 this->first = element;
440 this->last = element;
441 element->previous = NULL;
442 element->next = NULL;
443 }
444 else
445 {
446 element_t *old_last_element = this->last;
447 element->previous = old_last_element;
448 element->next = NULL;
449 old_last_element->next = element;
450 this->last = element;
451 }
452 this->count++;
453 }
454
455 /**
456 * Implementation of linked_list_t.remove_last.
457 */
458 static status_t remove_last(private_linked_list_t *this, void **item)
459 {
460 if (this->count == 0)
461 {
462 return NOT_FOUND;
463 }
464
465 element_t *element = this->last;
466
467 if (element->previous != NULL)
468 {
469 element->previous->next = NULL;
470 }
471 this->last = element->previous;
472
473 if (item != NULL)
474 {
475 *item = element->value;
476 }
477
478 this->count--;
479 free(element);
480 return SUCCESS;
481 }
482
483 /**
484 * Implementation of linked_list_t.insert_at_position.
485 */
486 static status_t insert_at_position (private_linked_list_t *this,size_t position, void *item)
487 {
488 element_t *current_element;
489 int i;
490
491 if (this->count <= position)
492 {
493 return INVALID_ARG;
494 }
495
496 current_element = this->first;
497
498 for (i = 0; i < position;i++)
499 {
500 current_element = current_element->next;
501 }
502
503 if (current_element == NULL)
504 {
505 this->public.insert_last(&(this->public),item);
506 return SUCCESS;
507 }
508
509 element_t *element = element_create(item);
510 if (current_element->previous == NULL)
511 {
512 current_element->previous = element;
513 element->next = current_element;
514 this->first = element;
515 }
516 else
517 {
518 current_element->previous->next = element;
519 element->previous = current_element->previous;
520 current_element->previous = element;
521 element->next = current_element;
522 }
523
524
525 this->count++;
526 return SUCCESS;
527 }
528
529 /**
530 * Implementation of linked_list_t.remove_at_position.
531 */
532 static status_t remove_at_position(private_linked_list_t *this,size_t position, void **item)
533 {
534 iterator_t *iterator;
535 int i;
536
537 if (this->count <= position)
538 {
539 return INVALID_ARG;
540 }
541
542 iterator = this->public.create_iterator(&(this->public),TRUE);
543 iterator->iterate(iterator, item);
544 for (i = 0; i < position; i++)
545 {
546 if (!iterator->iterate(iterator, item))
547 {
548 iterator->destroy(iterator);
549 return INVALID_ARG;
550 }
551 }
552 iterator->remove(iterator);
553 iterator->destroy(iterator);
554
555 return SUCCESS;
556 }
557
558 /**
559 * Implementation of linked_list_t.get_at_position.
560 */
561 static status_t get_at_position(private_linked_list_t *this,size_t position, void **item)
562 {
563 int i;
564 iterator_t *iterator;
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->destroy(iterator);
582 return SUCCESS;
583 }
584
585 /**
586 * Implementation of linked_list_t.get_last.
587 */
588 static status_t get_last(private_linked_list_t *this, void **item)
589 {
590 if (this->count == 0)
591 {
592 return NOT_FOUND;
593 }
594
595 *item = this->last->value;
596
597 return SUCCESS;
598 }
599
600 /**
601 * Implementation of linked_list_t.invoke.
602 */
603 static void invoke(private_linked_list_t *this, size_t offset)
604 {
605 element_t *current = this->first;
606
607 while (current)
608 {
609 void (**method)(void*) = current->value + offset;
610 (*method)(current->value);
611 current = current->next;
612 }
613 }
614
615 /**
616 * Implementation of linked_list_t.destroy.
617 */
618 static void destroy(private_linked_list_t *this)
619 {
620 void *value;
621 /* Remove all list items before destroying list */
622 while (this->public.remove_first(&(this->public), &value) == SUCCESS)
623 {
624 /* values are not destroyed so memory leaks are possible
625 * if list is not empty when deleting */
626 }
627 free(this);
628 }
629
630 /**
631 * Implementation of linked_list_t.destroy_offset.
632 */
633 static void destroy_offset(private_linked_list_t *this, size_t offset)
634 {
635 element_t *current = this->first, *next;
636
637 while (current)
638 {
639 void (**method)(void*) = current->value + offset;
640 (*method)(current->value);
641 next = current->next;
642 free(current);
643 current = next;
644 }
645 free(this);
646 }
647
648 /**
649 * Implementation of linked_list_t.destroy_function.
650 */
651 static void destroy_function(private_linked_list_t *this, void (*fn)(void*))
652 {
653 element_t *current = this->first, *next;
654
655 while (current)
656 {
657 fn(current->value);
658 next = current->next;
659 free(current);
660 current = next;
661 }
662 free(this);
663 }
664
665 /**
666 * Implementation of linked_list_t.create_iterator.
667 */
668 static iterator_t *create_iterator(private_linked_list_t *linked_list, bool forward)
669 {
670 private_iterator_t *this = malloc_thing(private_iterator_t);
671
672 this->public.get_count = (bool (*) (iterator_t *this)) get_list_count;
673 this->public.iterate = (bool (*) (iterator_t *this, void **value)) iterate;
674 this->public.set_iterator_hook = (void(*)(iterator_t *this, void*(*)(void*)))set_iterator_hook;
675 this->public.insert_before = (void (*) (iterator_t *this, void *item)) insert_before;
676 this->public.insert_after = (void (*) (iterator_t *this, void *item)) insert_after;
677 this->public.replace = (status_t (*) (iterator_t *, void **, void *)) replace;
678 this->public.remove = (status_t (*) (iterator_t *this)) remove_;
679 this->public.reset = (void (*) (iterator_t *this)) iterator_reset;
680 this->public.destroy = (void (*) (iterator_t *this)) iterator_destroy;
681
682 this->forward = forward;
683 this->current = NULL;
684 this->list = linked_list;
685 this->mutex = NULL;
686 this->hook = iterator_hook;
687
688 return &this->public;
689 }
690
691 /**
692 * Implementation of linked_list_t.create_iterator_locked.
693 */
694 static iterator_t *create_iterator_locked(private_linked_list_t *linked_list,
695 pthread_mutex_t *mutex)
696 {
697 private_iterator_t *this = (private_iterator_t*)create_iterator(linked_list, TRUE);
698 this->mutex = mutex;
699
700 pthread_mutex_lock(mutex);
701
702 return &this->public;
703 }
704
705 /*
706 * Described in header.
707 */
708 linked_list_t *linked_list_create()
709 {
710 private_linked_list_t *this = malloc_thing(private_linked_list_t);
711
712 this->public.get_count = (int (*) (linked_list_t *)) get_count;
713 this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool))create_iterator;
714 this->public.create_iterator_locked = (iterator_t * (*) (linked_list_t *,pthread_mutex_t*))create_iterator_locked;
715 this->public.get_first = (status_t (*) (linked_list_t *, void **item))get_first;
716 this->public.get_last = (status_t (*) (linked_list_t *, void **item))get_last;
717 this->public.insert_first = (void (*) (linked_list_t *, void *item))insert_first;
718 this->public.insert_last = (void (*) (linked_list_t *, void *item))insert_last;
719 this->public.remove_first = (status_t (*) (linked_list_t *, void **item))remove_first;
720 this->public.remove_last = (status_t (*) (linked_list_t *, void **item))remove_last;
721 this->public.insert_at_position = (status_t (*) (linked_list_t *,size_t, void *))insert_at_position;
722 this->public.remove_at_position = (status_t (*) (linked_list_t *,size_t, void **))remove_at_position;
723 this->public.get_at_position = (status_t (*) (linked_list_t *,size_t, void **))get_at_position;
724 this->public.invoke = (void (*)(linked_list_t*,size_t))invoke;
725 this->public.destroy = (void (*) (linked_list_t *))destroy;
726 this->public.destroy_offset = (void (*) (linked_list_t *,size_t))destroy_offset;
727 this->public.destroy_function = (void (*)(linked_list_t*,void(*)(void*)))destroy_function;
728
729 this->count = 0;
730 this->first = NULL;
731 this->last = NULL;
732
733 return &this->public;
734 }