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  * Inserts a link into the list before the given existing link.
 376  *
 377  * @param list the list to modify
 378  * @param before_this_link existing link to insert before, or #NULL to append
 379  * @param link the link to insert
 380  */
 381 void
 382 _dbus_list_insert_before_link (DBusList **list,
 383                                DBusList  *before_this_link,
 384                                DBusList  *link)
 385 {
 386   if (before_this_link == NULL)
 387     _dbus_list_append_link (list, link);
 388   else
 389     link_before (list, before_this_link, link);
 390 }
 391
 392 /**
 393  * Inserts a link into the list after the given existing link.
 394  *
 395  * @param list the list to modify
 396  * @param after_this_link existing link to insert after, or #NULL to prepend
 397  * @param link the link to insert
 398  */
 399 void
 400 _dbus_list_insert_after_link (DBusList **list,
 401                               DBusList  *after_this_link,
 402                               DBusList  *link)
 403 {
 404   if (after_this_link == NULL)
 405     _dbus_list_prepend_link (list, link);
 406   else
 407     link_after (list, after_this_link, link);
 408 }
 409
 410 /**
 411  * Removes a value from the list. Only removes the
 412  * first value equal to the given data pointer,
 413  * even if multiple values exist which match.
 414  * This is a linear-time operation.
 415  *
 416  * @param list address of the list head.
 417  * @param data the value to remove.
 418  * @returns #TRUE if a value was found to remove.
 419  */
 420 dbus_bool_t
 421 _dbus_list_remove (DBusList **list,
 422                    void      *data)
 423 {
 424   DBusList *link;
 425
 426   link = *list;
 427   while (link != NULL)
 428     {
 429       if (link->data == data)
 430         {
 431           _dbus_list_remove_link (list, link);
 432           return TRUE;
 433         }
 434
 435       link = _dbus_list_get_next_link (list, link);
 436     }
 437
 438   return FALSE;
 439 }
 440
 441 /**
 442  * Removes a value from the list. Only removes the
 443  * last value equal to the given data pointer,
 444  * even if multiple values exist which match.
 445  * This is a linear-time operation.
 446  *
 447  * @param list address of the list head.
 448  * @param data the value to remove.
 449  * @returns #TRUE if a value was found to remove.
 450  */
 451 dbus_bool_t
 452 _dbus_list_remove_last (DBusList **list,
 453                         void      *data)
 454 {
 455   DBusList *link;
 456
 457   link = _dbus_list_get_last_link (list);
 458
 459   while (link != NULL)
 460     {
 461       if (link->data == data)
 462         {
 463           _dbus_list_remove_link (list, link);
 464           return TRUE;
 465         }
 466
 467       link = _dbus_list_get_prev_link (list, link);
 468     }
 469
 470   return FALSE;
 471 }
 472
 473 static void
 474 _dbus_list_unlink (DBusList **list,
 475                    DBusList  *link)
 476 {
 477   if (link->next == link)
 478     {
 479       /* one-element list */
 480       *list = NULL;
 481     }
 482   else
 483     {
 484       link->prev->next = link->next;
 485       link->next->prev = link->prev;
 486
 487       if (*list == link)
 488         *list = link->next;
 489     }
 490 }
 491
 492 /**
 493  * Removes a link from the list. This is a constant-time operation.
 494  *
 495  * @param list address of the list head.
 496  * @param link the list link to remove.
 497  */
 498 void
 499 _dbus_list_remove_link (DBusList **list,
 500                         DBusList  *link)
 501 {
 502   _dbus_list_unlink (list, link);
 503   free_link (link);
 504 }
 505
 506 /**
 507  * Frees all links in the list and sets the list head to #NULL. Does
 508  * not free the data in each link, for obvious reasons. This is a
 509  * linear-time operation.
 510  *
 511  * @param list address of the list head.
 512  */
 513 void
 514 _dbus_list_clear (DBusList **list)
 515 {
 516   DBusList *link;
 517
 518   link = *list;
 519   while (link != NULL)
 520     {
 521       DBusList *next = _dbus_list_get_next_link (list, link);
 522
 523       free_link (link);
 524
 525       link = next;
 526     }
 527
 528   *list = NULL;
 529 }
 530
 531 /**
 532  * Gets the first link in the list.
 533  * This is a constant-time operation.
 534  *
 535  * @param list address of the list head.
 536  * @returns the first link, or #NULL for an empty list.
 537  */
 538 DBusList*
 539 _dbus_list_get_first_link (DBusList **list)
 540 {
 541   return *list;
 542 }
 543
 544 /**
 545  * Gets the last link in the list.
 546  * This is a constant-time operation.
 547  *
 548  * @param list address of the list head.
 549  * @returns the last link, or #NULL for an empty list.
 550  */
 551 DBusList*
 552 _dbus_list_get_last_link (DBusList **list)
 553 {
 554   if (*list == NULL)
 555     return NULL;
 556   else
 557     return (*list)->prev;
 558 }
 559
 560 /**
 561  * Gets the last data in the list.
 562  * This is a constant-time operation.
 563  *
 564  * @param list address of the list head.
 565  * @returns the last data in the list, or #NULL for an empty list.
 566  */
 567 void*
 568 _dbus_list_get_last (DBusList **list)
 569 {
 570   if (*list == NULL)
 571     return NULL;
 572   else
 573     return (*list)->prev->data;
 574 }
 575
 576 /**
 577  * Gets the first data in the list.
 578  * This is a constant-time operation.
 579  *
 580  * @param list address of the list head.
 581  * @returns the first data in the list, or #NULL for an empty list.
 582  */
 583 void*
 584 _dbus_list_get_first (DBusList **list)
 585 {
 586   if (*list == NULL)
 587     return NULL;
 588   else
 589     return (*list)->data;
 590 }
 591
 592 /**
 593  * Removes the first link in the list and returns it.  This is a
 594  * constant-time operation.
 595  *
 596  * @param list address of the list head.
 597  * @returns the first link in the list, or #NULL for an empty list.
 598  */
 599 DBusList*
 600 _dbus_list_pop_first_link (DBusList **list)
 601 {
 602   DBusList *link;
 603
 604   link = _dbus_list_get_first_link (list);
 605   if (link == NULL)
 606     return NULL;
 607
 608   _dbus_list_unlink (list, link);
 609
 610   return link;
 611 }
 612
 613 /**
 614  * Removes the first value in the list and returns it.  This is a
 615  * constant-time operation.
 616  *
 617  * @param list address of the list head.
 618  * @returns the first data in the list, or #NULL for an empty list.
 619  */
 620 void*
 621 _dbus_list_pop_first (DBusList **list)
 622 {
 623   DBusList *link;
 624   void *data;
 625
 626   link = _dbus_list_get_first_link (list);
 627   if (link == NULL)
 628     return NULL;
 629
 630   data = link->data;
 631   _dbus_list_remove_link (list, link);
 632
 633   return data;
 634 }
 635
 636 /**
 637  * Removes the last value in the list and returns it.  This is a
 638  * constant-time operation.
 639  *
 640  * @param list address of the list head.
 641  * @returns the last data in the list, or #NULL for an empty list.
 642  */
 643 void*
 644 _dbus_list_pop_last (DBusList **list)
 645 {
 646   DBusList *link;
 647   void *data;
 648
 649   link = _dbus_list_get_last_link (list);
 650   if (link == NULL)
 651     return NULL;
 652
 653   data = link->data;
 654   _dbus_list_remove_link (list, link);
 655
 656   return data;
 657 }
 658
 659 /**
 660  * Removes the last link in the list and returns it.  This is a
 661  * constant-time operation.
 662  *
 663  * @param list address of the list head.
 664  * @returns the last link in the list, or #NULL for an empty list.
 665  */
 666 DBusList*
 667 _dbus_list_pop_last_link (DBusList **list)
 668 {
 669   DBusList *link;
 670
 671   link = _dbus_list_get_last_link (list);
 672   if (link == NULL)
 673     return NULL;
 674
 675   _dbus_list_unlink (list, link);
 676
 677   return link;
 678 }
 679
 680 /**
 681  * Copies a list. This is a linear-time operation.  If there isn't
 682  * enough memory to copy the entire list, the destination list will be
 683  * set to #NULL.
 684  *
 685  * @param list address of the head of the list to copy.
 686  * @param dest address where the copied list should be placed.
 687  * @returns #TRUE on success, #FALSE if not enough memory.
 688  */
 689 dbus_bool_t
 690 _dbus_list_copy (DBusList **list,
 691                  DBusList **dest)
 692 {
 693   DBusList *link;
 694
 695   _dbus_assert (list != dest);
 696
 697   *dest = NULL;
 698
 699   link = *list;
 700   while (link != NULL)
 701     {
 702       if (!_dbus_list_append (dest, link->data))
 703         {
 704           /* free what we have so far */
 705           _dbus_list_clear (dest);
 706           return FALSE;
 707         }
 708
 709       link = _dbus_list_get_next_link (list, link);
 710     }
 711
 712   return TRUE;
 713 }
 714
 715 /**
 716  * Gets the length of a list. This is a linear-time
 717  * operation.
 718  *
 719  * @param list address of the head of the list
 720  * @returns number of elements in the list.
 721  */
 722 int
 723 _dbus_list_get_length (DBusList **list)
 724 {
 725   DBusList *link;
 726   int length;
 727
 728   length = 0;
 729
 730   link = *list;
 731   while (link != NULL)
 732     {
 733       ++length;
 734
 735       link = _dbus_list_get_next_link (list, link);
 736     }
 737
 738   return length;
 739 }
 740
 741 /**
 742  * Calls the given function for each element in the list.  The
 743  * function is passed the list element as its first argument, and the
 744  * given data as its second argument.
 745  *
 746  * @param list address of the head of the list.
 747  * @param function function to call for each element.
 748  * @param data extra data for the function.
 749  *
 750  */
 751 void
 752 _dbus_list_foreach (DBusList          **list,
 753                     DBusForeachFunction function,
 754                     void               *data)
 755 {
 756   DBusList *link;
 757
 758   link = *list;
 759   while (link != NULL)
 760     {
 761       DBusList *next = _dbus_list_get_next_link (list, link);
 762
 763       (* function) (link->data, data);
 764
 765       link = next;
 766     }
 767 }
 768
 769 /**
 770  * Check whether length is exactly one.
 771  *
 772  * @param list the list
 773  * @returns #TRUE if length is exactly one
 774  */
 775 dbus_bool_t
 776 _dbus_list_length_is_one (DBusList **list)
 777 {
 778   return (*list != NULL &&
 779           (*list)->next == *list);
 780 }
 781
 782 /** @} */
 783
 784 #ifdef DBUS_BUILD_TESTS
 785 #include "dbus-test.h"
 786 #include <stdio.h>
 787
 788 static void
 789 verify_list (DBusList **list)
 790 {
 791   DBusList *link;
 792   int length;
 793
 794   link = *list;
 795
 796   if (link == NULL)
 797     return;
 798
 799   if (link->next == link)
 800     {
 801       _dbus_assert (link->prev == link);
 802       _dbus_assert (*list == link);
 803       return;
 804     }
 805
 806   length = 0;
 807   do
 808     {
 809       length += 1;
 810       _dbus_assert (link->prev->next == link);
 811       _dbus_assert (link->next->prev == link);
 812       link = link->next;
 813     }
 814   while (link != *list);
 815
 816   _dbus_assert (length == _dbus_list_get_length (list));
 817
 818   if (length == 1)
 819     _dbus_assert (_dbus_list_length_is_one (list));
 820   else
 821     _dbus_assert (!_dbus_list_length_is_one (list));
 822 }
 823
 824 static dbus_bool_t
 825 is_ascending_sequence (DBusList **list)
 826 {
 827   DBusList *link;
 828   int prev;
 829
 830   prev = _DBUS_INT_MIN;
 831
 832   link = _dbus_list_get_first_link (list);
 833   while (link != NULL)
 834     {
 835       int v = _DBUS_POINTER_TO_INT (link->data);
 836
 837       if (v <= prev)
 838         return FALSE;
 839
 840       prev = v;
 841
 842       link = _dbus_list_get_next_link (list, link);
 843     }
 844
 845   return TRUE;
 846 }
 847
 848 static dbus_bool_t
 849 is_descending_sequence (DBusList **list)
 850 {
 851   DBusList *link;
 852   int prev;
 853
 854   prev = _DBUS_INT_MAX;
 855
 856   link = _dbus_list_get_first_link (list);
 857   while (link != NULL)
 858     {
 859       int v = _DBUS_POINTER_TO_INT (link->data);
 860
 861       if (v >= prev)
 862         return FALSE;
 863
 864       prev = v;
 865
 866       link = _dbus_list_get_next_link (list, link);
 867     }
 868
 869   return TRUE;
 870 }
 871
 872 static dbus_bool_t
 873 all_even_values (DBusList **list)
 874 {
 875   DBusList *link;
 876
 877   link = _dbus_list_get_first_link (list);
 878   while (link != NULL)
 879     {
 880       int v = _DBUS_POINTER_TO_INT (link->data);
 881
 882       if ((v % 2) != 0)
 883         return FALSE;
 884
 885       link = _dbus_list_get_next_link (list, link);
 886     }
 887
 888   return TRUE;
 889 }
 890
 891 static dbus_bool_t
 892 all_odd_values (DBusList **list)
 893 {
 894   DBusList *link;
 895
 896   link = _dbus_list_get_first_link (list);
 897   while (link != NULL)
 898     {
 899       int v = _DBUS_POINTER_TO_INT (link->data);
 900
 901       if ((v % 2) == 0)
 902         return FALSE;
 903
 904       link = _dbus_list_get_next_link (list, link);
 905     }
 906
 907   return TRUE;
 908 }
 909
 910 static dbus_bool_t
 911 lists_equal (DBusList **list1,
 912              DBusList **list2)
 913 {
 914   DBusList *link1;
 915   DBusList *link2;
 916
 917   link1 = _dbus_list_get_first_link (list1);
 918   link2 = _dbus_list_get_first_link (list2);
 919   while (link1 && link2)
 920     {
 921       if (link1->data != link2->data)
 922         return FALSE;
 923
 924       link1 = _dbus_list_get_next_link (list1, link1);
 925       link2 = _dbus_list_get_next_link (list2, link2);
 926     }
 927
 928   if (link1 || link2)
 929     return FALSE;
 930
 931   return TRUE;
 932 }
 933
 934 /**
 935  * @ingroup DBusListInternals
 936  * Unit test for DBusList
 937  * @returns #TRUE on success.
 938  */
 939 dbus_bool_t
 940 _dbus_list_test (void)
 941 {
 942   DBusList *list1;
 943   DBusList *list2;
 944   DBusList *link1;
 945   DBusList *link2;
 946   DBusList *copy1;
 947   DBusList *copy2;
 948   int i;
 949
 950   list1 = NULL;
 951   list2 = NULL;
 952
 953   /* Test append and prepend */
 954
 955   i = 0;
 956   while (i < 10)
 957     {
 958       if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
 959         _dbus_assert_not_reached ("could not allocate for append");
 960
 961       if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
 962         _dbus_assert_not_reached ("count not allocate for prepend");
 963       ++i;
 964
 965       verify_list (&list1);
 966       verify_list (&list2);
 967
 968       _dbus_assert (_dbus_list_get_length (&list1) == i);
 969       _dbus_assert (_dbus_list_get_length (&list2) == i);
 970     }
 971
 972   _dbus_assert (is_ascending_sequence (&list1));
 973   _dbus_assert (is_descending_sequence (&list2));
 974
 975   /* Test list clear */
 976   _dbus_list_clear (&list1);
 977   _dbus_list_clear (&list2);
 978
 979   verify_list (&list1);
 980   verify_list (&list2);
 981
 982   /* Test get_first, get_last, pop_first, pop_last */
 983
 984   i = 0;
 985   while (i < 10)
 986     {
 987       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
 988       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
 989       ++i;
 990     }
 991
 992   --i;
 993   while (i >= 0)
 994     {
 995       void *got_data1;
 996       void *got_data2;
 997
 998       void *data1;
 999       void *data2;
1000
1001       got_data1 = _dbus_list_get_last (&list1);
1002       got_data2 = _dbus_list_get_first (&list2);
1003
1004       data1 = _dbus_list_pop_last (&list1);
1005       data2 = _dbus_list_pop_first (&list2);
1006
1007       _dbus_assert (got_data1 == data1);
1008       _dbus_assert (got_data2 == data2);
1009
1010       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1011       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1012
1013       verify_list (&list1);
1014       verify_list (&list2);
1015
1016       _dbus_assert (is_ascending_sequence (&list1));
1017       _dbus_assert (is_descending_sequence (&list2));
1018
1019       --i;
1020     }
1021
1022   _dbus_assert (list1 == NULL);
1023   _dbus_assert (list2 == NULL);
1024
1025   /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1026
1027   i = 0;
1028   while (i < 10)
1029     {
1030       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1031       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1032       ++i;
1033     }
1034
1035   --i;
1036   while (i >= 0)
1037     {
1038       DBusList *got_link1;
1039       DBusList *got_link2;
1040
1041       DBusList *link1;
1042       DBusList *link2;
1043
1044       void *data1;
1045       void *data2;
1046
1047       got_link1 = _dbus_list_get_last_link (&list1);
1048       got_link2 = _dbus_list_get_first_link (&list2);
1049
1050       link1 = _dbus_list_pop_last_link (&list1);
1051       link2 = _dbus_list_pop_first_link (&list2);
1052
1053       _dbus_assert (got_link1 == link1);
1054       _dbus_assert (got_link2 == link2);
1055
1056       data1 = link1->data;
1057       data2 = link2->data;
1058
1059       _dbus_list_free_link (link1);
1060       _dbus_list_free_link (link2);
1061
1062       _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1063       _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1064
1065       verify_list (&list1);
1066       verify_list (&list2);
1067
1068       _dbus_assert (is_ascending_sequence (&list1));
1069       _dbus_assert (is_descending_sequence (&list2));
1070
1071       --i;
1072     }
1073
1074   _dbus_assert (list1 == NULL);
1075   _dbus_assert (list2 == NULL);
1076
1077   /* Test iteration */
1078
1079   i = 0;
1080   while (i < 10)
1081     {
1082       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1083       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1084       ++i;
1085
1086       verify_list (&list1);
1087       verify_list (&list2);
1088
1089       _dbus_assert (_dbus_list_get_length (&list1) == i);
1090       _dbus_assert (_dbus_list_get_length (&list2) == i);
1091     }
1092
1093   _dbus_assert (is_ascending_sequence (&list1));
1094   _dbus_assert (is_descending_sequence (&list2));
1095
1096   --i;
1097   link2 = _dbus_list_get_first_link (&list2);
1098   while (link2 != NULL)
1099     {
1100       verify_list (&link2); /* pretend this link is the head */
1101
1102       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1103
1104       link2 = _dbus_list_get_next_link (&list2, link2);
1105       --i;
1106     }
1107
1108   i = 0;
1109   link1 = _dbus_list_get_first_link (&list1);
1110   while (link1 != NULL)
1111     {
1112       verify_list (&link1); /* pretend this link is the head */
1113
1114       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1115
1116       link1 = _dbus_list_get_next_link (&list1, link1);
1117       ++i;
1118     }
1119
1120   --i;
1121   link1 = _dbus_list_get_last_link (&list1);
1122   while (link1 != NULL)
1123     {
1124       verify_list (&link1); /* pretend this link is the head */
1125
1126       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1127
1128       link1 = _dbus_list_get_prev_link (&list1, link1);
1129       --i;
1130     }
1131
1132   _dbus_list_clear (&list1);
1133   _dbus_list_clear (&list2);
1134
1135   /* Test remove */
1136
1137   i = 0;
1138   while (i < 10)
1139     {
1140       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1141       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1142       ++i;
1143     }
1144
1145   --i;
1146   while (i >= 0)
1147     {
1148       if ((i % 2) == 0)
1149         {
1150           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1151             _dbus_assert_not_reached ("element should have been in list");
1152           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1153             _dbus_assert_not_reached ("element should have been in list");
1154
1155           verify_list (&list1);
1156           verify_list (&list2);
1157         }
1158       --i;
1159     }
1160
1161   _dbus_assert (all_odd_values (&list1));
1162   _dbus_assert (all_odd_values (&list2));
1163
1164   _dbus_list_clear (&list1);
1165   _dbus_list_clear (&list2);
1166
1167   /* test removing the other half of the elements */
1168
1169   i = 0;
1170   while (i < 10)
1171     {
1172       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1173       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1174       ++i;
1175     }
1176
1177   --i;
1178   while (i >= 0)
1179     {
1180       if ((i % 2) != 0)
1181         {
1182           if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1183             _dbus_assert_not_reached ("element should have been in list");
1184           if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1185             _dbus_assert_not_reached ("element should have been in list");
1186
1187           verify_list (&list1);
1188           verify_list (&list2);
1189         }
1190       --i;
1191     }
1192
1193   _dbus_assert (all_even_values (&list1));
1194   _dbus_assert (all_even_values (&list2));
1195
1196   /* clear list using remove_link */
1197   while (list1 != NULL)
1198     {
1199       _dbus_list_remove_link (&list1, list1);
1200       verify_list (&list1);
1201     }
1202   while (list2 != NULL)
1203     {
1204       _dbus_list_remove_link (&list2, list2);
1205       verify_list (&list2);
1206     }
1207
1208   /* Test remove link more generally */
1209   i = 0;
1210   while (i < 10)
1211     {
1212       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1213       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1214       ++i;
1215     }
1216
1217   --i;
1218   link2 = _dbus_list_get_first_link (&list2);
1219   while (link2 != NULL)
1220     {
1221       DBusList *next = _dbus_list_get_next_link (&list2, link2);
1222
1223       _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1224
1225       if ((i % 2) == 0)
1226         _dbus_list_remove_link (&list2, link2);
1227
1228       verify_list (&list2);
1229
1230       link2 = next;
1231       --i;
1232     }
1233
1234   _dbus_assert (all_odd_values (&list2));
1235   _dbus_list_clear (&list2);
1236
1237   i = 0;
1238   link1 = _dbus_list_get_first_link (&list1);
1239   while (link1 != NULL)
1240     {
1241       DBusList *next = _dbus_list_get_next_link (&list1, link1);
1242
1243       _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1244
1245       if ((i % 2) != 0)
1246         _dbus_list_remove_link (&list1, link1);
1247
1248       verify_list (&list1);
1249
1250       link1 = next;
1251       ++i;
1252     }
1253
1254   _dbus_assert (all_even_values (&list1));
1255   _dbus_list_clear (&list1);
1256
1257   /* Test copying a list */
1258   i = 0;
1259   while (i < 10)
1260     {
1261       _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1262       _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1263       ++i;
1264     }
1265
1266   /* bad pointers, because they are allowed in the copy dest */
1267   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1268   copy2 = _DBUS_INT_TO_POINTER (23);
1269
1270   _dbus_list_copy (&list1, &copy1);
1271   verify_list (&list1);
1272   verify_list (&copy1);
1273   _dbus_assert (lists_equal (&list1, &copy1));
1274
1275   _dbus_list_copy (&list2, &copy2);
1276   verify_list (&list2);
1277   verify_list (&copy2);
1278   _dbus_assert (lists_equal (&list2, &copy2));
1279
1280   /* Now test copying empty lists */
1281   _dbus_list_clear (&list1);
1282   _dbus_list_clear (&list2);
1283   _dbus_list_clear (&copy1);
1284   _dbus_list_clear (&copy2);
1285
1286   /* bad pointers, because they are allowed in the copy dest */
1287   copy1 = _DBUS_INT_TO_POINTER (0x342234);
1288   copy2 = _DBUS_INT_TO_POINTER (23);
1289
1290   _dbus_list_copy (&list1, &copy1);
1291   verify_list (&list1);
1292   verify_list (&copy1);
1293   _dbus_assert (lists_equal (&list1, &copy1));
1294
1295   _dbus_list_copy (&list2, &copy2);
1296   verify_list (&list2);
1297   verify_list (&copy2);
1298   _dbus_assert (lists_equal (&list2, &copy2));
1299
1300   _dbus_list_clear (&list1);
1301   _dbus_list_clear (&list2);
1302
1303   /* insert_before on empty list */
1304   _dbus_list_insert_before (&list1, NULL,
1305                             _DBUS_INT_TO_POINTER (0));
1306   verify_list (&list1);
1307
1308   /* inserting before first element */
1309   _dbus_list_insert_before (&list1, list1,
1310                             _DBUS_INT_TO_POINTER (2));
1311   verify_list (&list1);
1312   _dbus_assert (is_descending_sequence (&list1));
1313
1314   /* inserting in the middle */
1315   _dbus_list_insert_before (&list1, list1->next,
1316                             _DBUS_INT_TO_POINTER (1));
1317   verify_list (&list1);
1318   _dbus_assert (is_descending_sequence (&list1));
1319
1320   /* using insert_before to append */
1321   _dbus_list_insert_before (&list1, NULL,
1322                             _DBUS_INT_TO_POINTER (-1));
1323   verify_list (&list1);
1324   _dbus_assert (is_descending_sequence (&list1));
1325
1326   _dbus_list_clear (&list1);
1327
1328   /* insert_after on empty list */
1329   _dbus_list_insert_after (&list1, NULL,
1330                            _DBUS_INT_TO_POINTER (0));
1331   verify_list (&list1);
1332
1333   /* inserting after first element */
1334   _dbus_list_insert_after (&list1, list1,
1335                            _DBUS_INT_TO_POINTER (1));
1336   verify_list (&list1);
1337   _dbus_assert (is_ascending_sequence (&list1));
1338
1339   /* inserting at the end */
1340   _dbus_list_insert_after (&list1, list1->next,
1341                            _DBUS_INT_TO_POINTER (2));
1342   verify_list (&list1);
1343   _dbus_assert (is_ascending_sequence (&list1));
1344
1345   /* using insert_after to prepend */
1346   _dbus_list_insert_after (&list1, NULL,
1347                            _DBUS_INT_TO_POINTER (-1));
1348   verify_list (&list1);
1349   _dbus_assert (is_ascending_sequence (&list1));
1350
1351   _dbus_list_clear (&list1);
1352
1353   /* using remove_last */
1354   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1355   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1356   _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1357
1358   _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1359
1360   verify_list (&list1);
1361   _dbus_assert (is_ascending_sequence (&list1));
1362
1363   _dbus_list_clear (&list1);
1364
1365   return TRUE;
1366 }
1367
1368 #endif