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