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