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