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