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