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