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