glib/gqueue.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * GQueue: Double ended queue implementation, piggy backed on GList.
   5  * Copyright (C) 1998 Tim Janik
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 /*
  22  * MT safe
  23  */
  24
  25 /**
  26  * SECTION:queue
  27  * @Title: Double-ended Queues
  28  * @Short_description: double-ended queue data structure
  29  *
  30  * The #GQueue structure and its associated functions provide a standard
  31  * queue data structure. Internally, GQueue uses the same data structure
  32  * as #GList to store elements.
  33  *
  34  * The data contained in each element can be either integer values, by
  35  * using one of the <link linkend="glib-Type-Conversion-Macros">Type
  36  * Conversion Macros</link>, or simply pointers to any type of data.
  37  *
  38  * To create a new GQueue, use g_queue_new().
  39  *
  40  * To initialize a statically-allocated GQueue, use #G_QUEUE_INIT or
  41  * g_queue_init().
  42  *
  43  * To add elements, use g_queue_push_head(), g_queue_push_head_link(),
  44  * g_queue_push_tail() and g_queue_push_tail_link().
  45  *
  46  * To remove elements, use g_queue_pop_head() and g_queue_pop_tail().
  47  *
  48  * To free the entire queue, use g_queue_free().
  49  */
  50 #include "config.h"
  51
  52 #include "gqueue.h"
  53
  54 #include "gtestutils.h"
  55 #include "gslice.h"
  56
  57 /**
  58  * g_queue_new:
  59  *
  60  * Creates a new #GQueue.
  61  *
  62  * Returns: a newly allocated #GQueue
  63  **/
  64 GQueue *
  65 g_queue_new (void)
  66 {
  67   return g_slice_new0 (GQueue);
  68 }
  69
  70 /**
  71  * g_queue_free:
  72  * @queue: a #GQueue
  73  *
  74  * Frees the memory allocated for the #GQueue. Only call this function
  75  * if @queue was created with g_queue_new(). If queue elements contain
  76  * dynamically-allocated memory, they should be freed first.
  77  *
  78  * If queue elements contain dynamically-allocated memory, you should
  79  * either use g_queue_free_full() or free them manually first.
  80  **/
  81 void
  82 g_queue_free (GQueue *queue)
  83 {
  84   g_return_if_fail (queue != NULL);
  85
  86   g_list_free (queue->head);
  87   g_slice_free (GQueue, queue);
  88 }
  89
  90 /**
  91  * g_queue_free_full:
  92  * @queue: a pointer to a #GQueue
  93  * @free_func: the function to be called to free each element's data
  94  *
  95  * Convenience method, which frees all the memory used by a #GQueue,
  96  * and calls the specified destroy function on every element's data.
  97  *
  98  * Since: 2.32
  99  */
 100 void
 101 g_queue_free_full (GQueue        *queue,
 102                   GDestroyNotify  free_func)
 103 {
 104   g_queue_foreach (queue, (GFunc) free_func, NULL);
 105   g_queue_free (queue);
 106 }
 107
 108 /**
 109  * g_queue_init:
 110  * @queue: an uninitialized #GQueue
 111  *
 112  * A statically-allocated #GQueue must be initialized with this function
 113  * before it can be used. Alternatively you can initialize it with
 114  * #G_QUEUE_INIT. It is not necessary to initialize queues created with
 115  * g_queue_new().
 116  *
 117  * Since: 2.14
 118  */
 119 void
 120 g_queue_init (GQueue *queue)
 121 {
 122   g_return_if_fail (queue != NULL);
 123
 124   queue->head = queue->tail = NULL;
 125   queue->length = 0;
 126 }
 127
 128 /**
 129  * g_queue_clear:
 130  * @queue: a #GQueue
 131  *
 132  * Removes all the elements in @queue. If queue elements contain
 133  * dynamically-allocated memory, they should be freed first.
 134  *
 135  * Since: 2.14
 136  */
 137 void
 138 g_queue_clear (GQueue *queue)
 139 {
 140   g_return_if_fail (queue != NULL);
 141
 142   g_list_free (queue->head);
 143   g_queue_init (queue);
 144 }
 145
 146 /**
 147  * g_queue_is_empty:
 148  * @queue: a #GQueue.
 149  *
 150  * Returns %TRUE if the queue is empty.
 151  *
 152  * Returns: %TRUE if the queue is empty
 153  */
 154 gboolean
 155 g_queue_is_empty (GQueue *queue)
 156 {
 157   g_return_val_if_fail (queue != NULL, TRUE);
 158
 159   return queue->head == NULL;
 160 }
 161
 162 /**
 163  * g_queue_get_length:
 164  * @queue: a #GQueue
 165  *
 166  * Returns the number of items in @queue.
 167  *
 168  * Return value: the number of items in @queue
 169  *
 170  * Since: 2.4
 171  */
 172 guint
 173 g_queue_get_length (GQueue *queue)
 174 {
 175   g_return_val_if_fail (queue != NULL, 0);
 176
 177   return queue->length;
 178 }
 179
 180 /**
 181  * g_queue_reverse:
 182  * @queue: a #GQueue
 183  *
 184  * Reverses the order of the items in @queue.
 185  *
 186  * Since: 2.4
 187  */
 188 void
 189 g_queue_reverse (GQueue *queue)
 190 {
 191   g_return_if_fail (queue != NULL);
 192
 193   queue->tail = queue->head;
 194   queue->head = g_list_reverse (queue->head);
 195 }
 196
 197 /**
 198  * g_queue_copy:
 199  * @queue: a #GQueue
 200  *
 201  * Copies a @queue. Note that is a shallow copy. If the elements in the
 202  * queue consist of pointers to data, the pointers are copied, but the
 203  * actual data is not.
 204  *
 205  * Return value: a copy of @queue
 206  *
 207  * Since: 2.4
 208  */
 209 GQueue *
 210 g_queue_copy (GQueue *queue)
 211 {
 212   GQueue *result;
 213   GList *list;
 214
 215   g_return_val_if_fail (queue != NULL, NULL);
 216
 217   result = g_queue_new ();
 218
 219   for (list = queue->head; list != NULL; list = list->next)
 220     g_queue_push_tail (result, list->data);
 221
 222   return result;
 223 }
 224
 225 /**
 226  * g_queue_foreach:
 227  * @queue: a #GQueue
 228  * @func: the function to call for each element's data
 229  * @user_data: user data to pass to @func
 230  *
 231  * Calls @func for each element in the queue passing @user_data to the
 232  * function.
 233  *
 234  * Since: 2.4
 235  */
 236 void
 237 g_queue_foreach (GQueue   *queue,
 238                  GFunc     func,
 239                  gpointer  user_data)
 240 {
 241   GList *list;
 242
 243   g_return_if_fail (queue != NULL);
 244   g_return_if_fail (func != NULL);
 245
 246   list = queue->head;
 247   while (list)
 248     {
 249       GList *next = list->next;
 250       func (list->data, user_data);
 251       list = next;
 252     }
 253 }
 254
 255 /**
 256  * g_queue_find:
 257  * @queue: a #GQueue
 258  * @data: data to find
 259  *
 260  * Finds the first link in @queue which contains @data.
 261  *
 262  * Return value: the first link in @queue which contains @data
 263  *
 264  * Since: 2.4
 265  */
 266 GList *
 267 g_queue_find (GQueue        *queue,
 268               gconstpointer  data)
 269 {
 270   g_return_val_if_fail (queue != NULL, NULL);
 271
 272   return g_list_find (queue->head, data);
 273 }
 274
 275 /**
 276  * g_queue_find_custom:
 277  * @queue: a #GQueue
 278  * @data: user data passed to @func
 279  * @func: a #GCompareFunc to call for each element. It should return 0
 280  *     when the desired element is found
 281  *
 282  * Finds an element in a #GQueue, using a supplied function to find the
 283  * desired element. It iterates over the queue, calling the given function
 284  * which should return 0 when the desired element is found. The function
 285  * takes two gconstpointer arguments, the #GQueue element's data as the
 286  * first argument and the given user data as the second argument.
 287  *
 288  * Return value: the found link, or %NULL if it wasn't found
 289  *
 290  * Since: 2.4
 291  */
 292 GList *
 293 g_queue_find_custom (GQueue        *queue,
 294                      gconstpointer  data,
 295                      GCompareFunc   func)
 296 {
 297   g_return_val_if_fail (queue != NULL, NULL);
 298   g_return_val_if_fail (func != NULL, NULL);
 299
 300   return g_list_find_custom (queue->head, data, func);
 301 }
 302
 303 /**
 304  * g_queue_sort:
 305  * @queue: a #GQueue
 306  * @compare_func: the #GCompareDataFunc used to sort @queue. This function
 307  *     is passed two elements of the queue and should return 0 if they are
 308  *     equal, a negative value if the first comes before the second, and
 309  *     a positive value if the second comes before the first.
 310  * @user_data: user data passed to @compare_func
 311  *
 312  * Sorts @queue using @compare_func.
 313  *
 314  * Since: 2.4
 315  */
 316 void
 317 g_queue_sort (GQueue           *queue,
 318               GCompareDataFunc  compare_func,
 319               gpointer          user_data)
 320 {
 321   g_return_if_fail (queue != NULL);
 322   g_return_if_fail (compare_func != NULL);
 323
 324   queue->head = g_list_sort_with_data (queue->head, compare_func, user_data);
 325   queue->tail = g_list_last (queue->head);
 326 }
 327
 328 /**
 329  * g_queue_push_head:
 330  * @queue: a #GQueue.
 331  * @data: the data for the new element.
 332  *
 333  * Adds a new element at the head of the queue.
 334  */
 335 void
 336 g_queue_push_head (GQueue   *queue,
 337                    gpointer  data)
 338 {
 339   g_return_if_fail (queue != NULL);
 340
 341   queue->head = g_list_prepend (queue->head, data);
 342   if (!queue->tail)
 343     queue->tail = queue->head;
 344   queue->length++;
 345 }
 346
 347 /**
 348  * g_queue_push_nth:
 349  * @queue: a #GQueue
 350  * @data: the data for the new element
 351  * @n: the position to insert the new element. If @n is negative or
 352  *     larger than the number of elements in the @queue, the element is
 353  *     added to the end of the queue.
 354  *
 355  * Inserts a new element into @queue at the given position.
 356  *
 357  * Since: 2.4
 358  */
 359 void
 360 g_queue_push_nth (GQueue   *queue,
 361                   gpointer  data,
 362                   gint      n)
 363 {
 364   g_return_if_fail (queue != NULL);
 365
 366   if (n < 0 || n >= queue->length)
 367     {
 368       g_queue_push_tail (queue, data);
 369       return;
 370     }
 371
 372   g_queue_insert_before (queue, g_queue_peek_nth_link (queue, n), data);
 373 }
 374
 375 /**
 376  * g_queue_push_head_link:
 377  * @queue: a #GQueue
 378  * @link_: a single #GList element, <emphasis>not</emphasis> a list with
 379  *     more than one element
 380  *
 381  * Adds a new element at the head of the queue.
 382  */
 383 void
 384 g_queue_push_head_link (GQueue *queue,
 385                         GList  *link)
 386 {
 387   g_return_if_fail (queue != NULL);
 388   g_return_if_fail (link != NULL);
 389   g_return_if_fail (link->prev == NULL);
 390   g_return_if_fail (link->next == NULL);
 391
 392   link->next = queue->head;
 393   if (queue->head)
 394     queue->head->prev = link;
 395   else
 396     queue->tail = link;
 397   queue->head = link;
 398   queue->length++;
 399 }
 400
 401 /**
 402  * g_queue_push_tail:
 403  * @queue: a #GQueue
 404  * @data: the data for the new element
 405  *
 406  * Adds a new element at the tail of the queue.
 407  */
 408 void
 409 g_queue_push_tail (GQueue   *queue,
 410                    gpointer  data)
 411 {
 412   g_return_if_fail (queue != NULL);
 413
 414   queue->tail = g_list_append (queue->tail, data);
 415   if (queue->tail->next)
 416     queue->tail = queue->tail->next;
 417   else
 418     queue->head = queue->tail;
 419   queue->length++;
 420 }
 421
 422 /**
 423  * g_queue_push_tail_link:
 424  * @queue: a #GQueue
 425  * @link_: a single #GList element, <emphasis>not</emphasis> a list with
 426  *   more than one element
 427  *
 428  * Adds a new element at the tail of the queue.
 429  */
 430 void
 431 g_queue_push_tail_link (GQueue *queue,
 432                         GList  *link)
 433 {
 434   g_return_if_fail (queue != NULL);
 435   g_return_if_fail (link != NULL);
 436   g_return_if_fail (link->prev == NULL);
 437   g_return_if_fail (link->next == NULL);
 438
 439   link->prev = queue->tail;
 440   if (queue->tail)
 441     queue->tail->next = link;
 442   else
 443     queue->head = link;
 444   queue->tail = link;
 445   queue->length++;
 446 }
 447
 448 /**
 449  * g_queue_push_nth_link:
 450  * @queue: a #GQueue
 451  * @n: the position to insert the link. If this is negative or larger than
 452  *     the number of elements in @queue, the link is added to the end of
 453  *     @queue.
 454  * @link_: the link to add to @queue
 455  *
 456  * Inserts @link into @queue at the given position.
 457  *
 458  * Since: 2.4
 459  */
 460 void
 461 g_queue_push_nth_link (GQueue *queue,
 462                        gint    n,
 463                        GList  *link_)
 464 {
 465   GList *next;
 466   GList *prev;
 467
 468   g_return_if_fail (queue != NULL);
 469   g_return_if_fail (link_ != NULL);
 470
 471   if (n < 0 || n >= queue->length)
 472     {
 473       g_queue_push_tail_link (queue, link_);
 474       return;
 475     }
 476
 477   g_assert (queue->head);
 478   g_assert (queue->tail);
 479
 480   next = g_queue_peek_nth_link (queue, n);
 481   prev = next->prev;
 482
 483   if (prev)
 484     prev->next = link_;
 485   next->prev = link_;
 486
 487   link_->next = next;
 488   link_->prev = prev;
 489
 490   if (queue->head->prev)
 491     queue->head = queue->head->prev;
 492
 493   if (queue->tail->next)
 494     queue->tail = queue->tail->next;
 495
 496   queue->length++;
 497 }
 498
 499 /**
 500  * g_queue_pop_head:
 501  * @queue: a #GQueue
 502  *
 503  * Removes the first element of the queue and returns its data.
 504  *
 505  * Returns: the data of the first element in the queue, or %NULL
 506  *     if the queue is empty
 507  */
 508 gpointer
 509 g_queue_pop_head (GQueue *queue)
 510 {
 511   g_return_val_if_fail (queue != NULL, NULL);
 512
 513   if (queue->head)
 514     {
 515       GList *node = queue->head;
 516       gpointer data = node->data;
 517
 518       queue->head = node->next;
 519       if (queue->head)
 520         queue->head->prev = NULL;
 521       else
 522         queue->tail = NULL;
 523       g_list_free_1 (node);
 524       queue->length--;
 525
 526       return data;
 527     }
 528
 529   return NULL;
 530 }
 531
 532 /**
 533  * g_queue_pop_head_link:
 534  * @queue: a #GQueue
 535  *
 536  * Removes and returns the first element of the queue.
 537  *
 538  * Returns: the #GList element at the head of the queue, or %NULL
 539  *     if the queue is empty
 540  */
 541 GList *
 542 g_queue_pop_head_link (GQueue *queue)
 543 {
 544   g_return_val_if_fail (queue != NULL, NULL);
 545
 546   if (queue->head)
 547     {
 548       GList *node = queue->head;
 549
 550       queue->head = node->next;
 551       if (queue->head)
 552         {
 553           queue->head->prev = NULL;
 554           node->next = NULL;
 555         }
 556       else
 557         queue->tail = NULL;
 558       queue->length--;
 559
 560       return node;
 561     }
 562
 563   return NULL;
 564 }
 565
 566 /**
 567  * g_queue_peek_head_link:
 568  * @queue: a #GQueue
 569  *
 570  * Returns the first link in @queue.
 571  *
 572  * Return value: the first link in @queue, or %NULL if @queue is empty
 573  *
 574  * Since: 2.4
 575  */
 576 GList *
 577 g_queue_peek_head_link (GQueue *queue)
 578 {
 579   g_return_val_if_fail (queue != NULL, NULL);
 580
 581   return queue->head;
 582 }
 583
 584 /**
 585  * g_queue_peek_tail_link:
 586  * @queue: a #GQueue
 587  *
 588  * Returns the last link in @queue.
 589  *
 590  * Return value: the last link in @queue, or %NULL if @queue is empty
 591  *
 592  * Since: 2.4
 593  */
 594 GList *
 595 g_queue_peek_tail_link (GQueue *queue)
 596 {
 597   g_return_val_if_fail (queue != NULL, NULL);
 598
 599   return queue->tail;
 600 }
 601
 602 /**
 603  * g_queue_pop_tail:
 604  * @queue: a #GQueue
 605  *
 606  * Removes the last element of the queue and returns its data.
 607  *
 608  * Returns: the data of the last element in the queue, or %NULL
 609  *     if the queue is empty
 610  */
 611 gpointer
 612 g_queue_pop_tail (GQueue *queue)
 613 {
 614   g_return_val_if_fail (queue != NULL, NULL);
 615
 616   if (queue->tail)
 617     {
 618       GList *node = queue->tail;
 619       gpointer data = node->data;
 620
 621       queue->tail = node->prev;
 622       if (queue->tail)
 623         queue->tail->next = NULL;
 624       else
 625         queue->head = NULL;
 626       queue->length--;
 627       g_list_free_1 (node);
 628
 629       return data;
 630     }
 631
 632   return NULL;
 633 }
 634
 635 /**
 636  * g_queue_pop_nth:
 637  * @queue: a #GQueue
 638  * @n: the position of the element
 639  *
 640  * Removes the @n'th element of @queue and returns its data.
 641  *
 642  * Return value: the element's data, or %NULL if @n is off the end of @queue
 643  *
 644  * Since: 2.4
 645  */
 646 gpointer
 647 g_queue_pop_nth (GQueue *queue,
 648                  guint   n)
 649 {
 650   GList *nth_link;
 651   gpointer result;
 652
 653   g_return_val_if_fail (queue != NULL, NULL);
 654
 655   if (n >= queue->length)
 656     return NULL;
 657
 658   nth_link = g_queue_peek_nth_link (queue, n);
 659   result = nth_link->data;
 660
 661   g_queue_delete_link (queue, nth_link);
 662
 663   return result;
 664 }
 665
 666 /**
 667  * g_queue_pop_tail_link:
 668  * @queue: a #GQueue
 669  *
 670  * Removes and returns the last element of the queue.
 671  *
 672  * Returns: the #GList element at the tail of the queue, or %NULL
 673  *     if the queue is empty
 674  */
 675 GList *
 676 g_queue_pop_tail_link (GQueue *queue)
 677 {
 678   g_return_val_if_fail (queue != NULL, NULL);
 679
 680   if (queue->tail)
 681     {
 682       GList *node = queue->tail;
 683
 684       queue->tail = node->prev;
 685       if (queue->tail)
 686         {
 687           queue->tail->next = NULL;
 688           node->prev = NULL;
 689         }
 690       else
 691         queue->head = NULL;
 692       queue->length--;
 693
 694       return node;
 695     }
 696
 697   return NULL;
 698 }
 699
 700 /**
 701  * g_queue_pop_nth_link:
 702  * @queue: a #GQueue
 703  * @n: the link's position
 704  *
 705  * Removes and returns the link at the given position.
 706  *
 707  * Return value: the @n'th link, or %NULL if @n is off the end of @queue
 708  *
 709  * Since: 2.4
 710  */
 711 GList*
 712 g_queue_pop_nth_link (GQueue *queue,
 713                       guint   n)
 714 {
 715   GList *link;
 716
 717   g_return_val_if_fail (queue != NULL, NULL);
 718
 719   if (n >= queue->length)
 720     return NULL;
 721
 722   link = g_queue_peek_nth_link (queue, n);
 723   g_queue_unlink (queue, link);
 724
 725   return link;
 726 }
 727
 728 /**
 729  * g_queue_peek_nth_link:
 730  * @queue: a #GQueue
 731  * @n: the position of the link
 732  *
 733  * Returns the link at the given position
 734  *
 735  * Return value: the link at the @n'th position, or %NULL
 736  *     if @n is off the end of the list
 737  *
 738  * Since: 2.4
 739  */
 740 GList *
 741 g_queue_peek_nth_link (GQueue *queue,
 742                        guint   n)
 743 {
 744   GList *link;
 745   gint i;
 746
 747   g_return_val_if_fail (queue != NULL, NULL);
 748
 749   if (n >= queue->length)
 750     return NULL;
 751
 752   if (n > queue->length / 2)
 753     {
 754       n = queue->length - n - 1;
 755
 756       link = queue->tail;
 757       for (i = 0; i < n; ++i)
 758         link = link->prev;
 759     }
 760   else
 761     {
 762       link = queue->head;
 763       for (i = 0; i < n; ++i)
 764         link = link->next;
 765     }
 766
 767   return link;
 768 }
 769
 770 /**
 771  * g_queue_link_index:
 772  * @queue: a #GQueue
 773  * @link_: a #GList link
 774  *
 775  * Returns the position of @link_ in @queue.
 776  *
 777  * Return value: the position of @link_, or -1 if the link is
 778  *     not part of @queue
 779  *
 780  * Since: 2.4
 781  */
 782 gint
 783 g_queue_link_index (GQueue *queue,
 784                     GList  *link_)
 785 {
 786   g_return_val_if_fail (queue != NULL, -1);
 787
 788   return g_list_position (queue->head, link_);
 789 }
 790
 791 /**
 792  * g_queue_unlink:
 793  * @queue: a #GQueue
 794  * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
 795  *
 796  * Unlinks @link_ so that it will no longer be part of @queue. The link is
 797  * not freed.
 798  *
 799  * @link_ must be part of @queue.
 800  *
 801  * Since: 2.4
 802  */
 803 void
 804 g_queue_unlink (GQueue *queue,
 805                 GList  *link_)
 806 {
 807   g_return_if_fail (queue != NULL);
 808   g_return_if_fail (link_ != NULL);
 809
 810   if (link_ == queue->tail)
 811     queue->tail = queue->tail->prev;
 812
 813   queue->head = g_list_remove_link (queue->head, link_);
 814   queue->length--;
 815 }
 816
 817 /**
 818  * g_queue_delete_link:
 819  * @queue: a #GQueue
 820  * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
 821  *
 822  * Removes @link_ from @queue and frees it.
 823  *
 824  * @link_ must be part of @queue.
 825  *
 826  * Since: 2.4
 827  */
 828 void
 829 g_queue_delete_link (GQueue *queue,
 830                      GList  *link_)
 831 {
 832   g_return_if_fail (queue != NULL);
 833   g_return_if_fail (link_ != NULL);
 834
 835   g_queue_unlink (queue, link_);
 836   g_list_free (link_);
 837 }
 838
 839 /**
 840  * g_queue_peek_head:
 841  * @queue: a #GQueue
 842  *
 843  * Returns the first element of the queue.
 844  *
 845  * Returns: the data of the first element in the queue, or %NULL
 846  *     if the queue is empty
 847  */
 848 gpointer
 849 g_queue_peek_head (GQueue *queue)
 850 {
 851   g_return_val_if_fail (queue != NULL, NULL);
 852
 853   return queue->head ? queue->head->data : NULL;
 854 }
 855
 856 /**
 857  * g_queue_peek_tail:
 858  * @queue: a #GQueue
 859  *
 860  * Returns the last element of the queue.
 861  *
 862  * Returns: the data of the last element in the queue, or %NULL
 863  *     if the queue is empty
 864  */
 865 gpointer
 866 g_queue_peek_tail (GQueue *queue)
 867 {
 868   g_return_val_if_fail (queue != NULL, NULL);
 869
 870   return queue->tail ? queue->tail->data : NULL;
 871 }
 872
 873 /**
 874  * g_queue_peek_nth:
 875  * @queue: a #GQueue
 876  * @n: the position of the element
 877  *
 878  * Returns the @n'th element of @queue.
 879  *
 880  * Return value: the data for the @n'th element of @queue,
 881  *     or %NULL if @n is off the end of @queue
 882  *
 883  * Since: 2.4
 884  */
 885 gpointer
 886 g_queue_peek_nth (GQueue *queue,
 887                   guint   n)
 888 {
 889   GList *link;
 890
 891   g_return_val_if_fail (queue != NULL, NULL);
 892
 893   link = g_queue_peek_nth_link (queue, n);
 894
 895   if (link)
 896     return link->data;
 897
 898   return NULL;
 899 }
 900
 901 /**
 902  * g_queue_index:
 903  * @queue: a #GQueue
 904  * @data: the data to find
 905  *
 906  * Returns the position of the first element in @queue which contains @data.
 907  *
 908  * Return value: the position of the first element in @queue which
 909  *     contains @data, or -1 if no element in @queue contains @data
 910  *
 911  * Since: 2.4
 912  */
 913 gint
 914 g_queue_index (GQueue        *queue,
 915                gconstpointer  data)
 916 {
 917   g_return_val_if_fail (queue != NULL, -1);
 918
 919   return g_list_index (queue->head, data);
 920 }
 921
 922 /**
 923  * g_queue_remove:
 924  * @queue: a #GQueue
 925  * @data: the data to remove
 926  *
 927  * Removes the first element in @queue that contains @data.
 928  *
 929  * Return value: %TRUE if @data was found and removed from @queue
 930  *
 931  * Since: 2.4
 932  */
 933 gboolean
 934 g_queue_remove (GQueue        *queue,
 935                 gconstpointer  data)
 936 {
 937   GList *link;
 938
 939   g_return_val_if_fail (queue != NULL, FALSE);
 940
 941   link = g_list_find (queue->head, data);
 942
 943   if (link)
 944     g_queue_delete_link (queue, link);
 945
 946   return (link != NULL);
 947 }
 948
 949 /**
 950  * g_queue_remove_all:
 951  * @queue: a #GQueue
 952  * @data: the data to remove
 953  *
 954  * Remove all elements whose data equals @data from @queue.
 955  *
 956  * Return value: the number of elements removed from @queue
 957  *
 958  * Since: 2.4
 959  */
 960 guint
 961 g_queue_remove_all (GQueue        *queue,
 962                     gconstpointer  data)
 963 {
 964   GList *list;
 965   guint old_length;
 966
 967   g_return_val_if_fail (queue != NULL, 0);
 968
 969   old_length = queue->length;
 970
 971   list = queue->head;
 972   while (list)
 973     {
 974       GList *next = list->next;
 975
 976       if (list->data == data)
 977         g_queue_delete_link (queue, list);
 978
 979       list = next;
 980     }
 981
 982   return (old_length - queue->length);
 983 }
 984
 985 /**
 986  * g_queue_insert_before:
 987  * @queue: a #GQueue
 988  * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
 989  * @data: the data to insert
 990  *
 991  * Inserts @data into @queue before @sibling.
 992  *
 993  * @sibling must be part of @queue.
 994  *
 995  * Since: 2.4
 996  */
 997 void
 998 g_queue_insert_before (GQueue   *queue,
 999                        GList    *sibling,
1000                        gpointer  data)
1001 {
1002   g_return_if_fail (queue != NULL);
1003   g_return_if_fail (sibling != NULL);
1004
1005   queue->head = g_list_insert_before (queue->head, sibling, data);
1006   queue->length++;
1007 }
1008
1009 /**
1010  * g_queue_insert_after:
1011  * @queue: a #GQueue
1012  * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
1013  * @data: the data to insert
1014  *
1015  * Inserts @data into @queue after @sibling
1016  *
1017  * @sibling must be part of @queue
1018  *
1019  * Since: 2.4
1020  */
1021 void
1022 g_queue_insert_after (GQueue   *queue,
1023                       GList    *sibling,
1024                       gpointer  data)
1025 {
1026   g_return_if_fail (queue != NULL);
1027   g_return_if_fail (sibling != NULL);
1028
1029   if (sibling == queue->tail)
1030     g_queue_push_tail (queue, data);
1031   else
1032     g_queue_insert_before (queue, sibling->next, data);
1033 }
1034
1035 /**
1036  * g_queue_insert_sorted:
1037  * @queue: a #GQueue
1038  * @data: the data to insert
1039  * @func: the #GCompareDataFunc used to compare elements in the queue. It is
1040  *     called with two elements of the @queue and @user_data. It should
1041  *     return 0 if the elements are equal, a negative value if the first
1042  *     element comes before the second, and a positive value if the second
1043  *     element comes before the first.
1044  * @user_data: user data passed to @func
1045  *
1046  * Inserts @data into @queue using @func to determine the new position.
1047  *
1048  * Since: 2.4
1049  */
1050 void
1051 g_queue_insert_sorted (GQueue           *queue,
1052                        gpointer          data,
1053                        GCompareDataFunc  func,
1054                        gpointer          user_data)
1055 {
1056   GList *list;
1057
1058   g_return_if_fail (queue != NULL);
1059
1060   list = queue->head;
1061   while (list && func (list->data, data, user_data) < 0)
1062     list = list->next;
1063
1064   if (list)
1065     g_queue_insert_before (queue, list, data);
1066   else
1067     g_queue_push_tail (queue, data);
1068 }