Moved packet_t and tun_device_t to networking folder
[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 #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, replace, void*,
320 private_linked_list_t *this, private_enumerator_t *enumerator,
321 void *item)
322 {
323 void *old = NULL;
324
325 if (enumerator->current)
326 {
327 old = enumerator->current->value;
328 enumerator->current->value = item;
329 }
330 return old;
331 }
332
333 METHOD(linked_list_t, get_last, status_t,
334 private_linked_list_t *this, void **item)
335 {
336 if (this->count == 0)
337 {
338 return NOT_FOUND;
339 }
340 *item = this->last->value;
341 return SUCCESS;
342 }
343
344 METHOD(linked_list_t, remove_last, status_t,
345 private_linked_list_t *this, void **item)
346 {
347 if (get_last(this, item) == SUCCESS)
348 {
349 remove_element(this, this->last);
350 return SUCCESS;
351 }
352 return NOT_FOUND;
353 }
354
355 METHOD(linked_list_t, remove_, int,
356 private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
357 {
358 element_t *current = this->first;
359 int removed = 0;
360
361 while (current)
362 {
363 if ((compare && compare(current->value, item)) ||
364 (!compare && current->value == item))
365 {
366 removed++;
367 current = remove_element(this, current);
368 }
369 else
370 {
371 current = current->next;
372 }
373 }
374 return removed;
375 }
376
377 METHOD(linked_list_t, remove_at, void,
378 private_linked_list_t *this, private_enumerator_t *enumerator)
379 {
380 element_t *current;
381
382 if (enumerator->current)
383 {
384 current = enumerator->current;
385 enumerator->current = current->previous;
386 remove_element(this, current);
387 }
388 }
389
390 METHOD(linked_list_t, find_first, status_t,
391 private_linked_list_t *this, linked_list_match_t match,
392 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
393 {
394 element_t *current = this->first;
395
396 while (current)
397 {
398 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
399 (!match && item && current->value == *item))
400 {
401 if (item != NULL)
402 {
403 *item = current->value;
404 }
405 return SUCCESS;
406 }
407 current = current->next;
408 }
409 return NOT_FOUND;
410 }
411
412 METHOD(linked_list_t, find_last, status_t,
413 private_linked_list_t *this, linked_list_match_t match,
414 void **item, void *d1, void *d2, void *d3, void *d4, void *d5)
415 {
416 element_t *current = this->last;
417
418 while (current)
419 {
420 if ((match && match(current->value, d1, d2, d3, d4, d5)) ||
421 (!match && item && current->value == *item))
422 {
423 if (item != NULL)
424 {
425 *item = current->value;
426 }
427 return SUCCESS;
428 }
429 current = current->previous;
430 }
431 return NOT_FOUND;
432 }
433
434 METHOD(linked_list_t, invoke_offset, void,
435 private_linked_list_t *this, size_t offset,
436 void *d1, void *d2, void *d3, void *d4, void *d5)
437 {
438 element_t *current = this->first;
439 linked_list_invoke_t *method;
440
441 while (current)
442 {
443 method = current->value + offset;
444 (*method)(current->value, d1, d2, d3, d4, d5);
445 current = current->next;
446 }
447 }
448
449 METHOD(linked_list_t, invoke_function, void,
450 private_linked_list_t *this, linked_list_invoke_t fn,
451 void *d1, void *d2, void *d3, void *d4, void *d5)
452 {
453 element_t *current = this->first;
454
455 while (current)
456 {
457 fn(current->value, d1, d2, d3, d4, d5);
458 current = current->next;
459 }
460 }
461
462 METHOD(linked_list_t, clone_offset, linked_list_t*,
463 private_linked_list_t *this, size_t offset)
464 {
465 element_t *current = this->first;
466 linked_list_t *clone;
467
468 clone = linked_list_create();
469 while (current)
470 {
471 void* (**method)(void*) = current->value + offset;
472 clone->insert_last(clone, (*method)(current->value));
473 current = current->next;
474 }
475
476 return clone;
477 }
478
479 METHOD(linked_list_t, clone_function, linked_list_t*,
480 private_linked_list_t *this, void* (*fn)(void*))
481 {
482 element_t *current = this->first;
483 linked_list_t *clone;
484
485 clone = linked_list_create();
486 while (current)
487 {
488 clone->insert_last(clone, fn(current->value));
489 current = current->next;
490 }
491 return clone;
492 }
493
494 METHOD(linked_list_t, destroy, void,
495 private_linked_list_t *this)
496 {
497 void *value;
498
499 /* Remove all list items before destroying list */
500 while (remove_first(this, &value) == SUCCESS)
501 {
502 /* values are not destroyed so memory leaks are possible
503 * if list is not empty when deleting */
504 }
505 free(this);
506 }
507
508 METHOD(linked_list_t, destroy_offset, void,
509 private_linked_list_t *this, size_t offset)
510 {
511 element_t *current = this->first, *next;
512
513 while (current)
514 {
515 void (**method)(void*) = current->value + offset;
516 (*method)(current->value);
517 next = current->next;
518 free(current);
519 current = next;
520 }
521 free(this);
522 }
523
524 METHOD(linked_list_t, destroy_function, void,
525 private_linked_list_t *this, void (*fn)(void*))
526 {
527 element_t *current = this->first, *next;
528
529 while (current)
530 {
531 fn(current->value);
532 next = current->next;
533 free(current);
534 current = next;
535 }
536 free(this);
537 }
538
539 /*
540 * Described in header.
541 */
542 linked_list_t *linked_list_create()
543 {
544 private_linked_list_t *this;
545
546 INIT(this,
547 .public = {
548 .get_count = _get_count,
549 .create_enumerator = _create_enumerator,
550 .reset_enumerator = (void*)_reset_enumerator,
551 .has_more = (void*)_has_more,
552 .get_first = _get_first,
553 .get_last = _get_last,
554 .find_first = (void*)_find_first,
555 .find_last = (void*)_find_last,
556 .insert_first = _insert_first,
557 .insert_last = _insert_last,
558 .insert_before = (void*)_insert_before,
559 .replace = (void*)_replace,
560 .remove_first = _remove_first,
561 .remove_last = _remove_last,
562 .remove = _remove_,
563 .remove_at = (void*)_remove_at,
564 .invoke_offset = (void*)_invoke_offset,
565 .invoke_function = (void*)_invoke_function,
566 .clone_offset = _clone_offset,
567 .clone_function = _clone_function,
568 .destroy = _destroy,
569 .destroy_offset = _destroy_offset,
570 .destroy_function = _destroy_function,
571 },
572 );
573
574 return &this->public;
575 }
576
577 /*
578 * See header.
579 */
580 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
581 {
582 linked_list_t *list;
583 void *item;
584
585 list = linked_list_create();
586
587 while (enumerator->enumerate(enumerator, &item))
588 {
589 list->insert_last(list, item);
590 }
591 enumerator->destroy(enumerator);
592
593 return list;
594 }
595
596 /*
597 * See header.
598 */
599 linked_list_t *linked_list_create_with_items(void *item, ...)
600 {
601 linked_list_t *list;
602 va_list args;
603
604 list = linked_list_create();
605
606 va_start(args, item);
607 while (item)
608 {
609 list->insert_last(list, item);
610 item = va_arg(args, void*);
611 }
612 va_end(args);
613
614 return list;
615 }