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