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 }