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