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