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 **/
68GQueue *
69g_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 **/
85void
86g_queue_free (GQueue *queue)
87{
88 g_return_if_fail (queue != NULL);
89
90 g_list_free (list: 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 */
107void
108g_queue_free_full (GQueue *queue,
109 GDestroyNotify free_func)
110{
111 g_queue_foreach (queue, func: (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 */
126void
127g_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 */
144void
145g_queue_clear (GQueue *queue)
146{
147 g_return_if_fail (queue != NULL);
148
149 g_list_free (list: 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 */
163void
164g_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, func: (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 */
183gboolean
184g_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 */
201guint
202g_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 */
217void
218g_queue_reverse (GQueue *queue)
219{
220 g_return_if_fail (queue != NULL);
221
222 queue->tail = queue->head;
223 queue->head = g_list_reverse (list: 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 */
238GQueue *
239g_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 (queue: result, data: 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 */
268void
269g_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 */
298GList *
299g_queue_find (GQueue *queue,
300 gconstpointer data)
301{
302 g_return_val_if_fail (queue != NULL, NULL);
303
304 return g_list_find (list: 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 */
324GList *
325g_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 (list: 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 */
348void
349g_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 (list: queue->head, compare_func, user_data);
357 queue->tail = g_list_last (list: 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 */
367void
368g_queue_push_head (GQueue *queue,
369 gpointer data)
370{
371 g_return_if_fail (queue != NULL);
372
373 queue->head = g_list_prepend (list: 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 */
391void
392g_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, sibling: 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 */
414void
415g_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 */
439void
440g_queue_push_tail (GQueue *queue,
441 gpointer data)
442{
443 g_return_if_fail (queue != NULL);
444
445 queue->tail = g_list_append (list: 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 */
460void
461g_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 */
490void
491g_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: 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 */
540gpointer
541g_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 (list: 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 */
573GList *
574g_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 */
608GList *
609g_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 */
626GList *
627g_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 */
643gpointer
644g_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 (list: 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 */
678gpointer
679g_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, link_: 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 */
707GList *
708g_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 */
743GList*
744g_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_: 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 */
772GList *
773g_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 */
814gint
815g_queue_link_index (GQueue *queue,
816 GList *link_)
817{
818 g_return_val_if_fail (queue != NULL, -1);
819
820 return g_list_position (list: queue->head, llink: 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 */
835void
836g_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 (list: queue->head, llink: 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 */
860void
861g_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 (list: 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 */
880gpointer
881g_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 */
897gpointer
898g_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 */
917gpointer
918g_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 */
945gint
946g_queue_index (GQueue *queue,
947 gconstpointer data)
948{
949 g_return_val_if_fail (queue != NULL, -1);
950
951 return g_list_index (list: 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 */
965gboolean
966g_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 (list: queue->head, data);
974
975 if (link)
976 g_queue_delete_link (queue, link_: 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 */
992guint
993g_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, link_: 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 */
1031void
1032g_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 (list: 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 */
1066void
1067g_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: link_);
1083 }
1084 else
1085 {
1086 queue->head = g_list_insert_before_link (list: 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 */
1105void
1106g_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: 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 */
1131void
1132g_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: link_);
1143 else
1144 g_queue_insert_before_link (queue, sibling: 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 */
1162void
1163g_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, sibling: list, data);
1177}
1178

source code of gtk/subprojects/glib/glib/gqueue.c