1 | /* GLIB - Library of useful routines for C programming |
2 | * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
3 | * |
4 | * This library is free software; you can redistribute it and/or |
5 | * modify it under the terms of the GNU Lesser General Public |
6 | * License as published by the Free Software Foundation; either |
7 | * version 2.1 of the License, or (at your option) any later version. |
8 | * |
9 | * This library is distributed in the hope that it will be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. |
13 | * |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
16 | */ |
17 | |
18 | /* |
19 | * Modified by the GLib Team and others 1997-2000. See the AUTHORS |
20 | * file for a list of people on the GLib Team. See the ChangeLog |
21 | * files for a list of changes. These files are distributed with |
22 | * GLib at ftp://ftp.gtk.org/pub/gtk/. |
23 | */ |
24 | |
25 | /* |
26 | * MT safe |
27 | */ |
28 | |
29 | #include "config.h" |
30 | |
31 | #include "glist.h" |
32 | #include "gslice.h" |
33 | #include "gmessages.h" |
34 | |
35 | #include "gtestutils.h" |
36 | |
37 | /** |
38 | * SECTION:linked_lists_double |
39 | * @title: Doubly-Linked Lists |
40 | * @short_description: linked lists that can be iterated over in both directions |
41 | * |
42 | * The #GList structure and its associated functions provide a standard |
43 | * doubly-linked list data structure. The benefit of this data-structure |
44 | * is to provide insertion/deletion operations in O(1) complexity where |
45 | * access/search operations are in O(n). The benefit of #GList over |
46 | * #GSList (singly linked list) is that the worst case on access/search |
47 | * operations is divided by two which comes at a cost in space as we need |
48 | * to retain two pointers in place of one. |
49 | * |
50 | * Each element in the list contains a piece of data, together with |
51 | * pointers which link to the previous and next elements in the list. |
52 | * Using these pointers it is possible to move through the list in both |
53 | * directions (unlike the singly-linked [GSList][glib-Singly-Linked-Lists], |
54 | * which only allows movement through the list in the forward direction). |
55 | * |
56 | * The double linked list does not keep track of the number of items |
57 | * and does not keep track of both the start and end of the list. If |
58 | * you want fast access to both the start and the end of the list, |
59 | * and/or the number of items in the list, use a |
60 | * [GQueue][glib-Double-ended-Queues] instead. |
61 | * |
62 | * The data contained in each element can be either integer values, by |
63 | * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros], |
64 | * or simply pointers to any type of data. |
65 | * |
66 | * List elements are allocated from the [slice allocator][glib-Memory-Slices], |
67 | * which is more efficient than allocating elements individually. |
68 | * |
69 | * Note that most of the #GList functions expect to be passed a pointer |
70 | * to the first element in the list. The functions which insert |
71 | * elements return the new start of the list, which may have changed. |
72 | * |
73 | * There is no function to create a #GList. %NULL is considered to be |
74 | * a valid, empty list so you simply set a #GList* to %NULL to initialize |
75 | * it. |
76 | * |
77 | * To add elements, use g_list_append(), g_list_prepend(), |
78 | * g_list_insert() and g_list_insert_sorted(). |
79 | * |
80 | * To visit all elements in the list, use a loop over the list: |
81 | * |[<!-- language="C" --> |
82 | * GList *l; |
83 | * for (l = list; l != NULL; l = l->next) |
84 | * { |
85 | * // do something with l->data |
86 | * } |
87 | * ]| |
88 | * |
89 | * To call a function for each element in the list, use g_list_foreach(). |
90 | * |
91 | * To loop over the list and modify it (e.g. remove a certain element) |
92 | * a while loop is more appropriate, for example: |
93 | * |[<!-- language="C" --> |
94 | * GList *l = list; |
95 | * while (l != NULL) |
96 | * { |
97 | * GList *next = l->next; |
98 | * if (should_be_removed (l)) |
99 | * { |
100 | * // possibly free l->data |
101 | * list = g_list_delete_link (list, l); |
102 | * } |
103 | * l = next; |
104 | * } |
105 | * ]| |
106 | * |
107 | * To remove elements, use g_list_remove(). |
108 | * |
109 | * To navigate in a list, use g_list_first(), g_list_last(), |
110 | * g_list_next(), g_list_previous(). |
111 | * |
112 | * To find elements in the list use g_list_nth(), g_list_nth_data(), |
113 | * g_list_find() and g_list_find_custom(). |
114 | * |
115 | * To find the index of an element use g_list_position() and |
116 | * g_list_index(). |
117 | * |
118 | * To free the entire list, use g_list_free() or g_list_free_full(). |
119 | */ |
120 | |
121 | /** |
122 | * GList: |
123 | * @data: holds the element's data, which can be a pointer to any kind |
124 | * of data, or any integer value using the |
125 | * [Type Conversion Macros][glib-Type-Conversion-Macros] |
126 | * @next: contains the link to the next element in the list |
127 | * @prev: contains the link to the previous element in the list |
128 | * |
129 | * The #GList struct is used for each element in a doubly-linked list. |
130 | **/ |
131 | |
132 | /** |
133 | * g_list_previous: |
134 | * @list: an element in a #GList |
135 | * |
136 | * A convenience macro to get the previous element in a #GList. |
137 | * Note that it is considered perfectly acceptable to access |
138 | * @list->prev directly. |
139 | * |
140 | * Returns: the previous element, or %NULL if there are no previous |
141 | * elements |
142 | **/ |
143 | |
144 | /** |
145 | * g_list_next: |
146 | * @list: an element in a #GList |
147 | * |
148 | * A convenience macro to get the next element in a #GList. |
149 | * Note that it is considered perfectly acceptable to access |
150 | * @list->next directly. |
151 | * |
152 | * Returns: the next element, or %NULL if there are no more elements |
153 | **/ |
154 | |
155 | #define _g_list_alloc() g_slice_new (GList) |
156 | #define _g_list_alloc0() g_slice_new0 (GList) |
157 | #define _g_list_free1(list) g_slice_free (GList, list) |
158 | |
159 | /** |
160 | * g_list_alloc: |
161 | * |
162 | * Allocates space for one #GList element. It is called by |
163 | * g_list_append(), g_list_prepend(), g_list_insert() and |
164 | * g_list_insert_sorted() and so is rarely used on its own. |
165 | * |
166 | * Returns: a pointer to the newly-allocated #GList element |
167 | **/ |
168 | GList * |
169 | g_list_alloc (void) |
170 | { |
171 | return _g_list_alloc0 (); |
172 | } |
173 | |
174 | /** |
175 | * g_list_free: |
176 | * @list: the first link of a #GList |
177 | * |
178 | * Frees all of the memory used by a #GList. |
179 | * The freed elements are returned to the slice allocator. |
180 | * |
181 | * If list elements contain dynamically-allocated memory, you should |
182 | * either use g_list_free_full() or free them manually first. |
183 | * |
184 | * It can be combined with g_steal_pointer() to ensure the list head pointer |
185 | * is not left dangling: |
186 | * |[<!-- language="C" --> |
187 | * GList *list_of_borrowed_things = …; /<!-- -->* (transfer container) *<!-- -->/ |
188 | * g_list_free (g_steal_pointer (&list_of_borrowed_things)); |
189 | * ]| |
190 | */ |
191 | void |
192 | g_list_free (GList *list) |
193 | { |
194 | g_slice_free_chain (GList, list, next); |
195 | } |
196 | |
197 | /** |
198 | * g_list_free_1: |
199 | * @list: a #GList element |
200 | * |
201 | * Frees one #GList element, but does not update links from the next and |
202 | * previous elements in the list, so you should not call this function on an |
203 | * element that is currently part of a list. |
204 | * |
205 | * It is usually used after g_list_remove_link(). |
206 | */ |
207 | /** |
208 | * g_list_free1: |
209 | * |
210 | * Another name for g_list_free_1(). |
211 | **/ |
212 | void |
213 | g_list_free_1 (GList *list) |
214 | { |
215 | _g_list_free1 (list); |
216 | } |
217 | |
218 | /** |
219 | * g_list_free_full: |
220 | * @list: the first link of a #GList |
221 | * @free_func: the function to be called to free each element's data |
222 | * |
223 | * Convenience method, which frees all the memory used by a #GList, |
224 | * and calls @free_func on every element's data. |
225 | * |
226 | * @free_func must not modify the list (eg, by removing the freed |
227 | * element from it). |
228 | * |
229 | * It can be combined with g_steal_pointer() to ensure the list head pointer |
230 | * is not left dangling — this also has the nice property that the head pointer |
231 | * is cleared before any of the list elements are freed, to prevent double frees |
232 | * from @free_func: |
233 | * |[<!-- language="C" --> |
234 | * GList *list_of_owned_things = …; /<!-- -->* (transfer full) (element-type GObject) *<!-- -->/ |
235 | * g_list_free_full (g_steal_pointer (&list_of_owned_things), g_object_unref); |
236 | * ]| |
237 | * |
238 | * Since: 2.28 |
239 | */ |
240 | void |
241 | g_list_free_full (GList *list, |
242 | GDestroyNotify free_func) |
243 | { |
244 | g_list_foreach (list, func: (GFunc) free_func, NULL); |
245 | g_list_free (list); |
246 | } |
247 | |
248 | /** |
249 | * g_list_append: |
250 | * @list: a pointer to a #GList |
251 | * @data: the data for the new element |
252 | * |
253 | * Adds a new element on to the end of the list. |
254 | * |
255 | * Note that the return value is the new start of the list, |
256 | * if @list was empty; make sure you store the new value. |
257 | * |
258 | * g_list_append() has to traverse the entire list to find the end, |
259 | * which is inefficient when adding multiple elements. A common idiom |
260 | * to avoid the inefficiency is to use g_list_prepend() and reverse |
261 | * the list with g_list_reverse() when all elements have been added. |
262 | * |
263 | * |[<!-- language="C" --> |
264 | * // Notice that these are initialized to the empty list. |
265 | * GList *string_list = NULL, *number_list = NULL; |
266 | * |
267 | * // This is a list of strings. |
268 | * string_list = g_list_append (string_list, "first"); |
269 | * string_list = g_list_append (string_list, "second"); |
270 | * |
271 | * // This is a list of integers. |
272 | * number_list = g_list_append (number_list, GINT_TO_POINTER (27)); |
273 | * number_list = g_list_append (number_list, GINT_TO_POINTER (14)); |
274 | * ]| |
275 | * |
276 | * Returns: either @list or the new start of the #GList if @list was %NULL |
277 | */ |
278 | GList * |
279 | g_list_append (GList *list, |
280 | gpointer data) |
281 | { |
282 | GList *new_list; |
283 | GList *last; |
284 | |
285 | new_list = _g_list_alloc (); |
286 | new_list->data = data; |
287 | new_list->next = NULL; |
288 | |
289 | if (list) |
290 | { |
291 | last = g_list_last (list); |
292 | /* g_assert (last != NULL); */ |
293 | last->next = new_list; |
294 | new_list->prev = last; |
295 | |
296 | return list; |
297 | } |
298 | else |
299 | { |
300 | new_list->prev = NULL; |
301 | return new_list; |
302 | } |
303 | } |
304 | |
305 | /** |
306 | * g_list_prepend: |
307 | * @list: a pointer to a #GList, this must point to the top of the list |
308 | * @data: the data for the new element |
309 | * |
310 | * Prepends a new element on to the start of the list. |
311 | * |
312 | * Note that the return value is the new start of the list, |
313 | * which will have changed, so make sure you store the new value. |
314 | * |
315 | * |[<!-- language="C" --> |
316 | * // Notice that it is initialized to the empty list. |
317 | * GList *list = NULL; |
318 | * |
319 | * list = g_list_prepend (list, "last"); |
320 | * list = g_list_prepend (list, "first"); |
321 | * ]| |
322 | * |
323 | * Do not use this function to prepend a new element to a different |
324 | * element than the start of the list. Use g_list_insert_before() instead. |
325 | * |
326 | * Returns: a pointer to the newly prepended element, which is the new |
327 | * start of the #GList |
328 | */ |
329 | GList * |
330 | g_list_prepend (GList *list, |
331 | gpointer data) |
332 | { |
333 | GList *new_list; |
334 | |
335 | new_list = _g_list_alloc (); |
336 | new_list->data = data; |
337 | new_list->next = list; |
338 | |
339 | if (list) |
340 | { |
341 | new_list->prev = list->prev; |
342 | if (list->prev) |
343 | list->prev->next = new_list; |
344 | list->prev = new_list; |
345 | } |
346 | else |
347 | new_list->prev = NULL; |
348 | |
349 | return new_list; |
350 | } |
351 | |
352 | /** |
353 | * g_list_insert: |
354 | * @list: a pointer to a #GList, this must point to the top of the list |
355 | * @data: the data for the new element |
356 | * @position: the position to insert the element. If this is |
357 | * negative, or is larger than the number of elements in the |
358 | * list, the new element is added on to the end of the list. |
359 | * |
360 | * Inserts a new element into the list at the given position. |
361 | * |
362 | * Returns: the (possibly changed) start of the #GList |
363 | */ |
364 | GList * |
365 | g_list_insert (GList *list, |
366 | gpointer data, |
367 | gint position) |
368 | { |
369 | GList *new_list; |
370 | GList *tmp_list; |
371 | |
372 | if (position < 0) |
373 | return g_list_append (list, data); |
374 | else if (position == 0) |
375 | return g_list_prepend (list, data); |
376 | |
377 | tmp_list = g_list_nth (list, n: position); |
378 | if (!tmp_list) |
379 | return g_list_append (list, data); |
380 | |
381 | new_list = _g_list_alloc (); |
382 | new_list->data = data; |
383 | new_list->prev = tmp_list->prev; |
384 | tmp_list->prev->next = new_list; |
385 | new_list->next = tmp_list; |
386 | tmp_list->prev = new_list; |
387 | |
388 | return list; |
389 | } |
390 | |
391 | /** |
392 | * g_list_insert_before_link: |
393 | * @list: a pointer to a #GList, this must point to the top of the list |
394 | * @sibling: (nullable): the list element before which the new element |
395 | * is inserted or %NULL to insert at the end of the list |
396 | * @link_: the list element to be added, which must not be part of |
397 | * any other list |
398 | * |
399 | * Inserts @link_ into the list before the given position. |
400 | * |
401 | * Returns: the (possibly changed) start of the #GList |
402 | * |
403 | * Since: 2.62 |
404 | */ |
405 | GList * |
406 | g_list_insert_before_link (GList *list, |
407 | GList *sibling, |
408 | GList *link_) |
409 | { |
410 | g_return_val_if_fail (link_ != NULL, list); |
411 | g_return_val_if_fail (link_->prev == NULL, list); |
412 | g_return_val_if_fail (link_->next == NULL, list); |
413 | |
414 | if (list == NULL) |
415 | { |
416 | g_return_val_if_fail (sibling == NULL, list); |
417 | return link_; |
418 | } |
419 | else if (sibling != NULL) |
420 | { |
421 | link_->prev = sibling->prev; |
422 | link_->next = sibling; |
423 | sibling->prev = link_; |
424 | if (link_->prev != NULL) |
425 | { |
426 | link_->prev->next = link_; |
427 | return list; |
428 | } |
429 | else |
430 | { |
431 | g_return_val_if_fail (sibling == list, link_); |
432 | return link_; |
433 | } |
434 | } |
435 | else |
436 | { |
437 | GList *last; |
438 | |
439 | for (last = list; last->next != NULL; last = last->next) {} |
440 | |
441 | last->next = link_; |
442 | last->next->prev = last; |
443 | last->next->next = NULL; |
444 | |
445 | return list; |
446 | } |
447 | } |
448 | |
449 | /** |
450 | * g_list_insert_before: |
451 | * @list: a pointer to a #GList, this must point to the top of the list |
452 | * @sibling: the list element before which the new element |
453 | * is inserted or %NULL to insert at the end of the list |
454 | * @data: the data for the new element |
455 | * |
456 | * Inserts a new element into the list before the given position. |
457 | * |
458 | * Returns: the (possibly changed) start of the #GList |
459 | */ |
460 | GList * |
461 | g_list_insert_before (GList *list, |
462 | GList *sibling, |
463 | gpointer data) |
464 | { |
465 | if (list == NULL) |
466 | { |
467 | list = g_list_alloc (); |
468 | list->data = data; |
469 | g_return_val_if_fail (sibling == NULL, list); |
470 | return list; |
471 | } |
472 | else if (sibling != NULL) |
473 | { |
474 | GList *node; |
475 | |
476 | node = _g_list_alloc (); |
477 | node->data = data; |
478 | node->prev = sibling->prev; |
479 | node->next = sibling; |
480 | sibling->prev = node; |
481 | if (node->prev != NULL) |
482 | { |
483 | node->prev->next = node; |
484 | return list; |
485 | } |
486 | else |
487 | { |
488 | g_return_val_if_fail (sibling == list, node); |
489 | return node; |
490 | } |
491 | } |
492 | else |
493 | { |
494 | GList *last; |
495 | |
496 | for (last = list; last->next != NULL; last = last->next) {} |
497 | |
498 | last->next = _g_list_alloc (); |
499 | last->next->data = data; |
500 | last->next->prev = last; |
501 | last->next->next = NULL; |
502 | |
503 | return list; |
504 | } |
505 | } |
506 | |
507 | /** |
508 | * g_list_concat: |
509 | * @list1: a #GList, this must point to the top of the list |
510 | * @list2: the #GList to add to the end of the first #GList, |
511 | * this must point to the top of the list |
512 | * |
513 | * Adds the second #GList onto the end of the first #GList. |
514 | * Note that the elements of the second #GList are not copied. |
515 | * They are used directly. |
516 | * |
517 | * This function is for example used to move an element in the list. |
518 | * The following example moves an element to the top of the list: |
519 | * |[<!-- language="C" --> |
520 | * list = g_list_remove_link (list, llink); |
521 | * list = g_list_concat (llink, list); |
522 | * ]| |
523 | * |
524 | * Returns: the start of the new #GList, which equals @list1 if not %NULL |
525 | */ |
526 | GList * |
527 | g_list_concat (GList *list1, |
528 | GList *list2) |
529 | { |
530 | GList *tmp_list; |
531 | |
532 | if (list2) |
533 | { |
534 | tmp_list = g_list_last (list: list1); |
535 | if (tmp_list) |
536 | tmp_list->next = list2; |
537 | else |
538 | list1 = list2; |
539 | list2->prev = tmp_list; |
540 | } |
541 | |
542 | return list1; |
543 | } |
544 | |
545 | static inline GList * |
546 | _g_list_remove_link (GList *list, |
547 | GList *link) |
548 | { |
549 | if (link == NULL) |
550 | return list; |
551 | |
552 | if (link->prev) |
553 | { |
554 | if (link->prev->next == link) |
555 | link->prev->next = link->next; |
556 | else |
557 | g_warning ("corrupted double-linked list detected" ); |
558 | } |
559 | if (link->next) |
560 | { |
561 | if (link->next->prev == link) |
562 | link->next->prev = link->prev; |
563 | else |
564 | g_warning ("corrupted double-linked list detected" ); |
565 | } |
566 | |
567 | if (link == list) |
568 | list = list->next; |
569 | |
570 | link->next = NULL; |
571 | link->prev = NULL; |
572 | |
573 | return list; |
574 | } |
575 | |
576 | /** |
577 | * g_list_remove: |
578 | * @list: a #GList, this must point to the top of the list |
579 | * @data: the data of the element to remove |
580 | * |
581 | * Removes an element from a #GList. |
582 | * If two elements contain the same data, only the first is removed. |
583 | * If none of the elements contain the data, the #GList is unchanged. |
584 | * |
585 | * Returns: the (possibly changed) start of the #GList |
586 | */ |
587 | GList * |
588 | g_list_remove (GList *list, |
589 | gconstpointer data) |
590 | { |
591 | GList *tmp; |
592 | |
593 | tmp = list; |
594 | while (tmp) |
595 | { |
596 | if (tmp->data != data) |
597 | tmp = tmp->next; |
598 | else |
599 | { |
600 | list = _g_list_remove_link (list, link: tmp); |
601 | _g_list_free1 (tmp); |
602 | |
603 | break; |
604 | } |
605 | } |
606 | return list; |
607 | } |
608 | |
609 | /** |
610 | * g_list_remove_all: |
611 | * @list: a #GList, this must point to the top of the list |
612 | * @data: data to remove |
613 | * |
614 | * Removes all list nodes with data equal to @data. |
615 | * Returns the new head of the list. Contrast with |
616 | * g_list_remove() which removes only the first node |
617 | * matching the given data. |
618 | * |
619 | * Returns: the (possibly changed) start of the #GList |
620 | */ |
621 | GList * |
622 | g_list_remove_all (GList *list, |
623 | gconstpointer data) |
624 | { |
625 | GList *tmp = list; |
626 | |
627 | while (tmp) |
628 | { |
629 | if (tmp->data != data) |
630 | tmp = tmp->next; |
631 | else |
632 | { |
633 | GList *next = tmp->next; |
634 | |
635 | if (tmp->prev) |
636 | tmp->prev->next = next; |
637 | else |
638 | list = next; |
639 | if (next) |
640 | next->prev = tmp->prev; |
641 | |
642 | _g_list_free1 (tmp); |
643 | tmp = next; |
644 | } |
645 | } |
646 | return list; |
647 | } |
648 | |
649 | /** |
650 | * g_list_remove_link: |
651 | * @list: a #GList, this must point to the top of the list |
652 | * @llink: an element in the #GList |
653 | * |
654 | * Removes an element from a #GList, without freeing the element. |
655 | * The removed element's prev and next links are set to %NULL, so |
656 | * that it becomes a self-contained list with one element. |
657 | * |
658 | * This function is for example used to move an element in the list |
659 | * (see the example for g_list_concat()) or to remove an element in |
660 | * the list before freeing its data: |
661 | * |[<!-- language="C" --> |
662 | * list = g_list_remove_link (list, llink); |
663 | * free_some_data_that_may_access_the_list_again (llink->data); |
664 | * g_list_free (llink); |
665 | * ]| |
666 | * |
667 | * Returns: the (possibly changed) start of the #GList |
668 | */ |
669 | GList * |
670 | g_list_remove_link (GList *list, |
671 | GList *llink) |
672 | { |
673 | return _g_list_remove_link (list, link: llink); |
674 | } |
675 | |
676 | /** |
677 | * g_list_delete_link: |
678 | * @list: a #GList, this must point to the top of the list |
679 | * @link_: node to delete from @list |
680 | * |
681 | * Removes the node link_ from the list and frees it. |
682 | * Compare this to g_list_remove_link() which removes the node |
683 | * without freeing it. |
684 | * |
685 | * Returns: the (possibly changed) start of the #GList |
686 | */ |
687 | GList * |
688 | g_list_delete_link (GList *list, |
689 | GList *link_) |
690 | { |
691 | list = _g_list_remove_link (list, link: link_); |
692 | _g_list_free1 (link_); |
693 | |
694 | return list; |
695 | } |
696 | |
697 | /** |
698 | * g_list_copy: |
699 | * @list: a #GList, this must point to the top of the list |
700 | * |
701 | * Copies a #GList. |
702 | * |
703 | * Note that this is a "shallow" copy. If the list elements |
704 | * consist of pointers to data, the pointers are copied but |
705 | * the actual data is not. See g_list_copy_deep() if you need |
706 | * to copy the data as well. |
707 | * |
708 | * Returns: the start of the new list that holds the same data as @list |
709 | */ |
710 | GList * |
711 | g_list_copy (GList *list) |
712 | { |
713 | return g_list_copy_deep (list, NULL, NULL); |
714 | } |
715 | |
716 | /** |
717 | * g_list_copy_deep: |
718 | * @list: a #GList, this must point to the top of the list |
719 | * @func: a copy function used to copy every element in the list |
720 | * @user_data: user data passed to the copy function @func, or %NULL |
721 | * |
722 | * Makes a full (deep) copy of a #GList. |
723 | * |
724 | * In contrast with g_list_copy(), this function uses @func to make |
725 | * a copy of each list element, in addition to copying the list |
726 | * container itself. |
727 | * |
728 | * @func, as a #GCopyFunc, takes two arguments, the data to be copied |
729 | * and a @user_data pointer. On common processor architectures, it's safe to |
730 | * pass %NULL as @user_data if the copy function takes only one argument. You |
731 | * may get compiler warnings from this though if compiling with GCC’s |
732 | * `-Wcast-function-type` warning. |
733 | * |
734 | * For instance, if @list holds a list of GObjects, you can do: |
735 | * |[<!-- language="C" --> |
736 | * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL); |
737 | * ]| |
738 | * |
739 | * And, to entirely free the new list, you could do: |
740 | * |[<!-- language="C" --> |
741 | * g_list_free_full (another_list, g_object_unref); |
742 | * ]| |
743 | * |
744 | * Returns: the start of the new list that holds a full copy of @list, |
745 | * use g_list_free_full() to free it |
746 | * |
747 | * Since: 2.34 |
748 | */ |
749 | GList * |
750 | g_list_copy_deep (GList *list, |
751 | GCopyFunc func, |
752 | gpointer user_data) |
753 | { |
754 | GList *new_list = NULL; |
755 | |
756 | if (list) |
757 | { |
758 | GList *last; |
759 | |
760 | new_list = _g_list_alloc (); |
761 | if (func) |
762 | new_list->data = func (list->data, user_data); |
763 | else |
764 | new_list->data = list->data; |
765 | new_list->prev = NULL; |
766 | last = new_list; |
767 | list = list->next; |
768 | while (list) |
769 | { |
770 | last->next = _g_list_alloc (); |
771 | last->next->prev = last; |
772 | last = last->next; |
773 | if (func) |
774 | last->data = func (list->data, user_data); |
775 | else |
776 | last->data = list->data; |
777 | list = list->next; |
778 | } |
779 | last->next = NULL; |
780 | } |
781 | |
782 | return new_list; |
783 | } |
784 | |
785 | /** |
786 | * g_list_reverse: |
787 | * @list: a #GList, this must point to the top of the list |
788 | * |
789 | * Reverses a #GList. |
790 | * It simply switches the next and prev pointers of each element. |
791 | * |
792 | * Returns: the start of the reversed #GList |
793 | */ |
794 | GList * |
795 | g_list_reverse (GList *list) |
796 | { |
797 | GList *last; |
798 | |
799 | last = NULL; |
800 | while (list) |
801 | { |
802 | last = list; |
803 | list = last->next; |
804 | last->next = last->prev; |
805 | last->prev = list; |
806 | } |
807 | |
808 | return last; |
809 | } |
810 | |
811 | /** |
812 | * g_list_nth: |
813 | * @list: a #GList, this must point to the top of the list |
814 | * @n: the position of the element, counting from 0 |
815 | * |
816 | * Gets the element at the given position in a #GList. |
817 | * |
818 | * This iterates over the list until it reaches the @n-th position. If you |
819 | * intend to iterate over every element, it is better to use a for-loop as |
820 | * described in the #GList introduction. |
821 | * |
822 | * Returns: the element, or %NULL if the position is off |
823 | * the end of the #GList |
824 | */ |
825 | GList * |
826 | g_list_nth (GList *list, |
827 | guint n) |
828 | { |
829 | while ((n-- > 0) && list) |
830 | list = list->next; |
831 | |
832 | return list; |
833 | } |
834 | |
835 | /** |
836 | * g_list_nth_prev: |
837 | * @list: a #GList |
838 | * @n: the position of the element, counting from 0 |
839 | * |
840 | * Gets the element @n places before @list. |
841 | * |
842 | * Returns: the element, or %NULL if the position is |
843 | * off the end of the #GList |
844 | */ |
845 | GList * |
846 | g_list_nth_prev (GList *list, |
847 | guint n) |
848 | { |
849 | while ((n-- > 0) && list) |
850 | list = list->prev; |
851 | |
852 | return list; |
853 | } |
854 | |
855 | /** |
856 | * g_list_nth_data: |
857 | * @list: a #GList, this must point to the top of the list |
858 | * @n: the position of the element |
859 | * |
860 | * Gets the data of the element at the given position. |
861 | * |
862 | * This iterates over the list until it reaches the @n-th position. If you |
863 | * intend to iterate over every element, it is better to use a for-loop as |
864 | * described in the #GList introduction. |
865 | * |
866 | * Returns: the element's data, or %NULL if the position |
867 | * is off the end of the #GList |
868 | */ |
869 | gpointer |
870 | g_list_nth_data (GList *list, |
871 | guint n) |
872 | { |
873 | while ((n-- > 0) && list) |
874 | list = list->next; |
875 | |
876 | return list ? list->data : NULL; |
877 | } |
878 | |
879 | /** |
880 | * g_list_find: |
881 | * @list: a #GList, this must point to the top of the list |
882 | * @data: the element data to find |
883 | * |
884 | * Finds the element in a #GList which contains the given data. |
885 | * |
886 | * Returns: the found #GList element, or %NULL if it is not found |
887 | */ |
888 | GList * |
889 | g_list_find (GList *list, |
890 | gconstpointer data) |
891 | { |
892 | while (list) |
893 | { |
894 | if (list->data == data) |
895 | break; |
896 | list = list->next; |
897 | } |
898 | |
899 | return list; |
900 | } |
901 | |
902 | /** |
903 | * g_list_find_custom: |
904 | * @list: a #GList, this must point to the top of the list |
905 | * @data: user data passed to the function |
906 | * @func: the function to call for each element. |
907 | * It should return 0 when the desired element is found |
908 | * |
909 | * Finds an element in a #GList, using a supplied function to |
910 | * find the desired element. It iterates over the list, calling |
911 | * the given function which should return 0 when the desired |
912 | * element is found. The function takes two #gconstpointer arguments, |
913 | * the #GList element's data as the first argument and the |
914 | * given user data. |
915 | * |
916 | * Returns: the found #GList element, or %NULL if it is not found |
917 | */ |
918 | GList * |
919 | g_list_find_custom (GList *list, |
920 | gconstpointer data, |
921 | GCompareFunc func) |
922 | { |
923 | g_return_val_if_fail (func != NULL, list); |
924 | |
925 | while (list) |
926 | { |
927 | if (! func (list->data, data)) |
928 | return list; |
929 | list = list->next; |
930 | } |
931 | |
932 | return NULL; |
933 | } |
934 | |
935 | /** |
936 | * g_list_position: |
937 | * @list: a #GList, this must point to the top of the list |
938 | * @llink: an element in the #GList |
939 | * |
940 | * Gets the position of the given element |
941 | * in the #GList (starting from 0). |
942 | * |
943 | * Returns: the position of the element in the #GList, |
944 | * or -1 if the element is not found |
945 | */ |
946 | gint |
947 | g_list_position (GList *list, |
948 | GList *llink) |
949 | { |
950 | gint i; |
951 | |
952 | i = 0; |
953 | while (list) |
954 | { |
955 | if (list == llink) |
956 | return i; |
957 | i++; |
958 | list = list->next; |
959 | } |
960 | |
961 | return -1; |
962 | } |
963 | |
964 | /** |
965 | * g_list_index: |
966 | * @list: a #GList, this must point to the top of the list |
967 | * @data: the data to find |
968 | * |
969 | * Gets the position of the element containing |
970 | * the given data (starting from 0). |
971 | * |
972 | * Returns: the index of the element containing the data, |
973 | * or -1 if the data is not found |
974 | */ |
975 | gint |
976 | g_list_index (GList *list, |
977 | gconstpointer data) |
978 | { |
979 | gint i; |
980 | |
981 | i = 0; |
982 | while (list) |
983 | { |
984 | if (list->data == data) |
985 | return i; |
986 | i++; |
987 | list = list->next; |
988 | } |
989 | |
990 | return -1; |
991 | } |
992 | |
993 | /** |
994 | * g_list_last: |
995 | * @list: any #GList element |
996 | * |
997 | * Gets the last element in a #GList. |
998 | * |
999 | * Returns: the last element in the #GList, |
1000 | * or %NULL if the #GList has no elements |
1001 | */ |
1002 | GList * |
1003 | g_list_last (GList *list) |
1004 | { |
1005 | if (list) |
1006 | { |
1007 | while (list->next) |
1008 | list = list->next; |
1009 | } |
1010 | |
1011 | return list; |
1012 | } |
1013 | |
1014 | /** |
1015 | * g_list_first: |
1016 | * @list: any #GList element |
1017 | * |
1018 | * Gets the first element in a #GList. |
1019 | * |
1020 | * Returns: the first element in the #GList, |
1021 | * or %NULL if the #GList has no elements |
1022 | */ |
1023 | GList * |
1024 | g_list_first (GList *list) |
1025 | { |
1026 | if (list) |
1027 | { |
1028 | while (list->prev) |
1029 | list = list->prev; |
1030 | } |
1031 | |
1032 | return list; |
1033 | } |
1034 | |
1035 | /** |
1036 | * g_list_length: |
1037 | * @list: a #GList, this must point to the top of the list |
1038 | * |
1039 | * Gets the number of elements in a #GList. |
1040 | * |
1041 | * This function iterates over the whole list to count its elements. |
1042 | * Use a #GQueue instead of a GList if you regularly need the number |
1043 | * of items. To check whether the list is non-empty, it is faster to check |
1044 | * @list against %NULL. |
1045 | * |
1046 | * Returns: the number of elements in the #GList |
1047 | */ |
1048 | guint |
1049 | g_list_length (GList *list) |
1050 | { |
1051 | guint length; |
1052 | |
1053 | length = 0; |
1054 | while (list) |
1055 | { |
1056 | length++; |
1057 | list = list->next; |
1058 | } |
1059 | |
1060 | return length; |
1061 | } |
1062 | |
1063 | /** |
1064 | * g_list_foreach: |
1065 | * @list: a #GList, this must point to the top of the list |
1066 | * @func: the function to call with each element's data |
1067 | * @user_data: user data to pass to the function |
1068 | * |
1069 | * Calls a function for each element of a #GList. |
1070 | * |
1071 | * It is safe for @func to remove the element from @list, but it must |
1072 | * not modify any part of the list after that element. |
1073 | */ |
1074 | /** |
1075 | * GFunc: |
1076 | * @data: the element's data |
1077 | * @user_data: user data passed to g_list_foreach() or g_slist_foreach() |
1078 | * |
1079 | * Specifies the type of functions passed to g_list_foreach() and |
1080 | * g_slist_foreach(). |
1081 | */ |
1082 | void |
1083 | g_list_foreach (GList *list, |
1084 | GFunc func, |
1085 | gpointer user_data) |
1086 | { |
1087 | while (list) |
1088 | { |
1089 | GList *next = list->next; |
1090 | (*func) (list->data, user_data); |
1091 | list = next; |
1092 | } |
1093 | } |
1094 | |
1095 | static GList* |
1096 | g_list_insert_sorted_real (GList *list, |
1097 | gpointer data, |
1098 | GFunc func, |
1099 | gpointer user_data) |
1100 | { |
1101 | GList *tmp_list = list; |
1102 | GList *new_list; |
1103 | gint cmp; |
1104 | |
1105 | g_return_val_if_fail (func != NULL, list); |
1106 | |
1107 | if (!list) |
1108 | { |
1109 | new_list = _g_list_alloc0 (); |
1110 | new_list->data = data; |
1111 | return new_list; |
1112 | } |
1113 | |
1114 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
1115 | |
1116 | while ((tmp_list->next) && (cmp > 0)) |
1117 | { |
1118 | tmp_list = tmp_list->next; |
1119 | |
1120 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
1121 | } |
1122 | |
1123 | new_list = _g_list_alloc0 (); |
1124 | new_list->data = data; |
1125 | |
1126 | if ((!tmp_list->next) && (cmp > 0)) |
1127 | { |
1128 | tmp_list->next = new_list; |
1129 | new_list->prev = tmp_list; |
1130 | return list; |
1131 | } |
1132 | |
1133 | if (tmp_list->prev) |
1134 | { |
1135 | tmp_list->prev->next = new_list; |
1136 | new_list->prev = tmp_list->prev; |
1137 | } |
1138 | new_list->next = tmp_list; |
1139 | tmp_list->prev = new_list; |
1140 | |
1141 | if (tmp_list == list) |
1142 | return new_list; |
1143 | else |
1144 | return list; |
1145 | } |
1146 | |
1147 | /** |
1148 | * g_list_insert_sorted: |
1149 | * @list: a pointer to a #GList, this must point to the top of the |
1150 | * already sorted list |
1151 | * @data: the data for the new element |
1152 | * @func: the function to compare elements in the list. It should |
1153 | * return a number > 0 if the first parameter comes after the |
1154 | * second parameter in the sort order. |
1155 | * |
1156 | * Inserts a new element into the list, using the given comparison |
1157 | * function to determine its position. |
1158 | * |
1159 | * If you are adding many new elements to a list, and the number of |
1160 | * new elements is much larger than the length of the list, use |
1161 | * g_list_prepend() to add the new items and sort the list afterwards |
1162 | * with g_list_sort(). |
1163 | * |
1164 | * Returns: the (possibly changed) start of the #GList |
1165 | */ |
1166 | GList * |
1167 | g_list_insert_sorted (GList *list, |
1168 | gpointer data, |
1169 | GCompareFunc func) |
1170 | { |
1171 | return g_list_insert_sorted_real (list, data, func: (GFunc) func, NULL); |
1172 | } |
1173 | |
1174 | /** |
1175 | * g_list_insert_sorted_with_data: |
1176 | * @list: a pointer to a #GList, this must point to the top of the |
1177 | * already sorted list |
1178 | * @data: the data for the new element |
1179 | * @func: the function to compare elements in the list. It should |
1180 | * return a number > 0 if the first parameter comes after the |
1181 | * second parameter in the sort order. |
1182 | * @user_data: user data to pass to comparison function |
1183 | * |
1184 | * Inserts a new element into the list, using the given comparison |
1185 | * function to determine its position. |
1186 | * |
1187 | * If you are adding many new elements to a list, and the number of |
1188 | * new elements is much larger than the length of the list, use |
1189 | * g_list_prepend() to add the new items and sort the list afterwards |
1190 | * with g_list_sort(). |
1191 | * |
1192 | * Returns: the (possibly changed) start of the #GList |
1193 | * |
1194 | * Since: 2.10 |
1195 | */ |
1196 | GList * |
1197 | g_list_insert_sorted_with_data (GList *list, |
1198 | gpointer data, |
1199 | GCompareDataFunc func, |
1200 | gpointer user_data) |
1201 | { |
1202 | return g_list_insert_sorted_real (list, data, func: (GFunc) func, user_data); |
1203 | } |
1204 | |
1205 | static GList * |
1206 | g_list_sort_merge (GList *l1, |
1207 | GList *l2, |
1208 | GFunc compare_func, |
1209 | gpointer user_data) |
1210 | { |
1211 | GList list, *l, *lprev; |
1212 | gint cmp; |
1213 | |
1214 | l = &list; |
1215 | lprev = NULL; |
1216 | |
1217 | while (l1 && l2) |
1218 | { |
1219 | cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data); |
1220 | |
1221 | if (cmp <= 0) |
1222 | { |
1223 | l->next = l1; |
1224 | l1 = l1->next; |
1225 | } |
1226 | else |
1227 | { |
1228 | l->next = l2; |
1229 | l2 = l2->next; |
1230 | } |
1231 | l = l->next; |
1232 | l->prev = lprev; |
1233 | lprev = l; |
1234 | } |
1235 | l->next = l1 ? l1 : l2; |
1236 | l->next->prev = l; |
1237 | |
1238 | return list.next; |
1239 | } |
1240 | |
1241 | static GList * |
1242 | g_list_sort_real (GList *list, |
1243 | GFunc compare_func, |
1244 | gpointer user_data) |
1245 | { |
1246 | GList *l1, *l2; |
1247 | |
1248 | if (!list) |
1249 | return NULL; |
1250 | if (!list->next) |
1251 | return list; |
1252 | |
1253 | l1 = list; |
1254 | l2 = list->next; |
1255 | |
1256 | while ((l2 = l2->next) != NULL) |
1257 | { |
1258 | if ((l2 = l2->next) == NULL) |
1259 | break; |
1260 | l1 = l1->next; |
1261 | } |
1262 | l2 = l1->next; |
1263 | l1->next = NULL; |
1264 | |
1265 | return g_list_sort_merge (l1: g_list_sort_real (list, compare_func, user_data), |
1266 | l2: g_list_sort_real (list: l2, compare_func, user_data), |
1267 | compare_func, |
1268 | user_data); |
1269 | } |
1270 | |
1271 | /** |
1272 | * g_list_sort: |
1273 | * @list: a #GList, this must point to the top of the list |
1274 | * @compare_func: the comparison function used to sort the #GList. |
1275 | * This function is passed the data from 2 elements of the #GList |
1276 | * and should return 0 if they are equal, a negative value if the |
1277 | * first element comes before the second, or a positive value if |
1278 | * the first element comes after the second. |
1279 | * |
1280 | * Sorts a #GList using the given comparison function. The algorithm |
1281 | * used is a stable sort. |
1282 | * |
1283 | * Returns: the (possibly changed) start of the #GList |
1284 | */ |
1285 | /** |
1286 | * GCompareFunc: |
1287 | * @a: a value |
1288 | * @b: a value to compare with |
1289 | * |
1290 | * Specifies the type of a comparison function used to compare two |
1291 | * values. The function should return a negative integer if the first |
1292 | * value comes before the second, 0 if they are equal, or a positive |
1293 | * integer if the first value comes after the second. |
1294 | * |
1295 | * Returns: negative value if @a < @b; zero if @a = @b; positive |
1296 | * value if @a > @b |
1297 | */ |
1298 | GList * |
1299 | g_list_sort (GList *list, |
1300 | GCompareFunc compare_func) |
1301 | { |
1302 | return g_list_sort_real (list, compare_func: (GFunc) compare_func, NULL); |
1303 | } |
1304 | |
1305 | /** |
1306 | * g_list_sort_with_data: |
1307 | * @list: a #GList, this must point to the top of the list |
1308 | * @compare_func: comparison function |
1309 | * @user_data: user data to pass to comparison function |
1310 | * |
1311 | * Like g_list_sort(), but the comparison function accepts |
1312 | * a user data argument. |
1313 | * |
1314 | * Returns: the (possibly changed) start of the #GList |
1315 | */ |
1316 | /** |
1317 | * GCompareDataFunc: |
1318 | * @a: a value |
1319 | * @b: a value to compare with |
1320 | * @user_data: user data |
1321 | * |
1322 | * Specifies the type of a comparison function used to compare two |
1323 | * values. The function should return a negative integer if the first |
1324 | * value comes before the second, 0 if they are equal, or a positive |
1325 | * integer if the first value comes after the second. |
1326 | * |
1327 | * Returns: negative value if @a < @b; zero if @a = @b; positive |
1328 | * value if @a > @b |
1329 | */ |
1330 | GList * |
1331 | g_list_sort_with_data (GList *list, |
1332 | GCompareDataFunc compare_func, |
1333 | gpointer user_data) |
1334 | { |
1335 | return g_list_sort_real (list, compare_func: (GFunc) compare_func, user_data); |
1336 | } |
1337 | |
1338 | /** |
1339 | * g_clear_list: (skip) |
1340 | * @list_ptr: (not nullable): a #GList return location |
1341 | * @destroy: (nullable): the function to pass to g_list_free_full() or %NULL to not free elements |
1342 | * |
1343 | * Clears a pointer to a #GList, freeing it and, optionally, freeing its elements using @destroy. |
1344 | * |
1345 | * @list_ptr must be a valid pointer. If @list_ptr points to a null #GList, this does nothing. |
1346 | * |
1347 | * Since: 2.64 |
1348 | */ |
1349 | void |
1350 | (g_clear_list) (GList **list_ptr, |
1351 | GDestroyNotify destroy) |
1352 | { |
1353 | GList *list; |
1354 | |
1355 | list = *list_ptr; |
1356 | if (list) |
1357 | { |
1358 | *list_ptr = NULL; |
1359 | |
1360 | if (destroy) |
1361 | g_list_free_full (list, free_func: destroy); |
1362 | else |
1363 | g_list_free (list); |
1364 | } |
1365 | } |
1366 | |