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