- applied patch from andreas, which allows certificate listing via stroke
[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 if (this->current->next != NULL)
272 {
273 new_current = this->current->next;
274 }
275 else
276 {
277 new_current = NULL;
278 }
279
280 /* now delete the entry :-) */
281 if (this->current->previous == NULL)
282 {
283 if (this->current->next == NULL)
284 {
285 this->list->first = NULL;
286 this->list->last = NULL;
287 }
288 else
289 {
290 this->current->next->previous = NULL;
291 this->list->first = this->current->next;
292 }
293 }
294 else if (this->current->next == NULL)
295 {
296 this->current->previous->next = NULL;
297 this->list->last = this->current->previous;
298 }
299 else
300 {
301 this->current->previous->next = this->current->next;
302 this->current->next->previous = this->current->previous;
303 }
304
305 this->list->count--;
306 this->current->destroy(this->current);
307 /* set the new iterator position */
308 this->current = new_current;
309 return SUCCESS;
310 }
311
312 /**
313 * Implementation of iterator_t.insert_before.
314 */
315 static void insert_before(private_iterator_t * iterator, void *item)
316 {
317 if (iterator->current == NULL)
318 {
319 iterator->list->public.insert_first(&(iterator->list->public), item);
320 }
321
322 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
323
324 if (iterator->current->previous == NULL)
325 {
326 iterator->current->previous = element;
327 element->next = iterator->current;
328 iterator->list->first = element;
329 }
330 else
331 {
332 iterator->current->previous->next = element;
333 element->previous = iterator->current->previous;
334 iterator->current->previous = element;
335 element->next = iterator->current;
336 }
337
338 iterator->list->count++;
339 }
340
341 /**
342 * Implementation of iterator_t.replace.
343 */
344 static status_t replace (private_iterator_t *this, void **old_item, void *new_item)
345 {
346 if (this->current == NULL)
347 {
348 return NOT_FOUND;
349 }
350 if (old_item != NULL)
351 {
352 *old_item = this->current->value;
353 }
354 this->current->value = new_item;
355
356 return SUCCESS;
357 }
358
359 /**
360 * Implementation of iterator_t.insert_after.
361 */
362 static void insert_after(private_iterator_t * iterator, void *item)
363 {
364 if (iterator->current == NULL)
365 {
366 iterator->list->public.insert_first(&(iterator->list->public),item);
367 return;
368 }
369
370 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
371
372 if (iterator->current->next == NULL)
373 {
374 iterator->current->next = element;
375 element->previous = iterator->current;
376 iterator->list->last = element;
377 }
378 else
379 {
380 iterator->current->next->previous = element;
381 element->next = iterator->current->next;
382 iterator->current->next = element;
383 element->previous = iterator->current;
384 }
385 iterator->list->count++;
386 }
387
388 /**
389 * Implementation of iterator_t.destroy.
390 */
391 static void iterator_destroy(private_iterator_t *this)
392 {
393 free(this);
394 }
395
396 /**
397 * Implementation of linked_list_t.get_count.
398 */
399 static int get_count(private_linked_list_t *this)
400 {
401 return this->count;
402 }
403
404 /**
405 * Implementation of linked_list_t.call_on_items.
406 */
407 static void call_on_items(private_linked_list_t *this, void(*func)(void*))
408 {
409 iterator_t *iterator;
410 void *item;
411
412 iterator = this->public.create_iterator(&(this->public),TRUE);
413
414 while (iterator->has_next(iterator))
415 {
416 iterator->current(iterator, &item);
417 (*func)(item);
418 }
419 iterator->destroy(iterator);
420 }
421
422 /**
423 * Implementation of linked_list_t.insert_first.
424 */
425 static void insert_first(private_linked_list_t *this, void *item)
426 {
427 linked_list_element_t *element;
428
429 element =(linked_list_element_t *) linked_list_element_create(item);
430
431 if (this->count == 0)
432 {
433 /* first entry in list */
434 this->first = element;
435 this->last = element;
436 element->previous = NULL;
437 element->next = NULL;
438 }
439 else
440 {
441 linked_list_element_t *old_first_element = this->first;
442 element->next = old_first_element;
443 element->previous = NULL;
444 old_first_element->previous = element;
445 this->first = element;
446 }
447
448 this->count++;
449 }
450
451 /**
452 * Implementation of linked_list_t.remove_first.
453 */
454 static status_t remove_first(private_linked_list_t *this, void **item)
455 {
456 if (this->count == 0)
457 {
458 return NOT_FOUND;
459 }
460
461 linked_list_element_t *element = this->first;
462
463 if (element->next != NULL)
464 {
465 element->next->previous = NULL;
466 }
467 this->first = element->next;
468
469 if (item != NULL)
470 {
471 *item = element->value;
472 }
473
474 this->count--;
475
476 element->destroy(element);
477
478 return SUCCESS;
479 }
480
481 /**
482 * Implementation of linked_list_t.get_first.
483 */
484 static status_t get_first(private_linked_list_t *this, void **item)
485 {
486 if (this->count == 0)
487 {
488 return NOT_FOUND;
489 }
490
491 *item = this->first->value;
492
493 return SUCCESS;
494 }
495
496 /**
497 * Implementation of linked_list_t.insert_last.
498 */
499 static void insert_last(private_linked_list_t *this, void *item)
500 {
501 linked_list_element_t *element = (linked_list_element_t *) linked_list_element_create(item);
502
503 if (this->count == 0)
504 {
505 /* first entry in list */
506 this->first = element;
507 this->last = element;
508 element->previous = NULL;
509 element->next = NULL;
510 }
511 else
512 {
513
514 linked_list_element_t *old_last_element = this->last;
515 element->previous = old_last_element;
516 element->next = NULL;
517 old_last_element->next = element;
518 this->last = element;
519 }
520
521 this->count++;
522 }
523
524 /**
525 * Implementation of linked_list_t.remove_last.
526 */
527 static status_t remove_last(private_linked_list_t *this, void **item)
528 {
529 if (this->count == 0)
530 {
531 return NOT_FOUND;
532 }
533
534 linked_list_element_t *element = this->last;
535
536 if (element->previous != NULL)
537 {
538 element->previous->next = NULL;
539 }
540 this->last = element->previous;
541
542 if (item != NULL)
543 {
544 *item = element->value;
545 }
546
547 this->count--;
548
549 element->destroy(element);
550
551 return SUCCESS;
552 }
553
554 /**
555 * Implementation of linked_list_t.insert_at_position.
556 */
557 static status_t insert_at_position (private_linked_list_t *this,size_t position, void *item)
558 {
559 linked_list_element_t *current_element;
560 int i;
561
562 if (this->count <= position)
563 {
564 return INVALID_ARG;
565 }
566
567 current_element = this->first;
568
569 for (i = 0; i < position;i++)
570 {
571 current_element = current_element->next;
572 }
573
574 if (current_element == NULL)
575 {
576 this->public.insert_last(&(this->public),item);
577 return SUCCESS;
578 }
579
580 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
581
582
583 if (current_element->previous == NULL)
584 {
585 current_element->previous = element;
586 element->next = current_element;
587 this->first = element;
588 }
589 else
590 {
591 current_element->previous->next = element;
592 element->previous = current_element->previous;
593 current_element->previous = element;
594 element->next = current_element;
595 }
596
597
598 this->count++;
599 return SUCCESS;
600 }
601
602 /**
603 * Implementation of linked_list_t.remove_at_position.
604 */
605 static status_t remove_at_position (private_linked_list_t *this,size_t position, void **item)
606 {
607 iterator_t *iterator;
608 int i;
609
610 if (this->count <= position)
611 {
612 return INVALID_ARG;
613 }
614
615 iterator = this->public.create_iterator(&(this->public),TRUE);
616
617 iterator->has_next(iterator);
618 for (i = 0; i < position;i++)
619 {
620 iterator->has_next(iterator);
621 }
622 iterator->current(iterator,item);
623 iterator->remove(iterator);
624 iterator->destroy(iterator);
625
626 return SUCCESS;
627 }
628
629 /**
630 * Implementation of linked_list_t.get_at_position.
631 */
632 static status_t get_at_position (private_linked_list_t *this,size_t position, void **item)
633 {
634 int i;
635 iterator_t *iterator;
636 status_t status;
637 if (this->count <= position)
638 {
639 return INVALID_ARG;
640 }
641
642 iterator = this->public.create_iterator(&(this->public),TRUE);
643
644 iterator->has_next(iterator);
645 for (i = 0; i < position;i++)
646 {
647 iterator->has_next(iterator);
648 }
649 status = iterator->current(iterator,item);
650 iterator->destroy(iterator);
651 return status;
652 }
653
654 /**
655 * Implementation of linked_list_t.get_last.
656 */
657 static status_t get_last(private_linked_list_t *this, void **item)
658 {
659 if (this->count == 0)
660 {
661 return NOT_FOUND;
662 }
663
664 *item = this->last->value;
665
666 return SUCCESS;
667 }
668
669 /**
670 * Implementation of linked_list_t.create_iterator.
671 */
672 static iterator_t *create_iterator (private_linked_list_t *linked_list,bool forward)
673 {
674 private_iterator_t *this = malloc_thing(private_iterator_t);
675
676 this->public.get_count = (bool (*) (iterator_t *this)) get_list_count;
677 this->public.iterate = (bool (*) (iterator_t *this, void **value)) iterate;
678 this->public.has_next = (bool (*) (iterator_t *this)) iterator_has_next;
679 this->public.current = (status_t (*) (iterator_t *this, void **value)) iterator_current;
680 this->public.insert_before = (void (*) (iterator_t *this, void *item)) insert_before;
681 this->public.insert_after = (void (*) (iterator_t *this, void *item)) insert_after;
682 this->public.replace = (status_t (*) (iterator_t *, void **, void *)) replace;
683 this->public.remove = (status_t (*) (iterator_t *this)) remove;
684 this->public.reset = (void (*) (iterator_t *this)) iterator_reset;
685 this->public.destroy = (void (*) (iterator_t *this)) iterator_destroy;
686
687 this->forward = forward;
688 this->current = NULL;
689 this->list = linked_list;
690
691 return &(this->public);
692 }
693
694 /**
695 * Implementation of linked_list_t.destroy.
696 */
697 static void linked_list_destroy(private_linked_list_t *this)
698 {
699 void * value;
700 /* Remove all list items before destroying list */
701 while (this->public.remove_first(&(this->public),&value) != NOT_FOUND)
702 {
703 /* values are not destroyed so memory leaks are possible
704 * if list is not empty when deleting */
705 }
706 free(this);
707 }
708
709 /*
710 * Described in header.
711 */
712 linked_list_t *linked_list_create()
713 {
714 private_linked_list_t *this = malloc_thing(private_linked_list_t);
715
716 this->public.get_count = (int (*) (linked_list_t *)) get_count;
717 this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool )) create_iterator;
718 this->public.call_on_items = (void (*) (linked_list_t *, void(*func)(void*)))call_on_items;
719 this->public.get_first = (status_t (*) (linked_list_t *, void **item)) get_first;
720 this->public.get_last = (status_t (*) (linked_list_t *, void **item)) get_last;
721 this->public.insert_first = (void (*) (linked_list_t *, void *item)) insert_first;
722 this->public.insert_last = (void (*) (linked_list_t *, void *item)) insert_last;
723 this->public.remove_first = (status_t (*) (linked_list_t *, void **item)) remove_first;
724 this->public.remove_last = (status_t (*) (linked_list_t *, void **item)) remove_last;
725 this->public.insert_at_position =(status_t (*) (linked_list_t *,size_t, void *)) insert_at_position;
726 this->public.remove_at_position =(status_t (*) (linked_list_t *,size_t, void **)) remove_at_position;
727 this->public.get_at_position =(status_t (*) (linked_list_t *,size_t, void **)) get_at_position;
728
729 this->public.destroy = (void (*) (linked_list_t *)) linked_list_destroy;
730
731 this->count = 0;
732 this->first = NULL;
733 this->last = NULL;
734
735 return (&(this->public));
736 }