glib/gqueue.c

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