Source/charon/utils/linked_list.c

   1 /**
   2  * @file linked_list.c
   3  *
   4  * @brief Generic Double Linked List
   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 #include <utils/allocator.h>
  28
  29
  30 typedef struct linked_list_element_t linked_list_element_t;
  31
  32 /**
  33  * @brief Element of the linked_list.
  34  *
  35  * This element holds a pointer to the value of the list item itself.
  36  */
  37 struct linked_list_element_t {
  38         /**
  39          * value of a list item
  40          */
  41         void *value;
  42
  43         /**
  44          * @brief Destroys a linked_list_element object
  45          *
  46          * @param linked_list_element_t calling object
  47          * @returns SUCCESS if succeeded, FAILED otherwise
  48          */
  49         status_t (*destroy) (linked_list_element_t *this);
  50
  51         /**
  52          * previous list element
  53          * NULL if first element in list
  54          */
  55         linked_list_element_t *previous;
  56         /**
  57          * next list element
  58          * NULL if last element in list
  59          */
  60         linked_list_element_t *next;
  61 };
  62
  63 /**
  64  * @brief implements function destroy of linked_list_item_t
  65  */
  66 static status_t linked_list_element_destroy(linked_list_element_t *this)
  67 {
  68         if (this == NULL)
  69         {
  70                 return FAILED;
  71         }
  72         allocator_free(this);
  73         return SUCCESS;
  74 }
  75
  76 /**
  77  * @brief Creates an empty linked list object
  78  *
  79  * @param[in] value value of item to be set
  80  *
  81  * @warning only the pointer to the value is stored
  82  *
  83  * @return linked_list_element object
  84  */
  85
  86 linked_list_element_t *linked_list_element_create(void *value)
  87 {
  88         linked_list_element_t *this = allocator_alloc_thing(linked_list_element_t);
  89
  90         if (this == NULL)
  91         {
  92                 return NULL;
  93         }
  94
  95         this->destroy = linked_list_element_destroy;
  96
  97         this->previous=NULL;
  98         this->next=NULL;
  99         this->value = value;
 100
 101         return (this);
 102 }
 103
 104 /**
 105  * Private variables and functions of linked list
 106  *
 107  */
 108 typedef struct private_linked_list_t private_linked_list_t;
 109
 110 struct private_linked_list_t {
 111         /**
 112          * Public part of linked list
 113          */
 114         linked_list_t public;
 115
 116         /**
 117          * number of items in the list
 118          */
 119         int count;
 120
 121         /**
 122          * First element in list
 123          * NULL if no elements in list
 124          */
 125         linked_list_element_t *first;
 126         /**
 127          * Last element in list
 128          * NULL if no elements in list
 129          */
 130         linked_list_element_t *last;
 131 };
 132
 133
 134 /**
 135  * Private variables and functions of linked list iterator
 136  *
 137  */
 138 typedef struct private_linked_list_iterator_t private_linked_list_iterator_t;
 139
 140 struct private_linked_list_iterator_t {
 141         /**
 142          * Public part of linked list iterator
 143          */
 144         linked_list_iterator_t public;
 145
 146         /**
 147          * associated linked list
 148          */
 149         private_linked_list_t * list;
 150
 151         /**
 152          * current element of the iterator
 153          */
 154         linked_list_element_t *current;
 155
 156         /**
 157          * direction of iterator
 158          */
 159         bool forward;
 160 };
 161
 162 /**
 163  * Implements function has_next of linked_list_iteratr
 164  */
 165 bool iterator_has_next(private_linked_list_iterator_t *this)
 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                 return TRUE;
 175         }
 176         if (this->forward)
 177         {
 178                 if (this->current->next == NULL)
 179                 {
 180                         return FALSE;
 181                 }
 182                 this->current = this->current->next;
 183                 return TRUE;
 184         }
 185         /* backward */
 186         if (this->current->previous == NULL)
 187         {
 188                 return FALSE;
 189         }
 190         this->current = this->current->previous;
 191         return TRUE;
 192 }
 193
 194 /**
 195  * Implements function current of linked_list_iteratr
 196  */
 197 static status_t iterator_current(private_linked_list_iterator_t *this, void **value)
 198 {
 199         if (this == NULL)
 200         {
 201                 return FAILED;
 202         }
 203         if (this->current == NULL)
 204         {
 205                 return FAILED;
 206         }
 207         *value = this->current->value;
 208         return SUCCESS;
 209 }
 210
 211 /**
 212  * Implements function current of linked_list_iteratr
 213  */
 214 static status_t iterator_reset(private_linked_list_iterator_t *this)
 215 {
 216         if (this == NULL)
 217         {
 218                 return FAILED;
 219         }
 220         this->current = NULL;
 221         return SUCCESS;
 222 }
 223
 224 /**
 225  * Implements function destroy of linked_list_iteratr
 226  */
 227 static status_t iterator_destroy(private_linked_list_iterator_t *this)
 228 {
 229         if (this == NULL)
 230         {
 231                 return FAILED;
 232         }
 233         allocator_free(this);
 234         return SUCCESS;
 235 }
 236
 237 /**
 238  * @brief implements function get_count of linked_list_t
 239  */
 240 static int get_count(private_linked_list_t *this)
 241 {
 242         return this->count;
 243 }
 244
 245
 246 /**
 247  * @brief implements function insert_first of linked_list_t
 248  */
 249 static status_t insert_first(private_linked_list_t *this, void *item)
 250 {
 251         linked_list_element_t *element;
 252
 253         if (this == NULL)
 254         {
 255                 return FAILED;
 256         }
 257
 258         element =(linked_list_element_t *) linked_list_element_create(item);
 259
 260         if (element == NULL)
 261         {
 262                 return FAILED;
 263         }
 264
 265         if (this->count == 0)
 266         {
 267                 /* first entry in list */
 268                 this->first = element;
 269                 this->last = element;
 270                 element->previous = NULL;
 271                 element->next = NULL;
 272         }
 273         else
 274         {
 275                 if ((this->first == NULL) || (this->last == NULL))
 276                 {
 277                         /* should never happen */
 278                         element->destroy(element);
 279                         return FAILED;
 280                 }
 281                 linked_list_element_t *old_first_element = this->first;
 282                 element->next = old_first_element;
 283                 element->previous = NULL;
 284                 old_first_element->previous = element;
 285                 this->first = element;
 286         }
 287
 288         this->count++;
 289
 290         return SUCCESS;
 291 }
 292
 293 /**
 294  * @brief implements function remove_first of linked_list_t
 295  */
 296 static status_t remove_first(private_linked_list_t *this, void **item)
 297 {
 298         if (this == NULL)
 299         {
 300                 return FAILED;
 301         }
 302
 303         if (this->count == 0)
 304         {
 305                 return FAILED;
 306         }
 307
 308         if (this->first == NULL)
 309         {
 310                 return FAILED;
 311         }
 312
 313         linked_list_element_t *element = this->first;
 314
 315         if (element->next != NULL)
 316         {
 317                 element->next->previous = NULL;
 318         }
 319         this->first = element->next;
 320
 321         *item = element->value;
 322
 323         this->count--;
 324
 325         return  (element->destroy(element));
 326 }
 327
 328 /**
 329  * @brief implements function get_first of linked_list_t
 330  */
 331 static status_t get_first(private_linked_list_t *this, void **item)
 332 {
 333         if (this == NULL)
 334         {
 335                 return FAILED;
 336         }
 337
 338         if (this->count == 0)
 339         {
 340                 return FAILED;
 341         }
 342
 343         if (this->first == NULL)
 344         {
 345                 return FAILED;
 346         }
 347
 348         *item = this->first->value;
 349
 350         return SUCCESS;
 351 }
 352
 353 /**
 354  * @brief implements function insert_last of linked_list_t
 355  */
 356 static status_t insert_last(private_linked_list_t *this, void *item)
 357 {
 358         if (this == NULL)
 359         {
 360                 return FAILED;
 361         }
 362
 363         linked_list_element_t *element = (linked_list_element_t *) linked_list_element_create(item);
 364
 365         if (element == NULL)
 366         {
 367                 return FAILED;
 368         }
 369
 370         if (this->count == 0)
 371         {
 372                 /* first entry in list */
 373                 this->first = element;
 374                 this->last = element;
 375                 element->previous = NULL;
 376                 element->next = NULL;
 377         }else
 378         {
 379                 if ((this->first == NULL) || (this->last == NULL))
 380                 {
 381                         /* should never happen */
 382                         element->destroy(element);
 383                         return FAILED;
 384                 }
 385                 linked_list_element_t *old_last_element = this->last;
 386                 element->previous = old_last_element;
 387                 element->next = NULL;
 388                 old_last_element->next = element;
 389                 this->last = element;
 390         }
 391
 392         this->count++;
 393
 394         return SUCCESS;
 395 }
 396
 397 /**
 398  * @brief implements function remove_last of linked_list_t
 399  */
 400 static status_t remove_last(private_linked_list_t *this, void **item)
 401 {
 402         if (this == NULL)
 403         {
 404                 return FAILED;
 405         }
 406
 407         if (this->count == 0)
 408         {
 409                 return FAILED;
 410         }
 411
 412         if (this->last == NULL)
 413         {
 414                 return FAILED;
 415         }
 416
 417         linked_list_element_t *element = this->last;
 418
 419         if (element->previous != NULL)
 420         {
 421                 element->previous->next = NULL;
 422         }
 423         this->last = element->previous;
 424
 425         *item = element->value;
 426
 427         this->count--;
 428
 429         return  (element->destroy(element));
 430 }
 431
 432 /**
 433  * @brief implements function get_last of linked_list_t
 434  */
 435 static status_t get_last(private_linked_list_t *this, void **item)
 436 {
 437         if (this == NULL)
 438         {
 439                 return FAILED;
 440         }
 441
 442         if (this->count == 0)
 443         {
 444                 return FAILED;
 445         }
 446
 447         if (this->last == NULL)
 448         {
 449                 return FAILED;
 450         }
 451
 452         *item = this->last->value;
 453
 454         return SUCCESS;
 455 }
 456
 457 /**
 458  * @brief implements function insert_before of linked_list_t
 459  */
 460 static status_t insert_before(private_linked_list_iterator_t * iterator, void *item)
 461 {
 462         if (iterator->current == NULL)
 463         {
 464                 return (iterator->list->public.insert_first(&(iterator->list->public), item));
 465         }
 466
 467         linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
 468
 469         if (element == NULL)
 470         {
 471                 return FAILED;
 472         }
 473
 474         if (iterator->current->previous == NULL)
 475         {
 476                 if (iterator->list->first != iterator->current)
 477                 {
 478                         element->destroy(element);
 479                         return FAILED;
 480                 }
 481
 482                 iterator->current->previous = element;
 483                 element->next = iterator->current;
 484                 iterator->list->first = element;
 485         }
 486         else
 487         {
 488                 iterator->current->previous->next = element;
 489                 element->previous = iterator->current->previous;
 490                 iterator->current->previous = element;
 491                 element->next = iterator->current;
 492         }
 493
 494         iterator->list->count++;
 495
 496         return SUCCESS;
 497 }
 498
 499 /**
 500  * @brief implements function insert_after of linked_list_t
 501  */
 502 static status_t insert_after(private_linked_list_iterator_t * iterator, void *item)
 503 {
 504         if (iterator->current == NULL)
 505         {
 506                 return (iterator->list->public.insert_first(&(iterator->list->public),item));
 507         }
 508
 509         linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
 510
 511         if (element == NULL)
 512         {
 513                 return FAILED;
 514         }
 515
 516         if (iterator->current->next == NULL)
 517         {
 518                 if (iterator->list->last != iterator->current)
 519                 {
 520                         element->destroy(element);
 521                         return FAILED;
 522                 }
 523
 524                 iterator->current->next = element;
 525                 element->previous = iterator->current;
 526                 iterator->list->last = element;
 527         }
 528         else
 529         {
 530                 iterator->current->next->previous = element;
 531                 element->next = iterator->current->next;
 532                 iterator->current->next = element;
 533                 element->previous = iterator->current;
 534         }
 535
 536         iterator->list->count++;
 537         return SUCCESS;
 538 }
 539
 540 static status_t create_iterator (private_linked_list_t *linked_list, linked_list_iterator_t **iterator,bool forward)
 541 {
 542         private_linked_list_iterator_t *this = allocator_alloc_thing(private_linked_list_iterator_t);
 543
 544         if (this == NULL)
 545         {
 546                 return FAILED;
 547         }
 548
 549         this->public.has_next = (bool (*) (linked_list_iterator_t *this)) iterator_has_next;
 550         this->public.current = (status_t (*) (linked_list_iterator_t *this, void **value)) iterator_current;
 551         this->public.insert_before = (status_t (*) (linked_list_iterator_t *this, void *item)) insert_before;
 552         this->public.insert_after = (status_t (*) (linked_list_iterator_t *this, void *item)) insert_after;
 553         this->public.reset = (status_t (*) (linked_list_iterator_t *this)) iterator_reset;
 554         this->public.destroy = (status_t (*) (linked_list_iterator_t *this)) iterator_destroy;
 555
 556
 557         this->forward = forward;
 558         this->current = NULL;
 559         this->list = linked_list;
 560
 561         *iterator = &(this->public);
 562
 563         return (SUCCESS);
 564 }
 565
 566 /**
 567  * @brief implements function remove of linked_list_t
 568  */
 569 static status_t linked_list_remove(private_linked_list_t *this, private_linked_list_iterator_t * iterator)
 570 {
 571         linked_list_element_t *new_current;
 572
 573         if ((this == NULL) || (iterator == NULL) || (iterator->current == NULL))
 574         {
 575                 return FAILED;
 576         }
 577
 578         if (this->count == 0)
 579         {
 580                 return FAILED;
 581         }
 582         /* find out the new iterator position */
 583         if (iterator->current->previous != NULL)
 584         {
 585                 new_current = iterator->current->previous;
 586         }
 587         else if (iterator->current->next != NULL)
 588         {
 589                 new_current = iterator->current->next;
 590         }
 591         else
 592         {
 593                 new_current = NULL;
 594         }
 595
 596         /* now delete the entry :-) */
 597         if (iterator->current->previous == NULL)
 598         {
 599                 if (iterator->current->next == NULL)
 600                 {
 601                         this->first = NULL;
 602                         this->last = NULL;
 603                 }
 604                 else
 605                 {
 606                         iterator->current->next->previous = NULL;
 607                         this->first = iterator->current->next;
 608                 }
 609         }
 610         else if (iterator->current->next == NULL)
 611         {
 612                 iterator->current->previous->next = NULL;
 613                 this->last = iterator->current->previous;
 614         }
 615         else
 616         {
 617                 iterator->current->previous->next = iterator->current->next;
 618                 iterator->current->next->previous = iterator->current->previous;
 619         }
 620
 621         this->count--;
 622         iterator->current->destroy(iterator->current);
 623         /* set the new iterator position */
 624         iterator->current = new_current;
 625         return SUCCESS;
 626 }
 627
 628 /**
 629  * @brief implements function destroy of linked_list_t
 630  */
 631 static status_t linked_list_destroy(private_linked_list_t *this)
 632 {
 633         if (this == NULL)
 634         {
 635                 return FAILED;
 636         }
 637
 638         /* Remove all list items before destroying list */
 639         while (this->count > 0)
 640         {
 641                 void * value;
 642                 /* values are not destroyed so memory leaks are possible
 643                  * if list is not empty when deleting */
 644                 if (this->public.remove_first(&(this->public),&value) != SUCCESS)
 645                 {
 646                         allocator_free(this);
 647                         return FAILED;
 648                 }
 649         }
 650         allocator_free(this);
 651         return SUCCESS;
 652 }
 653
 654 /*
 655  * Described in header
 656  */
 657 linked_list_t *linked_list_create()
 658 {
 659         private_linked_list_t *this = allocator_alloc_thing(private_linked_list_t);
 660
 661         this->public.get_count = (int (*) (linked_list_t *linked_list)) get_count;
 662         this->public.create_iterator = (status_t (*) (linked_list_t *linked_list, linked_list_iterator_t **iterator,bool forward)) create_iterator;
 663         this->public.get_first = (status_t (*) (linked_list_t *linked_list, void **item)) get_first;
 664         this->public.get_last = (status_t (*) (linked_list_t *linked_list, void **item)) get_last;
 665         this->public.insert_first = (status_t (*) (linked_list_t *linked_list, void *item)) insert_first;
 666         this->public.insert_last = (status_t (*) (linked_list_t *linked_list, void *item)) insert_last;
 667         this->public.remove = (status_t (*) (linked_list_t *linked_list, linked_list_iterator_t * element)) linked_list_remove;
 668         this->public.remove_first = (status_t (*) (linked_list_t *linked_list, void **item)) remove_first;
 669         this->public.remove_last = (status_t (*) (linked_list_t *linked_list, void **item)) remove_last;
 670         this->public.destroy = (status_t (*) (linked_list_t *linked_list)) linked_list_destroy;
 671
 672         this->count = 0;
 673         this->first = NULL;
 674         this->last = NULL;
 675
 676         return (&(this->public));
 677 }