Merge branch 'variadic-enumerators'
[strongswan.git] / src / libstrongswan / collections / linked_list.c
1 /*
2 * Copyright (C) 2007-2015 Tobias Brunner
3 * Copyright (C) 2005-2006 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * Hochschule fuer Technik Rapperswil
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 #include <stdlib.h>
19 #include <stdarg.h>
20
21 #include "linked_list.h"
22
23 typedef struct element_t element_t;
24
25 /**
26 * This element holds a pointer to the value it represents.
27 */
28 struct element_t {
29
30 /**
31 * Value of a list item.
32 */
33 void *value;
34
35 /**
36 * Previous list element.
37 *
38 * NULL if first element in list.
39 */
40 element_t *previous;
41
42 /**
43 * Next list element.
44 *
45 * NULL if last element in list.
46 */
47 element_t *next;
48 };
49
50 /*
51 * Described in header
52 */
53 bool linked_list_match_str(void *item, va_list args)
54 {
55 char *a = item, *b;
56
57 VA_ARGS_VGET(args, b);
58 return streq(a, b);
59 }
60
61 /**
62 * Creates an empty linked list object.
63 */
64 element_t *element_create(void *value)
65 {
66 element_t *this;
67 INIT(this,
68 .value = value,
69 );
70 return this;
71 }
72
73
74 typedef struct private_linked_list_t private_linked_list_t;
75
76 /**
77 * Private data of a linked_list_t object.
78 *
79 */
80 struct private_linked_list_t {
81 /**
82 * Public part of linked list.
83 */
84 linked_list_t public;
85
86 /**
87 * Number of items in the list.
88 */
89 int count;
90
91 /**
92 * First element in list.
93 * NULL if no elements in list.
94 */
95 element_t *first;
96
97 /**
98 * Last element in list.
99 * NULL if no elements in list.
100 */
101 element_t *last;
102 };
103
104 typedef struct private_enumerator_t private_enumerator_t;
105
106 /**
107 * linked lists enumerator implementation
108 */
109 struct private_enumerator_t {
110
111 /**
112 * implements enumerator interface
113 */
114 enumerator_t enumerator;
115
116 /**
117 * associated linked list
118 */
119 private_linked_list_t *list;
120
121 /**
122 * current item
123 */
124 element_t *current;
125
126 /**
127 * enumerator has enumerated all items
128 */
129 bool finished;
130 };
131
132 METHOD(enumerator_t, enumerate, bool,
133 private_enumerator_t *this, va_list args)
134 {
135 void **item;
136
137 VA_ARGS_VGET(args, item);
138
139 if (this->finished)
140 {
141 return FALSE;
142 }
143 if (!this->current)
144 {
145 this->current = this->list->first;
146 }
147 else
148 {
149 this->current = this->current->next;
150 }
151 if (!this->current)
152 {
153 this->finished = TRUE;
154 return FALSE;
155 }
156 if (item)
157 {
158 *item = this->current->value;
159 }
160 return TRUE;
161 }
162
163 METHOD(linked_list_t, create_enumerator, enumerator_t*,
164 private_linked_list_t *this)
165 {
166 private_enumerator_t *enumerator;
167
168 INIT(enumerator,
169 .enumerator = {
170 .enumerate = enumerator_enumerate_default,
171 .venumerate = _enumerate,
172 .destroy = (void*)free,
173 },
174 .list = this,
175 );
176
177 return &enumerator->enumerator;
178 }
179
180 METHOD(linked_list_t, reset_enumerator, void,
181 private_linked_list_t *this, private_enumerator_t *enumerator)
182 {
183 enumerator->current = NULL;
184 enumerator->finished = FALSE;
185 }
186
187 METHOD(linked_list_t, get_count, int,
188 private_linked_list_t *this)
189 {
190 return this->count;
191 }
192
193 METHOD(linked_list_t, insert_first, void,
194 private_linked_list_t *this, void *item)
195 {
196 element_t *element;
197
198 element = element_create(item);
199 if (this->count == 0)
200 {
201 /* first entry in list */
202 this->first = element;
203 this->last = element;
204 }
205 else
206 {
207 element->next = this->first;
208 this->first->previous = element;
209 this->first = element;
210 }
211 this->count++;
212 }
213
214 /**
215 * unlink an element form the list, returns following element
216 */
217 static element_t* remove_element(private_linked_list_t *this,
218 element_t *element)
219 {
220 element_t *next, *previous;
221
222 next = element->next;
223 previous = element->previous;
224 free(element);
225 if (next)
226 {
227 next->previous = previous;
228 }
229 else
230 {
231 this->last = previous;
232 }
233 if (previous)
234 {
235 previous->next = next;
236 }
237 else
238 {
239 this->first = next;
240 }
241 if (--this->count == 0)
242 {
243 this->first = NULL;
244 this->last = NULL;
245 }
246 return next;
247 }
248
249 METHOD(linked_list_t, get_first, status_t,
250 private_linked_list_t *this, void **item)
251 {
252 if (this->count == 0)
253 {
254 return NOT_FOUND;
255 }
256 *item = this->first->value;
257 return SUCCESS;
258 }
259
260 METHOD(linked_list_t, remove_first, status_t,
261 private_linked_list_t *this, void **item)
262 {
263 if (get_first(this, item) == SUCCESS)
264 {
265 remove_element(this, this->first);
266 return SUCCESS;
267 }
268 return NOT_FOUND;
269 }
270
271 METHOD(linked_list_t, insert_last, void,
272 private_linked_list_t *this, void *item)
273 {
274 element_t *element;
275
276 element = element_create(item);
277 if (this->count == 0)
278 {
279 /* first entry in list */
280 this->first = element;
281 this->last = element;
282 }
283 else
284 {
285 element->previous = this->last;
286 this->last->next = element;
287 this->last = element;
288 }
289 this->count++;
290 }
291
292 METHOD(linked_list_t, insert_before, void,
293 private_linked_list_t *this, private_enumerator_t *enumerator,
294 void *item)
295 {
296 element_t *current, *element;
297
298 current = enumerator->current;
299 if (!current)
300 {
301 if (enumerator->finished)
302 {
303 this->public.insert_last(&this->public, item);
304 }
305 else
306 {
307 this->public.insert_first(&this->public, item);
308 }
309 return;
310 }
311 element = element_create(item);
312 if (current->previous)
313 {
314 current->previous->next = element;
315 element->previous = current->previous;
316 current->previous = element;
317 element->next = current;
318 }
319 else
320 {
321 current->previous = element;
322 element->next = current;
323 this->first = element;
324 }
325 this->count++;
326 }
327
328 METHOD(linked_list_t, get_last, status_t,
329 private_linked_list_t *this, void **item)
330 {
331 if (this->count == 0)
332 {
333 return NOT_FOUND;
334 }
335 *item = this->last->value;
336 return SUCCESS;
337 }
338
339 METHOD(linked_list_t, remove_last, status_t,
340 private_linked_list_t *this, void **item)
341 {
342 if (get_last(this, item) == SUCCESS)
343 {
344 remove_element(this, this->last);
345 return SUCCESS;
346 }
347 return NOT_FOUND;
348 }
349
350 METHOD(linked_list_t, remove_, int,
351 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
352 {
353 element_t *current = this->first;
354 int removed = 0;
355
356 while (current)
357 {
358 if ((compare && compare(current->value, item)) ||
359 (!compare && current->value == item))
360 {
361 removed++;
362 current = remove_element(this, current);
363 }
364 else
365 {
366 current = current->next;
367 }
368 }
369 return removed;
370 }
371
372 METHOD(linked_list_t, remove_at, void,
373 private_linked_list_t *this, private_enumerator_t *enumerator)
374 {
375 element_t *current;
376
377 if (enumerator->current)
378 {
379 current = enumerator->current;
380 enumerator->current = current->previous;
381 remove_element(this, current);
382 }
383 }
384
385 METHOD(linked_list_t, find_first, bool,
386 private_linked_list_t *this, linked_list_match_t match, void **item, ...)
387 {
388 element_t *current = this->first;
389 va_list args;
390 bool matched = FALSE;
391
392 if (!match && !item)
393 {
394 return FALSE;
395 }
396
397 while (current)
398 {
399 if (match)
400 {
401 va_start(args, item);
402 matched = match(current->value, args);
403 va_end(args);
404 }
405 else
406 {
407 matched = current->value == *item;
408 }
409 if (matched)
410 {
411 if (item != NULL)
412 {
413 *item = current->value;
414 }
415 return TRUE;
416 }
417 current = current->next;
418 }
419 return FALSE;
420 }
421
422 METHOD(linked_list_t, invoke_offset, void,
423 private_linked_list_t *this, size_t offset)
424 {
425 element_t *current = this->first;
426 void (**method)(void*);
427
428 while (current)
429 {
430 method = current->value + offset;
431 (*method)(current->value);
432 current = current->next;
433 }
434 }
435
436 METHOD(linked_list_t, invoke_function, void,
437 private_linked_list_t *this, linked_list_invoke_t fn, ...)
438 {
439 element_t *current = this->first;
440 va_list args;
441
442 while (current)
443 {
444 va_start(args, fn);
445 fn(current->value, args);
446 va_end(args);
447 current = current->next;
448 }
449 }
450
451 METHOD(linked_list_t, clone_offset, linked_list_t*,
452 private_linked_list_t *this, size_t offset)
453 {
454 element_t *current = this->first;
455 linked_list_t *clone;
456
457 clone = linked_list_create();
458 while (current)
459 {
460 void* (**method)(void*) = current->value + offset;
461 clone->insert_last(clone, (*method)(current->value));
462 current = current->next;
463 }
464
465 return clone;
466 }
467
468 METHOD(linked_list_t, equals_offset, bool,
469 private_linked_list_t *this, linked_list_t *other_pub, size_t offset)
470 {
471 private_linked_list_t *other = (private_linked_list_t*)other_pub;
472 element_t *cur_t, *cur_o;
473
474 if (this->count != other->count)
475 {
476 return FALSE;
477 }
478 cur_t = this->first;
479 cur_o = other->first;
480 while (cur_t && cur_o)
481 {
482 bool (**method)(void*,void*) = cur_t->value + offset;
483 if (!(*method)(cur_t->value, cur_o->value))
484 {
485 return FALSE;
486 }
487 cur_t = cur_t->next;
488 cur_o = cur_o->next;
489 }
490 return TRUE;
491 }
492
493 METHOD(linked_list_t, equals_function, bool,
494 private_linked_list_t *this, linked_list_t *other_pub,
495 bool (*fn)(void*,void*))
496 {
497 private_linked_list_t *other = (private_linked_list_t*)other_pub;
498 element_t *cur_t, *cur_o;
499
500 if (this->count != other->count)
501 {
502 return FALSE;
503 }
504 cur_t = this->first;
505 cur_o = other->first;
506 while (cur_t && cur_o)
507 {
508 if (!fn(cur_t->value, cur_o->value))
509 {
510 return FALSE;
511 }
512 cur_t = cur_t->next;
513 cur_o = cur_o->next;
514 }
515 return TRUE;
516 }
517
518 METHOD(linked_list_t, destroy, void,
519 private_linked_list_t *this)
520 {
521 void *value;
522
523 /* Remove all list items before destroying list */
524 while (remove_first(this, &value) == SUCCESS)
525 {
526 /* values are not destroyed so memory leaks are possible
527 * if list is not empty when deleting */
528 }
529 free(this);
530 }
531
532 METHOD(linked_list_t, destroy_offset, void,
533 private_linked_list_t *this, size_t offset)
534 {
535 element_t *current = this->first, *next;
536
537 while (current)
538 {
539 void (**method)(void*) = current->value + offset;
540 (*method)(current->value);
541 next = current->next;
542 free(current);
543 current = next;
544 }
545 free(this);
546 }
547
548 METHOD(linked_list_t, destroy_function, void,
549 private_linked_list_t *this, void (*fn)(void*))
550 {
551 element_t *current = this->first, *next;
552
553 while (current)
554 {
555 fn(current->value);
556 next = current->next;
557 free(current);
558 current = next;
559 }
560 free(this);
561 }
562
563 /*
564 * Described in header.
565 */
566 linked_list_t *linked_list_create()
567 {
568 private_linked_list_t *this;
569
570 INIT(this,
571 .public = {
572 .get_count = _get_count,
573 .create_enumerator = _create_enumerator,
574 .reset_enumerator = (void*)_reset_enumerator,
575 .get_first = _get_first,
576 .get_last = _get_last,
577 .find_first = _find_first,
578 .insert_first = _insert_first,
579 .insert_last = _insert_last,
580 .insert_before = (void*)_insert_before,
581 .remove_first = _remove_first,
582 .remove_last = _remove_last,
583 .remove = _remove_,
584 .remove_at = (void*)_remove_at,
585 .invoke_offset = _invoke_offset,
586 .invoke_function = _invoke_function,
587 .clone_offset = _clone_offset,
588 .equals_offset = _equals_offset,
589 .equals_function = _equals_function,
590 .destroy = _destroy,
591 .destroy_offset = _destroy_offset,
592 .destroy_function = _destroy_function,
593 },
594 );
595
596 return &this->public;
597 }
598
599 /*
600 * See header.
601 */
602 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
603 {
604 linked_list_t *list;
605 void *item;
606
607 list = linked_list_create();
608
609 while (enumerator->enumerate(enumerator, &item))
610 {
611 list->insert_last(list, item);
612 }
613 enumerator->destroy(enumerator);
614
615 return list;
616 }
617
618 /*
619 * See header.
620 */
621 linked_list_t *linked_list_create_with_items(void *item, ...)
622 {
623 linked_list_t *list;
624 va_list args;
625
626 list = linked_list_create();
627
628 va_start(args, item);
629 while (item)
630 {
631 list->insert_last(list, item);
632 item = va_arg(args, void*);
633 }
634 va_end(args);
635
636 return list;
637 }