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