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