Make sure the enumerator stops after all items have been enumerated.
[strongswan.git] / src / libstrongswan / utils / linked_list.c
1 /*
2 * Copyright (C) 2007-2011 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
20 #include "linked_list.h"
21
22 typedef struct element_t element_t;
23
24 /**
25 * This element holds a pointer to the value it represents.
26 */
27 struct element_t {
28
29 /**
30 * Value of a list item.
31 */
32 void *value;
33
34 /**
35 * Previous list element.
36 *
37 * NULL if first element in list.
38 */
39 element_t *previous;
40
41 /**
42 * Next list element.
43 *
44 * NULL if last element in list.
45 */
46 element_t *next;
47 };
48
49 /**
50 * Creates an empty linked list object.
51 */
52 element_t *element_create(void *value)
53 {
54 element_t *this;
55 INIT(this,
56 .value = value,
57 );
58 return this;
59 }
60
61
62 typedef struct private_linked_list_t private_linked_list_t;
63
64 /**
65 * Private data of a linked_list_t object.
66 *
67 */
68 struct private_linked_list_t {
69 /**
70 * Public part of linked list.
71 */
72 linked_list_t public;
73
74 /**
75 * Number of items in the list.
76 */
77 int count;
78
79 /**
80 * First element in list.
81 * NULL if no elements in list.
82 */
83 element_t *first;
84
85 /**
86 * Last element in list.
87 * NULL if no elements in list.
88 */
89 element_t *last;
90 };
91
92 typedef struct private_enumerator_t private_enumerator_t;
93
94 /**
95 * linked lists enumerator implementation
96 */
97 struct private_enumerator_t {
98
99 /**
100 * implements enumerator interface
101 */
102 enumerator_t enumerator;
103
104 /**
105 * associated linked list
106 */
107 private_linked_list_t *list;
108
109 /**
110 * current item
111 */
112 element_t *current;
113
114 /**
115 * enumerator has enumerated all items
116 */
117 bool finished;
118 };
119
120 METHOD(enumerator_t, enumerate, bool,
121 private_enumerator_t *this, void **item)
122 {
123 if (this->finished)
124 {
125 return FALSE;
126 }
127 if (!this->current)
128 {
129 this->current = this->list->first;
130 }
131 else
132 {
133 this->current = this->current->next;
134 }
135 if (!this->current)
136 {
137 this->finished = TRUE;
138 return FALSE;
139 }
140 *item = this->current->value;
141 return TRUE;
142 }
143
144 METHOD(linked_list_t, create_enumerator, enumerator_t*,
145 private_linked_list_t *this)
146 {
147 private_enumerator_t *enumerator;
148
149 INIT(enumerator,
150 .enumerator = {
151 .enumerate = (void*)_enumerate,
152 .destroy = (void*)free,
153 },
154 .list = this,
155 );
156
157 return &enumerator->enumerator;
158 }
159
160 METHOD(linked_list_t, reset_enumerator, void,
161 private_linked_list_t *this, private_enumerator_t *enumerator)
162 {
163 enumerator->current = NULL;
164 enumerator->finished = FALSE;
165 }
166
167 METHOD(linked_list_t, get_count, int,
168 private_linked_list_t *this)
169 {
170 return this->count;
171 }
172
173 METHOD(linked_list_t, insert_first, void,
174 private_linked_list_t *this, void *item)
175 {
176 element_t *element;
177
178 element = element_create(item);
179 if (this->count == 0)
180 {
181 /* first entry in list */
182 this->first = element;
183 this->last = element;
184 }
185 else
186 {
187 element->next = this->first;
188 this->first->previous = element;
189 this->first = element;
190 }
191 this->count++;
192 }
193
194 /**
195 * unlink an element form the list, returns following element
196 */
197 static element_t* remove_element(private_linked_list_t *this,
198 element_t *element)
199 {
200 element_t *next, *previous;
201
202 next = element->next;
203 previous = element->previous;
204 free(element);
205 if (next)
206 {
207 next->previous = previous;
208 }
209 else
210 {
211 this->last = previous;
212 }
213 if (previous)
214 {
215 previous->next = next;
216 }
217 else
218 {
219 this->first = next;
220 }
221 if (--this->count == 0)
222 {
223 this->first = NULL;
224 this->last = NULL;
225 }
226 return next;
227 }
228
229 METHOD(linked_list_t, get_first, status_t,
230 private_linked_list_t *this, void **item)
231 {
232 if (this->count == 0)
233 {
234 return NOT_FOUND;
235 }
236 *item = this->first->value;
237 return SUCCESS;
238 }
239
240 METHOD(linked_list_t, remove_first, status_t,
241 private_linked_list_t *this, void **item)
242 {
243 if (get_first(this, item) == SUCCESS)
244 {
245 remove_element(this, this->first);
246 return SUCCESS;
247 }
248 return NOT_FOUND;
249 }
250
251 METHOD(linked_list_t, insert_last, void,
252 private_linked_list_t *this, void *item)
253 {
254 element_t *element;
255
256 element = element_create(item);
257 if (this->count == 0)
258 {
259 /* first entry in list */
260 this->first = element;
261 this->last = element;
262 }
263 else
264 {
265 element->previous = this->last;
266 this->last->next = element;
267 this->last = element;
268 }
269 this->count++;
270 }
271
272 METHOD(linked_list_t, insert_before, void,
273 private_linked_list_t *this, private_enumerator_t *enumerator,
274 void *item)
275 {
276 element_t *current, *element;
277
278 current = enumerator->current;
279 if (!current)
280 {
281 if (enumerator->finished)
282 {
283 this->public.insert_last(&this->public, item);
284 }
285 else
286 {
287 this->public.insert_first(&this->public, item);
288 }
289 return;
290 }
291 element = element_create(item);
292 if (current->previous)
293 {
294 current->previous->next = element;
295 element->previous = current->previous;
296 current->previous = element;
297 element->next = current;
298 }
299 else
300 {
301 current->previous = element;
302 element->next = current;
303 this->first = element;
304 }
305 this->count++;
306 }
307
308 METHOD(linked_list_t, replace, void*,
309 private_linked_list_t *this, private_enumerator_t *enumerator,
310 void *item)
311 {
312 void *old = NULL;
313
314 if (enumerator->current)
315 {
316 old = enumerator->current->value;
317 enumerator->current->value = item;
318 }
319 return old;
320 }
321
322 METHOD(linked_list_t, get_last, status_t,
323 private_linked_list_t *this, void **item)
324 {
325 if (this->count == 0)
326 {
327 return NOT_FOUND;
328 }
329 *item = this->last->value;
330 return SUCCESS;
331 }
332
333 METHOD(linked_list_t, remove_last, status_t,
334 private_linked_list_t *this, void **item)
335 {
336 if (get_last(this, item) == SUCCESS)
337 {
338 remove_element(this, this->last);
339 return SUCCESS;
340 }
341 return NOT_FOUND;
342 }
343
344 METHOD(linked_list_t, remove_, int,
345 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
346 {
347 element_t *current = this->first;
348 int removed = 0;
349
350 while (current)
351 {
352 if ((compare && compare(current->value, item)) ||
353 (!compare && current->value == item))
354 {
355 removed++;
356 current = remove_element(this, current);
357 }
358 else
359 {
360 current = current->next;
361 }
362 }
363 return removed;
364 }
365
366 METHOD(linked_list_t, remove_at, void,
367 private_linked_list_t *this, private_enumerator_t *enumerator)
368 {
369 element_t *current;
370
371 if (enumerator->current)
372 {
373 current = enumerator->current;
374 enumerator->current = current->previous;
375 remove_element(this, current);
376 }
377 }
378
379 METHOD(linked_list_t, find_first, status_t,
380 private_linked_list_t *this, linked_list_match_t match,
381 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
382 {
383 element_t *current = this->first;
384
385 while (current)
386 {
387 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
388 (!match && item && current->value == *item))
389 {
390 if (item != NULL)
391 {
392 *item = current->value;
393 }
394 return SUCCESS;
395 }
396 current = current->next;
397 }
398 return NOT_FOUND;
399 }
400
401 METHOD(linked_list_t, find_last, status_t,
402 private_linked_list_t *this, linked_list_match_t match,
403 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
404 {
405 element_t *current = this->last;
406
407 while (current)
408 {
409 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
410 (!match && item && current->value == *item))
411 {
412 if (item != NULL)
413 {
414 *item = current->value;
415 }
416 return SUCCESS;
417 }
418 current = current->previous;
419 }
420 return NOT_FOUND;
421 }
422
423 METHOD(linked_list_t, invoke_offset, void,
424 private_linked_list_t *this, size_t offset,
425 void *d1, void *d2, void *d3, void *d4, void *d5)
426 {
427 element_t *current = this->first;
428 linked_list_invoke_t *method;
429
430 while (current)
431 {
432 method = current->value + offset;
433 (*method)(current->value, d1, d2, d3, d4, d5);
434 current = current->next;
435 }
436 }
437
438 METHOD(linked_list_t, invoke_function, void,
439 private_linked_list_t *this, linked_list_invoke_t fn,
440 void *d1, void *d2, void *d3, void *d4, void *d5)
441 {
442 element_t *current = this->first;
443
444 while (current)
445 {
446 fn(current->value, d1, d2, d3, d4, d5);
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, clone_function, linked_list_t*,
469 private_linked_list_t *this, void* (*fn)(void*))
470 {
471 element_t *current = this->first;
472 linked_list_t *clone;
473
474 clone = linked_list_create();
475 while (current)
476 {
477 clone->insert_last(clone, fn(current->value));
478 current = current->next;
479 }
480 return clone;
481 }
482
483 METHOD(linked_list_t, destroy, void,
484 private_linked_list_t *this)
485 {
486 void *value;
487
488 /* Remove all list items before destroying list */
489 while (remove_first(this, &value) == SUCCESS)
490 {
491 /* values are not destroyed so memory leaks are possible
492 * if list is not empty when deleting */
493 }
494 free(this);
495 }
496
497 METHOD(linked_list_t, destroy_offset, void,
498 private_linked_list_t *this, size_t offset)
499 {
500 element_t *current = this->first, *next;
501
502 while (current)
503 {
504 void (**method)(void*) = current->value + offset;
505 (*method)(current->value);
506 next = current->next;
507 free(current);
508 current = next;
509 }
510 free(this);
511 }
512
513 METHOD(linked_list_t, destroy_function, void,
514 private_linked_list_t *this, void (*fn)(void*))
515 {
516 element_t *current = this->first, *next;
517
518 while (current)
519 {
520 fn(current->value);
521 next = current->next;
522 free(current);
523 current = next;
524 }
525 free(this);
526 }
527
528 /*
529 * Described in header.
530 */
531 linked_list_t *linked_list_create()
532 {
533 private_linked_list_t *this;
534
535 INIT(this,
536 .public = {
537 .get_count = _get_count,
538 .create_enumerator = _create_enumerator,
539 .reset_enumerator = (void*)_reset_enumerator,
540 .get_first = _get_first,
541 .get_last = _get_last,
542 .find_first = (void*)_find_first,
543 .find_last = (void*)_find_last,
544 .insert_first = _insert_first,
545 .insert_last = _insert_last,
546 .insert_before = (void*)_insert_before,
547 .replace = (void*)_replace,
548 .remove_first = _remove_first,
549 .remove_last = _remove_last,
550 .remove = _remove_,
551 .remove_at = (void*)_remove_at,
552 .invoke_offset = (void*)_invoke_offset,
553 .invoke_function = (void*)_invoke_function,
554 .clone_offset = _clone_offset,
555 .clone_function = _clone_function,
556 .destroy = _destroy,
557 .destroy_offset = _destroy_offset,
558 .destroy_function = _destroy_function,
559 },
560 );
561
562 return &this->public;
563 }