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