dbus/dbus-list.c

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