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