Branch data Line data Source code
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 : 46331 : g_queue_new (void)
43 : : {
44 : 46331 : 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 : 45577 : g_queue_free (GQueue *queue)
60 : : {
61 : 45577 : g_return_if_fail (queue != NULL);
62 : :
63 : 45577 : g_list_free (queue->head);
64 : 45577 : 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 : 7047 : g_queue_free_full (GQueue *queue,
82 : : GDestroyNotify free_func)
83 : : {
84 : 7047 : g_queue_foreach (queue, (GFunc) free_func, NULL);
85 : 7047 : g_queue_free (queue);
86 : 7047 : }
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 : 679 : g_queue_init (GQueue *queue)
101 : : {
102 : 679 : g_return_if_fail (queue != NULL);
103 : :
104 : 679 : queue->head = queue->tail = NULL;
105 : 679 : 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 : 89 : g_queue_clear (GQueue *queue)
119 : : {
120 : 89 : g_return_if_fail (queue != NULL);
121 : :
122 : 89 : g_list_free (queue->head);
123 : 89 : 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 : 2 : g_queue_clear_full (GQueue *queue,
138 : : GDestroyNotify free_func)
139 : : {
140 : 2 : g_return_if_fail (queue != NULL);
141 : :
142 : 2 : if (free_func != NULL)
143 : 1 : g_queue_foreach (queue, (GFunc) free_func, NULL);
144 : :
145 : 2 : 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 : 89351 : g_queue_is_empty (GQueue *queue)
158 : : {
159 : 89351 : g_return_val_if_fail (queue != NULL, TRUE);
160 : :
161 : 89351 : 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 : 7824501 : g_queue_get_length (GQueue *queue)
176 : : {
177 : 7824501 : g_return_val_if_fail (queue != NULL, 0);
178 : :
179 : 7824501 : 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 : 3034 : g_queue_reverse (GQueue *queue)
192 : : {
193 : 3034 : g_return_if_fail (queue != NULL);
194 : :
195 : 3034 : queue->tail = queue->head;
196 : 3034 : 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 : 2748 : g_queue_copy (GQueue *queue)
213 : : {
214 : : GQueue *result;
215 : : GList *list;
216 : :
217 : 2748 : g_return_val_if_fail (queue != NULL, NULL);
218 : :
219 : 2748 : result = g_queue_new ();
220 : :
221 : 20400 : for (list = queue->head; list != NULL; list = list->next)
222 : 17652 : g_queue_push_tail (result, list->data);
223 : :
224 : 2748 : 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 : 31394 : g_queue_foreach (GQueue *queue,
243 : : GFunc func,
244 : : gpointer user_data)
245 : : {
246 : : GList *list;
247 : :
248 : 31394 : g_return_if_fail (queue != NULL);
249 : 31394 : g_return_if_fail (func != NULL);
250 : :
251 : 31394 : list = queue->head;
252 : 194359 : while (list)
253 : : {
254 : 162965 : GList *next = list->next;
255 : 162965 : func (list->data, user_data);
256 : 162965 : 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 : 16066 : g_queue_find (GQueue *queue,
273 : : gconstpointer data)
274 : : {
275 : 16066 : g_return_val_if_fail (queue != NULL, NULL);
276 : :
277 : 16066 : 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 : 3 : g_queue_find_custom (GQueue *queue,
299 : : gconstpointer data,
300 : : GCompareFunc func)
301 : : {
302 : 3 : g_return_val_if_fail (queue != NULL, NULL);
303 : 3 : g_return_val_if_fail (func != NULL, NULL);
304 : :
305 : 3 : 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 : 190089 : g_queue_sort (GQueue *queue,
323 : : GCompareDataFunc compare_func,
324 : : gpointer user_data)
325 : : {
326 : 190089 : g_return_if_fail (queue != NULL);
327 : 190089 : g_return_if_fail (compare_func != NULL);
328 : :
329 : 190089 : queue->head = g_list_sort_with_data (queue->head, compare_func, user_data);
330 : 190089 : 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 : 578200 : g_queue_push_head (GQueue *queue,
342 : : gpointer data)
343 : : {
344 : 578200 : g_return_if_fail (queue != NULL);
345 : :
346 : 578200 : queue->head = g_list_prepend (queue->head, data);
347 : 578200 : if (!queue->tail)
348 : 83314 : queue->tail = queue->head;
349 : 578200 : 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 : 3065 : g_queue_push_nth (GQueue *queue,
366 : : gpointer data,
367 : : gint n)
368 : : {
369 : 3065 : g_return_if_fail (queue != NULL);
370 : :
371 : 3065 : if (n < 0 || (guint) n >= queue->length)
372 : : {
373 : 1995 : g_queue_push_tail (queue, data);
374 : 1995 : return;
375 : : }
376 : :
377 : 1070 : 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 : 2852 : g_queue_push_head_link (GQueue *queue,
389 : : GList *link)
390 : : {
391 : 2852 : g_return_if_fail (queue != NULL);
392 : 2852 : g_return_if_fail (link != NULL);
393 : 2852 : g_return_if_fail (link->prev == NULL);
394 : 2852 : g_return_if_fail (link->next == NULL);
395 : :
396 : 2852 : link->next = queue->head;
397 : 2852 : if (queue->head)
398 : 2143 : queue->head->prev = link;
399 : : else
400 : 709 : queue->tail = link;
401 : 2852 : queue->head = link;
402 : 2852 : 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 : 511485 : g_queue_push_tail (GQueue *queue,
414 : : gpointer data)
415 : : {
416 : 511485 : g_return_if_fail (queue != NULL);
417 : :
418 : 511485 : queue->tail = g_list_append (queue->tail, data);
419 : 511485 : if (queue->tail->next)
420 : 438335 : queue->tail = queue->tail->next;
421 : : else
422 : 73150 : queue->head = queue->tail;
423 : 511485 : 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 : 191190 : g_queue_push_tail_link (GQueue *queue,
435 : : GList *link)
436 : : {
437 : 191190 : g_return_if_fail (queue != NULL);
438 : 191190 : g_return_if_fail (link != NULL);
439 : 191190 : g_return_if_fail (link->prev == NULL);
440 : 191190 : g_return_if_fail (link->next == NULL);
441 : :
442 : 191190 : link->prev = queue->tail;
443 : 191190 : if (queue->tail)
444 : 3837 : queue->tail->next = link;
445 : : else
446 : 187353 : queue->head = link;
447 : 191190 : queue->tail = link;
448 : 191190 : 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 : 2990 : g_queue_push_nth_link (GQueue *queue,
465 : : gint n,
466 : : GList *link_)
467 : : {
468 : : GList *next;
469 : : GList *prev;
470 : :
471 : 2990 : g_return_if_fail (queue != NULL);
472 : 2990 : g_return_if_fail (link_ != NULL);
473 : :
474 : 2990 : if (n < 0 || (guint) n >= queue->length)
475 : : {
476 : 1901 : g_queue_push_tail_link (queue, link_);
477 : 1901 : return;
478 : : }
479 : :
480 : 1089 : g_assert (queue->head);
481 : 1089 : g_assert (queue->tail);
482 : :
483 : 1089 : next = g_queue_peek_nth_link (queue, n);
484 : 1089 : prev = next->prev;
485 : :
486 : 1089 : if (prev)
487 : 365 : prev->next = link_;
488 : 1089 : next->prev = link_;
489 : :
490 : 1089 : link_->next = next;
491 : 1089 : link_->prev = prev;
492 : :
493 : 1089 : if (queue->head->prev)
494 : 724 : 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 : 1089 : g_assert (queue->tail->next == NULL);
500 : :
501 : 1089 : 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 : 175510 : g_queue_pop_head (GQueue *queue)
515 : : {
516 : 175510 : g_return_val_if_fail (queue != NULL, NULL);
517 : :
518 : 175510 : if (queue->head)
519 : : {
520 : 165775 : GList *node = queue->head;
521 : 165775 : gpointer data = node->data;
522 : :
523 : 165775 : queue->head = node->next;
524 : 165775 : if (queue->head)
525 : 111165 : queue->head->prev = NULL;
526 : : else
527 : 54610 : queue->tail = NULL;
528 : 165775 : g_list_free_1 (node);
529 : 165775 : queue->length--;
530 : :
531 : 165775 : return data;
532 : : }
533 : :
534 : 9735 : 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 : 2098 : g_queue_pop_head_link (GQueue *queue)
548 : : {
549 : 2098 : g_return_val_if_fail (queue != NULL, NULL);
550 : :
551 : 2098 : if (queue->head)
552 : : {
553 : 2097 : GList *node = queue->head;
554 : :
555 : 2097 : queue->head = node->next;
556 : 2097 : if (queue->head)
557 : : {
558 : 1728 : queue->head->prev = NULL;
559 : 1728 : node->next = NULL;
560 : : }
561 : : else
562 : 369 : queue->tail = NULL;
563 : 2097 : queue->length--;
564 : :
565 : 2097 : return node;
566 : : }
567 : :
568 : 1 : 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 : 2865 : g_queue_peek_head_link (GQueue *queue)
583 : : {
584 : 2865 : g_return_val_if_fail (queue != NULL, NULL);
585 : :
586 : 2865 : 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 : 309918 : g_queue_peek_tail_link (GQueue *queue)
601 : : {
602 : 309918 : g_return_val_if_fail (queue != NULL, NULL);
603 : :
604 : 309918 : 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 : 209269 : g_queue_pop_tail (GQueue *queue)
618 : : {
619 : 209269 : g_return_val_if_fail (queue != NULL, NULL);
620 : :
621 : 209269 : if (queue->tail)
622 : : {
623 : 208363 : GList *node = queue->tail;
624 : 208363 : gpointer data = node->data;
625 : :
626 : 208363 : queue->tail = node->prev;
627 : 208363 : if (queue->tail)
628 : 160294 : queue->tail->next = NULL;
629 : : else
630 : 48069 : queue->head = NULL;
631 : 208363 : queue->length--;
632 : 208363 : g_list_free_1 (node);
633 : :
634 : 208363 : return data;
635 : : }
636 : :
637 : 906 : 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 : 2283 : g_queue_pop_nth (GQueue *queue,
653 : : guint n)
654 : : {
655 : : GList *nth_link;
656 : : gpointer result;
657 : :
658 : 2283 : g_return_val_if_fail (queue != NULL, NULL);
659 : :
660 : 2283 : if (n >= queue->length)
661 : 1121 : return NULL;
662 : :
663 : 1162 : nth_link = g_queue_peek_nth_link (queue, n);
664 : 1162 : result = nth_link->data;
665 : :
666 : 1162 : g_queue_delete_link (queue, nth_link);
667 : :
668 : 1162 : 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 : 2232 : g_queue_pop_tail_link (GQueue *queue)
682 : : {
683 : 2232 : g_return_val_if_fail (queue != NULL, NULL);
684 : :
685 : 2232 : if (queue->tail)
686 : : {
687 : 2231 : GList *node = queue->tail;
688 : :
689 : 2231 : queue->tail = node->prev;
690 : 2231 : if (queue->tail)
691 : : {
692 : 1832 : queue->tail->next = NULL;
693 : 1832 : node->prev = NULL;
694 : : }
695 : : else
696 : 399 : queue->head = NULL;
697 : 2231 : queue->length--;
698 : :
699 : 2231 : return node;
700 : : }
701 : :
702 : 1 : 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 : 2806 : g_queue_pop_nth_link (GQueue *queue,
718 : : guint n)
719 : : {
720 : : GList *link;
721 : :
722 : 2806 : g_return_val_if_fail (queue != NULL, NULL);
723 : :
724 : 2806 : if (n >= queue->length)
725 : 690 : return NULL;
726 : :
727 : 2116 : link = g_queue_peek_nth_link (queue, n);
728 : 2116 : g_queue_unlink (queue, link);
729 : :
730 : 2116 : 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 : 1954843 : g_queue_peek_nth_link (GQueue *queue,
747 : : guint n)
748 : : {
749 : : GList *link;
750 : : guint i;
751 : :
752 : 1954843 : g_return_val_if_fail (queue != NULL, NULL);
753 : :
754 : 1954843 : if (n >= queue->length)
755 : 786490 : return NULL;
756 : :
757 : 1168353 : if (n > queue->length / 2)
758 : : {
759 : 542160 : n = queue->length - n - 1;
760 : :
761 : 542160 : link = queue->tail;
762 : 6695381 : for (i = 0; i < n; ++i)
763 : 6153221 : link = link->prev;
764 : : }
765 : : else
766 : : {
767 : 626193 : link = queue->head;
768 : 7433017 : for (i = 0; i < n; ++i)
769 : 6806824 : link = link->next;
770 : : }
771 : :
772 : 1168353 : 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 : 1123985 : g_queue_link_index (GQueue *queue,
789 : : GList *link_)
790 : : {
791 : 1123985 : g_return_val_if_fail (queue != NULL, -1);
792 : :
793 : 1123985 : 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 : 1375027 : g_queue_unlink (GQueue *queue,
810 : : GList *link_)
811 : : {
812 : 1375027 : g_return_if_fail (queue != NULL);
813 : 1375027 : g_return_if_fail (link_ != NULL);
814 : :
815 : 1375027 : if (link_ == queue->tail)
816 : 354035 : queue->tail = queue->tail->prev;
817 : :
818 : 1375027 : queue->head = g_list_remove_link (queue->head, link_);
819 : 1375027 : 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 : 1084454 : g_queue_delete_link (GQueue *queue,
835 : : GList *link_)
836 : : {
837 : 1084454 : g_return_if_fail (queue != NULL);
838 : 1084454 : g_return_if_fail (link_ != NULL);
839 : :
840 : 1084454 : g_queue_unlink (queue, link_);
841 : 1084454 : 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 : 468978 : g_queue_peek_head (GQueue *queue)
855 : : {
856 : 468978 : g_return_val_if_fail (queue != NULL, NULL);
857 : :
858 : 468978 : 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 : 2923 : g_queue_peek_tail (GQueue *queue)
872 : : {
873 : 2923 : g_return_val_if_fail (queue != NULL, NULL);
874 : :
875 : 2923 : 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 : 21435 : g_queue_peek_nth (GQueue *queue,
892 : : guint n)
893 : : {
894 : : GList *link;
895 : :
896 : 21435 : g_return_val_if_fail (queue != NULL, NULL);
897 : :
898 : 21435 : link = g_queue_peek_nth_link (queue, n);
899 : :
900 : 21435 : if (link)
901 : 3697 : return link->data;
902 : :
903 : 17738 : 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 : 5799 : g_queue_index (GQueue *queue,
920 : : gconstpointer data)
921 : : {
922 : 5799 : g_return_val_if_fail (queue != NULL, -1);
923 : :
924 : 5799 : 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 : 46295 : g_queue_remove (GQueue *queue,
940 : : gconstpointer data)
941 : : {
942 : : GList *link;
943 : :
944 : 46295 : g_return_val_if_fail (queue != NULL, FALSE);
945 : :
946 : 46295 : link = g_list_find (queue->head, data);
947 : :
948 : 46295 : if (link)
949 : 31020 : g_queue_delete_link (queue, link);
950 : :
951 : 46295 : 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 : 15298 : g_queue_remove_all (GQueue *queue,
967 : : gconstpointer data)
968 : : {
969 : : GList *list;
970 : : guint old_length;
971 : :
972 : 15298 : g_return_val_if_fail (queue != NULL, 0);
973 : :
974 : 15298 : old_length = queue->length;
975 : :
976 : 15298 : list = queue->head;
977 : 130443 : while (list)
978 : : {
979 : 115145 : GList *next = list->next;
980 : :
981 : 115145 : if (list->data == data)
982 : 11774 : g_queue_delete_link (queue, list);
983 : :
984 : 115145 : list = next;
985 : : }
986 : :
987 : 15298 : 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 : 1797176 : g_queue_insert_before (GQueue *queue,
1006 : : GList *sibling,
1007 : : gpointer data)
1008 : : {
1009 : 1797176 : g_return_if_fail (queue != NULL);
1010 : :
1011 : 1797176 : 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 : 209701 : g_queue_push_tail (queue, data);
1018 : : }
1019 : : else
1020 : : {
1021 : 1587475 : queue->head = g_list_insert_before (queue->head, sibling, data);
1022 : 1587475 : 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 : 100264 : g_queue_insert_before_link (GQueue *queue,
1041 : : GList *sibling,
1042 : : GList *link_)
1043 : : {
1044 : 100264 : g_return_if_fail (queue != NULL);
1045 : 100264 : g_return_if_fail (link_ != NULL);
1046 : 100264 : g_return_if_fail (link_->prev == NULL);
1047 : 100264 : g_return_if_fail (link_->next == NULL);
1048 : :
1049 : 100264 : 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 : 1 : g_queue_push_tail_link (queue, link_);
1056 : : }
1057 : : else
1058 : : {
1059 : 100263 : queue->head = g_list_insert_before_link (queue->head, sibling, link_);
1060 : 100263 : 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 : 8908 : g_queue_insert_after (GQueue *queue,
1080 : : GList *sibling,
1081 : : gpointer data)
1082 : : {
1083 : 8908 : g_return_if_fail (queue != NULL);
1084 : :
1085 : 8908 : if (sibling == NULL)
1086 : 2227 : g_queue_push_head (queue, data);
1087 : : else
1088 : 6681 : 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 : 3 : g_queue_insert_after_link (GQueue *queue,
1106 : : GList *sibling,
1107 : : GList *link_)
1108 : : {
1109 : 3 : g_return_if_fail (queue != NULL);
1110 : 3 : g_return_if_fail (link_ != NULL);
1111 : 3 : g_return_if_fail (link_->prev == NULL);
1112 : 3 : g_return_if_fail (link_->next == NULL);
1113 : :
1114 : 3 : if G_UNLIKELY (sibling == NULL)
1115 : 1 : g_queue_push_head_link (queue, link_);
1116 : : else
1117 : 2 : 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 : 1454765 : g_queue_insert_sorted (GQueue *queue,
1137 : : gpointer data,
1138 : : GCompareDataFunc func,
1139 : : gpointer user_data)
1140 : : {
1141 : : GList *list;
1142 : :
1143 : 1454765 : g_return_if_fail (queue != NULL);
1144 : :
1145 : 1454765 : list = queue->head;
1146 : 34441718 : while (list && func (list->data, data, user_data) < 0)
1147 : 32986953 : list = list->next;
1148 : :
1149 : 1454765 : g_queue_insert_before (queue, list, data);
1150 : : }
|
