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