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