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