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