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