![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to linked_list.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections|
Return to linked_list.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections |
1.1 misho 1: /*
2: * Copyright (C) 2007-2018 Tobias Brunner
3: * Copyright (C) 2005-2006 Martin Willi
4: * Copyright (C) 2005 Jan Hutter
5: * HSR 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: * Described in header
52: */
53: bool linked_list_match_str(void *item, va_list args)
54: {
55: char *a = item, *b;
56:
57: VA_ARGS_VGET(args, b);
58: return streq(a, b);
59: }
60:
61: /**
62: * Creates an empty linked list object.
63: */
64: element_t *element_create(void *value)
65: {
66: element_t *this;
67: INIT(this,
68: .value = value,
69: );
70: return this;
71: }
72:
73:
74: typedef struct private_linked_list_t private_linked_list_t;
75:
76: /**
77: * Private data of a linked_list_t object.
78: *
79: */
80: struct private_linked_list_t {
81: /**
82: * Public part of linked list.
83: */
84: linked_list_t public;
85:
86: /**
87: * Number of items in the list.
88: */
89: int count;
90:
91: /**
92: * First element in list.
93: * NULL if no elements in list.
94: */
95: element_t *first;
96:
97: /**
98: * Last element in list.
99: * NULL if no elements in list.
100: */
101: element_t *last;
102: };
103:
104: typedef struct private_enumerator_t private_enumerator_t;
105:
106: /**
107: * linked lists enumerator implementation
108: */
109: struct private_enumerator_t {
110:
111: /**
112: * implements enumerator interface
113: */
114: enumerator_t public;
115:
116: /**
117: * associated linked list
118: */
119: private_linked_list_t *list;
120:
121: /**
122: * current item
123: */
124: element_t *current;
125: };
126:
127: /**
128: * Enumerate the current item
129: */
130: static bool do_enumerate(private_enumerator_t *this, va_list args)
131: {
132: void **item;
133:
134: VA_ARGS_VGET(args, item);
135:
136: if (!this->current)
137: {
138: return FALSE;
139: }
140: if (item)
141: {
142: *item = this->current->value;
143: }
144: return TRUE;
145: }
146:
147: METHOD(enumerator_t, enumerate_next, bool,
148: private_enumerator_t *this, va_list args)
149: {
150: if (this->current)
151: {
152: this->current = this->current->next;
153: }
154: return do_enumerate(this, args);
155: }
156:
157: METHOD(enumerator_t, enumerate_current, bool,
158: private_enumerator_t *this, va_list args)
159: {
160: this->public.venumerate = _enumerate_next;
161: return do_enumerate(this, args);
162: }
163:
164: METHOD(linked_list_t, create_enumerator, enumerator_t*,
165: private_linked_list_t *this)
166: {
167: private_enumerator_t *enumerator;
168:
169: INIT(enumerator,
170: .public = {
171: .enumerate = enumerator_enumerate_default,
172: .venumerate = _enumerate_current,
173: .destroy = (void*)free,
174: },
175: .list = this,
176: .current = this->first,
177: );
178:
179: return &enumerator->public;
180: }
181:
182: METHOD(linked_list_t, reset_enumerator, void,
183: private_linked_list_t *this, private_enumerator_t *enumerator)
184: {
185: enumerator->current = this->first;
186: enumerator->public.venumerate = _enumerate_current;
187: }
188:
189: METHOD(linked_list_t, get_count, int,
190: private_linked_list_t *this)
191: {
192: return this->count;
193: }
194:
195: METHOD(linked_list_t, insert_first, void,
196: private_linked_list_t *this, void *item)
197: {
198: element_t *element;
199:
200: element = element_create(item);
201: if (this->count == 0)
202: {
203: /* first entry in list */
204: this->first = element;
205: this->last = element;
206: }
207: else
208: {
209: element->next = this->first;
210: this->first->previous = element;
211: this->first = element;
212: }
213: this->count++;
214: }
215:
216: /**
217: * unlink an element form the list, returns following element
218: */
219: static element_t* remove_element(private_linked_list_t *this,
220: element_t *element)
221: {
222: element_t *next, *previous;
223:
224: next = element->next;
225: previous = element->previous;
226: free(element);
227: if (next)
228: {
229: next->previous = previous;
230: }
231: else
232: {
233: this->last = previous;
234: }
235: if (previous)
236: {
237: previous->next = next;
238: }
239: else
240: {
241: this->first = next;
242: }
243: if (--this->count == 0)
244: {
245: this->first = NULL;
246: this->last = NULL;
247: }
248: return next;
249: }
250:
251: METHOD(linked_list_t, get_first, status_t,
252: private_linked_list_t *this, void **item)
253: {
254: if (this->count == 0)
255: {
256: return NOT_FOUND;
257: }
258: *item = this->first->value;
259: return SUCCESS;
260: }
261:
262: METHOD(linked_list_t, remove_first, status_t,
263: private_linked_list_t *this, void **item)
264: {
265: if (get_first(this, item) == SUCCESS)
266: {
267: remove_element(this, this->first);
268: return SUCCESS;
269: }
270: return NOT_FOUND;
271: }
272:
273: METHOD(linked_list_t, insert_last, void,
274: private_linked_list_t *this, void *item)
275: {
276: element_t *element;
277:
278: element = element_create(item);
279: if (this->count == 0)
280: {
281: /* first entry in list */
282: this->first = element;
283: this->last = element;
284: }
285: else
286: {
287: element->previous = this->last;
288: this->last->next = element;
289: this->last = element;
290: }
291: this->count++;
292: }
293:
294: METHOD(linked_list_t, insert_before, void,
295: private_linked_list_t *this, private_enumerator_t *enumerator,
296: void *item)
297: {
298: element_t *current, *element;
299:
300: current = enumerator->current;
301: if (!current)
302: {
303: insert_last(this, item);
304: return;
305: }
306: element = element_create(item);
307: if (current->previous)
308: {
309: current->previous->next = element;
310: element->previous = current->previous;
311: current->previous = element;
312: element->next = current;
313: }
314: else
315: {
316: current->previous = element;
317: element->next = current;
318: this->first = element;
319: }
320: this->count++;
321: }
322:
323: METHOD(linked_list_t, get_last, status_t,
324: private_linked_list_t *this, void **item)
325: {
326: if (this->count == 0)
327: {
328: return NOT_FOUND;
329: }
330: *item = this->last->value;
331: return SUCCESS;
332: }
333:
334: METHOD(linked_list_t, remove_last, status_t,
335: private_linked_list_t *this, void **item)
336: {
337: if (get_last(this, item) == SUCCESS)
338: {
339: remove_element(this, this->last);
340: return SUCCESS;
341: }
342: return NOT_FOUND;
343: }
344:
345: METHOD(linked_list_t, remove_, int,
346: private_linked_list_t *this, void *item, bool (*compare)(void*,void*))
347: {
348: element_t *current = this->first;
349: int removed = 0;
350:
351: while (current)
352: {
353: if ((compare && compare(current->value, item)) ||
354: (!compare && current->value == item))
355: {
356: removed++;
357: current = remove_element(this, current);
358: }
359: else
360: {
361: current = current->next;
362: }
363: }
364: return removed;
365: }
366:
367: METHOD(linked_list_t, remove_at, void,
368: private_linked_list_t *this, private_enumerator_t *enumerator)
369: {
370: element_t *current;
371:
372: if (enumerator->current)
373: {
374: current = enumerator->current;
375: enumerator->current = current->next;
376: /* the enumerator already points to the next item */
377: enumerator->public.venumerate = _enumerate_current;
378: remove_element(this, current);
379: }
380: }
381:
382: METHOD(linked_list_t, find_first, bool,
383: private_linked_list_t *this, linked_list_match_t match, void **item, ...)
384: {
385: element_t *current = this->first;
386: va_list args;
387: bool matched = FALSE;
388:
389: if (!match && !item)
390: {
391: return FALSE;
392: }
393:
394: while (current)
395: {
396: if (match)
397: {
398: va_start(args, item);
399: matched = match(current->value, args);
400: va_end(args);
401: }
402: else
403: {
404: matched = current->value == *item;
405: }
406: if (matched)
407: {
408: if (item != NULL)
409: {
410: *item = current->value;
411: }
412: return TRUE;
413: }
414: current = current->next;
415: }
416: return FALSE;
417: }
418:
419: METHOD(linked_list_t, invoke_offset, void,
420: private_linked_list_t *this, size_t offset)
421: {
422: element_t *current = this->first;
423: void (**method)(void*);
424:
425: while (current)
426: {
427: method = current->value + offset;
428: (*method)(current->value);
429: current = current->next;
430: }
431: }
432:
433: METHOD(linked_list_t, invoke_function, void,
434: private_linked_list_t *this, linked_list_invoke_t fn, ...)
435: {
436: element_t *current = this->first;
437: va_list args;
438:
439: while (current)
440: {
441: va_start(args, fn);
442: fn(current->value, args);
443: va_end(args);
444: current = current->next;
445: }
446: }
447:
448: METHOD(linked_list_t, clone_offset, linked_list_t*,
449: private_linked_list_t *this, size_t offset)
450: {
451: element_t *current = this->first;
452: linked_list_t *clone;
453:
454: clone = linked_list_create();
455: while (current)
456: {
457: void* (**method)(void*) = current->value + offset;
458: clone->insert_last(clone, (*method)(current->value));
459: current = current->next;
460: }
461:
462: return clone;
463: }
464:
465: METHOD(linked_list_t, equals_offset, bool,
466: private_linked_list_t *this, linked_list_t *other_pub, size_t offset)
467: {
468: private_linked_list_t *other = (private_linked_list_t*)other_pub;
469: element_t *cur_t, *cur_o;
470:
471: if (this->count != other->count)
472: {
473: return FALSE;
474: }
475: cur_t = this->first;
476: cur_o = other->first;
477: while (cur_t && cur_o)
478: {
479: bool (**method)(void*,void*) = cur_t->value + offset;
480: if (!(*method)(cur_t->value, cur_o->value))
481: {
482: return FALSE;
483: }
484: cur_t = cur_t->next;
485: cur_o = cur_o->next;
486: }
487: return TRUE;
488: }
489:
490: METHOD(linked_list_t, equals_function, bool,
491: private_linked_list_t *this, linked_list_t *other_pub,
492: bool (*fn)(void*,void*))
493: {
494: private_linked_list_t *other = (private_linked_list_t*)other_pub;
495: element_t *cur_t, *cur_o;
496:
497: if (this->count != other->count)
498: {
499: return FALSE;
500: }
501: cur_t = this->first;
502: cur_o = other->first;
503: while (cur_t && cur_o)
504: {
505: if (!fn(cur_t->value, cur_o->value))
506: {
507: return FALSE;
508: }
509: cur_t = cur_t->next;
510: cur_o = cur_o->next;
511: }
512: return TRUE;
513: }
514:
515: METHOD(linked_list_t, destroy, void,
516: private_linked_list_t *this)
517: {
518: void *value;
519:
520: /* Remove all list items before destroying list */
521: while (remove_first(this, &value) == SUCCESS)
522: {
523: /* values are not destroyed so memory leaks are possible
524: * if list is not empty when deleting */
525: }
526: free(this);
527: }
528:
529: METHOD(linked_list_t, destroy_offset, void,
530: private_linked_list_t *this, size_t offset)
531: {
532: element_t *current = this->first, *next;
533:
534: while (current)
535: {
536: void (**method)(void*) = current->value + offset;
537: (*method)(current->value);
538: next = current->next;
539: free(current);
540: current = next;
541: }
542: free(this);
543: }
544:
545: METHOD(linked_list_t, destroy_function, void,
546: private_linked_list_t *this, void (*fn)(void*))
547: {
548: element_t *current = this->first, *next;
549:
550: while (current)
551: {
552: fn(current->value);
553: next = current->next;
554: free(current);
555: current = next;
556: }
557: free(this);
558: }
559:
560: /*
561: * Described in header.
562: */
563: linked_list_t *linked_list_create()
564: {
565: private_linked_list_t *this;
566:
567: INIT(this,
568: .public = {
569: .get_count = _get_count,
570: .create_enumerator = _create_enumerator,
571: .reset_enumerator = (void*)_reset_enumerator,
572: .get_first = _get_first,
573: .get_last = _get_last,
574: .find_first = _find_first,
575: .insert_first = _insert_first,
576: .insert_last = _insert_last,
577: .insert_before = (void*)_insert_before,
578: .remove_first = _remove_first,
579: .remove_last = _remove_last,
580: .remove = _remove_,
581: .remove_at = (void*)_remove_at,
582: .invoke_offset = _invoke_offset,
583: .invoke_function = _invoke_function,
584: .clone_offset = _clone_offset,
585: .equals_offset = _equals_offset,
586: .equals_function = _equals_function,
587: .destroy = _destroy,
588: .destroy_offset = _destroy_offset,
589: .destroy_function = _destroy_function,
590: },
591: );
592:
593: return &this->public;
594: }
595:
596: /*
597: * See header.
598: */
599: linked_list_t *linked_list_create_from_enumerator(enumerator_t *enumerator)
600: {
601: linked_list_t *list;
602: void *item;
603:
604: list = linked_list_create();
605:
606: while (enumerator->enumerate(enumerator, &item))
607: {
608: list->insert_last(list, item);
609: }
610: enumerator->destroy(enumerator);
611:
612: return list;
613: }
614:
615: /*
616: * See header.
617: */
618: linked_list_t *linked_list_create_with_items(void *item, ...)
619: {
620: linked_list_t *list;
621: va_list args;
622:
623: list = linked_list_create();
624:
625: va_start(args, item);
626: while (item)
627: {
628: list->insert_last(list, item);
629: item = va_arg(args, void*);
630: }
631: va_end(args);
632:
633: return list;
634: }