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