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