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