linked-list: Remove unused clone_function() method
[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, invoke_offset, void,
399 private_linked_list_t *this, size_t offset,
400 void *d1, void *d2, void *d3, void *d4, void *d5)
401 {
402 element_t *current = this->first;
403 linked_list_invoke_t *method;
404
405 while (current)
406 {
407 method = current->value + offset;
408 (*method)(current->value, d1, d2, d3, d4, d5);
409 current = current->next;
410 }
411 }
412
413 METHOD(linked_list_t, invoke_function, void,
414 private_linked_list_t *this, linked_list_invoke_t fn,
415 void *d1, void *d2, void *d3, void *d4, void *d5)
416 {
417 element_t *current = this->first;
418
419 while (current)
420 {
421 fn(current->value, d1, d2, d3, d4, d5);
422 current = current->next;
423 }
424 }
425
426 METHOD(linked_list_t, clone_offset, linked_list_t*,
427 private_linked_list_t *this, size_t offset)
428 {
429 element_t *current = this->first;
430 linked_list_t *clone;
431
432 clone = linked_list_create();
433 while (current)
434 {
435 void* (**method)(void*) = current->value + offset;
436 clone->insert_last(clone, (*method)(current->value));
437 current = current->next;
438 }
439
440 return clone;
441 }
442
443 METHOD(linked_list_t, destroy, void,
444 private_linked_list_t *this)
445 {
446 void *value;
447
448 /* Remove all list items before destroying list */
449 while (remove_first(this, &value) == SUCCESS)
450 {
451 /* values are not destroyed so memory leaks are possible
452 * if list is not empty when deleting */
453 }
454 free(this);
455 }
456
457 METHOD(linked_list_t, destroy_offset, void,
458 private_linked_list_t *this, size_t offset)
459 {
460 element_t *current = this->first, *next;
461
462 while (current)
463 {
464 void (**method)(void*) = current->value + offset;
465 (*method)(current->value);
466 next = current->next;
467 free(current);
468 current = next;
469 }
470 free(this);
471 }
472
473 METHOD(linked_list_t, destroy_function, void,
474 private_linked_list_t *this, void (*fn)(void*))
475 {
476 element_t *current = this->first, *next;
477
478 while (current)
479 {
480 fn(current->value);
481 next = current->next;
482 free(current);
483 current = next;
484 }
485 free(this);
486 }
487
488 /*
489 * Described in header.
490 */
491 linked_list_t *linked_list_create()
492 {
493 private_linked_list_t *this;
494
495 INIT(this,
496 .public = {
497 .get_count = _get_count,
498 .create_enumerator = _create_enumerator,
499 .reset_enumerator = (void*)_reset_enumerator,
500 .has_more = (void*)_has_more,
501 .get_first = _get_first,
502 .get_last = _get_last,
503 .find_first = (void*)_find_first,
504 .insert_first = _insert_first,
505 .insert_last = _insert_last,
506 .insert_before = (void*)_insert_before,
507 .remove_first = _remove_first,
508 .remove_last = _remove_last,
509 .remove = _remove_,
510 .remove_at = (void*)_remove_at,
511 .invoke_offset = (void*)_invoke_offset,
512 .invoke_function = (void*)_invoke_function,
513 .clone_offset = _clone_offset,
514 .destroy = _destroy,
515 .destroy_offset = _destroy_offset,
516 .destroy_function = _destroy_function,
517 },
518 );
519
520 return &this->public;
521 }
522
523 /*
524 * See header.
525 */
526 linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
527 {
528 linked_list_t *list;
529 void *item;
530
531 list = linked_list_create();
532
533 while (enumerator->enumerate(enumerator, &item))
534 {
535 list->insert_last(list, item);
536 }
537 enumerator->destroy(enumerator);
538
539 return list;
540 }
541
542 /*
543 * See header.
544 */
545 linked_list_t *linked_list_create_with_items(void *item, ...)
546 {
547 linked_list_t *list;
548 va_list args;
549
550 list = linked_list_create();
551
552 va_start(args, item);
553 while (item)
554 {
555 list->insert_last(list, item);
556 item = va_arg(args, void*);
557 }
558 va_end(args);
559
560 return list;
561 }