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 (&link);
 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 (&link);
 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 value from the list. Only removes the
 305  * last value equal to the given data pointer,
 306  * even if multiple values exist which match.
 307  * This is a linear-time operation.
 308  *
 309  * @param list address of the list head.
 310  * @param data the value to remove.
 311  * @returns #TRUE if a value was found to remove.
 312  */
 313 dbus_bool_t
 314 _dbus_list_remove_last (DBusList **list,
 315                         void      *data)
 316 {
 317   DBusList *link;
 318
 319   link = _dbus_list_get_last_link (list);
 320   while (link != NULL)
 321     {
 322       if (link->data == data)
 323         {
 324           _dbus_list_remove_link (list, link);
 325           return TRUE;
 326         }
 327
 328       link = _dbus_list_get_prev_link (list, link);
 329     }
 330
 331   return FALSE;
 332 }
 333
 334 /**
 335  * Removes a link from the list. This is a constant-time operation.
 336  *
 337  * @param list address of the list head.
 338  * @param link the list link to remove.
 339  */
 340 void
 341 _dbus_list_remove_link (DBusList **list,
 342                         DBusList  *link)
 343 {
 344   if (link->next == link)
 345     {
 346       /* one-element list */
 347       *list = NULL;
 348       free_link (link);
 349     }
 350   else
 351     {
 352       link->prev->next = link->next;
 353       link->next->prev = link->prev;
 354
 355       if (*list == link)
 356         *list = link->next;
 357
 358       free_link (link);
 359     }
 360 }
 361
 362 /**
 363  * Frees all links in the list and sets the list head to #NULL. Does
 364  * not free the data in each link, for obvious reasons. This is a
 365  * linear-time operation.
 366  *
 367  * @param list address of the list head.
 368  */
 369 void
 370 _dbus_list_clear (DBusList **list)
 371 {
 372   DBusList *link;
 373
 374   link = *list;
 375   while (link != NULL)
 376     {
 377       DBusList *next = _dbus_list_get_next_link (list, link);
 378
 379       free_link (link);
 380
 381       link = next;
 382     }
 383
 384   *list = NULL;
 385 }
 386
 387 /**
 388  * Gets the first link in the list.
 389  * This is a constant-time operation.
 390  *
 391  * @param list address of the list head.
 392  * @returns the first link, or #NULL for an empty list.
 393  */
 394 DBusList*
 395 _dbus_list_get_first_link (DBusList **list)
 396 {
 397   return *list;
 398 }
 399
 400 /**
 401  * Gets the last link in the list.
 402  * This is a constant-time operation.
 403  *
 404  * @param list address of the list head.
 405  * @returns the last link, or #NULL for an empty list.
 406  */
 407 DBusList*
 408 _dbus_list_get_last_link (DBusList **list)
 409 {
 410   if (*list == NULL)
 411     return NULL;
 412   else
 413     return (*list)->prev;
 414 }
 415
 416 /**
 417  * Gets the last data in the list.
 418  * This is a constant-time operation.
 419  *
 420  * @param list address of the list head.
 421  * @returns the last data in the list, or #NULL for an empty list.
 422  */
 423 void*
 424 _dbus_list_get_last (DBusList **list)
 425 {
 426   if (*list == NULL)
 427     return NULL;
 428   else
 429     return (*list)->prev->data;
 430 }
 431
 432 /**
 433  * Gets the first data in the list.
 434  * This is a constant-time operation.
 435  *
 436  * @param list address of the list head.
 437  * @returns the first data in the list, or #NULL for an empty list.
 438  */
 439 void*
 440 _dbus_list_get_first (DBusList **list)
 441 {
 442   if (*list == NULL)
 443     return NULL;
 444   else
 445     return (*list)->data;
 446 }
 447
 448 /**
 449  * Removes the first value in the list and returns it.  This is a
 450  * constant-time operation.
 451  *
 452  * @param list address of the list head.
 453  * @returns the first data in the list, or #NULL for an empty list.
 454  */
 455 void*
 456 _dbus_list_pop_first (DBusList **list)
 457 {
 458   DBusList *link;
 459   void *data;
 460
 461   link = _dbus_list_get_first_link (list);
 462   if (link == NULL)
 463     return NULL;
 464
 465   data = link->data;
 466   _dbus_list_remove_link (list, link);
 467
 468   return data;
 469 }
 470
 471 /**
 472  * Removes the last value in the list and returns it.  This is a
 473  * constant-time operation.
 474  *
 475  * @param list address of the list head.
 476  * @returns the last data in the list, or #NULL for an empty list.
 477  */
 478 void*
 479 _dbus_list_pop_last (DBusList **list)
 480 {
 481   DBusList *link;
 482   void *data;
 483
 484   link = _dbus_list_get_last_link (list);
 485   if (link == NULL)
 486     return NULL;
 487
 488   data = link->data;
 489   _dbus_list_remove_link (list, link);
 490
 491   return data;
 492 }
 493
 494 /**
 495  * Copies a list. This is a linear-time operation.  If there isn't
 496  * enough memory to copy the entire list, the destination list will be
 497  * set to #NULL.
 498  *
 499  * @param list address of the head of the list to copy.
 500  * @param dest address where the copied list should be placed.
 501  * @returns #TRUE on success, #FALSE if not enough memory.
 502  */
 503 dbus_bool_t
 504 _dbus_list_copy (DBusList **list,
 505                  DBusList **dest)
 506 {
 507   DBusList *link;
 508
 509   _dbus_assert (list != dest);
 510
 511   *dest = NULL;
 512
 513   link = *list;
 514   while (link != NULL)
 515     {
 516       if (!_dbus_list_append (dest, link->data))
 517         {
 518           /* free what we have so far */
 519           _dbus_list_clear (dest);
 520           return FALSE;
 521         }
 522
 523       link = _dbus_list_get_next_link (list, link);
 524     }
 525
 526   return TRUE;
 527 }
 528
 529 /**
 530  * Gets the length of a list. This is a linear-time
 531  * operation.
 532  *
 533  * @param list address of the head of the list
 534  * @returns number of elements in the list.
 535  */
 536 int
 537 _dbus_list_get_length (DBusList **list)
 538 {
 539   DBusList *link;
 540   int length;
 541
 542   length = 0;
 543
 544   link = *list;
 545   while (link != NULL)
 546     {
 547       ++length;
 548
 549       link = _dbus_list_get_next_link (list, link);
 550     }
 551
 552   return length;
 553 }
 554
 555 /**
 556  * Calls the given function for each element in the list.  The
 557  * function is passed the list element as its first argument, and the
 558  * given data as its second argument.
 559  *
 560  * @param list address of the head of the list.
 561  * @param function function to call for each element.
 562  * @param data extra data for the function.
 563  *
 564  */
 565 void
 566 _dbus_list_foreach (DBusList          **list,
 567                     DBusForeachFunction function,
 568                     void               *data)
 569 {
 570   DBusList *link;
 571
 572   link = *list;
 573   while (link != NULL)
 574     {
 575       DBusList *next = _dbus_list_get_next_link (list, link);
 576
 577       (* function) (link->data, data);
 578
 579       link = next;
 580     }
 581 }
 582
 583 /** @} */
 584
 585 #ifdef DBUS_BUILD_TESTS
 586 #include "dbus-test.h"
 587 #include <stdio.h>
 588
 589 static void
 590 verify_list (DBusList **list)
 591 {
 592   DBusList *link;
 593   int length;
 594
 595   link = *list;
 596
 597   if (link == NULL)
 598     return;
 599
 600   if (link->next == link)
 601     {
 602       _dbus_assert (link->prev == link);
 603       _dbus_assert (*list == link);
 604       return;
 605     }
 606
 607   length = 0;
 608   do
 609     {
 610       length += 1;
 611       _dbus_assert (link->prev->next == link);
 612       _dbus_assert (link->next->prev == link);
 613       link = link->next;
 614     }
 615   while (link != *list);
 616
 617   _dbus_assert (length == _dbus_list_get_length (list));
 618 }
 619
 620 static dbus_bool_t
 621 is_ascending_sequence (DBusList **list)
 622 {
 623   DBusList *link;
 624   int prev;
 625
 626   prev = _DBUS_INT_MIN;
 627
 628   link = _dbus_list_get_first_link (list);
 629   while (link != NULL)
 630     {
 631       int v = _DBUS_POINTER_TO_INT (link->data);
 632
 633       if (v <= prev)
 634         return FALSE;
 635
 636       prev = v;
 637
 638       link = _dbus_list_get_next_link (list, link);
 639     }
 640
 641   return TRUE;
 642 }
 643
 644 static dbus_bool_t
 645 is_descending_sequence (DBusList **list)
 646 {
 647   DBusList *link;
 648   int prev;
 649
 650   prev = _DBUS_INT_MAX;
 651
 652   link = _dbus_list_get_first_link (list);
 653   while (link != NULL)
 654     {
 655       int v = _DBUS_POINTER_TO_INT (link->data);
 656
 657       if (v >= prev)
 658         return FALSE;
 659
 660       prev = v;
 661
 662       link = _dbus_list_get_next_link (list, link);
 663     }
 664
 665   return TRUE;
 666 }
 667
 668 static dbus_bool_t
 669 all_even_values (DBusList **list)
 670 {
 671   DBusList *link;
 672
 673   link = _dbus_list_get_first_link (list);
 674   while (link != NULL)
 675     {
 676       int v = _DBUS_POINTER_TO_INT (link->data);
 677
 678       if ((v % 2) != 0)
 679         return FALSE;
 680
 681       link = _dbus_list_get_next_link (list, link);
 682     }
 683
 684   return TRUE;
 685 }
 686
 687 static dbus_bool_t
 688 all_odd_values (DBusList **list)
 689 {
 690   DBusList *link;
 691
 692   link = _dbus_list_get_first_link (list);
 693   while (link != NULL)
 694     {
 695       int v = _DBUS_POINTER_TO_INT (link->data);
 696
 697       if ((v % 2) == 0)
 698         return FALSE;
 699
 700       link = _dbus_list_get_next_link (list, link);
 701     }
 702
 703   return TRUE;
 704 }
 705
 706 static dbus_bool_t
 707 lists_equal (DBusList **list1,
 708              DBusList **list2)
 709 {
 710   DBusList *link1;
 711   DBusList *link2;
 712
 713   link1 = _dbus_list_get_first_link (list1);
 714   link2 = _dbus_list_get_first_link (list2);
 715   while (link1 && link2)
 716     {
 717       if (link1->data != link2->data)
 718         return FALSE;
 719
 720       link1 = _dbus_list_get_next_link (list1, link1);
 721       link2 = _dbus_list_get_next_link (list2, link2);
 722     }
 723
 724   if (link1 || link2)
 725     return FALSE;
 726
 727   return TRUE;
 728 }
 729
 730 /**
 731  * @ingroup DBusListInternals
 732  * Unit test for DBusList
 733  * @returns #TRUE on success.
 734  */
 735 dbus_bool_t
 736 _dbus_list_test (void)
 737 {
 738   DBusList *list1;
 739   DBusList *list2;
 740   DBusList *link1;
 741   DBusList *link2;
 742   DBusList *copy1;
 743   DBusList *copy2;
 744   int i;
 745
 746   list1 = NULL;
 747   list2 = NULL;
 748
 749   /* Test append and prepend */
 750
 751   i = 0;
 752   while (i < 10)
 753     {
 754       if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
 755         _dbus_assert_not_reached ("could not allocate for append");
 756
 757       if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
 758         _dbus_assert_not_reached ("count not allocate for prepend");
 759       ++i;
 760
 761       verify_list (&list1);
 762       verify_list (&list2);
 763
 764       _dbus_assert (_dbus_list_get_length (&list1) == i);
 765       _dbus_assert (_dbus_list_get_length (&list2) == i);
 766     }
 767
 768   _dbus_assert (is_ascending_sequence (&list1));
 769   _dbus_assert (is_descending_sequence (&list2));
 770
 771   /* Test list clear */
 772   _dbus_list_clear (&list1);
 773   _dbus_list_clear (&list2);
 774
 775   verify_list (&list1);
 776   verify_list (&list2);
 777
 778   /* Test get_first, get_last, pop_first, pop_last */
 779
 780   i = 0;
 781   while (i < 10)
 782     {
 783       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 784       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 785       ++i;
 786     }
 787
 788   --i;
 789   while (i >= 0)
 790     {
 791       void *got_data1;
 792       void *got_data2;
 793
 794       void *data1;
 795       void *data2;
 796
 797       got_data1 = _dbus_list_get_last (&list1);
 798       got_data2 = _dbus_list_get_first (&list2);
 799
 800       data1 = _dbus_list_pop_last (&list1);
 801       data2 = _dbus_list_pop_first (&list2);
 802
 803       _dbus_assert (got_data1 == data1);
 804       _dbus_assert (got_data2 == data2);
 805
 806       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
 807       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
 808
 809       verify_list (&list1);
 810       verify_list (&list2);
 811
 812       _dbus_assert (is_ascending_sequence (&list1));
 813       _dbus_assert (is_descending_sequence (&list2));
 814
 815       --i;
 816     }
 817
 818   _dbus_assert (list1 == NULL);
 819   _dbus_assert (list2 == NULL);
 820
 821   /* Test iteration */
 822
 823   i = 0;
 824   while (i < 10)
 825     {
 826       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 827       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 828       ++i;
 829
 830       verify_list (&list1);
 831       verify_list (&list2);
 832
 833       _dbus_assert (_dbus_list_get_length (&list1) == i);
 834       _dbus_assert (_dbus_list_get_length (&list2) == i);
 835     }
 836
 837   _dbus_assert (is_ascending_sequence (&list1));
 838   _dbus_assert (is_descending_sequence (&list2));
 839
 840   --i;
 841   link2 = _dbus_list_get_first_link (&list2);
 842   while (link2 != NULL)
 843     {
 844       verify_list (&link2); /* pretend this link is the head */
 845
 846       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
 847
 848       link2 = _dbus_list_get_next_link (&list2, link2);
 849       --i;
 850     }
 851
 852   i = 0;
 853   link1 = _dbus_list_get_first_link (&list1);
 854   while (link1 != NULL)
 855     {
 856       verify_list (&link1); /* pretend this link is the head */
 857
 858       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
 859
 860       link1 = _dbus_list_get_next_link (&list1, link1);
 861       ++i;
 862     }
 863
 864   _dbus_list_clear (&list1);
 865   _dbus_list_clear (&list2);
 866
 867   /* Test remove */
 868
 869   i = 0;
 870   while (i < 10)
 871     {
 872       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 873       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 874       ++i;
 875     }
 876
 877   --i;
 878   while (i >= 0)
 879     {
 880       if ((i % 2) == 0)
 881         {
 882           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
 883             _dbus_assert_not_reached ("element should have been in list");
 884           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
 885             _dbus_assert_not_reached ("element should have been in list");
 886
 887           verify_list (&list1);
 888           verify_list (&list2);
 889         }
 890       --i;
 891     }
 892
 893   _dbus_assert (all_odd_values (&list1));
 894   _dbus_assert (all_odd_values (&list2));
 895
 896   _dbus_list_clear (&list1);
 897   _dbus_list_clear (&list2);
 898
 899   /* test removing the other half of the elements */
 900
 901   i = 0;
 902   while (i < 10)
 903     {
 904       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 905       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 906       ++i;
 907     }
 908
 909   --i;
 910   while (i >= 0)
 911     {
 912       if ((i % 2) != 0)
 913         {
 914           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
 915             _dbus_assert_not_reached ("element should have been in list");
 916           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
 917             _dbus_assert_not_reached ("element should have been in list");
 918
 919           verify_list (&list1);
 920           verify_list (&list2);
 921         }
 922       --i;
 923     }
 924
 925   _dbus_assert (all_even_values (&list1));
 926   _dbus_assert (all_even_values (&list2));
 927
 928   /* clear list using remove_link */
 929   while (list1 != NULL)
 930     {
 931       _dbus_list_remove_link (&list1, list1);
 932       verify_list (&list1);
 933     }
 934   while (list2 != NULL)
 935     {
 936       _dbus_list_remove_link (&list2, list2);
 937       verify_list (&list2);
 938     }
 939
 940   /* Test remove link more generally */
 941   i = 0;
 942   while (i < 10)
 943     {
 944       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 945       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 946       ++i;
 947     }
 948
 949   --i;
 950   link2 = _dbus_list_get_first_link (&list2);
 951   while (link2 != NULL)
 952     {
 953       DBusList *next = _dbus_list_get_next_link (&list2, link2);
 954
 955       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
 956
 957       if ((i % 2) == 0)
 958         _dbus_list_remove_link (&list2, link2);
 959
 960       verify_list (&list2);
 961
 962       link2 = next;
 963       --i;
 964     }
 965
 966   _dbus_assert (all_odd_values (&list2));
 967   _dbus_list_clear (&list2);
 968
 969   i = 0;
 970   link1 = _dbus_list_get_first_link (&list1);
 971   while (link1 != NULL)
 972     {
 973       DBusList *next = _dbus_list_get_next_link (&list1, link1);
 974
 975       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
 976
 977       if ((i % 2) != 0)
 978         _dbus_list_remove_link (&list1, link1);
 979
 980       verify_list (&list1);
 981
 982       link1 = next;
 983       ++i;
 984     }
 985
 986   _dbus_assert (all_even_values (&list1));
 987   _dbus_list_clear (&list1);
 988
 989   /* Test copying a list */
 990   i = 0;
 991   while (i < 10)
 992     {
 993       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 994       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 995       ++i;
 996     }
 997
 998   /* bad pointers, because they are allowed in the copy dest */
 999   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1000   copy2 = _DBUS_INT_TO_POINTER (23);
1001
1002   _dbus_list_copy (&list1, &copy1);
1003   verify_list (&list1);
1004   verify_list (&copy1);
1005   _dbus_assert (lists_equal (&list1, &copy1));
1006
1007   _dbus_list_copy (&list2, &copy2);
1008   verify_list (&list2);
1009   verify_list (&copy2);
1010   _dbus_assert (lists_equal (&list2, &copy2));
1011
1012   /* Now test copying empty lists */
1013   _dbus_list_clear (&list1);
1014   _dbus_list_clear (&list2);
1015   _dbus_list_clear (&copy1);
1016   _dbus_list_clear (&copy2);
1017
1018   /* bad pointers, because they are allowed in the copy dest */
1019   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1020   copy2 = _DBUS_INT_TO_POINTER (23);
1021
1022   _dbus_list_copy (&list1, &copy1);
1023   verify_list (&list1);
1024   verify_list (&copy1);
1025   _dbus_assert (lists_equal (&list1, &copy1));
1026
1027   _dbus_list_copy (&list2, &copy2);
1028   verify_list (&list2);
1029   verify_list (&copy2);
1030   _dbus_assert (lists_equal (&list2, &copy2));
1031
1032   _dbus_list_clear (&list1);
1033   _dbus_list_clear (&list2);
1034
1035   /* insert_before on empty list */
1036   _dbus_list_insert_before (&list1, NULL,
1037                             _DBUS_INT_TO_POINTER (0));
1038   verify_list (&list1);
1039
1040   /* inserting before first element */
1041   _dbus_list_insert_before (&list1, list1,
1042                             _DBUS_INT_TO_POINTER (2));
1043   verify_list (&list1);
1044   _dbus_assert (is_descending_sequence (&list1));
1045
1046   /* inserting in the middle */
1047   _dbus_list_insert_before (&list1, list1->next,
1048                             _DBUS_INT_TO_POINTER (1));
1049   verify_list (&list1);
1050   _dbus_assert (is_descending_sequence (&list1));
1051
1052   /* using insert_before to append */
1053   _dbus_list_insert_before (&list1, NULL,
1054                             _DBUS_INT_TO_POINTER (-1));
1055   verify_list (&list1);
1056   _dbus_assert (is_descending_sequence (&list1));
1057
1058   _dbus_list_clear (&list1);
1059
1060   /* insert_after on empty list */
1061   _dbus_list_insert_after (&list1, NULL,
1062                            _DBUS_INT_TO_POINTER (0));
1063   verify_list (&list1);
1064
1065   /* inserting after first element */
1066   _dbus_list_insert_after (&list1, list1,
1067                            _DBUS_INT_TO_POINTER (1));
1068   verify_list (&list1);
1069   _dbus_assert (is_ascending_sequence (&list1));
1070
1071   /* inserting at the end */
1072   _dbus_list_insert_after (&list1, list1->next,
1073                            _DBUS_INT_TO_POINTER (2));
1074   verify_list (&list1);
1075   _dbus_assert (is_ascending_sequence (&list1));
1076
1077   /* using insert_after to prepend */
1078   _dbus_list_insert_after (&list1, NULL,
1079                            _DBUS_INT_TO_POINTER (-1));
1080   verify_list (&list1);
1081   _dbus_assert (is_ascending_sequence (&list1));
1082
1083   _dbus_list_clear (&list1);
1084
1085   return TRUE;
1086 }
1087
1088 #endif