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