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 "gslist.h" |
32 | |
33 | #include "gtestutils.h" |
34 | #include "gslice.h" |
35 | |
36 | /** |
37 | * SECTION:linked_lists_single |
38 | * @title: Singly-Linked Lists |
39 | * @short_description: linked lists that can be iterated in one direction |
40 | * |
41 | * The #GSList structure and its associated functions provide a |
42 | * standard singly-linked list data structure. The benefit of this |
43 | * data-structure is to provide insertion/deletion operations in O(1) |
44 | * complexity where access/search operations are in O(n). The benefit |
45 | * of #GSList over #GList (doubly linked list) is that they are lighter |
46 | * in space as they only need to retain one pointer but it double the |
47 | * cost of the worst case access/search operations. |
48 | * |
49 | * Each element in the list contains a piece of data, together with a |
50 | * pointer which links to the next element in the list. Using this |
51 | * pointer it is possible to move through the list in one direction |
52 | * only (unlike the [double-linked lists][glib-Doubly-Linked-Lists], |
53 | * which allow movement in both directions). |
54 | * |
55 | * The data contained in each element can be either integer values, by |
56 | * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros], |
57 | * or simply pointers to any type of data. |
58 | * |
59 | * List elements are allocated from the [slice allocator][glib-Memory-Slices], |
60 | * which is more efficient than allocating elements individually. |
61 | * |
62 | * Note that most of the #GSList functions expect to be passed a |
63 | * pointer to the first element in the list. The functions which insert |
64 | * elements return the new start of the list, which may have changed. |
65 | * |
66 | * There is no function to create a #GSList. %NULL is considered to be |
67 | * the empty list so you simply set a #GSList* to %NULL. |
68 | * |
69 | * To add elements, use g_slist_append(), g_slist_prepend(), |
70 | * g_slist_insert() and g_slist_insert_sorted(). |
71 | * |
72 | * To remove elements, use g_slist_remove(). |
73 | * |
74 | * To find elements in the list use g_slist_last(), g_slist_next(), |
75 | * g_slist_nth(), g_slist_nth_data(), g_slist_find() and |
76 | * g_slist_find_custom(). |
77 | * |
78 | * To find the index of an element use g_slist_position() and |
79 | * g_slist_index(). |
80 | * |
81 | * To call a function for each element in the list use |
82 | * g_slist_foreach(). |
83 | * |
84 | * To free the entire list, use g_slist_free(). |
85 | **/ |
86 | |
87 | /** |
88 | * GSList: |
89 | * @data: holds the element's data, which can be a pointer to any kind |
90 | * of data, or any integer value using the |
91 | * [Type Conversion Macros][glib-Type-Conversion-Macros] |
92 | * @next: contains the link to the next element in the list. |
93 | * |
94 | * The #GSList struct is used for each element in the singly-linked |
95 | * list. |
96 | **/ |
97 | |
98 | /** |
99 | * g_slist_next: |
100 | * @slist: an element in a #GSList. |
101 | * |
102 | * A convenience macro to get the next element in a #GSList. |
103 | * Note that it is considered perfectly acceptable to access |
104 | * @slist->next directly. |
105 | * |
106 | * Returns: the next element, or %NULL if there are no more elements. |
107 | **/ |
108 | |
109 | #define _g_slist_alloc0() g_slice_new0 (GSList) |
110 | #define _g_slist_alloc() g_slice_new (GSList) |
111 | #define _g_slist_free1(slist) g_slice_free (GSList, slist) |
112 | |
113 | /** |
114 | * g_slist_alloc: |
115 | * |
116 | * Allocates space for one #GSList element. It is called by the |
117 | * g_slist_append(), g_slist_prepend(), g_slist_insert() and |
118 | * g_slist_insert_sorted() functions and so is rarely used on its own. |
119 | * |
120 | * Returns: a pointer to the newly-allocated #GSList element. |
121 | **/ |
122 | GSList* |
123 | g_slist_alloc (void) |
124 | { |
125 | return _g_slist_alloc0 (); |
126 | } |
127 | |
128 | /** |
129 | * g_slist_free: |
130 | * @list: the first link of a #GSList |
131 | * |
132 | * Frees all of the memory used by a #GSList. |
133 | * The freed elements are returned to the slice allocator. |
134 | * |
135 | * If list elements contain dynamically-allocated memory, |
136 | * you should either use g_slist_free_full() or free them manually |
137 | * first. |
138 | * |
139 | * It can be combined with g_steal_pointer() to ensure the list head pointer |
140 | * is not left dangling: |
141 | * |[<!-- language="C" --> |
142 | * GSList *list_of_borrowed_things = …; /<!-- -->* (transfer container) *<!-- -->/ |
143 | * g_slist_free (g_steal_pointer (&list_of_borrowed_things)); |
144 | * ]| |
145 | */ |
146 | void |
147 | g_slist_free (GSList *list) |
148 | { |
149 | g_slice_free_chain (GSList, list, next); |
150 | } |
151 | |
152 | /** |
153 | * g_slist_free_1: |
154 | * @list: a #GSList element |
155 | * |
156 | * Frees one #GSList element. |
157 | * It is usually used after g_slist_remove_link(). |
158 | */ |
159 | /** |
160 | * g_slist_free1: |
161 | * |
162 | * A macro which does the same as g_slist_free_1(). |
163 | * |
164 | * Since: 2.10 |
165 | **/ |
166 | void |
167 | g_slist_free_1 (GSList *list) |
168 | { |
169 | _g_slist_free1 (list); |
170 | } |
171 | |
172 | /** |
173 | * g_slist_free_full: |
174 | * @list: the first link of a #GSList |
175 | * @free_func: the function to be called to free each element's data |
176 | * |
177 | * Convenience method, which frees all the memory used by a #GSList, and |
178 | * calls the specified destroy function on every element's data. |
179 | * |
180 | * @free_func must not modify the list (eg, by removing the freed |
181 | * element from it). |
182 | * |
183 | * It can be combined with g_steal_pointer() to ensure the list head pointer |
184 | * is not left dangling — this also has the nice property that the head pointer |
185 | * is cleared before any of the list elements are freed, to prevent double frees |
186 | * from @free_func: |
187 | * |[<!-- language="C" --> |
188 | * GSList *list_of_owned_things = …; /<!-- -->* (transfer full) (element-type GObject) *<!-- -->/ |
189 | * g_slist_free_full (g_steal_pointer (&list_of_owned_things), g_object_unref); |
190 | * ]| |
191 | * |
192 | * Since: 2.28 |
193 | **/ |
194 | void |
195 | g_slist_free_full (GSList *list, |
196 | GDestroyNotify free_func) |
197 | { |
198 | g_slist_foreach (list, func: (GFunc) free_func, NULL); |
199 | g_slist_free (list); |
200 | } |
201 | |
202 | /** |
203 | * g_slist_append: |
204 | * @list: a #GSList |
205 | * @data: the data for the new element |
206 | * |
207 | * Adds a new element on to the end of the list. |
208 | * |
209 | * The return value is the new start of the list, which may |
210 | * have changed, so make sure you store the new value. |
211 | * |
212 | * Note that g_slist_append() has to traverse the entire list |
213 | * to find the end, which is inefficient when adding multiple |
214 | * elements. A common idiom to avoid the inefficiency is to prepend |
215 | * the elements and reverse the list when all elements have been added. |
216 | * |
217 | * |[<!-- language="C" --> |
218 | * // Notice that these are initialized to the empty list. |
219 | * GSList *list = NULL, *number_list = NULL; |
220 | * |
221 | * // This is a list of strings. |
222 | * list = g_slist_append (list, "first"); |
223 | * list = g_slist_append (list, "second"); |
224 | * |
225 | * // This is a list of integers. |
226 | * number_list = g_slist_append (number_list, GINT_TO_POINTER (27)); |
227 | * number_list = g_slist_append (number_list, GINT_TO_POINTER (14)); |
228 | * ]| |
229 | * |
230 | * Returns: the new start of the #GSList |
231 | */ |
232 | GSList* |
233 | g_slist_append (GSList *list, |
234 | gpointer data) |
235 | { |
236 | GSList *new_list; |
237 | GSList *last; |
238 | |
239 | new_list = _g_slist_alloc (); |
240 | new_list->data = data; |
241 | new_list->next = NULL; |
242 | |
243 | if (list) |
244 | { |
245 | last = g_slist_last (list); |
246 | /* g_assert (last != NULL); */ |
247 | last->next = new_list; |
248 | |
249 | return list; |
250 | } |
251 | else |
252 | return new_list; |
253 | } |
254 | |
255 | /** |
256 | * g_slist_prepend: |
257 | * @list: a #GSList |
258 | * @data: the data for the new element |
259 | * |
260 | * Adds a new element on to the start of the list. |
261 | * |
262 | * The return value is the new start of the list, which |
263 | * may have changed, so make sure you store the new value. |
264 | * |
265 | * |[<!-- language="C" --> |
266 | * // Notice that it is initialized to the empty list. |
267 | * GSList *list = NULL; |
268 | * list = g_slist_prepend (list, "last"); |
269 | * list = g_slist_prepend (list, "first"); |
270 | * ]| |
271 | * |
272 | * Returns: the new start of the #GSList |
273 | */ |
274 | GSList* |
275 | g_slist_prepend (GSList *list, |
276 | gpointer data) |
277 | { |
278 | GSList *new_list; |
279 | |
280 | new_list = _g_slist_alloc (); |
281 | new_list->data = data; |
282 | new_list->next = list; |
283 | |
284 | return new_list; |
285 | } |
286 | |
287 | /** |
288 | * g_slist_insert: |
289 | * @list: a #GSList |
290 | * @data: the data for the new element |
291 | * @position: the position to insert the element. |
292 | * If this is negative, or is larger than the number |
293 | * of elements in the list, the new element is added on |
294 | * to the end of the list. |
295 | * |
296 | * Inserts a new element into the list at the given position. |
297 | * |
298 | * Returns: the new start of the #GSList |
299 | */ |
300 | GSList* |
301 | g_slist_insert (GSList *list, |
302 | gpointer data, |
303 | gint position) |
304 | { |
305 | GSList *prev_list; |
306 | GSList *tmp_list; |
307 | GSList *new_list; |
308 | |
309 | if (position < 0) |
310 | return g_slist_append (list, data); |
311 | else if (position == 0) |
312 | return g_slist_prepend (list, data); |
313 | |
314 | new_list = _g_slist_alloc (); |
315 | new_list->data = data; |
316 | |
317 | if (!list) |
318 | { |
319 | new_list->next = NULL; |
320 | return new_list; |
321 | } |
322 | |
323 | prev_list = NULL; |
324 | tmp_list = list; |
325 | |
326 | while ((position-- > 0) && tmp_list) |
327 | { |
328 | prev_list = tmp_list; |
329 | tmp_list = tmp_list->next; |
330 | } |
331 | |
332 | new_list->next = prev_list->next; |
333 | prev_list->next = new_list; |
334 | |
335 | return list; |
336 | } |
337 | |
338 | /** |
339 | * g_slist_insert_before: |
340 | * @slist: a #GSList |
341 | * @sibling: node to insert @data before |
342 | * @data: data to put in the newly-inserted node |
343 | * |
344 | * Inserts a node before @sibling containing @data. |
345 | * |
346 | * Returns: the new head of the list. |
347 | */ |
348 | GSList* |
349 | g_slist_insert_before (GSList *slist, |
350 | GSList *sibling, |
351 | gpointer data) |
352 | { |
353 | if (!slist) |
354 | { |
355 | slist = _g_slist_alloc (); |
356 | slist->data = data; |
357 | slist->next = NULL; |
358 | g_return_val_if_fail (sibling == NULL, slist); |
359 | return slist; |
360 | } |
361 | else |
362 | { |
363 | GSList *node, *last = NULL; |
364 | |
365 | for (node = slist; node; last = node, node = last->next) |
366 | if (node == sibling) |
367 | break; |
368 | if (!last) |
369 | { |
370 | node = _g_slist_alloc (); |
371 | node->data = data; |
372 | node->next = slist; |
373 | |
374 | return node; |
375 | } |
376 | else |
377 | { |
378 | node = _g_slist_alloc (); |
379 | node->data = data; |
380 | node->next = last->next; |
381 | last->next = node; |
382 | |
383 | return slist; |
384 | } |
385 | } |
386 | } |
387 | |
388 | /** |
389 | * g_slist_concat: |
390 | * @list1: a #GSList |
391 | * @list2: the #GSList to add to the end of the first #GSList |
392 | * |
393 | * Adds the second #GSList onto the end of the first #GSList. |
394 | * Note that the elements of the second #GSList are not copied. |
395 | * They are used directly. |
396 | * |
397 | * Returns: the start of the new #GSList |
398 | */ |
399 | GSList * |
400 | g_slist_concat (GSList *list1, GSList *list2) |
401 | { |
402 | if (list2) |
403 | { |
404 | if (list1) |
405 | g_slist_last (list: list1)->next = list2; |
406 | else |
407 | list1 = list2; |
408 | } |
409 | |
410 | return list1; |
411 | } |
412 | |
413 | static GSList* |
414 | _g_slist_remove_data (GSList *list, |
415 | gconstpointer data, |
416 | gboolean all) |
417 | { |
418 | GSList *tmp = NULL; |
419 | GSList **previous_ptr = &list; |
420 | |
421 | while (*previous_ptr) |
422 | { |
423 | tmp = *previous_ptr; |
424 | if (tmp->data == data) |
425 | { |
426 | *previous_ptr = tmp->next; |
427 | g_slist_free_1 (list: tmp); |
428 | if (!all) |
429 | break; |
430 | } |
431 | else |
432 | { |
433 | previous_ptr = &tmp->next; |
434 | } |
435 | } |
436 | |
437 | return list; |
438 | } |
439 | /** |
440 | * g_slist_remove: |
441 | * @list: a #GSList |
442 | * @data: the data of the element to remove |
443 | * |
444 | * Removes an element from a #GSList. |
445 | * If two elements contain the same data, only the first is removed. |
446 | * If none of the elements contain the data, the #GSList is unchanged. |
447 | * |
448 | * Returns: the new start of the #GSList |
449 | */ |
450 | GSList* |
451 | g_slist_remove (GSList *list, |
452 | gconstpointer data) |
453 | { |
454 | return _g_slist_remove_data (list, data, FALSE); |
455 | } |
456 | |
457 | /** |
458 | * g_slist_remove_all: |
459 | * @list: a #GSList |
460 | * @data: data to remove |
461 | * |
462 | * Removes all list nodes with data equal to @data. |
463 | * Returns the new head of the list. Contrast with |
464 | * g_slist_remove() which removes only the first node |
465 | * matching the given data. |
466 | * |
467 | * Returns: new head of @list |
468 | */ |
469 | GSList* |
470 | g_slist_remove_all (GSList *list, |
471 | gconstpointer data) |
472 | { |
473 | return _g_slist_remove_data (list, data, TRUE); |
474 | } |
475 | |
476 | static inline GSList* |
477 | _g_slist_remove_link (GSList *list, |
478 | GSList *link) |
479 | { |
480 | GSList *tmp = NULL; |
481 | GSList **previous_ptr = &list; |
482 | |
483 | while (*previous_ptr) |
484 | { |
485 | tmp = *previous_ptr; |
486 | if (tmp == link) |
487 | { |
488 | *previous_ptr = tmp->next; |
489 | tmp->next = NULL; |
490 | break; |
491 | } |
492 | |
493 | previous_ptr = &tmp->next; |
494 | } |
495 | |
496 | return list; |
497 | } |
498 | |
499 | /** |
500 | * g_slist_remove_link: |
501 | * @list: a #GSList |
502 | * @link_: an element in the #GSList |
503 | * |
504 | * Removes an element from a #GSList, without |
505 | * freeing the element. The removed element's next |
506 | * link is set to %NULL, so that it becomes a |
507 | * self-contained list with one element. |
508 | * |
509 | * Removing arbitrary nodes from a singly-linked list |
510 | * requires time that is proportional to the length of the list |
511 | * (ie. O(n)). If you find yourself using g_slist_remove_link() |
512 | * frequently, you should consider a different data structure, |
513 | * such as the doubly-linked #GList. |
514 | * |
515 | * Returns: the new start of the #GSList, without the element |
516 | */ |
517 | GSList* |
518 | g_slist_remove_link (GSList *list, |
519 | GSList *link_) |
520 | { |
521 | return _g_slist_remove_link (list, link: link_); |
522 | } |
523 | |
524 | /** |
525 | * g_slist_delete_link: |
526 | * @list: a #GSList |
527 | * @link_: node to delete |
528 | * |
529 | * Removes the node link_ from the list and frees it. |
530 | * Compare this to g_slist_remove_link() which removes the node |
531 | * without freeing it. |
532 | * |
533 | * Removing arbitrary nodes from a singly-linked list requires time |
534 | * that is proportional to the length of the list (ie. O(n)). If you |
535 | * find yourself using g_slist_delete_link() frequently, you should |
536 | * consider a different data structure, such as the doubly-linked |
537 | * #GList. |
538 | * |
539 | * Returns: the new head of @list |
540 | */ |
541 | GSList* |
542 | g_slist_delete_link (GSList *list, |
543 | GSList *link_) |
544 | { |
545 | list = _g_slist_remove_link (list, link: link_); |
546 | _g_slist_free1 (link_); |
547 | |
548 | return list; |
549 | } |
550 | |
551 | /** |
552 | * g_slist_copy: |
553 | * @list: a #GSList |
554 | * |
555 | * Copies a #GSList. |
556 | * |
557 | * Note that this is a "shallow" copy. If the list elements |
558 | * consist of pointers to data, the pointers are copied but |
559 | * the actual data isn't. See g_slist_copy_deep() if you need |
560 | * to copy the data as well. |
561 | * |
562 | * Returns: a copy of @list |
563 | */ |
564 | GSList* |
565 | g_slist_copy (GSList *list) |
566 | { |
567 | return g_slist_copy_deep (list, NULL, NULL); |
568 | } |
569 | |
570 | /** |
571 | * g_slist_copy_deep: |
572 | * @list: a #GSList |
573 | * @func: a copy function used to copy every element in the list |
574 | * @user_data: user data passed to the copy function @func, or #NULL |
575 | * |
576 | * Makes a full (deep) copy of a #GSList. |
577 | * |
578 | * In contrast with g_slist_copy(), this function uses @func to make a copy of |
579 | * each list element, in addition to copying the list container itself. |
580 | * |
581 | * @func, as a #GCopyFunc, takes two arguments, the data to be copied |
582 | * and a @user_data pointer. On common processor architectures, it's safe to |
583 | * pass %NULL as @user_data if the copy function takes only one argument. You |
584 | * may get compiler warnings from this though if compiling with GCC’s |
585 | * `-Wcast-function-type` warning. |
586 | * |
587 | * For instance, if @list holds a list of GObjects, you can do: |
588 | * |[<!-- language="C" --> |
589 | * another_list = g_slist_copy_deep (list, (GCopyFunc) g_object_ref, NULL); |
590 | * ]| |
591 | * |
592 | * And, to entirely free the new list, you could do: |
593 | * |[<!-- language="C" --> |
594 | * g_slist_free_full (another_list, g_object_unref); |
595 | * ]| |
596 | * |
597 | * Returns: a full copy of @list, use g_slist_free_full() to free it |
598 | * |
599 | * Since: 2.34 |
600 | */ |
601 | GSList* |
602 | g_slist_copy_deep (GSList *list, GCopyFunc func, gpointer user_data) |
603 | { |
604 | GSList *new_list = NULL; |
605 | |
606 | if (list) |
607 | { |
608 | GSList *last; |
609 | |
610 | new_list = _g_slist_alloc (); |
611 | if (func) |
612 | new_list->data = func (list->data, user_data); |
613 | else |
614 | new_list->data = list->data; |
615 | last = new_list; |
616 | list = list->next; |
617 | while (list) |
618 | { |
619 | last->next = _g_slist_alloc (); |
620 | last = last->next; |
621 | if (func) |
622 | last->data = func (list->data, user_data); |
623 | else |
624 | last->data = list->data; |
625 | list = list->next; |
626 | } |
627 | last->next = NULL; |
628 | } |
629 | |
630 | return new_list; |
631 | } |
632 | |
633 | /** |
634 | * g_slist_reverse: |
635 | * @list: a #GSList |
636 | * |
637 | * Reverses a #GSList. |
638 | * |
639 | * Returns: the start of the reversed #GSList |
640 | */ |
641 | GSList* |
642 | g_slist_reverse (GSList *list) |
643 | { |
644 | GSList *prev = NULL; |
645 | |
646 | while (list) |
647 | { |
648 | GSList *next = list->next; |
649 | |
650 | list->next = prev; |
651 | |
652 | prev = list; |
653 | list = next; |
654 | } |
655 | |
656 | return prev; |
657 | } |
658 | |
659 | /** |
660 | * g_slist_nth: |
661 | * @list: a #GSList |
662 | * @n: the position of the element, counting from 0 |
663 | * |
664 | * Gets the element at the given position in a #GSList. |
665 | * |
666 | * Returns: the element, or %NULL if the position is off |
667 | * the end of the #GSList |
668 | */ |
669 | GSList* |
670 | g_slist_nth (GSList *list, |
671 | guint n) |
672 | { |
673 | while (n-- > 0 && list) |
674 | list = list->next; |
675 | |
676 | return list; |
677 | } |
678 | |
679 | /** |
680 | * g_slist_nth_data: |
681 | * @list: a #GSList |
682 | * @n: the position of the element |
683 | * |
684 | * Gets the data of the element at the given position. |
685 | * |
686 | * Returns: the element's data, or %NULL if the position |
687 | * is off the end of the #GSList |
688 | */ |
689 | gpointer |
690 | g_slist_nth_data (GSList *list, |
691 | guint n) |
692 | { |
693 | while (n-- > 0 && list) |
694 | list = list->next; |
695 | |
696 | return list ? list->data : NULL; |
697 | } |
698 | |
699 | /** |
700 | * g_slist_find: |
701 | * @list: a #GSList |
702 | * @data: the element data to find |
703 | * |
704 | * Finds the element in a #GSList which |
705 | * contains the given data. |
706 | * |
707 | * Returns: the found #GSList element, |
708 | * or %NULL if it is not found |
709 | */ |
710 | GSList* |
711 | g_slist_find (GSList *list, |
712 | gconstpointer data) |
713 | { |
714 | while (list) |
715 | { |
716 | if (list->data == data) |
717 | break; |
718 | list = list->next; |
719 | } |
720 | |
721 | return list; |
722 | } |
723 | |
724 | |
725 | /** |
726 | * g_slist_find_custom: |
727 | * @list: a #GSList |
728 | * @data: user data passed to the function |
729 | * @func: the function to call for each element. |
730 | * It should return 0 when the desired element is found |
731 | * |
732 | * Finds an element in a #GSList, using a supplied function to |
733 | * find the desired element. It iterates over the list, calling |
734 | * the given function which should return 0 when the desired |
735 | * element is found. The function takes two #gconstpointer arguments, |
736 | * the #GSList element's data as the first argument and the |
737 | * given user data. |
738 | * |
739 | * Returns: the found #GSList element, or %NULL if it is not found |
740 | */ |
741 | GSList* |
742 | g_slist_find_custom (GSList *list, |
743 | gconstpointer data, |
744 | GCompareFunc func) |
745 | { |
746 | g_return_val_if_fail (func != NULL, list); |
747 | |
748 | while (list) |
749 | { |
750 | if (! func (list->data, data)) |
751 | return list; |
752 | list = list->next; |
753 | } |
754 | |
755 | return NULL; |
756 | } |
757 | |
758 | /** |
759 | * g_slist_position: |
760 | * @list: a #GSList |
761 | * @llink: an element in the #GSList |
762 | * |
763 | * Gets the position of the given element |
764 | * in the #GSList (starting from 0). |
765 | * |
766 | * Returns: the position of the element in the #GSList, |
767 | * or -1 if the element is not found |
768 | */ |
769 | gint |
770 | g_slist_position (GSList *list, |
771 | GSList *llink) |
772 | { |
773 | gint i; |
774 | |
775 | i = 0; |
776 | while (list) |
777 | { |
778 | if (list == llink) |
779 | return i; |
780 | i++; |
781 | list = list->next; |
782 | } |
783 | |
784 | return -1; |
785 | } |
786 | |
787 | /** |
788 | * g_slist_index: |
789 | * @list: a #GSList |
790 | * @data: the data to find |
791 | * |
792 | * Gets the position of the element containing |
793 | * the given data (starting from 0). |
794 | * |
795 | * Returns: the index of the element containing the data, |
796 | * or -1 if the data is not found |
797 | */ |
798 | gint |
799 | g_slist_index (GSList *list, |
800 | gconstpointer data) |
801 | { |
802 | gint i; |
803 | |
804 | i = 0; |
805 | while (list) |
806 | { |
807 | if (list->data == data) |
808 | return i; |
809 | i++; |
810 | list = list->next; |
811 | } |
812 | |
813 | return -1; |
814 | } |
815 | |
816 | /** |
817 | * g_slist_last: |
818 | * @list: a #GSList |
819 | * |
820 | * Gets the last element in a #GSList. |
821 | * |
822 | * This function iterates over the whole list. |
823 | * |
824 | * Returns: the last element in the #GSList, |
825 | * or %NULL if the #GSList has no elements |
826 | */ |
827 | GSList* |
828 | g_slist_last (GSList *list) |
829 | { |
830 | if (list) |
831 | { |
832 | while (list->next) |
833 | list = list->next; |
834 | } |
835 | |
836 | return list; |
837 | } |
838 | |
839 | /** |
840 | * g_slist_length: |
841 | * @list: a #GSList |
842 | * |
843 | * Gets the number of elements in a #GSList. |
844 | * |
845 | * This function iterates over the whole list to |
846 | * count its elements. To check whether the list is non-empty, it is faster to |
847 | * check @list against %NULL. |
848 | * |
849 | * Returns: the number of elements in the #GSList |
850 | */ |
851 | guint |
852 | g_slist_length (GSList *list) |
853 | { |
854 | guint length; |
855 | |
856 | length = 0; |
857 | while (list) |
858 | { |
859 | length++; |
860 | list = list->next; |
861 | } |
862 | |
863 | return length; |
864 | } |
865 | |
866 | /** |
867 | * g_slist_foreach: |
868 | * @list: a #GSList |
869 | * @func: the function to call with each element's data |
870 | * @user_data: user data to pass to the function |
871 | * |
872 | * Calls a function for each element of a #GSList. |
873 | * |
874 | * It is safe for @func to remove the element from @list, but it must |
875 | * not modify any part of the list after that element. |
876 | */ |
877 | void |
878 | g_slist_foreach (GSList *list, |
879 | GFunc func, |
880 | gpointer user_data) |
881 | { |
882 | while (list) |
883 | { |
884 | GSList *next = list->next; |
885 | (*func) (list->data, user_data); |
886 | list = next; |
887 | } |
888 | } |
889 | |
890 | static GSList* |
891 | g_slist_insert_sorted_real (GSList *list, |
892 | gpointer data, |
893 | GFunc func, |
894 | gpointer user_data) |
895 | { |
896 | GSList *tmp_list = list; |
897 | GSList *prev_list = NULL; |
898 | GSList *new_list; |
899 | gint cmp; |
900 | |
901 | g_return_val_if_fail (func != NULL, list); |
902 | |
903 | if (!list) |
904 | { |
905 | new_list = _g_slist_alloc (); |
906 | new_list->data = data; |
907 | new_list->next = NULL; |
908 | return new_list; |
909 | } |
910 | |
911 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
912 | |
913 | while ((tmp_list->next) && (cmp > 0)) |
914 | { |
915 | prev_list = tmp_list; |
916 | tmp_list = tmp_list->next; |
917 | |
918 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
919 | } |
920 | |
921 | new_list = _g_slist_alloc (); |
922 | new_list->data = data; |
923 | |
924 | if ((!tmp_list->next) && (cmp > 0)) |
925 | { |
926 | tmp_list->next = new_list; |
927 | new_list->next = NULL; |
928 | return list; |
929 | } |
930 | |
931 | if (prev_list) |
932 | { |
933 | prev_list->next = new_list; |
934 | new_list->next = tmp_list; |
935 | return list; |
936 | } |
937 | else |
938 | { |
939 | new_list->next = list; |
940 | return new_list; |
941 | } |
942 | } |
943 | |
944 | /** |
945 | * g_slist_insert_sorted: |
946 | * @list: a #GSList |
947 | * @data: the data for the new element |
948 | * @func: the function to compare elements in the list. |
949 | * It should return a number > 0 if the first parameter |
950 | * comes after the second parameter in the sort order. |
951 | * |
952 | * Inserts a new element into the list, using the given |
953 | * comparison function to determine its position. |
954 | * |
955 | * Returns: the new start of the #GSList |
956 | */ |
957 | GSList* |
958 | g_slist_insert_sorted (GSList *list, |
959 | gpointer data, |
960 | GCompareFunc func) |
961 | { |
962 | return g_slist_insert_sorted_real (list, data, func: (GFunc) func, NULL); |
963 | } |
964 | |
965 | /** |
966 | * g_slist_insert_sorted_with_data: |
967 | * @list: a #GSList |
968 | * @data: the data for the new element |
969 | * @func: the function to compare elements in the list. |
970 | * It should return a number > 0 if the first parameter |
971 | * comes after the second parameter in the sort order. |
972 | * @user_data: data to pass to comparison function |
973 | * |
974 | * Inserts a new element into the list, using the given |
975 | * comparison function to determine its position. |
976 | * |
977 | * Returns: the new start of the #GSList |
978 | * |
979 | * Since: 2.10 |
980 | */ |
981 | GSList* |
982 | g_slist_insert_sorted_with_data (GSList *list, |
983 | gpointer data, |
984 | GCompareDataFunc func, |
985 | gpointer user_data) |
986 | { |
987 | return g_slist_insert_sorted_real (list, data, func: (GFunc) func, user_data); |
988 | } |
989 | |
990 | static GSList * |
991 | g_slist_sort_merge (GSList *l1, |
992 | GSList *l2, |
993 | GFunc compare_func, |
994 | gpointer user_data) |
995 | { |
996 | GSList list, *l; |
997 | gint cmp; |
998 | |
999 | l=&list; |
1000 | |
1001 | while (l1 && l2) |
1002 | { |
1003 | cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data); |
1004 | |
1005 | if (cmp <= 0) |
1006 | { |
1007 | l=l->next=l1; |
1008 | l1=l1->next; |
1009 | } |
1010 | else |
1011 | { |
1012 | l=l->next=l2; |
1013 | l2=l2->next; |
1014 | } |
1015 | } |
1016 | l->next= l1 ? l1 : l2; |
1017 | |
1018 | return list.next; |
1019 | } |
1020 | |
1021 | static GSList * |
1022 | g_slist_sort_real (GSList *list, |
1023 | GFunc compare_func, |
1024 | gpointer user_data) |
1025 | { |
1026 | GSList *l1, *l2; |
1027 | |
1028 | if (!list) |
1029 | return NULL; |
1030 | if (!list->next) |
1031 | return list; |
1032 | |
1033 | l1 = list; |
1034 | l2 = list->next; |
1035 | |
1036 | while ((l2 = l2->next) != NULL) |
1037 | { |
1038 | if ((l2 = l2->next) == NULL) |
1039 | break; |
1040 | l1=l1->next; |
1041 | } |
1042 | l2 = l1->next; |
1043 | l1->next = NULL; |
1044 | |
1045 | return g_slist_sort_merge (l1: g_slist_sort_real (list, compare_func, user_data), |
1046 | l2: g_slist_sort_real (list: l2, compare_func, user_data), |
1047 | compare_func, |
1048 | user_data); |
1049 | } |
1050 | |
1051 | /** |
1052 | * g_slist_sort: |
1053 | * @list: a #GSList |
1054 | * @compare_func: the comparison function used to sort the #GSList. |
1055 | * This function is passed the data from 2 elements of the #GSList |
1056 | * and should return 0 if they are equal, a negative value if the |
1057 | * first element comes before the second, or a positive value if |
1058 | * the first element comes after the second. |
1059 | * |
1060 | * Sorts a #GSList using the given comparison function. The algorithm |
1061 | * used is a stable sort. |
1062 | * |
1063 | * Returns: the start of the sorted #GSList |
1064 | */ |
1065 | GSList * |
1066 | g_slist_sort (GSList *list, |
1067 | GCompareFunc compare_func) |
1068 | { |
1069 | return g_slist_sort_real (list, compare_func: (GFunc) compare_func, NULL); |
1070 | } |
1071 | |
1072 | /** |
1073 | * g_slist_sort_with_data: |
1074 | * @list: a #GSList |
1075 | * @compare_func: comparison function |
1076 | * @user_data: data to pass to comparison function |
1077 | * |
1078 | * Like g_slist_sort(), but the sort function accepts a user data argument. |
1079 | * |
1080 | * Returns: new head of the list |
1081 | */ |
1082 | GSList * |
1083 | g_slist_sort_with_data (GSList *list, |
1084 | GCompareDataFunc compare_func, |
1085 | gpointer user_data) |
1086 | { |
1087 | return g_slist_sort_real (list, compare_func: (GFunc) compare_func, user_data); |
1088 | } |
1089 | |
1090 | /** |
1091 | * g_clear_slist: (skip) |
1092 | * @slist_ptr: (not nullable): a #GSList return location |
1093 | * @destroy: (nullable): the function to pass to g_slist_free_full() or %NULL to not free elements |
1094 | * |
1095 | * Clears a pointer to a #GSList, freeing it and, optionally, freeing its elements using @destroy. |
1096 | * |
1097 | * @slist_ptr must be a valid pointer. If @slist_ptr points to a null #GSList, this does nothing. |
1098 | * |
1099 | * Since: 2.64 |
1100 | */ |
1101 | void |
1102 | (g_clear_slist) (GSList **slist_ptr, |
1103 | GDestroyNotify destroy) |
1104 | { |
1105 | GSList *slist; |
1106 | |
1107 | slist = *slist_ptr; |
1108 | if (slist) |
1109 | { |
1110 | *slist_ptr = NULL; |
1111 | |
1112 | if (destroy) |
1113 | g_slist_free_full (list: slist, free_func: destroy); |
1114 | else |
1115 | g_slist_free (list: slist); |
1116 | } |
1117 | } |
1118 | |