linked-list: invoke_offset() doesn't take any additional arguments anymore
[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 * Creates an empty linked list object.
52 */
53 element_t *element_create(void *value)
54 {
55 element_t *this;
56 INIT(this,
57 .value = value,
58 );
59 return this;
60 }
61
62
63 typedef struct private_linked_list_t private_linked_list_t;
64
65 /**
66 * Private data of a linked_list_t object.
67 *
68 */
69 struct private_linked_list_t {
70 /**
71 * Public part of linked list.
72 */
73 linked_list_t public;
74
75 /**
76 * Number of items in the list.
77 */
78 int count;
79
80 /**
81 * First element in list.
82 * NULL if no elements in list.
83 */
84 element_t *first;
85
86 /**
87 * Last element in list.
88 * NULL if no elements in list.
89 */
90 element_t *last;
91 };
92
93 typedef struct private_enumerator_t private_enumerator_t;
94
95 /**
96 * linked lists enumerator implementation
97 */
98 struct private_enumerator_t {
99
100 /**
101 * implements enumerator interface
102 */
103 enumerator_t enumerator;
104
105 /**
106 * associated linked list
107 */
108 private_linked_list_t *list;
109
110 /**
111 * current item
112 */
113 element_t *current;
114
115 /**
116 * enumerator has enumerated all items
117 */
118 bool finished;
119 };
120
121 METHOD(enumerator_t, enumerate, bool,
122 private_enumerator_t *this, va_list args)
123 {
124 void **item;
125
126 VA_ARGS_VGET(args, item);
127
128 if (this->finished)
129 {
130 return FALSE;
131 }
132 if (!this->current)
133 {
134 this->current = this->list->first;
135 }
136 else
137 {
138 this->current = this->current->next;
139 }
140 if (!this->current)
141 {
142 this->finished = TRUE;
143 return FALSE;
144 }
145 if (item)
146 {
147 *item = this->current->value;
148 }
149 return TRUE;
150 }
151
152 METHOD(linked_list_t, create_enumerator, enumerator_t*,
153 private_linked_list_t *this)
154 {
155 private_enumerator_t *enumerator;
156
157 INIT(enumerator,
158 .enumerator = {
159 .enumerate = enumerator_enumerate_default,
160 .venumerate = _enumerate,
161 .destroy = (void*)free,
162 },
163 .list = this,
164 );
165
166 return &enumerator->enumerator;
167 }
168
169 METHOD(linked_list_t, reset_enumerator, void,
170 private_linked_list_t *this, private_enumerator_t *enumerator)
171 {
172 enumerator->current = NULL;
173 enumerator->finished = FALSE;
174 }
175
176 METHOD(linked_list_t, get_count, int,
177 private_linked_list_t *this)
178 {
179 return this->count;
180 }
181
182 METHOD(linked_list_t, insert_first, void,
183 private_linked_list_t *this, void *item)
184 {
185 element_t *element;
186
187 element = element_create(item);
188 if (this->count == 0)
189 {
190 /* first entry in list */
191 this->first = element;
192 this->last = element;
193 }
194 else
195 {
196 element->next = this->first;
197 this->first->previous = element;
198 this->first = element;
199 }
200 this->count++;
201 }
202
203 /**
204 * unlink an element form the list, returns following element
205 */
206 static element_t* remove_element(private_linked_list_t *this,
207 element_t *element)
208 {
209 element_t *next, *previous;
210
211 next = element->next;
212 previous = element->previous;
213 free(element);
214 if (next)
215 {
216 next->previous = previous;
217 }
218 else
219 {
220 this->last = previous;
221 }
222 if (previous)
223 {
224 previous->next = next;
225 }
226 else
227 {
228 this->first = next;
229 }
230 if (--this->count == 0)
231 {
232 this->first = NULL;
233 this->last = NULL;
234 }
235 return next;
236 }
237
238 METHOD(linked_list_t, get_first, status_t,
239 private_linked_list_t *this, void **item)
240 {
241 if (this->count == 0)
242 {
243 return NOT_FOUND;
244 }
245 *item = this->first->value;
246 return SUCCESS;
247 }
248
249 METHOD(linked_list_t, remove_first, status_t,
250 private_linked_list_t *this, void **item)
251 {
252 if (get_first(this, item) == SUCCESS)
253 {
254 remove_element(this, this->first);
255 return SUCCESS;
256 }
257 return NOT_FOUND;
258 }
259
260 METHOD(linked_list_t, insert_last, void,
261 private_linked_list_t *this, void *item)
262 {
263 element_t *element;
264
265 element = element_create(item);
266 if (this->count == 0)
267 {
268 /* first entry in list */
269 this->first = element;
270 this->last = element;
271 }
272 else
273 {
274 element->previous = this->last;
275 this->last->next = element;
276 this->last = element;
277 }
278 this->count++;
279 }
280
281 METHOD(linked_list_t, insert_before, void,
282 private_linked_list_t *this, private_enumerator_t *enumerator,
283 void *item)
284 {
285 element_t *current, *element;
286
287 current = enumerator->current;
288 if (!current)
289 {
290 if (enumerator->finished)
291 {
292 this->public.insert_last(&this->public, item);
293 }
294 else
295 {
296 this->public.insert_first(&this->public, item);
297 }
298 return;
299 }
300 element = element_create(item);
301 if (current->previous)
302 {
303 current->previous->next = element;
304 element->previous = current->previous;
305 current->previous = element;
306 element->next = current;
307 }
308 else
309 {
310 current->previous = element;
311 element->next = current;
312 this->first = element;
313 }
314 this->count++;
315 }
316
317 METHOD(linked_list_t, get_last, status_t,
318 private_linked_list_t *this, void **item)
319 {
320 if (this->count == 0)
321 {
322 return NOT_FOUND;
323 }
324 *item = this->last->value;
325 return SUCCESS;
326 }
327
328 METHOD(linked_list_t, remove_last, status_t,
329 private_linked_list_t *this, void **item)
330 {
331 if (get_last(this, item) == SUCCESS)
332 {
333 remove_element(this, this->last);
334 return SUCCESS;
335 }
336 return NOT_FOUND;
337 }
338
339 METHOD(linked_list_t, remove_, int,
340 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
341 {
342 element_t *current = this->first;
343 int removed = 0;
344
345 while (current)
346 {
347 if ((compare && compare(current->value, item)) ||
348 (!compare && current->value == item))
349 {
350 removed++;
351 current = remove_element(this, current);
352 }
353 else
354 {
355 current = current->next;
356 }
357 }
358 return removed;
359 }
360
361 METHOD(linked_list_t, remove_at, void,
362 private_linked_list_t *this, private_enumerator_t *enumerator)
363 {
364 element_t *current;
365
366 if (enumerator->current)
367 {
368 current = enumerator->current;
369 enumerator->current = current->previous;
370 remove_element(this, current);
371 }
372 }
373
374 METHOD(linked_list_t, find_first, status_t,
375 private_linked_list_t *this, linked_list_match_t match,
376 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
377 {
378 element_t *current = this->first;
379
380 while (current)
381 {
382 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
383 (!match && item && current->value == *item))
384 {
385 if (item != NULL)
386 {
387 *item = current->value;
388 }
389 return SUCCESS;
390 }
391 current = current->next;
392 }
393 return NOT_FOUND;
394 }
395
396 METHOD(linked_list_t, invoke_offset, void,
397 private_linked_list_t *this, size_t offset)
398 {
399 element_t *current = this->first;
400 void (**method)(void*);
401
402 while (current)
403 {
404 method = current->value + offset;
405 (*method)(current->value);
406 current = current->next;
407 }
408 }
409
410 METHOD(linked_list_t, invoke_function, void,
411 private_linked_list_t *this, linked_list_invoke_t fn,
412 void *d1, void *d2, void *d3, void *d4, void *d5)
413 {
414 element_t *current = this->first;
415
416 while (current)
417 {
418 fn(current->value, d1, d2, d3, d4, d5);
419 current = current->next;
420 }
421 }
422
423 METHOD(linked_list_t, clone_offset, linked_list_t*,
424 private_linked_list_t *this, size_t offset)
425 {
426 element_t *current = this->first;
427 linked_list_t *clone;
428
429 clone = linked_list_create();
430 while (current)
431 {
432 void* (**method)(void*) = current->value + offset;
433 clone->insert_last(clone, (*method)(current->value));
434 current = current->next;
435 }
436
437 return clone;
438 }
439
440 METHOD(linked_list_t, equals_offset, bool,
441 private_linked_list_t *this, linked_list_t *other_pub, size_t offset)
442 {
443 private_linked_list_t *other = (private_linked_list_t*)other_pub;
444 element_t *cur_t, *cur_o;
445
446 if (this->count != other->count)
447 {
448 return FALSE;
449 }
450 cur_t = this->first;
451 cur_o = other->first;
452 while (cur_t && cur_o)
453 {
454 bool (**method)(void*,void*) = cur_t->value + offset;
455 if (!(*method)(cur_t->value, cur_o->value))
456 {
457 return FALSE;
458 }
459 cur_t = cur_t->next;
460 cur_o = cur_o->next;
461 }
462 return TRUE;
463 }
464
465 METHOD(linked_list_t, equals_function, bool,
466 private_linked_list_t *this, linked_list_t *other_pub,
467 bool (*fn)(void*,void*))
468 {
469 private_linked_list_t *other = (private_linked_list_t*)other_pub;
470 element_t *cur_t, *cur_o;
471
472 if (this->count != other->count)
473 {
474 return FALSE;
475 }
476 cur_t = this->first;
477 cur_o = other->first;
478 while (cur_t && cur_o)
479 {
480 if (!fn(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, destroy, void,
491 private_linked_list_t *this)
492 {
493 void *value;
494
495 /* Remove all list items before destroying list */
496 while (remove_first(this, &value) == SUCCESS)
497 {
498 /* values are not destroyed so memory leaks are possible
499 * if list is not empty when deleting */
500 }
501 free(this);
502 }
503
504 METHOD(linked_list_t, destroy_offset, void,
505 private_linked_list_t *this, size_t offset)
506 {
507 element_t *current = this->first, *next;
508
509 while (current)
510 {
511 void (**method)(void*) = current->value + offset;
512 (*method)(current->value);
513 next = current->next;
514 free(current);
515 current = next;
516 }
517 free(this);
518 }
519
520 METHOD(linked_list_t, destroy_function, void,
521 private_linked_list_t *this, void (*fn)(void*))
522 {
523 element_t *current = this->first, *next;
524
525 while (current)
526 {
527 fn(current->value);
528 next = current->next;
529 free(current);
530 current = next;
531 }
532 free(this);
533 }
534
535 /*
536 * Described in header.
537 */
538 linked_list_t *linked_list_create()
539 {
540 private_linked_list_t *this;
541
542 INIT(this,
543 .public = {
544 .get_count = _get_count,
545 .create_enumerator = _create_enumerator,
546 .reset_enumerator = (void*)_reset_enumerator,
547 .get_first = _get_first,
548 .get_last = _get_last,
549 .find_first = (void*)_find_first,
550 .insert_first = _insert_first,
551 .insert_last = _insert_last,
552 .insert_before = (void*)_insert_before,
553 .remove_first = _remove_first,
554 .remove_last = _remove_last,
555 .remove = _remove_,
556 .remove_at = (void*)_remove_at,
557 .invoke_offset = _invoke_offset,
558 .invoke_function = (void*)_invoke_function,
559 .clone_offset = _clone_offset,
560 .equals_offset = _equals_offset,
561 .equals_function = _equals_function,
562 .destroy = _destroy,
563 .destroy_offset = _destroy_offset,
564 .destroy_function = _destroy_function,
565 },
566 );
567
568 return &this->public;
569 }
570
571 /*
572 * See header.
573 */
574 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
575 {
576 linked_list_t *list;
577 void *item;
578
579 list = linked_list_create();
580
581 while (enumerator->enumerate(enumerator, &item))
582 {
583 list->insert_last(list, item);
584 }
585 enumerator->destroy(enumerator);
586
587 return list;
588 }
589
590 /*
591 * See header.
592 */
593 linked_list_t *linked_list_create_with_items(void *item, ...)
594 {
595 linked_list_t *list;
596 va_list args;
597
598 list = linked_list_create();
599
600 va_start(args, item);
601 while (item)
602 {
603 list->insert_last(list, item);
604 item = va_arg(args, void*);
605 }
606 va_end(args);
607
608 return list;
609 }