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  * Calls the given function for each element in the list.  The
 526  * function is passed the list element as its first argument, and the
 527  * given data as its second argument.
 528  *
 529  * @param list address of the head of the list.
 530  * @param function function to call for each element.
 531  * @param data extra data for the function.
 532  *
 533  */
 534 void
 535 _dbus_list_foreach (DBusList          **list,
 536                     DBusForeachFunction function,
 537                     void               *data)
 538 {
 539   DBusList *link;
 540
 541   link = *list;
 542   while (link != NULL)
 543     {
 544       DBusList *next = _dbus_list_get_next_link (list, link);
 545
 546       (* function) (link->data, data);
 547
 548       link = next;
 549     }
 550 }
 551
 552 /** @} */
 553
 554 #ifdef DBUS_BUILD_TESTS
 555 #include "dbus-test.h"
 556 #include <stdio.h>
 557
 558 static void
 559 verify_list (DBusList **list)
 560 {
 561   DBusList *link;
 562   int length;
 563
 564   link = *list;
 565
 566   if (link == NULL)
 567     return;
 568
 569   if (link->next == link)
 570     {
 571       _dbus_assert (link->prev == link);
 572       _dbus_assert (*list == link);
 573       return;
 574     }
 575
 576   length = 0;
 577   do
 578     {
 579       length += 1;
 580       _dbus_assert (link->prev->next == link);
 581       _dbus_assert (link->next->prev == link);
 582       link = link->next;
 583     }
 584   while (link != *list);
 585
 586   _dbus_assert (length == _dbus_list_get_length (list));
 587 }
 588
 589 static dbus_bool_t
 590 is_ascending_sequence (DBusList **list)
 591 {
 592   DBusList *link;
 593   int prev;
 594
 595   prev = _DBUS_INT_MIN;
 596
 597   link = _dbus_list_get_first_link (list);
 598   while (link != NULL)
 599     {
 600       int v = _DBUS_POINTER_TO_INT (link->data);
 601
 602       if (v <= prev)
 603         return FALSE;
 604
 605       prev = v;
 606
 607       link = _dbus_list_get_next_link (list, link);
 608     }
 609
 610   return TRUE;
 611 }
 612
 613 static dbus_bool_t
 614 is_descending_sequence (DBusList **list)
 615 {
 616   DBusList *link;
 617   int prev;
 618
 619   prev = _DBUS_INT_MAX;
 620
 621   link = _dbus_list_get_first_link (list);
 622   while (link != NULL)
 623     {
 624       int v = _DBUS_POINTER_TO_INT (link->data);
 625
 626       if (v >= prev)
 627         return FALSE;
 628
 629       prev = v;
 630
 631       link = _dbus_list_get_next_link (list, link);
 632     }
 633
 634   return TRUE;
 635 }
 636
 637 static dbus_bool_t
 638 all_even_values (DBusList **list)
 639 {
 640   DBusList *link;
 641
 642   link = _dbus_list_get_first_link (list);
 643   while (link != NULL)
 644     {
 645       int v = _DBUS_POINTER_TO_INT (link->data);
 646
 647       if ((v % 2) != 0)
 648         return FALSE;
 649
 650       link = _dbus_list_get_next_link (list, link);
 651     }
 652
 653   return TRUE;
 654 }
 655
 656 static dbus_bool_t
 657 all_odd_values (DBusList **list)
 658 {
 659   DBusList *link;
 660
 661   link = _dbus_list_get_first_link (list);
 662   while (link != NULL)
 663     {
 664       int v = _DBUS_POINTER_TO_INT (link->data);
 665
 666       if ((v % 2) == 0)
 667         return FALSE;
 668
 669       link = _dbus_list_get_next_link (list, link);
 670     }
 671
 672   return TRUE;
 673 }
 674
 675 static dbus_bool_t
 676 lists_equal (DBusList **list1,
 677              DBusList **list2)
 678 {
 679   DBusList *link1;
 680   DBusList *link2;
 681
 682   link1 = _dbus_list_get_first_link (list1);
 683   link2 = _dbus_list_get_first_link (list2);
 684   while (link1 && link2)
 685     {
 686       if (link1->data != link2->data)
 687         return FALSE;
 688
 689       link1 = _dbus_list_get_next_link (list1, link1);
 690       link2 = _dbus_list_get_next_link (list2, link2);
 691     }
 692
 693   if (link1 || link2)
 694     return FALSE;
 695
 696   return TRUE;
 697 }
 698
 699 /**
 700  * @ingroup DBusListInternals
 701  * Unit test for DBusList
 702  * @returns #TRUE on success.
 703  */
 704 dbus_bool_t
 705 _dbus_list_test (void)
 706 {
 707   DBusList *list1;
 708   DBusList *list2;
 709   DBusList *link1;
 710   DBusList *link2;
 711   DBusList *copy1;
 712   DBusList *copy2;
 713   int i;
 714
 715   list1 = NULL;
 716   list2 = NULL;
 717
 718   /* Test append and prepend */
 719
 720   i = 0;
 721   while (i < 10)
 722     {
 723       if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
 724         _dbus_assert_not_reached ("could not allocate for append");
 725
 726       if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
 727         _dbus_assert_not_reached ("count not allocate for prepend");
 728       ++i;
 729
 730       verify_list (&list1);
 731       verify_list (&list2);
 732
 733       _dbus_assert (_dbus_list_get_length (&list1) == i);
 734       _dbus_assert (_dbus_list_get_length (&list2) == i);
 735     }
 736
 737   _dbus_assert (is_ascending_sequence (&list1));
 738   _dbus_assert (is_descending_sequence (&list2));
 739
 740   /* Test list clear */
 741   _dbus_list_clear (&list1);
 742   _dbus_list_clear (&list2);
 743
 744   verify_list (&list1);
 745   verify_list (&list2);
 746
 747   /* Test get_first, get_last, pop_first, pop_last */
 748
 749   i = 0;
 750   while (i < 10)
 751     {
 752       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 753       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 754       ++i;
 755     }
 756
 757   --i;
 758   while (i >= 0)
 759     {
 760       void *got_data1;
 761       void *got_data2;
 762
 763       void *data1;
 764       void *data2;
 765
 766       got_data1 = _dbus_list_get_last (&list1);
 767       got_data2 = _dbus_list_get_first (&list2);
 768
 769       data1 = _dbus_list_pop_last (&list1);
 770       data2 = _dbus_list_pop_first (&list2);
 771
 772       _dbus_assert (got_data1 == data1);
 773       _dbus_assert (got_data2 == data2);
 774
 775       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
 776       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
 777
 778       verify_list (&list1);
 779       verify_list (&list2);
 780
 781       _dbus_assert (is_ascending_sequence (&list1));
 782       _dbus_assert (is_descending_sequence (&list2));
 783
 784       --i;
 785     }
 786
 787   _dbus_assert (list1 == NULL);
 788   _dbus_assert (list2 == NULL);
 789
 790   /* Test iteration */
 791
 792   i = 0;
 793   while (i < 10)
 794     {
 795       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 796       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 797       ++i;
 798
 799       verify_list (&list1);
 800       verify_list (&list2);
 801
 802       _dbus_assert (_dbus_list_get_length (&list1) == i);
 803       _dbus_assert (_dbus_list_get_length (&list2) == i);
 804     }
 805
 806   _dbus_assert (is_ascending_sequence (&list1));
 807   _dbus_assert (is_descending_sequence (&list2));
 808
 809   --i;
 810   link2 = _dbus_list_get_first_link (&list2);
 811   while (link2 != NULL)
 812     {
 813       verify_list (&link2); /* pretend this link is the head */
 814
 815       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
 816
 817       link2 = _dbus_list_get_next_link (&list2, link2);
 818       --i;
 819     }
 820
 821   i = 0;
 822   link1 = _dbus_list_get_first_link (&list1);
 823   while (link1 != NULL)
 824     {
 825       verify_list (&link1); /* pretend this link is the head */
 826
 827       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
 828
 829       link1 = _dbus_list_get_next_link (&list1, link1);
 830       ++i;
 831     }
 832
 833   _dbus_list_clear (&list1);
 834   _dbus_list_clear (&list2);
 835
 836   /* Test remove */
 837
 838   i = 0;
 839   while (i < 10)
 840     {
 841       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 842       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 843       ++i;
 844     }
 845
 846   --i;
 847   while (i >= 0)
 848     {
 849       if ((i % 2) == 0)
 850         {
 851           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
 852             _dbus_assert_not_reached ("element should have been in list");
 853           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
 854             _dbus_assert_not_reached ("element should have been in list");
 855
 856           verify_list (&list1);
 857           verify_list (&list2);
 858         }
 859       --i;
 860     }
 861
 862   _dbus_assert (all_odd_values (&list1));
 863   _dbus_assert (all_odd_values (&list2));
 864
 865   _dbus_list_clear (&list1);
 866   _dbus_list_clear (&list2);
 867
 868   /* test removing the other half of the elements */
 869
 870   i = 0;
 871   while (i < 10)
 872     {
 873       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 874       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 875       ++i;
 876     }
 877
 878   --i;
 879   while (i >= 0)
 880     {
 881       if ((i % 2) != 0)
 882         {
 883           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
 884             _dbus_assert_not_reached ("element should have been in list");
 885           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
 886             _dbus_assert_not_reached ("element should have been in list");
 887
 888           verify_list (&list1);
 889           verify_list (&list2);
 890         }
 891       --i;
 892     }
 893
 894   _dbus_assert (all_even_values (&list1));
 895   _dbus_assert (all_even_values (&list2));
 896
 897   /* clear list using remove_link */
 898   while (list1 != NULL)
 899     {
 900       _dbus_list_remove_link (&list1, list1);
 901       verify_list (&list1);
 902     }
 903   while (list2 != NULL)
 904     {
 905       _dbus_list_remove_link (&list2, list2);
 906       verify_list (&list2);
 907     }
 908
 909   /* Test remove link more generally */
 910   i = 0;
 911   while (i < 10)
 912     {
 913       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 914       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 915       ++i;
 916     }
 917
 918   --i;
 919   link2 = _dbus_list_get_first_link (&list2);
 920   while (link2 != NULL)
 921     {
 922       DBusList *next = _dbus_list_get_next_link (&list2, link2);
 923
 924       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
 925
 926       if ((i % 2) == 0)
 927         _dbus_list_remove_link (&list2, link2);
 928
 929       verify_list (&list2);
 930
 931       link2 = next;
 932       --i;
 933     }
 934
 935   _dbus_assert (all_odd_values (&list2));
 936   _dbus_list_clear (&list2);
 937
 938   i = 0;
 939   link1 = _dbus_list_get_first_link (&list1);
 940   while (link1 != NULL)
 941     {
 942       DBusList *next = _dbus_list_get_next_link (&list1, link1);
 943
 944       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
 945
 946       if ((i % 2) != 0)
 947         _dbus_list_remove_link (&list1, link1);
 948
 949       verify_list (&list1);
 950
 951       link1 = next;
 952       ++i;
 953     }
 954
 955   _dbus_assert (all_even_values (&list1));
 956   _dbus_list_clear (&list1);
 957
 958   /* Test copying a list */
 959   i = 0;
 960   while (i < 10)
 961     {
 962       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 963       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 964       ++i;
 965     }
 966
 967   /* bad pointers, because they are allowed in the copy dest */
 968   copy1 = _DBUS_INT_TO_POINTER (0x342234);
 969   copy2 = _DBUS_INT_TO_POINTER (23);
 970
 971   _dbus_list_copy (&list1, &copy1);
 972   verify_list (&list1);
 973   verify_list (&copy1);
 974   _dbus_assert (lists_equal (&list1, &copy1));
 975
 976   _dbus_list_copy (&list2, &copy2);
 977   verify_list (&list2);
 978   verify_list (&copy2);
 979   _dbus_assert (lists_equal (&list2, &copy2));
 980
 981   /* Now test copying empty lists */
 982   _dbus_list_clear (&list1);
 983   _dbus_list_clear (&list2);
 984   _dbus_list_clear (&copy1);
 985   _dbus_list_clear (&copy2);
 986
 987   /* bad pointers, because they are allowed in the copy dest */
 988   copy1 = _DBUS_INT_TO_POINTER (0x342234);
 989   copy2 = _DBUS_INT_TO_POINTER (23);
 990
 991   _dbus_list_copy (&list1, &copy1);
 992   verify_list (&list1);
 993   verify_list (&copy1);
 994   _dbus_assert (lists_equal (&list1, &copy1));
 995
 996   _dbus_list_copy (&list2, &copy2);
 997   verify_list (&list2);
 998   verify_list (&copy2);
 999   _dbus_assert (lists_equal (&list2, &copy2));
1000
1001   _dbus_list_clear (&list1);
1002   _dbus_list_clear (&list2);
1003
1004   /* insert_before on empty list */
1005   _dbus_list_insert_before (&list1, NULL,
1006                             _DBUS_INT_TO_POINTER (0));
1007   verify_list (&list1);
1008
1009   /* inserting before first element */
1010   _dbus_list_insert_before (&list1, list1,
1011                             _DBUS_INT_TO_POINTER (2));
1012   verify_list (&list1);
1013   _dbus_assert (is_descending_sequence (&list1));
1014
1015   /* inserting in the middle */
1016   _dbus_list_insert_before (&list1, list1->next,
1017                             _DBUS_INT_TO_POINTER (1));
1018   verify_list (&list1);
1019   _dbus_assert (is_descending_sequence (&list1));
1020
1021   /* using insert_before to append */
1022   _dbus_list_insert_before (&list1, NULL,
1023                             _DBUS_INT_TO_POINTER (-1));
1024   verify_list (&list1);
1025   _dbus_assert (is_descending_sequence (&list1));
1026
1027   _dbus_list_clear (&list1);
1028
1029   /* insert_after on empty list */
1030   _dbus_list_insert_after (&list1, NULL,
1031                            _DBUS_INT_TO_POINTER (0));
1032   verify_list (&list1);
1033
1034   /* inserting after first element */
1035   _dbus_list_insert_after (&list1, list1,
1036                            _DBUS_INT_TO_POINTER (1));
1037   verify_list (&list1);
1038   _dbus_assert (is_ascending_sequence (&list1));
1039
1040   /* inserting at the end */
1041   _dbus_list_insert_after (&list1, list1->next,
1042                            _DBUS_INT_TO_POINTER (2));
1043   verify_list (&list1);
1044   _dbus_assert (is_ascending_sequence (&list1));
1045
1046   /* using insert_after to prepend */
1047   _dbus_list_insert_after (&list1, NULL,
1048                            _DBUS_INT_TO_POINTER (-1));
1049   verify_list (&list1);
1050   _dbus_assert (is_ascending_sequence (&list1));
1051
1052   _dbus_list_clear (&list1);
1053
1054   return TRUE;
1055 }
1056
1057 #endif