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