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