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