Annotation of embedaddon/strongswan/src/libstrongswan/collections/linked_list.c, revision 1.1
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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