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