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