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