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