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