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