dbus/dbus-list.c

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