Source/lib/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.has_next.
 156  */
 157 static bool iterate(private_iterator_t *this, void** value)
 158 {
 159         if (this->list->count == 0)
 160         {
 161                 return FALSE;
 162         }
 163         if (this->current == NULL)
 164         {
 165                 this->current = (this->forward) ? this->list->first : this->list->last;
 166                 *value = this->current->value;
 167                 return TRUE;
 168         }
 169         if (this->forward)
 170         {
 171                 if (this->current->next == NULL)
 172                 {
 173                         return FALSE;
 174                 }
 175                 this->current = this->current->next;
 176                 *value = this->current->value;
 177                 return TRUE;
 178         }
 179         /* backward */
 180         if (this->current->previous == NULL)
 181         {
 182                 return FALSE;
 183         }
 184         this->current = this->current->previous;
 185         *value = this->current->value;
 186         return TRUE;
 187 }
 188
 189 /**
 190  * Implementation of iterator_t.has_next.
 191  */
 192 static bool iterator_has_next(private_iterator_t *this)
 193 {
 194         if (this->list->count == 0)
 195         {
 196                 return FALSE;
 197         }
 198         if (this->current == NULL)
 199         {
 200                 this->current = (this->forward) ? this->list->first : this->list->last;
 201                 return TRUE;
 202         }
 203         if (this->forward)
 204         {
 205                 if (this->current->next == NULL)
 206                 {
 207                         return FALSE;
 208                 }
 209                 this->current = this->current->next;
 210                 return TRUE;
 211         }
 212         /* backward */
 213         if (this->current->previous == NULL)
 214         {
 215                 return FALSE;
 216         }
 217         this->current = this->current->previous;
 218         return TRUE;
 219 }
 220
 221 /**
 222  * Implementation of iterator_t.current.
 223  */
 224 static status_t iterator_current(private_iterator_t *this, void **value)
 225 {
 226         if (this->current == NULL)
 227         {
 228                 return NOT_FOUND;
 229         }
 230         *value = this->current->value;
 231         return SUCCESS;
 232 }
 233
 234 /**
 235  * Implementation of iterator_t.reset.
 236  */
 237 static void iterator_reset(private_iterator_t *this)
 238 {
 239         this->current = NULL;
 240 }
 241
 242 /**
 243  * Implementation of iterator_t.remove.
 244  */
 245 static status_t remove(private_iterator_t *this)
 246 {
 247         linked_list_element_t *new_current;
 248
 249         if (this->current == NULL)
 250         {
 251                 return NOT_FOUND;
 252         }
 253
 254         if (this->list->count == 0)
 255         {
 256                 return NOT_FOUND;
 257         }
 258         /* find out the new iterator position */
 259         if (this->current->previous != NULL)
 260         {
 261                 new_current = this->current->previous;
 262         }
 263         else if (this->current->next != NULL)
 264         {
 265                 new_current = this->current->next;
 266         }
 267         else
 268         {
 269                 new_current = NULL;
 270         }
 271
 272         /* now delete the entry :-) */
 273         if (this->current->previous == NULL)
 274         {
 275                 if (this->current->next == NULL)
 276                 {
 277                         this->list->first = NULL;
 278                         this->list->last = NULL;
 279                 }
 280                 else
 281                 {
 282                         this->current->next->previous = NULL;
 283                         this->list->first = this->current->next;
 284                 }
 285         }
 286         else if (this->current->next == NULL)
 287         {
 288                 this->current->previous->next = NULL;
 289                 this->list->last = this->current->previous;
 290         }
 291         else
 292         {
 293                 this->current->previous->next = this->current->next;
 294                 this->current->next->previous = this->current->previous;
 295         }
 296
 297         this->list->count--;
 298         this->current->destroy(this->current);
 299         /* set the new iterator position */
 300         this->current = new_current;
 301         return SUCCESS;
 302 }
 303
 304 /**
 305  * Implementation of iterator_t.insert_before.
 306  */
 307 static void insert_before(private_iterator_t * iterator, void *item)
 308 {
 309         if (iterator->current == NULL)
 310         {
 311                 iterator->list->public.insert_first(&(iterator->list->public), item);
 312         }
 313
 314         linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
 315
 316         if (iterator->current->previous == NULL)
 317         {
 318                 iterator->current->previous = element;
 319                 element->next = iterator->current;
 320                 iterator->list->first = element;
 321         }
 322         else
 323         {
 324                 iterator->current->previous->next = element;
 325                 element->previous = iterator->current->previous;
 326                 iterator->current->previous = element;
 327                 element->next = iterator->current;
 328         }
 329
 330         iterator->list->count++;
 331 }
 332
 333 /**
 334  * Implementation of iterator_t.replace.
 335  */
 336 static status_t replace (private_iterator_t *this, void **old_item, void *new_item)
 337 {
 338         if (this->current == NULL)
 339         {
 340                 return NOT_FOUND;
 341         }
 342         if (old_item != NULL)
 343         {
 344                 *old_item = this->current->value;
 345         }
 346         this->current->value = new_item;
 347
 348         return SUCCESS;
 349 }
 350
 351 /**
 352  * Implementation of iterator_t.insert_after.
 353  */
 354 static void insert_after(private_iterator_t * iterator, void *item)
 355 {
 356         if (iterator->current == NULL)
 357         {
 358                 iterator->list->public.insert_first(&(iterator->list->public),item);
 359                 return;
 360         }
 361
 362         linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
 363
 364         if (iterator->current->next == NULL)
 365         {
 366                 iterator->current->next = element;
 367                 element->previous = iterator->current;
 368                 iterator->list->last = element;
 369         }
 370         else
 371         {
 372                 iterator->current->next->previous = element;
 373                 element->next = iterator->current->next;
 374                 iterator->current->next = element;
 375                 element->previous = iterator->current;
 376         }
 377         iterator->list->count++;
 378 }
 379
 380 /**
 381  * Implementation of iterator_t.destroy.
 382  */
 383 static void iterator_destroy(private_iterator_t *this)
 384 {
 385         free(this);
 386 }
 387
 388 /**
 389  * Implementation of linked_list_t.get_count.
 390  */
 391 static int get_count(private_linked_list_t *this)
 392 {
 393         return this->count;
 394 }
 395
 396 /**
 397  * Implementation of linked_list_t.call_on_items.
 398  */
 399 static void call_on_items(private_linked_list_t *this, void(*func)(void*))
 400 {
 401         iterator_t *iterator;
 402         void *item;
 403
 404         iterator = this->public.create_iterator(&(this->public),TRUE);
 405
 406         while (iterator->has_next(iterator))
 407         {
 408                 iterator->current(iterator, &item);
 409                 (*func)(item);
 410         }
 411         iterator->destroy(iterator);
 412 }
 413
 414 /**
 415  * Implementation of linked_list_t.insert_first.
 416  */
 417 static void insert_first(private_linked_list_t *this, void *item)
 418 {
 419         linked_list_element_t *element;
 420
 421         element =(linked_list_element_t *) linked_list_element_create(item);
 422
 423         if (this->count == 0)
 424         {
 425                 /* first entry in list */
 426                 this->first = element;
 427                 this->last = element;
 428                 element->previous = NULL;
 429                 element->next = NULL;
 430         }
 431         else
 432         {
 433                 linked_list_element_t *old_first_element = this->first;
 434                 element->next = old_first_element;
 435                 element->previous = NULL;
 436                 old_first_element->previous = element;
 437                 this->first = element;
 438         }
 439
 440         this->count++;
 441 }
 442
 443 /**
 444  * Implementation of linked_list_t.remove_first.
 445  */
 446 static status_t remove_first(private_linked_list_t *this, void **item)
 447 {
 448         if (this->count == 0)
 449         {
 450                 return NOT_FOUND;
 451         }
 452
 453         linked_list_element_t *element = this->first;
 454
 455         if (element->next != NULL)
 456         {
 457                 element->next->previous = NULL;
 458         }
 459         this->first = element->next;
 460
 461         if (item != NULL)
 462         {
 463                 *item = element->value;
 464         }
 465
 466         this->count--;
 467
 468         element->destroy(element);
 469
 470         return SUCCESS;
 471 }
 472
 473 /**
 474  * Implementation of linked_list_t.get_first.
 475  */
 476 static status_t get_first(private_linked_list_t *this, void **item)
 477 {
 478         if (this->count == 0)
 479         {
 480                 return NOT_FOUND;
 481         }
 482
 483         *item = this->first->value;
 484
 485         return SUCCESS;
 486 }
 487
 488 /**
 489  * Implementation of linked_list_t.insert_last.
 490  */
 491 static void insert_last(private_linked_list_t *this, void *item)
 492 {
 493         linked_list_element_t *element = (linked_list_element_t *) linked_list_element_create(item);
 494
 495         if (this->count == 0)
 496         {
 497                 /* first entry in list */
 498                 this->first = element;
 499                 this->last = element;
 500                 element->previous = NULL;
 501                 element->next = NULL;
 502         }
 503         else
 504         {
 505
 506                 linked_list_element_t *old_last_element = this->last;
 507                 element->previous = old_last_element;
 508                 element->next = NULL;
 509                 old_last_element->next = element;
 510                 this->last = element;
 511         }
 512
 513         this->count++;
 514 }
 515
 516 /**
 517  * Implementation of linked_list_t.remove_last.
 518  */
 519 static status_t remove_last(private_linked_list_t *this, void **item)
 520 {
 521         if (this->count == 0)
 522         {
 523                 return NOT_FOUND;
 524         }
 525
 526         linked_list_element_t *element = this->last;
 527
 528         if (element->previous != NULL)
 529         {
 530                 element->previous->next = NULL;
 531         }
 532         this->last = element->previous;
 533
 534         if (item != NULL)
 535         {
 536                 *item = element->value;
 537         }
 538
 539         this->count--;
 540
 541         element->destroy(element);
 542
 543         return SUCCESS;
 544 }
 545
 546 /**
 547  * Implementation of linked_list_t.insert_at_position.
 548  */
 549 static status_t insert_at_position (private_linked_list_t *this,size_t position, void *item)
 550 {
 551         linked_list_element_t *current_element;
 552         int i;
 553
 554         if (this->count <= position)
 555         {
 556                 return INVALID_ARG;
 557         }
 558
 559         current_element =  this->first;
 560
 561         for (i = 0; i < position;i++)
 562         {
 563                 current_element = current_element->next;
 564         }
 565
 566         if (current_element == NULL)
 567         {
 568                 this->public.insert_last(&(this->public),item);
 569                 return SUCCESS;
 570         }
 571
 572         linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
 573
 574
 575         if (current_element->previous == NULL)
 576         {
 577                 current_element->previous = element;
 578                 element->next = current_element;
 579                 this->first = element;
 580         }
 581         else
 582         {
 583                 current_element->previous->next = element;
 584                 element->previous = current_element->previous;
 585                 current_element->previous = element;
 586                 element->next = current_element;
 587         }
 588
 589
 590         this->count++;
 591         return SUCCESS;
 592 }
 593
 594 /**
 595  * Implementation of linked_list_t.remove_at_position.
 596  */
 597 static status_t remove_at_position (private_linked_list_t *this,size_t position, void **item)
 598 {
 599         iterator_t *iterator;
 600         int i;
 601
 602         if (this->count <= position)
 603         {
 604                 return INVALID_ARG;
 605         }
 606
 607         iterator = this->public.create_iterator(&(this->public),TRUE);
 608
 609         iterator->has_next(iterator);
 610         for (i = 0; i < position;i++)
 611         {
 612                 iterator->has_next(iterator);
 613         }
 614         iterator->current(iterator,item);
 615         iterator->remove(iterator);
 616         iterator->destroy(iterator);
 617
 618         return SUCCESS;
 619 }
 620
 621 /**
 622  * Implementation of linked_list_t.get_at_position.
 623  */
 624 static status_t get_at_position (private_linked_list_t *this,size_t position, void **item)
 625 {
 626         int i;
 627         iterator_t *iterator;
 628         status_t status;
 629         if (this->count <= position)
 630         {
 631                 return INVALID_ARG;
 632         }
 633
 634         iterator = this->public.create_iterator(&(this->public),TRUE);
 635
 636         iterator->has_next(iterator);
 637         for (i = 0; i < position;i++)
 638         {
 639                 iterator->has_next(iterator);
 640         }
 641         status = iterator->current(iterator,item);
 642         iterator->destroy(iterator);
 643         return status;
 644 }
 645
 646 /**
 647  * Implementation of linked_list_t.get_last.
 648  */
 649 static status_t get_last(private_linked_list_t *this, void **item)
 650 {
 651         if (this->count == 0)
 652         {
 653                 return NOT_FOUND;
 654         }
 655
 656         *item = this->last->value;
 657
 658         return SUCCESS;
 659 }
 660
 661 /**
 662  * Implementation of linked_list_t.create_iterator.
 663  */
 664 static iterator_t *create_iterator (private_linked_list_t *linked_list,bool forward)
 665 {
 666         private_iterator_t *this = malloc_thing(private_iterator_t);
 667
 668         this->public.iterate = (bool (*) (iterator_t *this, void **value)) iterate;
 669         this->public.has_next = (bool (*) (iterator_t *this)) iterator_has_next;
 670         this->public.current = (status_t (*) (iterator_t *this, void **value)) iterator_current;
 671         this->public.insert_before = (void (*) (iterator_t *this, void *item)) insert_before;
 672         this->public.insert_after = (void (*) (iterator_t *this, void *item)) insert_after;
 673         this->public.replace = (status_t (*) (iterator_t *, void **, void *)) replace;
 674         this->public.remove = (status_t (*) (iterator_t *this)) remove;
 675         this->public.reset = (void (*) (iterator_t *this)) iterator_reset;
 676         this->public.destroy = (void (*) (iterator_t *this)) iterator_destroy;
 677
 678         this->forward = forward;
 679         this->current = NULL;
 680         this->list = linked_list;
 681
 682         return &(this->public);
 683 }
 684
 685 /**
 686  * Implementation of linked_list_t.destroy.
 687  */
 688 static void linked_list_destroy(private_linked_list_t *this)
 689 {
 690         void * value;
 691         /* Remove all list items before destroying list */
 692         while (this->public.remove_first(&(this->public),&value) != NOT_FOUND)
 693         {
 694                 /* values are not destroyed so memory leaks are possible
 695                  * if list is not empty when deleting */
 696         }
 697         free(this);
 698 }
 699
 700 /*
 701  * Described in header.
 702  */
 703 linked_list_t *linked_list_create()
 704 {
 705         private_linked_list_t *this = malloc_thing(private_linked_list_t);
 706
 707         this->public.get_count = (int (*) (linked_list_t *)) get_count;
 708         this->public.create_iterator = (iterator_t * (*) (linked_list_t *,bool )) create_iterator;
 709         this->public.call_on_items = (void (*) (linked_list_t *, void(*func)(void*)))call_on_items;
 710         this->public.get_first = (status_t (*) (linked_list_t *, void **item)) get_first;
 711         this->public.get_last = (status_t (*) (linked_list_t *, void **item)) get_last;
 712         this->public.insert_first = (void (*) (linked_list_t *, void *item)) insert_first;
 713         this->public.insert_last = (void (*) (linked_list_t *, void *item)) insert_last;
 714         this->public.remove_first = (status_t (*) (linked_list_t *, void **item)) remove_first;
 715         this->public.remove_last = (status_t (*) (linked_list_t *, void **item)) remove_last;
 716         this->public.insert_at_position =(status_t (*) (linked_list_t *,size_t, void *)) insert_at_position;
 717         this->public.remove_at_position =(status_t (*) (linked_list_t *,size_t, void **)) remove_at_position;
 718         this->public.get_at_position =(status_t (*) (linked_list_t *,size_t, void **)) get_at_position;
 719
 720         this->public.destroy = (void (*) (linked_list_t *)) linked_list_destroy;
 721
 722         this->count = 0;
 723         this->first = NULL;
 724         this->last = NULL;
 725
 726         return (&(this->public));
 727 }