dbus/dbus-list.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-list.c Generic linked list utility (internal to D-BUS implementation)
   3  *
   4  * Copyright (C) 2002  Red Hat, Inc.
   5  *
   6  * Licensed under the Academic Free License version 2.1
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  */
  23
  24 #include "dbus-internals.h"
  25 #include "dbus-list.h"
  26 #include "dbus-mempool.h"
  27 #include "dbus-threads.h"
  28
  29 /**
  30  * @defgroup DBusList Linked list
  31  * @ingroup  DBusInternals
  32  * @brief DBusList data structure
  33  *
  34  * Types and functions related to DBusList.
  35  */
  36
  37 static DBusMemPool *list_pool;
  38 _DBUS_DEFINE_GLOBAL_LOCK (list);
  39
  40 /**
  41  * @defgroup DBusListInternals Linked list implementation details
  42  * @ingroup  DBusInternals
  43  * @brief DBusList implementation details
  44  *
  45  * The guts of DBusList.
  46  *
  47  * @{
  48  */
  49
  50 /* the mem pool is probably a speed hit, with the thread
  51  * lock, though it does still save memory - unknown.
  52  */
  53 static DBusList*
  54 alloc_link (void *data)
  55 {
  56   DBusList *link;
  57
  58   if (!_DBUS_LOCK (list))
  59     return NULL;
  60
  61   if (list_pool == NULL)
  62     {
  63       list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
  64
  65       if (list_pool == NULL)
  66         {
  67           _DBUS_UNLOCK (list);
  68           return NULL;
  69         }
  70
  71       link = _dbus_mem_pool_alloc (list_pool);
  72       if (link == NULL)
  73         {
  74           _dbus_mem_pool_free (list_pool);
  75           list_pool = NULL;
  76           _DBUS_UNLOCK (list);
  77           return NULL;
  78         }
  79     }
  80   else
  81     {
  82       link = _dbus_mem_pool_alloc (list_pool);
  83     }
  84
  85   if (link)
  86     link->data = data;
  87
  88   _DBUS_UNLOCK (list);
  89
  90   return link;
  91 }
  92
  93 static void
  94 free_link (DBusList *link)
  95 {
  96   _DBUS_LOCK (list);
  97   if (_dbus_mem_pool_dealloc (list_pool, link))
  98     {
  99       _dbus_mem_pool_free (list_pool);
 100       list_pool = NULL;
 101     }
 102
 103   _DBUS_UNLOCK (list);
 104 }
 105
 106 static void
 107 link_before (DBusList **list,
 108              DBusList  *before_this_link,
 109              DBusList  *link)
 110 {
 111   if (*list == NULL)
 112     {
 113       link->prev = link;
 114       link->next = link;
 115       *list = link;
 116     }
 117   else
 118     {
 119       link->next = before_this_link;
 120       link->prev = before_this_link->prev;
 121       before_this_link->prev = link;
 122       link->prev->next = link;
 123
 124       if (before_this_link == *list)
 125         *list = link;
 126     }
 127 }
 128
 129 #ifdef DBUS_BUILD_TESTS
 130 static void
 131 link_after (DBusList **list,
 132             DBusList  *after_this_link,
 133             DBusList  *link)
 134 {
 135   if (*list == NULL)
 136     {
 137       link->prev = link;
 138       link->next = link;
 139       *list = link;
 140     }
 141   else
 142     {
 143       link->prev = after_this_link;
 144       link->next = after_this_link->next;
 145       after_this_link->next = link;
 146       link->next->prev = link;
 147     }
 148 }
 149 #endif /* DBUS_BUILD_TESTS */
 150
 151 /** @} */
 152
 153 /**
 154  * @addtogroup DBusList
 155  * @{
 156  */
 157
 158 /**
 159  * @struct DBusList
 160  *
 161  * A node in a linked list.
 162  *
 163  * DBusList is a circular list; that is, the tail of the list
 164  * points back to the head of the list. The empty list is
 165  * represented by a #NULL pointer.
 166  */
 167
 168 /**
 169  * @def _dbus_list_get_next_link
 170  *
 171  * Gets the next link in the list, or #NULL if
 172  * there are no more links. Used for iteration.
 173  *
 174  * @code
 175  * DBusList *link;
 176  * link = _dbus_list_get_first_link (&list);
 177  * while (link != NULL)
 178  *   {
 179  *     printf ("value is %p\n", link->data);
 180  *     link = _dbus_list_get_next_link (&link);
 181  *   }
 182  * @endcode
 183  *
 184  * @param list address of the list head.
 185  * @param link current link.
 186  * @returns the next link, or %NULL if none.
 187  *
 188  */
 189
 190 /**
 191  * @def _dbus_list_get_prev_link
 192  *
 193  * Gets the previous link in the list, or #NULL if
 194  * there are no more links. Used for iteration.
 195  *
 196  * @code
 197  * DBusList *link;
 198  * link = _dbus_list_get_last_link (&list);
 199  * while (link != NULL)
 200  *   {
 201  *     printf ("value is %p\n", link->data);
 202  *     link = _dbus_list_get_prev_link (&link);
 203  *   }
 204  * @endcode
 205  *
 206  * @param list address of the list head.
 207  * @param link current link.
 208  * @returns the previous link, or %NULL if none.
 209  *
 210  */
 211
 212 /**
 213  * Allocates a linked list node. Useful for preallocating
 214  * nodes and using _dbus_list_append_link() to avoid
 215  * allocations.
 216  *
 217  * @param data the value to store in the link.
 218  * @returns a newly allocated link.
 219  */
 220 DBusList*
 221 _dbus_list_alloc_link (void *data)
 222 {
 223   return alloc_link (data);
 224 }
 225
 226 /**
 227  * Frees a linked list node allocated with _dbus_list_alloc_link.
 228  * Does not free the data in the node.
 229  *
 230  * @param link the list node
 231  */
 232 void
 233 _dbus_list_free_link (DBusList *link)
 234 {
 235   free_link (link);
 236 }
 237
 238
 239 /**
 240  * Appends a value to the list. May return #FALSE
 241  * if insufficient memory exists to add a list link.
 242  * This is a constant-time operation.
 243  *
 244  * @param list address of the list head.
 245  * @param data the value to append.
 246  * @returns #TRUE on success.
 247  */
 248 dbus_bool_t
 249 _dbus_list_append (DBusList **list,
 250                    void      *data)
 251 {
 252   if (!_dbus_list_prepend (list, data))
 253     return FALSE;
 254
 255   /* Now cycle the list forward one so the prepended node is the tail */
 256   *list = (*list)->next;
 257
 258   return TRUE;
 259 }
 260
 261 /**
 262  * Prepends a value to the list. May return #FALSE
 263  * if insufficient memory exists to add a list link.
 264  * This is a constant-time operation.
 265  *
 266  * @param list address of the list head.
 267  * @param data the value to prepend.
 268  * @returns #TRUE on success.
 269  */
 270 dbus_bool_t
 271 _dbus_list_prepend (DBusList **list,
 272                     void      *data)
 273 {
 274   DBusList *link;
 275
 276   link = alloc_link (data);
 277   if (link == NULL)
 278     return FALSE;
 279
 280   link_before (list, *list, link);
 281
 282   return TRUE;
 283 }
 284
 285 /**
 286  * Appends a link to the list.
 287  * Cannot fail due to out of memory.
 288  * This is a constant-time operation.
 289  *
 290  * @param list address of the list head.
 291  * @param link the link to append.
 292  */
 293 void
 294 _dbus_list_append_link (DBusList **list,
 295                         DBusList *link)
 296 {
 297   _dbus_list_prepend_link (list, link);
 298
 299   /* Now cycle the list forward one so the prepended node is the tail */
 300   *list = (*list)->next;
 301 }
 302
 303 /**
 304  * Prepends a link to the list.
 305  * Cannot fail due to out of memory.
 306  * This is a constant-time operation.
 307  *
 308  * @param list address of the list head.
 309  * @param link the link to prepend.
 310  */
 311 void
 312 _dbus_list_prepend_link (DBusList **list,
 313                          DBusList *link)
 314 {
 315   link_before (list, *list, link);
 316 }
 317
 318 #ifdef DBUS_BUILD_TESTS
 319 /**
 320  * Inserts data into the list before the given existing link.
 321  *
 322  * @param list the list to modify
 323  * @param before_this_link existing link to insert before, or #NULL to append
 324  * @param data the value to insert
 325  * @returns #TRUE on success, #FALSE if memory allocation fails
 326  */
 327 dbus_bool_t
 328 _dbus_list_insert_before (DBusList **list,
 329                           DBusList  *before_this_link,
 330                           void      *data)
 331 {
 332   DBusList *link;
 333
 334   if (before_this_link == NULL)
 335     return _dbus_list_append (list, data);
 336   else
 337     {
 338       link = alloc_link (data);
 339       if (link == NULL)
 340         return FALSE;
 341
 342       link_before (list, before_this_link, link);
 343     }
 344
 345   return TRUE;
 346 }
 347 #endif /* DBUS_BUILD_TESTS */
 348
 349 #ifdef DBUS_BUILD_TESTS
 350 /**
 351  * Inserts data into the list after the given existing link.
 352  *
 353  * @param list the list to modify
 354  * @param after_this_link existing link to insert after, or #NULL to prepend
 355  * @param data the value to insert
 356  * @returns #TRUE on success, #FALSE if memory allocation fails
 357  */
 358 dbus_bool_t
 359 _dbus_list_insert_after (DBusList **list,
 360                          DBusList  *after_this_link,
 361                          void      *data)
 362 {
 363   DBusList *link;
 364
 365   if (after_this_link == NULL)
 366     return _dbus_list_prepend (list, data);
 367   else
 368     {
 369       link = alloc_link (data);
 370       if (link == NULL)
 371         return FALSE;
 372
 373       link_after (list, after_this_link, link);
 374     }
 375
 376   return TRUE;
 377 }
 378 #endif /* DBUS_BUILD_TESTS */
 379
 380 /**
 381  * Inserts a link into the list before the given existing link.
 382  *
 383  * @param list the list to modify
 384  * @param before_this_link existing link to insert before, or #NULL to append
 385  * @param link the link to insert
 386  */
 387 void
 388 _dbus_list_insert_before_link (DBusList **list,
 389                                DBusList  *before_this_link,
 390                                DBusList  *link)
 391 {
 392   if (before_this_link == NULL)
 393     _dbus_list_append_link (list, link);
 394   else
 395     link_before (list, before_this_link, link);
 396 }
 397
 398 #ifdef DBUS_BUILD_TESTS
 399 /**
 400  * Inserts a link into the list after the given existing link.
 401  *
 402  * @param list the list to modify
 403  * @param after_this_link existing link to insert after, or #NULL to prepend
 404  * @param link the link to insert
 405  */
 406 void
 407 _dbus_list_insert_after_link (DBusList **list,
 408                               DBusList  *after_this_link,
 409                               DBusList  *link)
 410 {
 411   if (after_this_link == NULL)
 412     _dbus_list_prepend_link (list, link);
 413   else
 414     link_after (list, after_this_link, link);
 415 }
 416 #endif /* DBUS_BUILD_TESTS */
 417
 418 /**
 419  * Removes a value from the list. Only removes the
 420  * first value equal to the given data pointer,
 421  * even if multiple values exist which match.
 422  * This is a linear-time operation.
 423  *
 424  * @param list address of the list head.
 425  * @param data the value to remove.
 426  * @returns #TRUE if a value was found to remove.
 427  */
 428 dbus_bool_t
 429 _dbus_list_remove (DBusList **list,
 430                    void      *data)
 431 {
 432   DBusList *link;
 433
 434   link = *list;
 435   while (link != NULL)
 436     {
 437       if (link->data == data)
 438         {
 439           _dbus_list_remove_link (list, link);
 440           return TRUE;
 441         }
 442
 443       link = _dbus_list_get_next_link (list, link);
 444     }
 445
 446   return FALSE;
 447 }
 448
 449 /**
 450  * Removes a value from the list. Only removes the
 451  * last value equal to the given data pointer,
 452  * even if multiple values exist which match.
 453  * This is a linear-time operation.
 454  *
 455  * @param list address of the list head.
 456  * @param data the value to remove.
 457  * @returns #TRUE if a value was found to remove.
 458  */
 459 dbus_bool_t
 460 _dbus_list_remove_last (DBusList **list,
 461                         void      *data)
 462 {
 463   DBusList *link;
 464
 465   link = _dbus_list_find_last (list, data);
 466   if (link)
 467     {
 468       _dbus_list_remove_link (list, link);
 469       return TRUE;
 470     }
 471   else
 472     return FALSE;
 473 }
 474
 475 /**
 476  * Finds a value in the list. Returns the last link
 477  * with value equal to the given data pointer.
 478  * This is a linear-time operation.
 479  * Returns #NULL if no value found that matches.
 480  *
 481  * @param list address of the list head.
 482  * @param data the value to find.
 483  * @returns the link if found
 484  */
 485 DBusList*
 486 _dbus_list_find_last (DBusList **list,
 487                       void      *data)
 488 {
 489   DBusList *link;
 490
 491   link = _dbus_list_get_last_link (list);
 492
 493   while (link != NULL)
 494     {
 495       if (link->data == data)
 496         return link;
 497
 498       link = _dbus_list_get_prev_link (list, link);
 499     }
 500
 501   return NULL;
 502 }
 503
 504 /**
 505  * Removes the given link from the list, but doesn't
 506  * free it. _dbus_list_remove_link() both removes the
 507  * link and also frees it.
 508  *
 509  * @param list the list
 510  * @param link the link in the list
 511  */
 512 void
 513 _dbus_list_unlink (DBusList **list,
 514                    DBusList  *link)
 515 {
 516   if (link->next == link)
 517     {
 518       /* one-element list */
 519       *list = NULL;
 520     }
 521   else
 522     {
 523       link->prev->next = link->next;
 524       link->next->prev = link->prev;
 525
 526       if (*list == link)
 527         *list = link->next;
 528     }
 529
 530   link->next = NULL;
 531   link->prev = NULL;
 532 }
 533
 534 /**
 535  * Removes a link from the list. This is a constant-time operation.
 536  *
 537  * @param list address of the list head.
 538  * @param link the list link to remove.
 539  */
 540 void
 541 _dbus_list_remove_link (DBusList **list,
 542                         DBusList  *link)
 543 {
 544   _dbus_list_unlink (list, link);
 545   free_link (link);
 546 }
 547
 548 /**
 549  * Frees all links in the list and sets the list head to #NULL. Does
 550  * not free the data in each link, for obvious reasons. This is a
 551  * linear-time operation.
 552  *
 553  * @param list address of the list head.
 554  */
 555 void
 556 _dbus_list_clear (DBusList **list)
 557 {
 558   DBusList *link;
 559
 560   link = *list;
 561   while (link != NULL)
 562     {
 563       DBusList *next = _dbus_list_get_next_link (list, link);
 564
 565       free_link (link);
 566
 567       link = next;
 568     }
 569
 570   *list = NULL;
 571 }
 572
 573 /**
 574  * Gets the first link in the list.
 575  * This is a constant-time operation.
 576  *
 577  * @param list address of the list head.
 578  * @returns the first link, or #NULL for an empty list.
 579  */
 580 DBusList*
 581 _dbus_list_get_first_link (DBusList **list)
 582 {
 583   return *list;
 584 }
 585
 586 /**
 587  * Gets the last link in the list.
 588  * This is a constant-time operation.
 589  *
 590  * @param list address of the list head.
 591  * @returns the last link, or #NULL for an empty list.
 592  */
 593 DBusList*
 594 _dbus_list_get_last_link (DBusList **list)
 595 {
 596   if (*list == NULL)
 597     return NULL;
 598   else
 599     return (*list)->prev;
 600 }
 601
 602 /**
 603  * Gets the last data in the list.
 604  * This is a constant-time operation.
 605  *
 606  * @param list address of the list head.
 607  * @returns the last data in the list, or #NULL for an empty list.
 608  */
 609 void*
 610 _dbus_list_get_last (DBusList **list)
 611 {
 612   if (*list == NULL)
 613     return NULL;
 614   else
 615     return (*list)->prev->data;
 616 }
 617
 618 /**
 619  * Gets the first data in the list.
 620  * This is a constant-time operation.
 621  *
 622  * @param list address of the list head.
 623  * @returns the first data in the list, or #NULL for an empty list.
 624  */
 625 void*
 626 _dbus_list_get_first (DBusList **list)
 627 {
 628   if (*list == NULL)
 629     return NULL;
 630   else
 631     return (*list)->data;
 632 }
 633
 634 /**
 635  * Removes the first link in the list and returns it.  This is a
 636  * constant-time operation.
 637  *
 638  * @param list address of the list head.
 639  * @returns the first link in the list, or #NULL for an empty list.
 640  */
 641 DBusList*
 642 _dbus_list_pop_first_link (DBusList **list)
 643 {
 644   DBusList *link;
 645
 646   link = _dbus_list_get_first_link (list);
 647   if (link == NULL)
 648     return NULL;
 649
 650   _dbus_list_unlink (list, link);
 651
 652   return link;
 653 }
 654
 655 /**
 656  * Removes the first value in the list and returns it.  This is a
 657  * constant-time operation.
 658  *
 659  * @param list address of the list head.
 660  * @returns the first data in the list, or #NULL for an empty list.
 661  */
 662 void*
 663 _dbus_list_pop_first (DBusList **list)
 664 {
 665   DBusList *link;
 666   void *data;
 667
 668   link = _dbus_list_get_first_link (list);
 669   if (link == NULL)
 670     return NULL;
 671
 672   data = link->data;
 673   _dbus_list_remove_link (list, link);
 674
 675   return data;
 676 }
 677
 678 /**
 679  * Removes the last value in the list and returns it.  This is a
 680  * constant-time operation.
 681  *
 682  * @param list address of the list head.
 683  * @returns the last data in the list, or #NULL for an empty list.
 684  */
 685 void*
 686 _dbus_list_pop_last (DBusList **list)
 687 {
 688   DBusList *link;
 689   void *data;
 690
 691   link = _dbus_list_get_last_link (list);
 692   if (link == NULL)
 693     return NULL;
 694
 695   data = link->data;
 696   _dbus_list_remove_link (list, link);
 697
 698   return data;
 699 }
 700
 701 #ifdef DBUS_BUILD_TESTS
 702 /**
 703  * Removes the last link in the list and returns it.  This is a
 704  * constant-time operation.
 705  *
 706  * @param list address of the list head.
 707  * @returns the last link in the list, or #NULL for an empty list.
 708  */
 709 DBusList*
 710 _dbus_list_pop_last_link (DBusList **list)
 711 {
 712   DBusList *link;
 713
 714   link = _dbus_list_get_last_link (list);
 715   if (link == NULL)
 716     return NULL;
 717
 718   _dbus_list_unlink (list, link);
 719
 720   return link;
 721 }
 722 #endif /* DBUS_BUILD_TESTS */
 723
 724 /**
 725  * Copies a list. This is a linear-time operation.  If there isn't
 726  * enough memory to copy the entire list, the destination list will be
 727  * set to #NULL.
 728  *
 729  * @param list address of the head of the list to copy.
 730  * @param dest address where the copied list should be placed.
 731  * @returns #TRUE on success, #FALSE if not enough memory.
 732  */
 733 dbus_bool_t
 734 _dbus_list_copy (DBusList **list,
 735                  DBusList **dest)
 736 {
 737   DBusList *link;
 738
 739   _dbus_assert (list != dest);
 740
 741   *dest = NULL;
 742
 743   link = *list;
 744   while (link != NULL)
 745     {
 746       if (!_dbus_list_append (dest, link->data))
 747         {
 748           /* free what we have so far */
 749           _dbus_list_clear (dest);
 750           return FALSE;
 751         }
 752
 753       link = _dbus_list_get_next_link (list, link);
 754     }
 755
 756   return TRUE;
 757 }
 758
 759 /**
 760  * Gets the length of a list. This is a linear-time
 761  * operation.
 762  *
 763  * @param list address of the head of the list
 764  * @returns number of elements in the list.
 765  */
 766 int
 767 _dbus_list_get_length (DBusList **list)
 768 {
 769   DBusList *link;
 770   int length;
 771
 772   length = 0;
 773
 774   link = *list;
 775   while (link != NULL)
 776     {
 777       ++length;
 778
 779       link = _dbus_list_get_next_link (list, link);
 780     }
 781
 782   return length;
 783 }
 784
 785 /**
 786  * Calls the given function for each element in the list.  The
 787  * function is passed the list element as its first argument, and the
 788  * given data as its second argument.
 789  *
 790  * @param list address of the head of the list.
 791  * @param function function to call for each element.
 792  * @param data extra data for the function.
 793  *
 794  */
 795 void
 796 _dbus_list_foreach (DBusList          **list,
 797                     DBusForeachFunction function,
 798                     void               *data)
 799 {
 800   DBusList *link;
 801
 802   link = *list;
 803   while (link != NULL)
 804     {
 805       DBusList *next = _dbus_list_get_next_link (list, link);
 806
 807       (* function) (link->data, data);
 808
 809       link = next;
 810     }
 811 }
 812
 813 /**
 814  * Check whether length is exactly one.
 815  *
 816  * @param list the list
 817  * @returns #TRUE if length is exactly one
 818  */
 819 dbus_bool_t
 820 _dbus_list_length_is_one (DBusList **list)
 821 {
 822   return (*list != NULL &&
 823           (*list)->next == *list);
 824 }
 825
 826 /** @} */
 827
 828 #ifdef DBUS_BUILD_TESTS
 829 #include "dbus-test.h"
 830 #include <stdio.h>
 831
 832 static void
 833 verify_list (DBusList **list)
 834 {
 835   DBusList *link;
 836   int length;
 837
 838   link = *list;
 839
 840   if (link == NULL)
 841     return;
 842
 843   if (link->next == link)
 844     {
 845       _dbus_assert (link->prev == link);
 846       _dbus_assert (*list == link);
 847       return;
 848     }
 849
 850   length = 0;
 851   do
 852     {
 853       length += 1;
 854       _dbus_assert (link->prev->next == link);
 855       _dbus_assert (link->next->prev == link);
 856       link = link->next;
 857     }
 858   while (link != *list);
 859
 860   _dbus_assert (length == _dbus_list_get_length (list));
 861
 862   if (length == 1)
 863     _dbus_assert (_dbus_list_length_is_one (list));
 864   else
 865     _dbus_assert (!_dbus_list_length_is_one (list));
 866 }
 867
 868 static dbus_bool_t
 869 is_ascending_sequence (DBusList **list)
 870 {
 871   DBusList *link;
 872   int prev;
 873
 874   prev = _DBUS_INT_MIN;
 875
 876   link = _dbus_list_get_first_link (list);
 877   while (link != NULL)
 878     {
 879       int v = _DBUS_POINTER_TO_INT (link->data);
 880
 881       if (v <= prev)
 882         return FALSE;
 883
 884       prev = v;
 885
 886       link = _dbus_list_get_next_link (list, link);
 887     }
 888
 889   return TRUE;
 890 }
 891
 892 static dbus_bool_t
 893 is_descending_sequence (DBusList **list)
 894 {
 895   DBusList *link;
 896   int prev;
 897
 898   prev = _DBUS_INT_MAX;
 899
 900   link = _dbus_list_get_first_link (list);
 901   while (link != NULL)
 902     {
 903       int v = _DBUS_POINTER_TO_INT (link->data);
 904
 905       if (v >= prev)
 906         return FALSE;
 907
 908       prev = v;
 909
 910       link = _dbus_list_get_next_link (list, link);
 911     }
 912
 913   return TRUE;
 914 }
 915
 916 static dbus_bool_t
 917 all_even_values (DBusList **list)
 918 {
 919   DBusList *link;
 920
 921   link = _dbus_list_get_first_link (list);
 922   while (link != NULL)
 923     {
 924       int v = _DBUS_POINTER_TO_INT (link->data);
 925
 926       if ((v % 2) != 0)
 927         return FALSE;
 928
 929       link = _dbus_list_get_next_link (list, link);
 930     }
 931
 932   return TRUE;
 933 }
 934
 935 static dbus_bool_t
 936 all_odd_values (DBusList **list)
 937 {
 938   DBusList *link;
 939
 940   link = _dbus_list_get_first_link (list);
 941   while (link != NULL)
 942     {
 943       int v = _DBUS_POINTER_TO_INT (link->data);
 944
 945       if ((v % 2) == 0)
 946         return FALSE;
 947
 948       link = _dbus_list_get_next_link (list, link);
 949     }
 950
 951   return TRUE;
 952 }
 953
 954 static dbus_bool_t
 955 lists_equal (DBusList **list1,
 956              DBusList **list2)
 957 {
 958   DBusList *link1;
 959   DBusList *link2;
 960
 961   link1 = _dbus_list_get_first_link (list1);
 962   link2 = _dbus_list_get_first_link (list2);
 963   while (link1 && link2)
 964     {
 965       if (link1->data != link2->data)
 966         return FALSE;
 967
 968       link1 = _dbus_list_get_next_link (list1, link1);
 969       link2 = _dbus_list_get_next_link (list2, link2);
 970     }
 971
 972   if (link1 || link2)
 973     return FALSE;
 974
 975   return TRUE;
 976 }
 977
 978 /**
 979  * @ingroup DBusListInternals
 980  * Unit test for DBusList
 981  * @returns #TRUE on success.
 982  */
 983 dbus_bool_t
 984 _dbus_list_test (void)
 985 {
 986   DBusList *list1;
 987   DBusList *list2;
 988   DBusList *link1;
 989   DBusList *link2;
 990   DBusList *copy1;
 991   DBusList *copy2;
 992   int i;
 993
 994   list1 = NULL;
 995   list2 = NULL;
 996
 997   /* Test append and prepend */
 998
 999   i = 0;
1000   while (i < 10)
1001     {
1002       if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1003         _dbus_assert_not_reached ("could not allocate for append");
1004
1005       if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1006         _dbus_assert_not_reached ("count not allocate for prepend");
1007       ++i;
1008
1009       verify_list (&list1);
1010       verify_list (&list2);
1011
1012       _dbus_assert (_dbus_list_get_length (&list1) == i);
1013       _dbus_assert (_dbus_list_get_length (&list2) == i);
1014     }
1015
1016   _dbus_assert (is_ascending_sequence (&list1));
1017   _dbus_assert (is_descending_sequence (&list2));
1018
1019   /* Test list clear */
1020   _dbus_list_clear (&list1);
1021   _dbus_list_clear (&list2);
1022
1023   verify_list (&list1);
1024   verify_list (&list2);
1025
1026   /* Test get_first, get_last, pop_first, pop_last */
1027
1028   i = 0;
1029   while (i < 10)
1030     {
1031       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1032       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1033       ++i;
1034     }
1035
1036   --i;
1037   while (i >= 0)
1038     {
1039       void *got_data1;
1040       void *got_data2;
1041
1042       void *data1;
1043       void *data2;
1044
1045       got_data1 = _dbus_list_get_last (&list1);
1046       got_data2 = _dbus_list_get_first (&list2);
1047
1048       data1 = _dbus_list_pop_last (&list1);
1049       data2 = _dbus_list_pop_first (&list2);
1050
1051       _dbus_assert (got_data1 == data1);
1052       _dbus_assert (got_data2 == data2);
1053
1054       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1055       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1056
1057       verify_list (&list1);
1058       verify_list (&list2);
1059
1060       _dbus_assert (is_ascending_sequence (&list1));
1061       _dbus_assert (is_descending_sequence (&list2));
1062
1063       --i;
1064     }
1065
1066   _dbus_assert (list1 == NULL);
1067   _dbus_assert (list2 == NULL);
1068
1069   /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1070
1071   i = 0;
1072   while (i < 10)
1073     {
1074       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1075       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1076       ++i;
1077     }
1078
1079   --i;
1080   while (i >= 0)
1081     {
1082       DBusList *got_link1;
1083       DBusList *got_link2;
1084
1085       DBusList *link1;
1086       DBusList *link2;
1087
1088       void *data1;
1089       void *data2;
1090
1091       got_link1 = _dbus_list_get_last_link (&list1);
1092       got_link2 = _dbus_list_get_first_link (&list2);
1093
1094       link1 = _dbus_list_pop_last_link (&list1);
1095       link2 = _dbus_list_pop_first_link (&list2);
1096
1097       _dbus_assert (got_link1 == link1);
1098       _dbus_assert (got_link2 == link2);
1099
1100       data1 = link1->data;
1101       data2 = link2->data;
1102
1103       _dbus_list_free_link (link1);
1104       _dbus_list_free_link (link2);
1105
1106       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1107       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1108
1109       verify_list (&list1);
1110       verify_list (&list2);
1111
1112       _dbus_assert (is_ascending_sequence (&list1));
1113       _dbus_assert (is_descending_sequence (&list2));
1114
1115       --i;
1116     }
1117
1118   _dbus_assert (list1 == NULL);
1119   _dbus_assert (list2 == NULL);
1120
1121   /* Test iteration */
1122
1123   i = 0;
1124   while (i < 10)
1125     {
1126       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1127       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1128       ++i;
1129
1130       verify_list (&list1);
1131       verify_list (&list2);
1132
1133       _dbus_assert (_dbus_list_get_length (&list1) == i);
1134       _dbus_assert (_dbus_list_get_length (&list2) == i);
1135     }
1136
1137   _dbus_assert (is_ascending_sequence (&list1));
1138   _dbus_assert (is_descending_sequence (&list2));
1139
1140   --i;
1141   link2 = _dbus_list_get_first_link (&list2);
1142   while (link2 != NULL)
1143     {
1144       verify_list (&link2); /* pretend this link is the head */
1145
1146       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1147
1148       link2 = _dbus_list_get_next_link (&list2, link2);
1149       --i;
1150     }
1151
1152   i = 0;
1153   link1 = _dbus_list_get_first_link (&list1);
1154   while (link1 != NULL)
1155     {
1156       verify_list (&link1); /* pretend this link is the head */
1157
1158       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1159
1160       link1 = _dbus_list_get_next_link (&list1, link1);
1161       ++i;
1162     }
1163
1164   --i;
1165   link1 = _dbus_list_get_last_link (&list1);
1166   while (link1 != NULL)
1167     {
1168       verify_list (&link1); /* pretend this link is the head */
1169
1170       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1171
1172       link1 = _dbus_list_get_prev_link (&list1, link1);
1173       --i;
1174     }
1175
1176   _dbus_list_clear (&list1);
1177   _dbus_list_clear (&list2);
1178
1179   /* Test remove */
1180
1181   i = 0;
1182   while (i < 10)
1183     {
1184       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1185       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1186       ++i;
1187     }
1188
1189   --i;
1190   while (i >= 0)
1191     {
1192       if ((i % 2) == 0)
1193         {
1194           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1195             _dbus_assert_not_reached ("element should have been in list");
1196           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1197             _dbus_assert_not_reached ("element should have been in list");
1198
1199           verify_list (&list1);
1200           verify_list (&list2);
1201         }
1202       --i;
1203     }
1204
1205   _dbus_assert (all_odd_values (&list1));
1206   _dbus_assert (all_odd_values (&list2));
1207
1208   _dbus_list_clear (&list1);
1209   _dbus_list_clear (&list2);
1210
1211   /* test removing the other half of the elements */
1212
1213   i = 0;
1214   while (i < 10)
1215     {
1216       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1217       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1218       ++i;
1219     }
1220
1221   --i;
1222   while (i >= 0)
1223     {
1224       if ((i % 2) != 0)
1225         {
1226           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1227             _dbus_assert_not_reached ("element should have been in list");
1228           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1229             _dbus_assert_not_reached ("element should have been in list");
1230
1231           verify_list (&list1);
1232           verify_list (&list2);
1233         }
1234       --i;
1235     }
1236
1237   _dbus_assert (all_even_values (&list1));
1238   _dbus_assert (all_even_values (&list2));
1239
1240   /* clear list using remove_link */
1241   while (list1 != NULL)
1242     {
1243       _dbus_list_remove_link (&list1, list1);
1244       verify_list (&list1);
1245     }
1246   while (list2 != NULL)
1247     {
1248       _dbus_list_remove_link (&list2, list2);
1249       verify_list (&list2);
1250     }
1251
1252   /* Test remove link more generally */
1253   i = 0;
1254   while (i < 10)
1255     {
1256       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1257       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1258       ++i;
1259     }
1260
1261   --i;
1262   link2 = _dbus_list_get_first_link (&list2);
1263   while (link2 != NULL)
1264     {
1265       DBusList *next = _dbus_list_get_next_link (&list2, link2);
1266
1267       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1268
1269       if ((i % 2) == 0)
1270         _dbus_list_remove_link (&list2, link2);
1271
1272       verify_list (&list2);
1273
1274       link2 = next;
1275       --i;
1276     }
1277
1278   _dbus_assert (all_odd_values (&list2));
1279   _dbus_list_clear (&list2);
1280
1281   i = 0;
1282   link1 = _dbus_list_get_first_link (&list1);
1283   while (link1 != NULL)
1284     {
1285       DBusList *next = _dbus_list_get_next_link (&list1, link1);
1286
1287       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1288
1289       if ((i % 2) != 0)
1290         _dbus_list_remove_link (&list1, link1);
1291
1292       verify_list (&list1);
1293
1294       link1 = next;
1295       ++i;
1296     }
1297
1298   _dbus_assert (all_even_values (&list1));
1299   _dbus_list_clear (&list1);
1300
1301   /* Test copying a list */
1302   i = 0;
1303   while (i < 10)
1304     {
1305       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1306       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1307       ++i;
1308     }
1309
1310   /* bad pointers, because they are allowed in the copy dest */
1311   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1312   copy2 = _DBUS_INT_TO_POINTER (23);
1313
1314   _dbus_list_copy (&list1, &copy1);
1315   verify_list (&list1);
1316   verify_list (&copy1);
1317   _dbus_assert (lists_equal (&list1, &copy1));
1318
1319   _dbus_list_copy (&list2, &copy2);
1320   verify_list (&list2);
1321   verify_list (&copy2);
1322   _dbus_assert (lists_equal (&list2, &copy2));
1323
1324   /* Now test copying empty lists */
1325   _dbus_list_clear (&list1);
1326   _dbus_list_clear (&list2);
1327   _dbus_list_clear (&copy1);
1328   _dbus_list_clear (&copy2);
1329
1330   /* bad pointers, because they are allowed in the copy dest */
1331   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1332   copy2 = _DBUS_INT_TO_POINTER (23);
1333
1334   _dbus_list_copy (&list1, &copy1);
1335   verify_list (&list1);
1336   verify_list (&copy1);
1337   _dbus_assert (lists_equal (&list1, &copy1));
1338
1339   _dbus_list_copy (&list2, &copy2);
1340   verify_list (&list2);
1341   verify_list (&copy2);
1342   _dbus_assert (lists_equal (&list2, &copy2));
1343
1344   _dbus_list_clear (&list1);
1345   _dbus_list_clear (&list2);
1346
1347   /* insert_before on empty list */
1348   _dbus_list_insert_before (&list1, NULL,
1349                             _DBUS_INT_TO_POINTER (0));
1350   verify_list (&list1);
1351
1352   /* inserting before first element */
1353   _dbus_list_insert_before (&list1, list1,
1354                             _DBUS_INT_TO_POINTER (2));
1355   verify_list (&list1);
1356   _dbus_assert (is_descending_sequence (&list1));
1357
1358   /* inserting in the middle */
1359   _dbus_list_insert_before (&list1, list1->next,
1360                             _DBUS_INT_TO_POINTER (1));
1361   verify_list (&list1);
1362   _dbus_assert (is_descending_sequence (&list1));
1363
1364   /* using insert_before to append */
1365   _dbus_list_insert_before (&list1, NULL,
1366                             _DBUS_INT_TO_POINTER (-1));
1367   verify_list (&list1);
1368   _dbus_assert (is_descending_sequence (&list1));
1369
1370   _dbus_list_clear (&list1);
1371
1372   /* insert_after on empty list */
1373   _dbus_list_insert_after (&list1, NULL,
1374                            _DBUS_INT_TO_POINTER (0));
1375   verify_list (&list1);
1376
1377   /* inserting after first element */
1378   _dbus_list_insert_after (&list1, list1,
1379                            _DBUS_INT_TO_POINTER (1));
1380   verify_list (&list1);
1381   _dbus_assert (is_ascending_sequence (&list1));
1382
1383   /* inserting at the end */
1384   _dbus_list_insert_after (&list1, list1->next,
1385                            _DBUS_INT_TO_POINTER (2));
1386   verify_list (&list1);
1387   _dbus_assert (is_ascending_sequence (&list1));
1388
1389   /* using insert_after to prepend */
1390   _dbus_list_insert_after (&list1, NULL,
1391                            _DBUS_INT_TO_POINTER (-1));
1392   verify_list (&list1);
1393   _dbus_assert (is_ascending_sequence (&list1));
1394
1395   _dbus_list_clear (&list1);
1396
1397   /* using remove_last */
1398   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1399   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1400   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1401
1402   _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1403
1404   verify_list (&list1);
1405   _dbus_assert (is_ascending_sequence (&list1));
1406
1407   _dbus_list_clear (&list1);
1408
1409   return TRUE;
1410 }
1411
1412 #endif