botan: Add support for Ed25519 keys
[strongswan.git] / src / libstrongswan / collections / linked_list.c
1 /*
2 * Copyright (C) 2007-2018 Tobias Brunner
3 * Copyright (C) 2005-2006 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * HSR 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 public;
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 /**
128 * Enumerate the current item
129 */
130 static bool do_enumerate(private_enumerator_t *this, va_list args)
131 {
132 void **item;
133
134 VA_ARGS_VGET(args, item);
135
136 if (!this->current)
137 {
138 return FALSE;
139 }
140 if (item)
141 {
142 *item = this->current->value;
143 }
144 return TRUE;
145 }
146
147 METHOD(enumerator_t, enumerate_next, bool,
148 private_enumerator_t *this, va_list args)
149 {
150 if (this->current)
151 {
152 this->current = this->current->next;
153 }
154 return do_enumerate(this, args);
155 }
156
157 METHOD(enumerator_t, enumerate_current, bool,
158 private_enumerator_t *this, va_list args)
159 {
160 this->public.venumerate = _enumerate_next;
161 return do_enumerate(this, args);
162 }
163
164 METHOD(linked_list_t, create_enumerator, enumerator_t*,
165 private_linked_list_t *this)
166 {
167 private_enumerator_t *enumerator;
168
169 INIT(enumerator,
170 .public = {
171 .enumerate = enumerator_enumerate_default,
172 .venumerate = _enumerate_current,
173 .destroy = (void*)free,
174 },
175 .list = this,
176 .current = this->first,
177 );
178
179 return &enumerator->public;
180 }
181
182 METHOD(linked_list_t, reset_enumerator, void,
183 private_linked_list_t *this, private_enumerator_t *enumerator)
184 {
185 enumerator->current = this->first;
186 enumerator->public.venumerate = _enumerate_current;
187 }
188
189 METHOD(linked_list_t, get_count, int,
190 private_linked_list_t *this)
191 {
192 return this->count;
193 }
194
195 METHOD(linked_list_t, insert_first, void,
196 private_linked_list_t *this, void *item)
197 {
198 element_t *element;
199
200 element = element_create(item);
201 if (this->count == 0)
202 {
203 /* first entry in list */
204 this->first = element;
205 this->last = element;
206 }
207 else
208 {
209 element->next = this->first;
210 this->first->previous = element;
211 this->first = element;
212 }
213 this->count++;
214 }
215
216 /**
217 * unlink an element form the list, returns following element
218 */
219 static element_t* remove_element(private_linked_list_t *this,
220 element_t *element)
221 {
222 element_t *next, *previous;
223
224 next = element->next;
225 previous = element->previous;
226 free(element);
227 if (next)
228 {
229 next->previous = previous;
230 }
231 else
232 {
233 this->last = previous;
234 }
235 if (previous)
236 {
237 previous->next = next;
238 }
239 else
240 {
241 this->first = next;
242 }
243 if (--this->count == 0)
244 {
245 this->first = NULL;
246 this->last = NULL;
247 }
248 return next;
249 }
250
251 METHOD(linked_list_t, get_first, status_t,
252 private_linked_list_t *this, void **item)
253 {
254 if (this->count == 0)
255 {
256 return NOT_FOUND;
257 }
258 *item = this->first->value;
259 return SUCCESS;
260 }
261
262 METHOD(linked_list_t, remove_first, status_t,
263 private_linked_list_t *this, void **item)
264 {
265 if (get_first(this, item) == SUCCESS)
266 {
267 remove_element(this, this->first);
268 return SUCCESS;
269 }
270 return NOT_FOUND;
271 }
272
273 METHOD(linked_list_t, insert_last, void,
274 private_linked_list_t *this, void *item)
275 {
276 element_t *element;
277
278 element = element_create(item);
279 if (this->count == 0)
280 {
281 /* first entry in list */
282 this->first = element;
283 this->last = element;
284 }
285 else
286 {
287 element->previous = this->last;
288 this->last->next = element;
289 this->last = element;
290 }
291 this->count++;
292 }
293
294 METHOD(linked_list_t, insert_before, void,
295 private_linked_list_t *this, private_enumerator_t *enumerator,
296 void *item)
297 {
298 element_t *current, *element;
299
300 current = enumerator->current;
301 if (!current)
302 {
303 insert_last(this, item);
304 return;
305 }
306 element = element_create(item);
307 if (current->previous)
308 {
309 current->previous->next = element;
310 element->previous = current->previous;
311 current->previous = element;
312 element->next = current;
313 }
314 else
315 {
316 current->previous = element;
317 element->next = current;
318 this->first = element;
319 }
320 this->count++;
321 }
322
323 METHOD(linked_list_t, get_last, status_t,
324 private_linked_list_t *this, void **item)
325 {
326 if (this->count == 0)
327 {
328 return NOT_FOUND;
329 }
330 *item = this->last->value;
331 return SUCCESS;
332 }
333
334 METHOD(linked_list_t, remove_last, status_t,
335 private_linked_list_t *this, void **item)
336 {
337 if (get_last(this, item) == SUCCESS)
338 {
339 remove_element(this, this->last);
340 return SUCCESS;
341 }
342 return NOT_FOUND;
343 }
344
345 METHOD(linked_list_t, remove_, int,
346 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
347 {
348 element_t *current = this->first;
349 int removed = 0;
350
351 while (current)
352 {
353 if ((compare && compare(current->value, item)) ||
354 (!compare && current->value == item))
355 {
356 removed++;
357 current = remove_element(this, current);
358 }
359 else
360 {
361 current = current->next;
362 }
363 }
364 return removed;
365 }
366
367 METHOD(linked_list_t, remove_at, void,
368 private_linked_list_t *this, private_enumerator_t *enumerator)
369 {
370 element_t *current;
371
372 if (enumerator->current)
373 {
374 current = enumerator->current;
375 enumerator->current = current->next;
376 /* the enumerator already points to the next item */
377 enumerator->public.venumerate = _enumerate_current;
378 remove_element(this, current);
379 }
380 }
381
382 METHOD(linked_list_t, find_first, bool,
383 private_linked_list_t *this, linked_list_match_t match, void **item, ...)
384 {
385 element_t *current = this->first;
386 va_list args;
387 bool matched = FALSE;
388
389 if (!match && !item)
390 {
391 return FALSE;
392 }
393
394 while (current)
395 {
396 if (match)
397 {
398 va_start(args, item);
399 matched = match(current->value, args);
400 va_end(args);
401 }
402 else
403 {
404 matched = current->value == *item;
405 }
406 if (matched)
407 {
408 if (item != NULL)
409 {
410 *item = current->value;
411 }
412 return TRUE;
413 }
414 current = current->next;
415 }
416 return FALSE;
417 }
418
419 METHOD(linked_list_t, invoke_offset, void,
420 private_linked_list_t *this, size_t offset)
421 {
422 element_t *current = this->first;
423 void (**method)(void*);
424
425 while (current)
426 {
427 method = current->value + offset;
428 (*method)(current->value);
429 current = current->next;
430 }
431 }
432
433 METHOD(linked_list_t, invoke_function, void,
434 private_linked_list_t *this, linked_list_invoke_t fn, ...)
435 {
436 element_t *current = this->first;
437 va_list args;
438
439 while (current)
440 {
441 va_start(args, fn);
442 fn(current->value, args);
443 va_end(args);
444 current = current->next;
445 }
446 }
447
448 METHOD(linked_list_t, clone_offset, linked_list_t*,
449 private_linked_list_t *this, size_t offset)
450 {
451 element_t *current = this->first;
452 linked_list_t *clone;
453
454 clone = linked_list_create();
455 while (current)
456 {
457 void* (**method)(void*) = current->value + offset;
458 clone->insert_last(clone, (*method)(current->value));
459 current = current->next;
460 }
461
462 return clone;
463 }
464
465 METHOD(linked_list_t, equals_offset, bool,
466 private_linked_list_t *this, linked_list_t *other_pub, size_t offset)
467 {
468 private_linked_list_t *other = (private_linked_list_t*)other_pub;
469 element_t *cur_t, *cur_o;
470
471 if (this->count != other->count)
472 {
473 return FALSE;
474 }
475 cur_t = this->first;
476 cur_o = other->first;
477 while (cur_t && cur_o)
478 {
479 bool (**method)(void*,void*) = cur_t->value + offset;
480 if (!(*method)(cur_t->value, cur_o->value))
481 {
482 return FALSE;
483 }
484 cur_t = cur_t->next;
485 cur_o = cur_o->next;
486 }
487 return TRUE;
488 }
489
490 METHOD(linked_list_t, equals_function, bool,
491 private_linked_list_t *this, linked_list_t *other_pub,
492 bool (*fn)(void*,void*))
493 {
494 private_linked_list_t *other = (private_linked_list_t*)other_pub;
495 element_t *cur_t, *cur_o;
496
497 if (this->count != other->count)
498 {
499 return FALSE;
500 }
501 cur_t = this->first;
502 cur_o = other->first;
503 while (cur_t && cur_o)
504 {
505 if (!fn(cur_t->value, cur_o->value))
506 {
507 return FALSE;
508 }
509 cur_t = cur_t->next;
510 cur_o = cur_o->next;
511 }
512 return TRUE;
513 }
514
515 METHOD(linked_list_t, destroy, void,
516 private_linked_list_t *this)
517 {
518 void *value;
519
520 /* Remove all list items before destroying list */
521 while (remove_first(this, &value) == SUCCESS)
522 {
523 /* values are not destroyed so memory leaks are possible
524 * if list is not empty when deleting */
525 }
526 free(this);
527 }
528
529 METHOD(linked_list_t, destroy_offset, void,
530 private_linked_list_t *this, size_t offset)
531 {
532 element_t *current = this->first, *next;
533
534 while (current)
535 {
536 void (**method)(void*) = current->value + offset;
537 (*method)(current->value);
538 next = current->next;
539 free(current);
540 current = next;
541 }
542 free(this);
543 }
544
545 METHOD(linked_list_t, destroy_function, void,
546 private_linked_list_t *this, void (*fn)(void*))
547 {
548 element_t *current = this->first, *next;
549
550 while (current)
551 {
552 fn(current->value);
553 next = current->next;
554 free(current);
555 current = next;
556 }
557 free(this);
558 }
559
560 /*
561 * Described in header.
562 */
563 linked_list_t *linked_list_create()
564 {
565 private_linked_list_t *this;
566
567 INIT(this,
568 .public = {
569 .get_count = _get_count,
570 .create_enumerator = _create_enumerator,
571 .reset_enumerator = (void*)_reset_enumerator,
572 .get_first = _get_first,
573 .get_last = _get_last,
574 .find_first = _find_first,
575 .insert_first = _insert_first,
576 .insert_last = _insert_last,
577 .insert_before = (void*)_insert_before,
578 .remove_first = _remove_first,
579 .remove_last = _remove_last,
580 .remove = _remove_,
581 .remove_at = (void*)_remove_at,
582 .invoke_offset = _invoke_offset,
583 .invoke_function = _invoke_function,
584 .clone_offset = _clone_offset,
585 .equals_offset = _equals_offset,
586 .equals_function = _equals_function,
587 .destroy = _destroy,
588 .destroy_offset = _destroy_offset,
589 .destroy_function = _destroy_function,
590 },
591 );
592
593 return &this->public;
594 }
595
596 /*
597 * See header.
598 */
599 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
600 {
601 linked_list_t *list;
602 void *item;
603
604 list = linked_list_create();
605
606 while (enumerator->enumerate(enumerator, &item))
607 {
608 list->insert_last(list, item);
609 }
610 enumerator->destroy(enumerator);
611
612 return list;
613 }
614
615 /*
616 * See header.
617 */
618 linked_list_t *linked_list_create_with_items(void *item, ...)
619 {
620 linked_list_t *list;
621 va_list args;
622
623 list = linked_list_create();
624
625 va_start(args, item);
626 while (item)
627 {
628 list->insert_last(list, item);
629 item = va_arg(args, void*);
630 }
631 va_end(args);
632
633 return list;
634 }