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