69e0ffc12e0d6e453a1c720482d4bb4e50d7b751
[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 /**
365 * Implementation of linked_list_t.insert_first.
366 */
367 static void insert_first(private_linked_list_t *this, void *item)
368 {
369 linked_list_element_t *element;
370
371 element =(linked_list_element_t *) linked_list_element_create(item);
372
373 if (this->count == 0)
374 {
375 /* first entry in list */
376 this->first = element;
377 this->last = element;
378 element->previous = NULL;
379 element->next = NULL;
380 }
381 else
382 {
383 linked_list_element_t *old_first_element = this->first;
384 element->next = old_first_element;
385 element->previous = NULL;
386 old_first_element->previous = element;
387 this->first = element;
388 }
389
390 this->count++;
391 }
392
393 /**
394 * Implementation of linked_list_t.remove_first.
395 */
396 static status_t remove_first(private_linked_list_t *this, void **item)
397 {
398 if (this->count == 0)
399 {
400 return NOT_FOUND;
401 }
402
403 linked_list_element_t *element = this->first;
404
405 if (element->next != NULL)
406 {
407 element->next->previous = NULL;
408 }
409 this->first = element->next;
410
411 *item = element->value;
412
413 this->count--;
414
415 element->destroy(element);
416
417 return SUCCESS;
418 }
419
420 /**
421 * Implementation of linked_list_t.get_first.
422 */
423 static status_t get_first(private_linked_list_t *this, void **item)
424 {
425 if (this->count == 0)
426 {
427 return NOT_FOUND;
428 }
429
430 *item = this->first->value;
431
432 return SUCCESS;
433 }
434
435 /**
436 * Implementation of linked_list_t.insert_last.
437 */
438 static void insert_last(private_linked_list_t *this, void *item)
439 {
440 linked_list_element_t *element = (linked_list_element_t *) linked_list_element_create(item);
441
442 if (this->count == 0)
443 {
444 /* first entry in list */
445 this->first = element;
446 this->last = element;
447 element->previous = NULL;
448 element->next = NULL;
449 }
450 else
451 {
452
453 linked_list_element_t *old_last_element = this->last;
454 element->previous = old_last_element;
455 element->next = NULL;
456 old_last_element->next = element;
457 this->last = element;
458 }
459
460 this->count++;
461 }
462
463 /**
464 * Implementation of linked_list_t.remove_last.
465 */
466 static status_t remove_last(private_linked_list_t *this, void **item)
467 {
468 if (this->count == 0)
469 {
470 return NOT_FOUND;
471 }
472
473 linked_list_element_t *element = this->last;
474
475 if (element->previous != NULL)
476 {
477 element->previous->next = NULL;
478 }
479 this->last = element->previous;
480
481 *item = element->value;
482
483 this->count--;
484
485 element->destroy(element);
486
487 return SUCCESS;
488 }
489
490 /**
491 * Implementation of linked_list_t.insert_at_position.
492 */
493 static status_t insert_at_position (private_linked_list_t *this,size_t position, void *item)
494 {
495 linked_list_element_t *current_element;
496 int i;
497
498 if (this->count <= position)
499 {
500 return INVALID_ARG;
501 }
502
503 current_element = this->first;
504
505 for (i = 0; i < position;i++)
506 {
507 current_element = current_element->next;
508 }
509
510 if (current_element == NULL)
511 {
512 this->public.insert_last(&(this->public),item);
513 return SUCCESS;
514 }
515
516 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
517
518
519 if (current_element->previous == NULL)
520 {
521 current_element->previous = element;
522 element->next = current_element;
523 this->first = element;
524 }
525 else
526 {
527 current_element->previous->next = element;
528 element->previous = current_element->previous;
529 current_element->previous = element;
530 element->next = current_element;
531 }
532
533
534 this->count++;
535 return SUCCESS;
536 }
537
538 /**
539 * Implementation of linked_list_t.remove_at_position.
540 */
541 static status_t remove_at_position (private_linked_list_t *this,size_t position, void **item)
542 {
543 iterator_t *iterator;
544 int i;
545
546 if (this->count <= position)
547 {
548 return INVALID_ARG;
549 }
550
551 iterator = this->public.create_iterator(&(this->public),TRUE);
552
553 iterator->has_next(iterator);
554 for (i = 0; i < position;i++)
555 {
556 iterator->has_next(iterator);
557 }
558 iterator->current(iterator,item);
559 iterator->remove(iterator);
560 iterator->destroy(iterator);
561
562 return SUCCESS;
563 }
564
565 /**
566 * Implementation of linked_list_t.get_at_position.
567 */
568 static status_t get_at_position (private_linked_list_t *this,size_t position, void **item)
569 {
570 int i;
571 iterator_t *iterator;
572 status_t status;
573 if (this->count <= position)
574 {
575 return INVALID_ARG;
576 }
577
578 iterator = this->public.create_iterator(&(this->public),TRUE);
579
580 iterator->has_next(iterator);
581 for (i = 0; i < position;i++)
582 {
583 iterator->has_next(iterator);
584 }
585 status = iterator->current(iterator,item);
586 iterator->destroy(iterator);
587 return status;
588 }
589
590 /**
591 * Implementation of linked_list_t.get_last.
592 */
593 static status_t get_last(private_linked_list_t *this, void **item)
594 {
595 if (this->count == 0)
596 {
597 return NOT_FOUND;
598 }
599
600 *item = this->last->value;
601
602 return SUCCESS;
603 }
604
605 /**
606 * Implementation of linked_list_t.create_iterator.
607 */
608 static iterator_t *create_iterator (private_linked_list_t *linked_list,bool forward)
609 {
610 private_iterator_t *this = allocator_alloc_thing(private_iterator_t);
611
612 this->public.has_next = (bool (*) (iterator_t *this)) iterator_has_next;
613 this->public.current = (status_t (*) (iterator_t *this, void **value)) iterator_current;
614 this->public.insert_before = (void (*) (iterator_t *this, void *item)) insert_before;
615 this->public.insert_after = (void (*) (iterator_t *this, void *item)) insert_after;
616 this->public.replace = (status_t (*) (iterator_t *, void **, void *)) replace;
617 this->public.remove = (status_t (*) (iterator_t *this)) remove;
618 this->public.reset = (void (*) (iterator_t *this)) iterator_reset;
619 this->public.destroy = (void (*) (iterator_t *this)) iterator_destroy;
620
621 this->forward = forward;
622 this->current = NULL;
623 this->list = linked_list;
624
625 return &(this->public);
626 }
627
628 /**
629 * Implementation of linked_list_t.destroy.
630 */
631 static void linked_list_destroy(private_linked_list_t *this)
632 {
633 void * value;
634 /* Remove all list items before destroying list */
635 while (this->public.remove_first(&(this->public),&value) != NOT_FOUND)
636 {
637 /* values are not destroyed so memory leaks are possible
638 * if list is not empty when deleting */
639 }
640 allocator_free(this);
641 }
642
643 /*
644 * Described in header.
645 */
646 linked_list_t *linked_list_create()
647 {
648 private_linked_list_t *this = allocator_alloc_thing(private_linked_list_t);
649
650 this->public.get_count = (int (*) (linked_list_t *)) get_count;
651 this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool )) create_iterator;
652 this->public.get_first = (status_t (*) (linked_list_t *, void **item)) get_first;
653 this->public.get_last = (status_t (*) (linked_list_t *, void **item)) get_last;
654 this->public.insert_first = (void (*) (linked_list_t *, void *item)) insert_first;
655 this->public.insert_last = (void (*) (linked_list_t *, void *item)) insert_last;
656 this->public.remove_first = (status_t (*) (linked_list_t *, void **item)) remove_first;
657 this->public.remove_last = (status_t (*) (linked_list_t *, void **item)) remove_last;
658 this->public.insert_at_position =(status_t (*) (linked_list_t *,size_t, void *)) insert_at_position;
659 this->public.remove_at_position =(status_t (*) (linked_list_t *,size_t, void **)) remove_at_position;
660 this->public.get_at_position =(status_t (*) (linked_list_t *,size_t, void **)) get_at_position;
661
662 this->public.destroy = (void (*) (linked_list_t *)) linked_list_destroy;
663
664 this->count = 0;
665 this->first = NULL;
666 this->last = NULL;
667
668 return (&(this->public));
669 }