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