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