src/libstrongswan/utils/linked_list.c

   1 /**
   2  * @file linked_list.c
   3  *
   4  * @brief Implementation of linked_list_t.
   5  *
   6  */
   7
   8 /*
   9  * Copyright (C) 2005-2006 Martin Willi
  10  * Copyright (C) 2005 Jan Hutter
  11  * Hochschule fuer Technik Rapperswil
  12  *
  13  * This program is free software; you can redistribute it and/or modify it
  14  * under the terms of the GNU General Public License as published by the
  15  * Free Software Foundation; either version 2 of the License, or (at your
  16  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  17  *
  18  * This program is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  20  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  21  * for more details.
  22  */
  23
  24 #include <stdlib.h>
  25
  26 #include "linked_list.h"
  27
  28 typedef struct element_t element_t;
  29
  30 /**
  31  * This element holds a pointer to the value it represents.
  32  */
  33 struct element_t {
  34
  35         /**
  36          * Value of a list item.
  37          */
  38         void *value;
  39
  40         /**
  41          * Previous list element.
  42          *
  43          * NULL if first element in list.
  44          */
  45         element_t *previous;
  46
  47         /**
  48          * Next list element.
  49          *
  50          * NULL if last element in list.
  51          */
  52         element_t *next;
  53 };
  54
  55 /**
  56  * Creates an empty linked list object.
  57  */
  58 element_t *element_create(void *value)
  59 {
  60         element_t *this = malloc_thing(element_t);
  61
  62         this->previous = NULL;
  63         this->next = NULL;
  64         this->value = value;
  65
  66         return (this);
  67 }
  68
  69
  70 typedef struct private_linked_list_t private_linked_list_t;
  71
  72 /**
  73  * Private data of a linked_list_t object.
  74  *
  75  */
  76 struct private_linked_list_t {
  77         /**
  78          * Public part of linked list.
  79          */
  80         linked_list_t public;
  81
  82         /**
  83          * Number of items in the list.
  84          */
  85         int count;
  86
  87         /**
  88          * First element in list.
  89          * NULL if no elements in list.
  90          */
  91         element_t *first;
  92
  93         /**
  94          * Last element in list.
  95          * NULL if no elements in list.
  96          */
  97         element_t *last;
  98 };
  99
 100
 101 typedef struct private_iterator_t private_iterator_t;
 102
 103 /**
 104  * Private variables and functions of linked list iterator.
 105  */
 106 struct private_iterator_t {
 107         /**
 108          * Public part of linked list iterator.
 109          */
 110         iterator_t public;
 111
 112         /**
 113          * Associated linked list.
 114          */
 115         private_linked_list_t * list;
 116
 117         /**
 118          * Current element of the iterator.
 119          */
 120         element_t *current;
 121
 122         /**
 123          * Direction of iterator.
 124          */
 125         bool forward;
 126
 127         /**
 128          * Mutex to use to synchronize access
 129          */
 130         pthread_mutex_t *mutex;
 131
 132         /**
 133          * iteration hook
 134          */
 135         iterator_hook_t *hook;
 136
 137         /**
 138          * user parameter for iterator hook
 139          */
 140         void *hook_param;
 141 };
 142
 143 /**
 144  * Implementation of iterator_t.get_count.
 145  */
 146 static int get_list_count(private_iterator_t *this)
 147 {
 148         return this->list->count;
 149 }
 150
 151 /**
 152  * default iterator hook which does nothing
 153  */
 154 static bool iterator_hook(void *param, void *in, void **out)
 155 {
 156         *out = in;
 157         return TRUE;
 158 }
 159
 160 /**
 161  * Implementation of iterator_t.set_iterator_hook.
 162  */
 163 static void set_iterator_hook(private_iterator_t *this, iterator_hook_t *hook,
 164                                                           void* param)
 165 {
 166         if (hook == NULL)
 167         {
 168                 this->hook = iterator_hook;
 169                 this->hook_param = NULL;
 170         }
 171         else
 172         {
 173                 this->hook = hook;
 174                 this->hook_param = param;
 175         }
 176 }
 177
 178 /**
 179  * Implementation of iterator_t.iterate.
 180  */
 181 static bool iterate(private_iterator_t *this, void** value)
 182 {
 183         if (this->list->count == 0)
 184         {
 185                 return FALSE;
 186         }
 187         if (this->current == NULL)
 188         {
 189                 this->current = (this->forward) ? this->list->first : this->list->last;
 190                 if (!this->hook(this->hook_param, this->current->value, value))
 191                 {
 192                         return iterate(this, value);
 193                 }
 194                 return TRUE;
 195         }
 196         if (this->forward)
 197         {
 198                 if (this->current->next == NULL)
 199                 {
 200                         return FALSE;
 201                 }
 202                 this->current = this->current->next;
 203                 if (!this->hook(this->hook_param, this->current->value, value))
 204                 {
 205                         return iterate(this, value);
 206                 }
 207                 return TRUE;
 208         }
 209         if (this->current->previous == NULL)
 210         {
 211                 return FALSE;
 212         }
 213         this->current = this->current->previous;
 214         if (!this->hook(this->hook_param, this->current->value, value))
 215         {
 216                 return iterate(this, value);
 217         }
 218         return TRUE;
 219 }
 220
 221 /**
 222  * Implementation of iterator_t.reset.
 223  */
 224 static void iterator_reset(private_iterator_t *this)
 225 {
 226         this->current = NULL;
 227 }
 228
 229 /**
 230  * Implementation of iterator_t.remove.
 231  */
 232 static status_t remove_(private_iterator_t *this)
 233 {
 234         element_t *new_current;
 235
 236         if (this->current == NULL)
 237         {
 238                 return NOT_FOUND;
 239         }
 240
 241         if (this->list->count == 0)
 242         {
 243                 return NOT_FOUND;
 244         }
 245         /* find out the new iterator position, depending on iterator direction */
 246         if (this->forward && this->current->previous != NULL)
 247         {
 248                 new_current = this->current->previous;
 249         }
 250         else if (!this->forward && this->current->next != NULL)
 251         {
 252                 new_current = this->current->next;
 253         }
 254         else
 255         {
 256                 new_current = NULL;
 257         }
 258
 259         /* now delete the entry :-) */
 260         if (this->current->previous == NULL)
 261         {
 262                 if (this->current->next == NULL)
 263                 {
 264                         this->list->first = NULL;
 265                         this->list->last = NULL;
 266                 }
 267                 else
 268                 {
 269                         this->current->next->previous = NULL;
 270                         this->list->first = this->current->next;
 271                 }
 272         }
 273         else if (this->current->next == NULL)
 274         {
 275                 this->current->previous->next = NULL;
 276                 this->list->last = this->current->previous;
 277         }
 278         else
 279         {
 280                 this->current->previous->next = this->current->next;
 281                 this->current->next->previous = this->current->previous;
 282         }
 283
 284         this->list->count--;
 285         free(this->current);
 286         /* set the new iterator position */
 287         this->current = new_current;
 288         return SUCCESS;
 289 }
 290
 291 /**
 292  * Implementation of iterator_t.insert_before.
 293  */
 294 static void insert_before(private_iterator_t * iterator, void *item)
 295 {
 296         if (iterator->current == NULL)
 297         {
 298                 iterator->list->public.insert_first(&(iterator->list->public), item);
 299         }
 300
 301         element_t *element = element_create(item);
 302         if (iterator->current->previous == NULL)
 303         {
 304                 iterator->current->previous = element;
 305                 element->next = iterator->current;
 306                 iterator->list->first = element;
 307         }
 308         else
 309         {
 310                 iterator->current->previous->next = element;
 311                 element->previous = iterator->current->previous;
 312                 iterator->current->previous = element;
 313                 element->next = iterator->current;
 314         }
 315         iterator->list->count++;
 316 }
 317
 318 /**
 319  * Implementation of iterator_t.replace.
 320  */
 321 static status_t replace(private_iterator_t *this, void **old_item, void *new_item)
 322 {
 323         if (this->current == NULL)
 324         {
 325                 return NOT_FOUND;
 326         }
 327         if (old_item != NULL)
 328         {
 329                 *old_item = this->current->value;
 330         }
 331         this->current->value = new_item;
 332
 333         return SUCCESS;
 334 }
 335
 336 /**
 337  * Implementation of iterator_t.insert_after.
 338  */
 339 static void insert_after(private_iterator_t *iterator, void *item)
 340 {
 341         if (iterator->current == NULL)
 342         {
 343                 iterator->list->public.insert_first(&(iterator->list->public),item);
 344                 return;
 345         }
 346
 347         element_t *element = element_create(item);
 348         if (iterator->current->next == NULL)
 349         {
 350                 iterator->current->next = element;
 351                 element->previous = iterator->current;
 352                 iterator->list->last = element;
 353         }
 354         else
 355         {
 356                 iterator->current->next->previous = element;
 357                 element->next = iterator->current->next;
 358                 iterator->current->next = element;
 359                 element->previous = iterator->current;
 360         }
 361         iterator->list->count++;
 362 }
 363
 364 /**
 365  * Implementation of iterator_t.destroy.
 366  */
 367 static void iterator_destroy(private_iterator_t *this)
 368 {
 369         if (this->mutex)
 370         {
 371                 pthread_mutex_unlock(this->mutex);
 372         }
 373         free(this);
 374 }
 375
 376 /**
 377  * Implementation of linked_list_t.get_count.
 378  */
 379 static int get_count(private_linked_list_t *this)
 380 {
 381         return this->count;
 382 }
 383
 384 /**
 385  * Implementation of linked_list_t.insert_first.
 386  */
 387 static void insert_first(private_linked_list_t *this, void *item)
 388 {
 389         element_t *element;
 390
 391         element = element_create(item);
 392         if (this->count == 0)
 393         {
 394                 /* first entry in list */
 395                 this->first = element;
 396                 this->last = element;
 397                 element->previous = NULL;
 398                 element->next = NULL;
 399         }
 400         else
 401         {
 402                 element_t *old_first_element = this->first;
 403                 element->next = old_first_element;
 404                 element->previous = NULL;
 405                 old_first_element->previous = element;
 406                 this->first = element;
 407         }
 408         this->count++;
 409 }
 410
 411 /**
 412  * Implementation of linked_list_t.remove_first.
 413  */
 414 static status_t remove_first(private_linked_list_t *this, void **item)
 415 {
 416         element_t *element = this->first;
 417
 418         if (element == NULL)
 419         {
 420                 return NOT_FOUND;
 421         }
 422         if (element->next != NULL)
 423         {
 424                 element->next->previous = NULL;
 425         }
 426         this->first = element->next;
 427
 428         if (item != NULL)
 429         {
 430                 *item = element->value;
 431         }
 432         if (--this->count == 0)
 433         {
 434                 this->last = NULL;
 435         }
 436
 437         free(element);
 438
 439         return SUCCESS;
 440 }
 441
 442 /**
 443  * Implementation of linked_list_t.get_first.
 444  */
 445 static status_t get_first(private_linked_list_t *this, void **item)
 446 {
 447         if (this->count == 0)
 448         {
 449                 return NOT_FOUND;
 450         }
 451         *item = this->first->value;
 452         return SUCCESS;
 453 }
 454
 455 /**
 456  * Implementation of linked_list_t.insert_last.
 457  */
 458 static void insert_last(private_linked_list_t *this, void *item)
 459 {
 460         element_t *element = element_create(item);
 461
 462         if (this->count == 0)
 463         {
 464                 /* first entry in list */
 465                 this->first = element;
 466                 this->last = element;
 467                 element->previous = NULL;
 468                 element->next = NULL;
 469         }
 470         else
 471         {
 472                 element_t *old_last_element = this->last;
 473                 element->previous = old_last_element;
 474                 element->next = NULL;
 475                 old_last_element->next = element;
 476                 this->last = element;
 477         }
 478         this->count++;
 479 }
 480
 481 /**
 482  * Implementation of linked_list_t.remove_last.
 483  */
 484 static status_t remove_last(private_linked_list_t *this, void **item)
 485 {
 486         element_t *element = this->last;
 487
 488         if (element == NULL)
 489         {
 490                 return NOT_FOUND;
 491         }
 492         if (element->previous != NULL)
 493         {
 494                 element->previous->next = NULL;
 495         }
 496         this->last = element->previous;
 497
 498         if (item != NULL)
 499         {
 500                 *item = element->value;
 501         }
 502         if (--this->count == 0)
 503         {
 504                 this->first = NULL;
 505         }
 506
 507         free(element);
 508
 509         return SUCCESS;
 510 }
 511
 512 /**
 513  * Implementation of linked_list_t.insert_at_position.
 514  */
 515 static status_t insert_at_position (private_linked_list_t *this,size_t position, void *item)
 516 {
 517         element_t *current_element;
 518         int i;
 519
 520         if (this->count <= position)
 521         {
 522                 return INVALID_ARG;
 523         }
 524
 525         current_element =  this->first;
 526
 527         for (i = 0; i < position;i++)
 528         {
 529                 current_element = current_element->next;
 530         }
 531
 532         if (current_element == NULL)
 533         {
 534                 this->public.insert_last(&(this->public),item);
 535                 return SUCCESS;
 536         }
 537
 538         element_t *element = element_create(item);
 539         if (current_element->previous == NULL)
 540         {
 541                 current_element->previous = element;
 542                 element->next = current_element;
 543                 this->first = element;
 544         }
 545         else
 546         {
 547                 current_element->previous->next = element;
 548                 element->previous = current_element->previous;
 549                 current_element->previous = element;
 550                 element->next = current_element;
 551         }
 552
 553
 554         this->count++;
 555         return SUCCESS;
 556 }
 557
 558 /**
 559  * Implementation of linked_list_t.remove_at_position.
 560  */
 561 static status_t remove_at_position(private_linked_list_t *this,size_t position, void **item)
 562 {
 563         iterator_t *iterator;
 564         int i;
 565
 566         if (this->count <= position)
 567         {
 568                 return INVALID_ARG;
 569         }
 570
 571         iterator = this->public.create_iterator(&(this->public),TRUE);
 572         iterator->iterate(iterator, item);
 573         for (i = 0; i < position; i++)
 574         {
 575                 if (!iterator->iterate(iterator, item))
 576                 {
 577                         iterator->destroy(iterator);
 578                         return INVALID_ARG;
 579                 }
 580         }
 581         iterator->remove(iterator);
 582         iterator->destroy(iterator);
 583
 584         return SUCCESS;
 585 }
 586
 587 /**
 588  * Implementation of linked_list_t.get_at_position.
 589  */
 590 static status_t get_at_position(private_linked_list_t *this,size_t position, void **item)
 591 {
 592         int i;
 593         iterator_t *iterator;
 594
 595         if (this->count <= position)
 596         {
 597                 return INVALID_ARG;
 598         }
 599
 600         iterator = this->public.create_iterator(&(this->public),TRUE);
 601         iterator->iterate(iterator, item);
 602         for (i = 0; i < position; i++)
 603         {
 604                 if (!iterator->iterate(iterator, item))
 605                 {
 606                         iterator->destroy(iterator);
 607                         return INVALID_ARG;
 608                 }
 609         }
 610         iterator->destroy(iterator);
 611         return SUCCESS;
 612 }
 613
 614 /**
 615  * Implementation of linked_list_t.get_last.
 616  */
 617 static status_t get_last(private_linked_list_t *this, void **item)
 618 {
 619         if (this->count == 0)
 620         {
 621                 return NOT_FOUND;
 622         }
 623
 624         *item = this->last->value;
 625
 626         return SUCCESS;
 627 }
 628
 629 /**
 630  * Implementation of linked_list_t.invoke.
 631  */
 632 static void invoke(private_linked_list_t *this, size_t offset)
 633 {
 634         element_t *current = this->first;
 635
 636         while (current)
 637         {
 638                 void (**method)(void*) = current->value + offset;
 639                 (*method)(current->value);
 640                 current = current->next;
 641         }
 642 }
 643
 644 /**
 645  * Implementation of linked_list_t.destroy.
 646  */
 647 static void destroy(private_linked_list_t *this)
 648 {
 649         void *value;
 650         /* Remove all list items before destroying list */
 651         while (this->public.remove_first(&(this->public), &value) == SUCCESS)
 652         {
 653                 /* values are not destroyed so memory leaks are possible
 654                  * if list is not empty when deleting */
 655         }
 656         free(this);
 657 }
 658
 659 /**
 660  * Implementation of linked_list_t.destroy_offset.
 661  */
 662 static void destroy_offset(private_linked_list_t *this, size_t offset)
 663 {
 664         element_t *current = this->first, *next;
 665
 666         while (current)
 667         {
 668                 void (**method)(void*) = current->value + offset;
 669                 (*method)(current->value);
 670                 next = current->next;
 671                 free(current);
 672                 current = next;
 673         }
 674         free(this);
 675 }
 676
 677 /**
 678  * Implementation of linked_list_t.destroy_function.
 679  */
 680 static void destroy_function(private_linked_list_t *this, void (*fn)(void*))
 681 {
 682         element_t *current = this->first, *next;
 683
 684         while (current)
 685         {
 686                 fn(current->value);
 687                 next = current->next;
 688                 free(current);
 689                 current = next;
 690         }
 691         free(this);
 692 }
 693
 694 /**
 695  * Implementation of linked_list_t.create_iterator.
 696  */
 697 static iterator_t *create_iterator(private_linked_list_t *linked_list, bool forward)
 698 {
 699         private_iterator_t *this = malloc_thing(private_iterator_t);
 700
 701         this->public.get_count = (int (*) (iterator_t*)) get_list_count;
 702         this->public.iterate = (bool (*) (iterator_t*, void **value)) iterate;
 703         this->public.set_iterator_hook = (void(*)(iterator_t*, iterator_hook_t*, void*))set_iterator_hook;
 704         this->public.insert_before = (void (*) (iterator_t*, void *item)) insert_before;
 705         this->public.insert_after = (void (*) (iterator_t*, void *item)) insert_after;
 706         this->public.replace = (status_t (*) (iterator_t*, void **, void *)) replace;
 707         this->public.remove = (status_t (*) (iterator_t*)) remove_;
 708         this->public.reset = (void (*) (iterator_t*)) iterator_reset;
 709         this->public.destroy = (void (*) (iterator_t*)) iterator_destroy;
 710
 711         this->forward = forward;
 712         this->current = NULL;
 713         this->list = linked_list;
 714         this->mutex = NULL;
 715         this->hook = iterator_hook;
 716
 717         return &this->public;
 718 }
 719
 720 /**
 721  * Implementation of linked_list_t.create_iterator_locked.
 722  */
 723 static iterator_t *create_iterator_locked(private_linked_list_t *linked_list,
 724                                                                                   pthread_mutex_t *mutex)
 725 {
 726         private_iterator_t *this = (private_iterator_t*)create_iterator(linked_list, TRUE);
 727         this->mutex = mutex;
 728
 729         pthread_mutex_lock(mutex);
 730
 731         return &this->public;
 732 }
 733
 734 /*
 735  * Described in header.
 736  */
 737 linked_list_t *linked_list_create()
 738 {
 739         private_linked_list_t *this = malloc_thing(private_linked_list_t);
 740
 741         this->public.get_count = (int (*) (linked_list_t *)) get_count;
 742         this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool))create_iterator;
 743         this->public.create_iterator_locked = (iterator_t * (*) (linked_list_t *,pthread_mutex_t*))create_iterator_locked;
 744         this->public.get_first = (status_t (*) (linked_list_t *, void **item))get_first;
 745         this->public.get_last = (status_t (*) (linked_list_t *, void **item))get_last;
 746         this->public.insert_first = (void (*) (linked_list_t *, void *item))insert_first;
 747         this->public.insert_last = (void (*) (linked_list_t *, void *item))insert_last;
 748         this->public.remove_first = (status_t (*) (linked_list_t *, void **item))remove_first;
 749         this->public.remove_last = (status_t (*) (linked_list_t *, void **item))remove_last;
 750         this->public.insert_at_position = (status_t (*) (linked_list_t *,size_t, void *))insert_at_position;
 751         this->public.remove_at_position = (status_t (*) (linked_list_t *,size_t, void **))remove_at_position;
 752         this->public.get_at_position = (status_t (*) (linked_list_t *,size_t, void **))get_at_position;
 753         this->public.invoke = (void (*)(linked_list_t*,size_t))invoke;
 754         this->public.destroy = (void (*) (linked_list_t *))destroy;
 755         this->public.destroy_offset = (void (*) (linked_list_t *,size_t))destroy_offset;
 756         this->public.destroy_function = (void (*)(linked_list_t*,void(*)(void*)))destroy_function;
 757
 758         this->count = 0;
 759         this->first = NULL;
 760         this->last = NULL;
 761
 762         return &this->public;
 763 }