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