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