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