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