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