1 | /* GLIB - Library of useful routines for C programming |
2 | * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
3 | * |
4 | * GQueue: Double ended queue implementation, piggy backed on GList. |
5 | * Copyright (C) 1998 Tim Janik |
6 | * |
7 | * This library is free software; you can redistribute it and/or |
8 | * modify it under the terms of the GNU Lesser General Public |
9 | * License as published by the Free Software Foundation; either |
10 | * version 2.1 of the License, or (at your option) any later version. |
11 | * |
12 | * This library is distributed in the hope that it will be useful, |
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | * Lesser General Public License for more details. |
16 | * |
17 | * You should have received a copy of the GNU Lesser General Public |
18 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
19 | */ |
20 | |
21 | /* |
22 | * MT safe |
23 | */ |
24 | |
25 | /** |
26 | * SECTION:queue |
27 | * @Title: Double-ended Queues |
28 | * @Short_description: double-ended queue data structure |
29 | * |
30 | * The #GQueue structure and its associated functions provide a standard |
31 | * queue data structure. Internally, GQueue uses the same data structure |
32 | * as #GList to store elements with the same complexity over |
33 | * insertion/deletion (O(1)) and access/search (O(n)) operations. |
34 | * |
35 | * The data contained in each element can be either integer values, by |
36 | * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros], |
37 | * or simply pointers to any type of data. |
38 | * |
39 | * As with all other GLib data structures, #GQueue is not thread-safe. |
40 | * For a thread-safe queue, use #GAsyncQueue. |
41 | * |
42 | * To create a new GQueue, use g_queue_new(). |
43 | * |
44 | * To initialize a statically-allocated GQueue, use #G_QUEUE_INIT or |
45 | * g_queue_init(). |
46 | * |
47 | * To add elements, use g_queue_push_head(), g_queue_push_head_link(), |
48 | * g_queue_push_tail() and g_queue_push_tail_link(). |
49 | * |
50 | * To remove elements, use g_queue_pop_head() and g_queue_pop_tail(). |
51 | * |
52 | * To free the entire queue, use g_queue_free(). |
53 | */ |
54 | #include "config.h" |
55 | |
56 | #include "gqueue.h" |
57 | |
58 | #include "gtestutils.h" |
59 | #include "gslice.h" |
60 | |
61 | /** |
62 | * g_queue_new: |
63 | * |
64 | * Creates a new #GQueue. |
65 | * |
66 | * Returns: a newly allocated #GQueue |
67 | **/ |
68 | GQueue * |
69 | g_queue_new (void) |
70 | { |
71 | return g_slice_new0 (GQueue); |
72 | } |
73 | |
74 | /** |
75 | * g_queue_free: |
76 | * @queue: a #GQueue |
77 | * |
78 | * Frees the memory allocated for the #GQueue. Only call this function |
79 | * if @queue was created with g_queue_new(). If queue elements contain |
80 | * dynamically-allocated memory, they should be freed first. |
81 | * |
82 | * If queue elements contain dynamically-allocated memory, you should |
83 | * either use g_queue_free_full() or free them manually first. |
84 | **/ |
85 | void |
86 | g_queue_free (GQueue *queue) |
87 | { |
88 | g_return_if_fail (queue != NULL); |
89 | |
90 | g_list_free (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 | */ |
107 | void |
108 | g_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 | */ |
126 | void |
127 | g_queue_init (GQueue *queue) |
128 | { |
129 | g_return_if_fail (queue != NULL); |
130 | |
131 | queue->head = queue->tail = NULL; |
132 | queue->length = 0; |
133 | } |
134 | |
135 | /** |
136 | * g_queue_clear: |
137 | * @queue: a #GQueue |
138 | * |
139 | * Removes all the elements in @queue. If queue elements contain |
140 | * dynamically-allocated memory, they should be freed first. |
141 | * |
142 | * Since: 2.14 |
143 | */ |
144 | void |
145 | g_queue_clear (GQueue *queue) |
146 | { |
147 | g_return_if_fail (queue != NULL); |
148 | |
149 | g_list_free (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 | */ |
163 | void |
164 | g_queue_clear_full (GQueue *queue, |
165 | GDestroyNotify free_func) |
166 | { |
167 | g_return_if_fail (queue != NULL); |
168 | |
169 | if (free_func != NULL) |
170 | g_queue_foreach (queue, 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 | */ |
183 | gboolean |
184 | g_queue_is_empty (GQueue *queue) |
185 | { |
186 | g_return_val_if_fail (queue != NULL, TRUE); |
187 | |
188 | return queue->head == NULL; |
189 | } |
190 | |
191 | /** |
192 | * g_queue_get_length: |
193 | * @queue: a #GQueue |
194 | * |
195 | * Returns the number of items in @queue. |
196 | * |
197 | * Returns: the number of items in @queue |
198 | * |
199 | * Since: 2.4 |
200 | */ |
201 | guint |
202 | g_queue_get_length (GQueue *queue) |
203 | { |
204 | g_return_val_if_fail (queue != NULL, 0); |
205 | |
206 | return queue->length; |
207 | } |
208 | |
209 | /** |
210 | * g_queue_reverse: |
211 | * @queue: a #GQueue |
212 | * |
213 | * Reverses the order of the items in @queue. |
214 | * |
215 | * Since: 2.4 |
216 | */ |
217 | void |
218 | g_queue_reverse (GQueue *queue) |
219 | { |
220 | g_return_if_fail (queue != NULL); |
221 | |
222 | queue->tail = queue->head; |
223 | queue->head = g_list_reverse (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 | */ |
238 | GQueue * |
239 | g_queue_copy (GQueue *queue) |
240 | { |
241 | GQueue *result; |
242 | GList *list; |
243 | |
244 | g_return_val_if_fail (queue != NULL, NULL); |
245 | |
246 | result = g_queue_new (); |
247 | |
248 | for (list = queue->head; list != NULL; list = list->next) |
249 | g_queue_push_tail (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 | */ |
268 | void |
269 | g_queue_foreach (GQueue *queue, |
270 | GFunc func, |
271 | gpointer user_data) |
272 | { |
273 | GList *list; |
274 | |
275 | g_return_if_fail (queue != NULL); |
276 | g_return_if_fail (func != NULL); |
277 | |
278 | list = queue->head; |
279 | while (list) |
280 | { |
281 | GList *next = list->next; |
282 | func (list->data, user_data); |
283 | list = next; |
284 | } |
285 | } |
286 | |
287 | /** |
288 | * g_queue_find: |
289 | * @queue: a #GQueue |
290 | * @data: data to find |
291 | * |
292 | * Finds the first link in @queue which contains @data. |
293 | * |
294 | * Returns: the first link in @queue which contains @data |
295 | * |
296 | * Since: 2.4 |
297 | */ |
298 | GList * |
299 | g_queue_find (GQueue *queue, |
300 | gconstpointer data) |
301 | { |
302 | g_return_val_if_fail (queue != NULL, NULL); |
303 | |
304 | return g_list_find (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 | */ |
324 | GList * |
325 | g_queue_find_custom (GQueue *queue, |
326 | gconstpointer data, |
327 | GCompareFunc func) |
328 | { |
329 | g_return_val_if_fail (queue != NULL, NULL); |
330 | g_return_val_if_fail (func != NULL, NULL); |
331 | |
332 | return g_list_find_custom (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 | */ |
348 | void |
349 | g_queue_sort (GQueue *queue, |
350 | GCompareDataFunc compare_func, |
351 | gpointer user_data) |
352 | { |
353 | g_return_if_fail (queue != NULL); |
354 | g_return_if_fail (compare_func != NULL); |
355 | |
356 | queue->head = g_list_sort_with_data (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 | */ |
367 | void |
368 | g_queue_push_head (GQueue *queue, |
369 | gpointer data) |
370 | { |
371 | g_return_if_fail (queue != NULL); |
372 | |
373 | queue->head = g_list_prepend (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 | */ |
391 | void |
392 | g_queue_push_nth (GQueue *queue, |
393 | gpointer data, |
394 | gint n) |
395 | { |
396 | g_return_if_fail (queue != NULL); |
397 | |
398 | if (n < 0 || (guint) n >= queue->length) |
399 | { |
400 | g_queue_push_tail (queue, data); |
401 | return; |
402 | } |
403 | |
404 | g_queue_insert_before (queue, 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 | */ |
414 | void |
415 | g_queue_push_head_link (GQueue *queue, |
416 | GList *link) |
417 | { |
418 | g_return_if_fail (queue != NULL); |
419 | g_return_if_fail (link != NULL); |
420 | g_return_if_fail (link->prev == NULL); |
421 | g_return_if_fail (link->next == NULL); |
422 | |
423 | link->next = queue->head; |
424 | if (queue->head) |
425 | queue->head->prev = link; |
426 | else |
427 | queue->tail = link; |
428 | queue->head = link; |
429 | queue->length++; |
430 | } |
431 | |
432 | /** |
433 | * g_queue_push_tail: |
434 | * @queue: a #GQueue |
435 | * @data: the data for the new element |
436 | * |
437 | * Adds a new element at the tail of the queue. |
438 | */ |
439 | void |
440 | g_queue_push_tail (GQueue *queue, |
441 | gpointer data) |
442 | { |
443 | g_return_if_fail (queue != NULL); |
444 | |
445 | queue->tail = g_list_append (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 | */ |
460 | void |
461 | g_queue_push_tail_link (GQueue *queue, |
462 | GList *link) |
463 | { |
464 | g_return_if_fail (queue != NULL); |
465 | g_return_if_fail (link != NULL); |
466 | g_return_if_fail (link->prev == NULL); |
467 | g_return_if_fail (link->next == NULL); |
468 | |
469 | link->prev = queue->tail; |
470 | if (queue->tail) |
471 | queue->tail->next = link; |
472 | else |
473 | queue->head = link; |
474 | queue->tail = link; |
475 | queue->length++; |
476 | } |
477 | |
478 | /** |
479 | * g_queue_push_nth_link: |
480 | * @queue: a #GQueue |
481 | * @n: the position to insert the link. If this is negative or larger than |
482 | * the number of elements in @queue, the link is added to the end of |
483 | * @queue. |
484 | * @link_: the link to add to @queue |
485 | * |
486 | * Inserts @link into @queue at the given position. |
487 | * |
488 | * Since: 2.4 |
489 | */ |
490 | void |
491 | g_queue_push_nth_link (GQueue *queue, |
492 | gint n, |
493 | GList *link_) |
494 | { |
495 | GList *next; |
496 | GList *prev; |
497 | |
498 | g_return_if_fail (queue != NULL); |
499 | g_return_if_fail (link_ != NULL); |
500 | |
501 | if (n < 0 || (guint) n >= queue->length) |
502 | { |
503 | g_queue_push_tail_link (queue, link: link_); |
504 | return; |
505 | } |
506 | |
507 | g_assert (queue->head); |
508 | g_assert (queue->tail); |
509 | |
510 | next = g_queue_peek_nth_link (queue, n); |
511 | prev = next->prev; |
512 | |
513 | if (prev) |
514 | prev->next = link_; |
515 | next->prev = link_; |
516 | |
517 | link_->next = next; |
518 | link_->prev = prev; |
519 | |
520 | if (queue->head->prev) |
521 | queue->head = queue->head->prev; |
522 | |
523 | /* The case where we’re pushing @link_ at the end of @queue is handled above |
524 | * using g_queue_push_tail_link(), so we should never have to manually adjust |
525 | * queue->tail. */ |
526 | g_assert (queue->tail->next == NULL); |
527 | |
528 | queue->length++; |
529 | } |
530 | |
531 | /** |
532 | * g_queue_pop_head: |
533 | * @queue: a #GQueue |
534 | * |
535 | * Removes the first element of the queue and returns its data. |
536 | * |
537 | * Returns: the data of the first element in the queue, or %NULL |
538 | * if the queue is empty |
539 | */ |
540 | gpointer |
541 | g_queue_pop_head (GQueue *queue) |
542 | { |
543 | g_return_val_if_fail (queue != NULL, NULL); |
544 | |
545 | if (queue->head) |
546 | { |
547 | GList *node = queue->head; |
548 | gpointer data = node->data; |
549 | |
550 | queue->head = node->next; |
551 | if (queue->head) |
552 | queue->head->prev = NULL; |
553 | else |
554 | queue->tail = NULL; |
555 | g_list_free_1 (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 | */ |
573 | GList * |
574 | g_queue_pop_head_link (GQueue *queue) |
575 | { |
576 | g_return_val_if_fail (queue != NULL, NULL); |
577 | |
578 | if (queue->head) |
579 | { |
580 | GList *node = queue->head; |
581 | |
582 | queue->head = node->next; |
583 | if (queue->head) |
584 | { |
585 | queue->head->prev = NULL; |
586 | node->next = NULL; |
587 | } |
588 | else |
589 | queue->tail = NULL; |
590 | queue->length--; |
591 | |
592 | return node; |
593 | } |
594 | |
595 | return NULL; |
596 | } |
597 | |
598 | /** |
599 | * g_queue_peek_head_link: |
600 | * @queue: a #GQueue |
601 | * |
602 | * Returns the first link in @queue. |
603 | * |
604 | * Returns: the first link in @queue, or %NULL if @queue is empty |
605 | * |
606 | * Since: 2.4 |
607 | */ |
608 | GList * |
609 | g_queue_peek_head_link (GQueue *queue) |
610 | { |
611 | g_return_val_if_fail (queue != NULL, NULL); |
612 | |
613 | return queue->head; |
614 | } |
615 | |
616 | /** |
617 | * g_queue_peek_tail_link: |
618 | * @queue: a #GQueue |
619 | * |
620 | * Returns the last link in @queue. |
621 | * |
622 | * Returns: the last link in @queue, or %NULL if @queue is empty |
623 | * |
624 | * Since: 2.4 |
625 | */ |
626 | GList * |
627 | g_queue_peek_tail_link (GQueue *queue) |
628 | { |
629 | g_return_val_if_fail (queue != NULL, NULL); |
630 | |
631 | return queue->tail; |
632 | } |
633 | |
634 | /** |
635 | * g_queue_pop_tail: |
636 | * @queue: a #GQueue |
637 | * |
638 | * Removes the last element of the queue and returns its data. |
639 | * |
640 | * Returns: the data of the last element in the queue, or %NULL |
641 | * if the queue is empty |
642 | */ |
643 | gpointer |
644 | g_queue_pop_tail (GQueue *queue) |
645 | { |
646 | g_return_val_if_fail (queue != NULL, NULL); |
647 | |
648 | if (queue->tail) |
649 | { |
650 | GList *node = queue->tail; |
651 | gpointer data = node->data; |
652 | |
653 | queue->tail = node->prev; |
654 | if (queue->tail) |
655 | queue->tail->next = NULL; |
656 | else |
657 | queue->head = NULL; |
658 | queue->length--; |
659 | g_list_free_1 (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 | */ |
678 | gpointer |
679 | g_queue_pop_nth (GQueue *queue, |
680 | guint n) |
681 | { |
682 | GList *nth_link; |
683 | gpointer result; |
684 | |
685 | g_return_val_if_fail (queue != NULL, NULL); |
686 | |
687 | if (n >= queue->length) |
688 | return NULL; |
689 | |
690 | nth_link = g_queue_peek_nth_link (queue, n); |
691 | result = nth_link->data; |
692 | |
693 | g_queue_delete_link (queue, 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 | */ |
707 | GList * |
708 | g_queue_pop_tail_link (GQueue *queue) |
709 | { |
710 | g_return_val_if_fail (queue != NULL, NULL); |
711 | |
712 | if (queue->tail) |
713 | { |
714 | GList *node = queue->tail; |
715 | |
716 | queue->tail = node->prev; |
717 | if (queue->tail) |
718 | { |
719 | queue->tail->next = NULL; |
720 | node->prev = NULL; |
721 | } |
722 | else |
723 | queue->head = NULL; |
724 | queue->length--; |
725 | |
726 | return node; |
727 | } |
728 | |
729 | return NULL; |
730 | } |
731 | |
732 | /** |
733 | * g_queue_pop_nth_link: |
734 | * @queue: a #GQueue |
735 | * @n: the link's position |
736 | * |
737 | * Removes and returns the link at the given position. |
738 | * |
739 | * Returns: the @n'th link, or %NULL if @n is off the end of @queue |
740 | * |
741 | * Since: 2.4 |
742 | */ |
743 | GList* |
744 | g_queue_pop_nth_link (GQueue *queue, |
745 | guint n) |
746 | { |
747 | GList *link; |
748 | |
749 | g_return_val_if_fail (queue != NULL, NULL); |
750 | |
751 | if (n >= queue->length) |
752 | return NULL; |
753 | |
754 | link = g_queue_peek_nth_link (queue, n); |
755 | g_queue_unlink (queue, link_: link); |
756 | |
757 | return link; |
758 | } |
759 | |
760 | /** |
761 | * g_queue_peek_nth_link: |
762 | * @queue: a #GQueue |
763 | * @n: the position of the link |
764 | * |
765 | * Returns the link at the given position |
766 | * |
767 | * Returns: the link at the @n'th position, or %NULL |
768 | * if @n is off the end of the list |
769 | * |
770 | * Since: 2.4 |
771 | */ |
772 | GList * |
773 | g_queue_peek_nth_link (GQueue *queue, |
774 | guint n) |
775 | { |
776 | GList *link; |
777 | guint i; |
778 | |
779 | g_return_val_if_fail (queue != NULL, NULL); |
780 | |
781 | if (n >= queue->length) |
782 | return NULL; |
783 | |
784 | if (n > queue->length / 2) |
785 | { |
786 | n = queue->length - n - 1; |
787 | |
788 | link = queue->tail; |
789 | for (i = 0; i < n; ++i) |
790 | link = link->prev; |
791 | } |
792 | else |
793 | { |
794 | link = queue->head; |
795 | for (i = 0; i < n; ++i) |
796 | link = link->next; |
797 | } |
798 | |
799 | return link; |
800 | } |
801 | |
802 | /** |
803 | * g_queue_link_index: |
804 | * @queue: a #GQueue |
805 | * @link_: a #GList link |
806 | * |
807 | * Returns the position of @link_ in @queue. |
808 | * |
809 | * Returns: the position of @link_, or -1 if the link is |
810 | * not part of @queue |
811 | * |
812 | * Since: 2.4 |
813 | */ |
814 | gint |
815 | g_queue_link_index (GQueue *queue, |
816 | GList *link_) |
817 | { |
818 | g_return_val_if_fail (queue != NULL, -1); |
819 | |
820 | return g_list_position (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 | */ |
835 | void |
836 | g_queue_unlink (GQueue *queue, |
837 | GList *link_) |
838 | { |
839 | g_return_if_fail (queue != NULL); |
840 | g_return_if_fail (link_ != NULL); |
841 | |
842 | if (link_ == queue->tail) |
843 | queue->tail = queue->tail->prev; |
844 | |
845 | queue->head = g_list_remove_link (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 | */ |
860 | void |
861 | g_queue_delete_link (GQueue *queue, |
862 | GList *link_) |
863 | { |
864 | g_return_if_fail (queue != NULL); |
865 | g_return_if_fail (link_ != NULL); |
866 | |
867 | g_queue_unlink (queue, link_); |
868 | g_list_free (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 | */ |
880 | gpointer |
881 | g_queue_peek_head (GQueue *queue) |
882 | { |
883 | g_return_val_if_fail (queue != NULL, NULL); |
884 | |
885 | return queue->head ? queue->head->data : NULL; |
886 | } |
887 | |
888 | /** |
889 | * g_queue_peek_tail: |
890 | * @queue: a #GQueue |
891 | * |
892 | * Returns the last element of the queue. |
893 | * |
894 | * Returns: the data of the last element in the queue, or %NULL |
895 | * if the queue is empty |
896 | */ |
897 | gpointer |
898 | g_queue_peek_tail (GQueue *queue) |
899 | { |
900 | g_return_val_if_fail (queue != NULL, NULL); |
901 | |
902 | return queue->tail ? queue->tail->data : NULL; |
903 | } |
904 | |
905 | /** |
906 | * g_queue_peek_nth: |
907 | * @queue: a #GQueue |
908 | * @n: the position of the element |
909 | * |
910 | * Returns the @n'th element of @queue. |
911 | * |
912 | * Returns: the data for the @n'th element of @queue, |
913 | * or %NULL if @n is off the end of @queue |
914 | * |
915 | * Since: 2.4 |
916 | */ |
917 | gpointer |
918 | g_queue_peek_nth (GQueue *queue, |
919 | guint n) |
920 | { |
921 | GList *link; |
922 | |
923 | g_return_val_if_fail (queue != NULL, NULL); |
924 | |
925 | link = g_queue_peek_nth_link (queue, n); |
926 | |
927 | if (link) |
928 | return link->data; |
929 | |
930 | return NULL; |
931 | } |
932 | |
933 | /** |
934 | * g_queue_index: |
935 | * @queue: a #GQueue |
936 | * @data: the data to find |
937 | * |
938 | * Returns the position of the first element in @queue which contains @data. |
939 | * |
940 | * Returns: the position of the first element in @queue which |
941 | * contains @data, or -1 if no element in @queue contains @data |
942 | * |
943 | * Since: 2.4 |
944 | */ |
945 | gint |
946 | g_queue_index (GQueue *queue, |
947 | gconstpointer data) |
948 | { |
949 | g_return_val_if_fail (queue != NULL, -1); |
950 | |
951 | return g_list_index (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 | */ |
965 | gboolean |
966 | g_queue_remove (GQueue *queue, |
967 | gconstpointer data) |
968 | { |
969 | GList *link; |
970 | |
971 | g_return_val_if_fail (queue != NULL, FALSE); |
972 | |
973 | link = g_list_find (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 | */ |
992 | guint |
993 | g_queue_remove_all (GQueue *queue, |
994 | gconstpointer data) |
995 | { |
996 | GList *list; |
997 | guint old_length; |
998 | |
999 | g_return_val_if_fail (queue != NULL, 0); |
1000 | |
1001 | old_length = queue->length; |
1002 | |
1003 | list = queue->head; |
1004 | while (list) |
1005 | { |
1006 | GList *next = list->next; |
1007 | |
1008 | if (list->data == data) |
1009 | g_queue_delete_link (queue, 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 | */ |
1031 | void |
1032 | g_queue_insert_before (GQueue *queue, |
1033 | GList *sibling, |
1034 | gpointer data) |
1035 | { |
1036 | g_return_if_fail (queue != NULL); |
1037 | |
1038 | if (sibling == NULL) |
1039 | { |
1040 | /* We don't use g_list_insert_before() with a NULL sibling because it |
1041 | * would be a O(n) operation and we would need to update manually the tail |
1042 | * pointer. |
1043 | */ |
1044 | g_queue_push_tail (queue, data); |
1045 | } |
1046 | else |
1047 | { |
1048 | queue->head = g_list_insert_before (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 | */ |
1066 | void |
1067 | g_queue_insert_before_link (GQueue *queue, |
1068 | GList *sibling, |
1069 | GList *link_) |
1070 | { |
1071 | g_return_if_fail (queue != NULL); |
1072 | g_return_if_fail (link_ != NULL); |
1073 | g_return_if_fail (link_->prev == NULL); |
1074 | g_return_if_fail (link_->next == NULL); |
1075 | |
1076 | if G_UNLIKELY (sibling == NULL) |
1077 | { |
1078 | /* We don't use g_list_insert_before_link() with a NULL sibling because it |
1079 | * would be a O(n) operation and we would need to update manually the tail |
1080 | * pointer. |
1081 | */ |
1082 | g_queue_push_tail_link (queue, link: 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 | */ |
1105 | void |
1106 | g_queue_insert_after (GQueue *queue, |
1107 | GList *sibling, |
1108 | gpointer data) |
1109 | { |
1110 | g_return_if_fail (queue != NULL); |
1111 | |
1112 | if (sibling == NULL) |
1113 | g_queue_push_head (queue, data); |
1114 | else |
1115 | g_queue_insert_before (queue, sibling: sibling->next, data); |
1116 | } |
1117 | |
1118 | /** |
1119 | * g_queue_insert_after_link: |
1120 | * @queue: a #GQueue |
1121 | * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to |
1122 | * push at the head of the queue. |
1123 | * @link_: a #GList link to insert which must not be part of any other list. |
1124 | * |
1125 | * Inserts @link_ into @queue after @sibling. |
1126 | * |
1127 | * @sibling must be part of @queue. |
1128 | * |
1129 | * Since: 2.62 |
1130 | */ |
1131 | void |
1132 | g_queue_insert_after_link (GQueue *queue, |
1133 | GList *sibling, |
1134 | GList *link_) |
1135 | { |
1136 | g_return_if_fail (queue != NULL); |
1137 | g_return_if_fail (link_ != NULL); |
1138 | g_return_if_fail (link_->prev == NULL); |
1139 | g_return_if_fail (link_->next == NULL); |
1140 | |
1141 | if G_UNLIKELY (sibling == NULL) |
1142 | g_queue_push_head_link (queue, link: 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 | */ |
1162 | void |
1163 | g_queue_insert_sorted (GQueue *queue, |
1164 | gpointer data, |
1165 | GCompareDataFunc func, |
1166 | gpointer user_data) |
1167 | { |
1168 | GList *list; |
1169 | |
1170 | g_return_if_fail (queue != NULL); |
1171 | |
1172 | list = queue->head; |
1173 | while (list && func (list->data, data, user_data) < 0) |
1174 | list = list->next; |
1175 | |
1176 | g_queue_insert_before (queue, sibling: list, data); |
1177 | } |
1178 | |