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  * SPDX-License-Identifier: LGPL-2.1-or-later
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2.1 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  21  */
  22
  23 /*
  24  * MT safe
  25  */
  26
  27 #include "config.h"
  28
  29 #include "gqueue.h"
  30
  31 #include "gtestutils.h"
  32 #include "gslice.h"
  33
  34 /**
  35  * g_queue_new:
  36  *
  37  * Creates a new #GQueue.
  38  *
  39  * Returns: a newly allocated #GQueue
  40  **/
  41 GQueue *
  42 g_queue_new (void)
  43 {
  44   return g_slice_new0 (GQueue);
  45 }
  46
  47 /**
  48  * g_queue_free:
  49  * @queue: a #GQueue
  50  *
  51  * Frees the memory allocated for the #GQueue. Only call this function
  52  * if @queue was created with g_queue_new(). If queue elements contain
  53  * dynamically-allocated memory, they should be freed first.
  54  *
  55  * If queue elements contain dynamically-allocated memory, you should
  56  * either use g_queue_free_full() or free them manually first.
  57  **/
  58 void
  59 g_queue_free (GQueue *queue)
  60 {
  61   g_return_if_fail (queue != NULL);
  62
  63   g_list_free (queue->head);
  64   g_slice_free (GQueue, queue);
  65 }
  66
  67 /**
  68  * g_queue_free_full:
  69  * @queue: a pointer to a #GQueue
  70  * @free_func: the function to be called to free each element's data
  71  *
  72  * Convenience method, which frees all the memory used by a #GQueue,
  73  * and calls the specified destroy function on every element's data.
  74  *
  75  * @free_func should not modify the queue (eg, by removing the freed
  76  * element from it).
  77  *
  78  * Since: 2.32
  79  */
  80 void
  81 g_queue_free_full (GQueue        *queue,
  82                   GDestroyNotify  free_func)
  83 {
  84   g_queue_foreach (queue, (GFunc) free_func, NULL);
  85   g_queue_free (queue);
  86 }
  87
  88 /**
  89  * g_queue_init:
  90  * @queue: an uninitialized #GQueue
  91  *
  92  * A statically-allocated #GQueue must be initialized with this function
  93  * before it can be used. Alternatively you can initialize it with
  94  * %G_QUEUE_INIT. It is not necessary to initialize queues created with
  95  * g_queue_new().
  96  *
  97  * Since: 2.14
  98  */
  99 void
 100 g_queue_init (GQueue *queue)
 101 {
 102   g_return_if_fail (queue != NULL);
 103
 104   queue->head = queue->tail = NULL;
 105   queue->length = 0;
 106 }
 107
 108 /**
 109  * g_queue_clear:
 110  * @queue: a #GQueue
 111  *
 112  * Removes all the elements in @queue. If queue elements contain
 113  * dynamically-allocated memory, they should be freed first.
 114  *
 115  * Since: 2.14
 116  */
 117 void
 118 g_queue_clear (GQueue *queue)
 119 {
 120   g_return_if_fail (queue != NULL);
 121
 122   g_list_free (queue->head);
 123   g_queue_init (queue);
 124 }
 125
 126 /**
 127  * g_queue_clear_full:
 128  * @queue: a pointer to a #GQueue
 129  * @free_func: (nullable): the function to be called to free memory allocated
 130  *
 131  * Convenience method, which frees all the memory used by a #GQueue,
 132  * and calls the provided @free_func on each item in the #GQueue.
 133  *
 134  * Since: 2.60
 135  */
 136 void
 137 g_queue_clear_full (GQueue          *queue,
 138                     GDestroyNotify  free_func)
 139 {
 140   g_return_if_fail (queue != NULL);
 141
 142   if (free_func != NULL)
 143     g_queue_foreach (queue, (GFunc) free_func, NULL);
 144
 145   g_queue_clear (queue);
 146 }
 147
 148 /**
 149  * g_queue_is_empty:
 150  * @queue: a #GQueue.
 151  *
 152  * Returns %TRUE if the queue is empty.
 153  *
 154  * Returns: %TRUE if the queue is empty
 155  */
 156 gboolean
 157 g_queue_is_empty (GQueue *queue)
 158 {
 159   g_return_val_if_fail (queue != NULL, TRUE);
 160
 161   return queue->head == NULL;
 162 }
 163
 164 /**
 165  * g_queue_get_length:
 166  * @queue: a #GQueue
 167  *
 168  * Returns the number of items in @queue.
 169  *
 170  * Returns: the number of items in @queue
 171  *
 172  * Since: 2.4
 173  */
 174 guint
 175 g_queue_get_length (GQueue *queue)
 176 {
 177   g_return_val_if_fail (queue != NULL, 0);
 178
 179   return queue->length;
 180 }
 181
 182 /**
 183  * g_queue_reverse:
 184  * @queue: a #GQueue
 185  *
 186  * Reverses the order of the items in @queue.
 187  *
 188  * Since: 2.4
 189  */
 190 void
 191 g_queue_reverse (GQueue *queue)
 192 {
 193   g_return_if_fail (queue != NULL);
 194
 195   queue->tail = queue->head;
 196   queue->head = g_list_reverse (queue->head);
 197 }
 198
 199 /**
 200  * g_queue_copy:
 201  * @queue: a #GQueue
 202  *
 203  * Copies a @queue. Note that is a shallow copy. If the elements in the
 204  * queue consist of pointers to data, the pointers are copied, but the
 205  * actual data is not.
 206  *
 207  * Returns: a copy of @queue
 208  *
 209  * Since: 2.4
 210  */
 211 GQueue *
 212 g_queue_copy (GQueue *queue)
 213 {
 214   GQueue *result;
 215   GList *list;
 216
 217   g_return_val_if_fail (queue != NULL, NULL);
 218
 219   result = g_queue_new ();
 220
 221   for (list = queue->head; list != NULL; list = list->next)
 222     g_queue_push_tail (result, list->data);
 223
 224   return result;
 225 }
 226
 227 /**
 228  * g_queue_foreach:
 229  * @queue: a #GQueue
 230  * @func: (scope call): the function to call for each element's data
 231  * @user_data: user data to pass to @func
 232  *
 233  * Calls @func for each element in the queue passing @user_data to the
 234  * function.
 235  *
 236  * It is safe for @func to remove the element from @queue, but it must
 237  * not modify any part of the queue after that element.
 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  * Returns: 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: (scope call): 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  * Returns: 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: (scope call): 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 || (guint) 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, not a list with more than one element
 384  *
 385  * Adds a new element at the head of the queue.
 386  */
 387 void
 388 g_queue_push_head_link (GQueue *queue,
 389                         GList  *link)
 390 {
 391   g_return_if_fail (queue != NULL);
 392   g_return_if_fail (link != NULL);
 393   g_return_if_fail (link->prev == NULL);
 394   g_return_if_fail (link->next == NULL);
 395
 396   link->next = queue->head;
 397   if (queue->head)
 398     queue->head->prev = link;
 399   else
 400     queue->tail = link;
 401   queue->head = link;
 402   queue->length++;
 403 }
 404
 405 /**
 406  * g_queue_push_tail:
 407  * @queue: a #GQueue
 408  * @data: the data for the new element
 409  *
 410  * Adds a new element at the tail of the queue.
 411  */
 412 void
 413 g_queue_push_tail (GQueue   *queue,
 414                    gpointer  data)
 415 {
 416   g_return_if_fail (queue != NULL);
 417
 418   queue->tail = g_list_append (queue->tail, data);
 419   if (queue->tail->next)
 420     queue->tail = queue->tail->next;
 421   else
 422     queue->head = queue->tail;
 423   queue->length++;
 424 }
 425
 426 /**
 427  * g_queue_push_tail_link:
 428  * @queue: a #GQueue
 429  * @link_: a single #GList element, not a list with more than one element
 430  *
 431  * Adds a new element at the tail of the queue.
 432  */
 433 void
 434 g_queue_push_tail_link (GQueue *queue,
 435                         GList  *link)
 436 {
 437   g_return_if_fail (queue != NULL);
 438   g_return_if_fail (link != NULL);
 439   g_return_if_fail (link->prev == NULL);
 440   g_return_if_fail (link->next == NULL);
 441
 442   link->prev = queue->tail;
 443   if (queue->tail)
 444     queue->tail->next = link;
 445   else
 446     queue->head = link;
 447   queue->tail = link;
 448   queue->length++;
 449 }
 450
 451 /**
 452  * g_queue_push_nth_link:
 453  * @queue: a #GQueue
 454  * @n: the position to insert the link. If this is negative or larger than
 455  *     the number of elements in @queue, the link is added to the end of
 456  *     @queue.
 457  * @link_: the link to add to @queue
 458  *
 459  * Inserts @link into @queue at the given position.
 460  *
 461  * Since: 2.4
 462  */
 463 void
 464 g_queue_push_nth_link (GQueue *queue,
 465                        gint    n,
 466                        GList  *link_)
 467 {
 468   GList *next;
 469   GList *prev;
 470
 471   g_return_if_fail (queue != NULL);
 472   g_return_if_fail (link_ != NULL);
 473
 474   if (n < 0 || (guint) n >= queue->length)
 475     {
 476       g_queue_push_tail_link (queue, link_);
 477       return;
 478     }
 479
 480   g_assert (queue->head);
 481   g_assert (queue->tail);
 482
 483   next = g_queue_peek_nth_link (queue, n);
 484   prev = next->prev;
 485
 486   if (prev)
 487     prev->next = link_;
 488   next->prev = link_;
 489
 490   link_->next = next;
 491   link_->prev = prev;
 492
 493   if (queue->head->prev)
 494     queue->head = queue->head->prev;
 495
 496   /* The case where we’re pushing @link_ at the end of @queue is handled above
 497    * using g_queue_push_tail_link(), so we should never have to manually adjust
 498    * queue->tail. */
 499   g_assert (queue->tail->next == NULL);
 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 and returns its data.
 509  *
 510  * Returns: the data of the first element in the queue, or %NULL
 511  *     if the queue 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 and returns the first element of the queue.
 542  *
 543  * Returns: the #GList element at the head of the queue, or %NULL
 544  *     if the queue 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  * Returns: 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 in @queue.
 594  *
 595  * Returns: 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 and returns its data.
 612  *
 613  * Returns: the data of the last element in the queue, or %NULL
 614  *     if the queue 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 and returns its data.
 646  *
 647  * Returns: 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 and returns the last element of the queue.
 676  *
 677  * Returns: the #GList element at the tail of the queue, or %NULL
 678  *     if the queue 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  * Returns: 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  * Returns: the link at the @n'th position, or %NULL
 741  *     if @n is off the 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   guint 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  * Returns: 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 must be part of @queue
 800  *
 801  * Unlinks @link_ so that it will no longer be part of @queue.
 802  * The link is 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 must 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
 851  *     if the queue 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
 868  *     if the queue 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  * Returns: the data for the @n'th element of @queue,
 886  *     or %NULL if @n is 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  * Returns: the position of the first element in @queue which
 914  *     contains @data, or -1 if no element in @queue contains @data
 915  *
 916  * Since: 2.4
 917  */
 918 gint
 919 g_queue_index (GQueue        *queue,
 920                gconstpointer  data)
 921 {
 922   g_return_val_if_fail (queue != NULL, -1);
 923
 924   return g_list_index (queue->head, data);
 925 }
 926
 927 /**
 928  * g_queue_remove:
 929  * @queue: a #GQueue
 930  * @data: the data to remove
 931  *
 932  * Removes the first element in @queue that contains @data.
 933  *
 934  * Returns: %TRUE if @data was found and removed from @queue
 935  *
 936  * Since: 2.4
 937  */
 938 gboolean
 939 g_queue_remove (GQueue        *queue,
 940                 gconstpointer  data)
 941 {
 942   GList *link;
 943
 944   g_return_val_if_fail (queue != NULL, FALSE);
 945
 946   link = g_list_find (queue->head, data);
 947
 948   if (link)
 949     g_queue_delete_link (queue, link);
 950
 951   return (link != NULL);
 952 }
 953
 954 /**
 955  * g_queue_remove_all:
 956  * @queue: a #GQueue
 957  * @data: the data to remove
 958  *
 959  * Remove all elements whose data equals @data from @queue.
 960  *
 961  * Returns: the number of elements removed from @queue
 962  *
 963  * Since: 2.4
 964  */
 965 guint
 966 g_queue_remove_all (GQueue        *queue,
 967                     gconstpointer  data)
 968 {
 969   GList *list;
 970   guint old_length;
 971
 972   g_return_val_if_fail (queue != NULL, 0);
 973
 974   old_length = queue->length;
 975
 976   list = queue->head;
 977   while (list)
 978     {
 979       GList *next = list->next;
 980
 981       if (list->data == data)
 982         g_queue_delete_link (queue, list);
 983
 984       list = next;
 985     }
 986
 987   return (old_length - queue->length);
 988 }
 989
 990 /**
 991  * g_queue_insert_before:
 992  * @queue: a #GQueue
 993  * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
 994  *   push at the tail of the queue.
 995  * @data: the data to insert
 996  *
 997  * Inserts @data into @queue before @sibling.
 998  *
 999  * @sibling must be part of @queue. Since GLib 2.44 a %NULL sibling pushes the
1000  * data at the tail of the queue.
1001  *
1002  * Since: 2.4
1003  */
1004 void
1005 g_queue_insert_before (GQueue   *queue,
1006                        GList    *sibling,
1007                        gpointer  data)
1008 {
1009   g_return_if_fail (queue != NULL);
1010
1011   if (sibling == NULL)
1012     {
1013       /* We don't use g_list_insert_before() with a NULL sibling because it
1014        * would be a O(n) operation and we would need to update manually the tail
1015        * pointer.
1016        */
1017       g_queue_push_tail (queue, data);
1018     }
1019   else
1020     {
1021       queue->head = g_list_insert_before (queue->head, sibling, data);
1022       queue->length++;
1023     }
1024 }
1025
1026 /**
1027  * g_queue_insert_before_link:
1028  * @queue: a #GQueue
1029  * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
1030  *   push at the tail of the queue.
1031  * @link_: a #GList link to insert which must not be part of any other list.
1032  *
1033  * Inserts @link_ into @queue before @sibling.
1034  *
1035  * @sibling must be part of @queue.
1036  *
1037  * Since: 2.62
1038  */
1039 void
1040 g_queue_insert_before_link (GQueue   *queue,
1041                             GList    *sibling,
1042                             GList    *link_)
1043 {
1044   g_return_if_fail (queue != NULL);
1045   g_return_if_fail (link_ != NULL);
1046   g_return_if_fail (link_->prev == NULL);
1047   g_return_if_fail (link_->next == NULL);
1048
1049   if G_UNLIKELY (sibling == NULL)
1050     {
1051       /* We don't use g_list_insert_before_link() with a NULL sibling because it
1052        * would be a O(n) operation and we would need to update manually the tail
1053        * pointer.
1054        */
1055       g_queue_push_tail_link (queue, link_);
1056     }
1057   else
1058     {
1059       queue->head = g_list_insert_before_link (queue->head, sibling, link_);
1060       queue->length++;
1061     }
1062 }
1063
1064 /**
1065  * g_queue_insert_after:
1066  * @queue: a #GQueue
1067  * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
1068  *   push at the head of the queue.
1069  * @data: the data to insert
1070  *
1071  * Inserts @data into @queue after @sibling.
1072  *
1073  * @sibling must be part of @queue. Since GLib 2.44 a %NULL sibling pushes the
1074  * data at the head of the queue.
1075  *
1076  * Since: 2.4
1077  */
1078 void
1079 g_queue_insert_after (GQueue   *queue,
1080                       GList    *sibling,
1081                       gpointer  data)
1082 {
1083   g_return_if_fail (queue != NULL);
1084
1085   if (sibling == NULL)
1086     g_queue_push_head (queue, data);
1087   else
1088     g_queue_insert_before (queue, sibling->next, data);
1089 }
1090
1091 /**
1092  * g_queue_insert_after_link:
1093  * @queue: a #GQueue
1094  * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
1095  *   push at the head of the queue.
1096  * @link_: a #GList link to insert which must not be part of any other list.
1097  *
1098  * Inserts @link_ into @queue after @sibling.
1099  *
1100  * @sibling must be part of @queue.
1101  *
1102  * Since: 2.62
1103  */
1104 void
1105 g_queue_insert_after_link (GQueue   *queue,
1106                            GList    *sibling,
1107                            GList    *link_)
1108 {
1109   g_return_if_fail (queue != NULL);
1110   g_return_if_fail (link_ != NULL);
1111   g_return_if_fail (link_->prev == NULL);
1112   g_return_if_fail (link_->next == NULL);
1113
1114   if G_UNLIKELY (sibling == NULL)
1115     g_queue_push_head_link (queue, link_);
1116   else
1117     g_queue_insert_before_link (queue, sibling->next, link_);
1118 }
1119
1120 /**
1121  * g_queue_insert_sorted:
1122  * @queue: a #GQueue
1123  * @data: the data to insert
1124  * @func: (scope call): the #GCompareDataFunc used to compare elements in the queue. It is
1125  *     called with two elements of the @queue and @user_data. It should
1126  *     return 0 if the elements are equal, a negative value if the first
1127  *     element comes before the second, and a positive value if the second
1128  *     element comes before the first.
1129  * @user_data: user data passed to @func
1130  *
1131  * Inserts @data into @queue using @func to determine the new position.
1132  *
1133  * Since: 2.4
1134  */
1135 void
1136 g_queue_insert_sorted (GQueue           *queue,
1137                        gpointer          data,
1138                        GCompareDataFunc  func,
1139                        gpointer          user_data)
1140 {
1141   GList *list;
1142
1143   g_return_if_fail (queue != NULL);
1144
1145   list = queue->head;
1146   while (list && func (list->data, data, user_data) < 0)
1147     list = list->next;
1148
1149   g_queue_insert_before (queue, list, data);
1150 }