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