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