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](conversion-macros.html#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 : 23880 : g_slist_alloc (void)
75 : : {
76 : 23880 : 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 : 1609567 : g_slist_free (GSList *list)
99 : : {
100 : 1609567 : g_slice_free_chain (GSList, list, next);
101 : 1609567 : }
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 : 301355 : g_slist_free_1 (GSList *list)
119 : : {
120 : 301355 : _g_slist_free1 (list);
121 : 301355 : }
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 : 768360 : g_slist_free_full (GSList *list,
147 : : GDestroyNotify free_func)
148 : : {
149 : 768360 : g_slist_foreach (list, (GFunc) free_func, NULL);
150 : 768360 : g_slist_free (list);
151 : 768360 : }
152 : :
153 : : /**
154 : : * g_slist_append:
155 : : * @list: (nullable): 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 : : * Note that the return value is the new start of the list
161 : : * if @list was empty; 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: either @list or the new start of the #GSList if @list was %NULL
182 : : */
183 : : GSList*
184 : 72672 : g_slist_append (GSList *list,
185 : : gpointer data)
186 : : {
187 : : GSList *new_list;
188 : : GSList *last;
189 : :
190 : 72672 : new_list = _g_slist_alloc ();
191 : 72672 : new_list->data = data;
192 : 72672 : new_list->next = NULL;
193 : :
194 : 72672 : if (list)
195 : : {
196 : 50941 : last = g_slist_last (list);
197 : : /* g_assert (last != NULL); */
198 : 50941 : last->next = new_list;
199 : :
200 : 50941 : return list;
201 : : }
202 : : else
203 : 21731 : return new_list;
204 : : }
205 : :
206 : : /**
207 : : * g_slist_prepend:
208 : : * @list: (nullable): 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 : : * Note that the return value is the new start of the list,
214 : : * which will 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: a pointer to the newly prepended element,
224 : : * which is the new start of the #GSList
225 : : */
226 : : GSList*
227 : 1437349 : g_slist_prepend (GSList *list,
228 : : gpointer data)
229 : : {
230 : : GSList *new_list;
231 : :
232 : 1437349 : new_list = _g_slist_alloc ();
233 : 1437349 : new_list->data = data;
234 : 1437349 : new_list->next = list;
235 : :
236 : 1437349 : return new_list;
237 : : }
238 : :
239 : : /**
240 : : * g_slist_insert:
241 : : * @list: (nullable): a #GSList
242 : : * @data: the data for the new element
243 : : * @position: the position to insert the element.
244 : : * If this is negative, or is larger than the number
245 : : * of elements in the list, the new element is added on
246 : : * to the end of the list.
247 : : *
248 : : * Inserts a new element into the list at the given position.
249 : : *
250 : : * Returns: the (possibly changed) start of the #GSList
251 : : */
252 : : GSList*
253 : 9 : g_slist_insert (GSList *list,
254 : : gpointer data,
255 : : gint position)
256 : : {
257 : : GSList *prev_list;
258 : : GSList *tmp_list;
259 : : GSList *new_list;
260 : :
261 : 9 : if (position < 0)
262 : 1 : return g_slist_append (list, data);
263 : 8 : else if (position == 0)
264 : 1 : return g_slist_prepend (list, data);
265 : :
266 : 7 : new_list = _g_slist_alloc ();
267 : 7 : new_list->data = data;
268 : :
269 : 7 : if (!list)
270 : : {
271 : 1 : new_list->next = NULL;
272 : 1 : return new_list;
273 : : }
274 : :
275 : 6 : prev_list = NULL;
276 : 6 : tmp_list = list;
277 : :
278 : 34 : while ((position-- > 0) && tmp_list)
279 : : {
280 : 28 : prev_list = tmp_list;
281 : 28 : tmp_list = tmp_list->next;
282 : : }
283 : :
284 : 6 : new_list->next = prev_list->next;
285 : 6 : prev_list->next = new_list;
286 : :
287 : 6 : return list;
288 : : }
289 : :
290 : : /**
291 : : * g_slist_insert_before:
292 : : * @slist: (nullable): a #GSList
293 : : * @sibling: node to insert @data before
294 : : * @data: data to put in the newly-inserted node
295 : : *
296 : : * Inserts a node before @sibling containing @data.
297 : : *
298 : : * Returns: the new head of the list.
299 : : */
300 : : GSList*
301 : 4 : g_slist_insert_before (GSList *slist,
302 : : GSList *sibling,
303 : : gpointer data)
304 : : {
305 : 4 : if (!slist)
306 : : {
307 : 1 : slist = _g_slist_alloc ();
308 : 1 : slist->data = data;
309 : 1 : slist->next = NULL;
310 : 1 : g_return_val_if_fail (sibling == NULL, slist);
311 : 1 : return slist;
312 : : }
313 : : else
314 : : {
315 : 3 : GSList *node, *last = NULL;
316 : :
317 : 10 : for (node = slist; node; last = node, node = last->next)
318 : 9 : if (node == sibling)
319 : 2 : break;
320 : 3 : if (!last)
321 : : {
322 : 1 : node = _g_slist_alloc ();
323 : 1 : node->data = data;
324 : 1 : node->next = slist;
325 : :
326 : 1 : return node;
327 : : }
328 : : else
329 : : {
330 : 2 : node = _g_slist_alloc ();
331 : 2 : node->data = data;
332 : 2 : node->next = last->next;
333 : 2 : last->next = node;
334 : :
335 : 2 : return slist;
336 : : }
337 : : }
338 : : }
339 : :
340 : : /**
341 : : * g_slist_concat:
342 : : * @list1: a #GSList
343 : : * @list2: the #GSList to add to the end of the first #GSList
344 : : *
345 : : * Adds the second #GSList onto the end of the first #GSList.
346 : : * Note that the elements of the second #GSList are not copied.
347 : : * They are used directly.
348 : : *
349 : : * Returns: the start of the new #GSList
350 : : */
351 : : GSList *
352 : 23296511 : g_slist_concat (GSList *list1, GSList *list2)
353 : : {
354 : 23296511 : if (list2)
355 : : {
356 : 23166526 : if (list1)
357 : 23166516 : g_slist_last (list1)->next = list2;
358 : : else
359 : 10 : list1 = list2;
360 : : }
361 : :
362 : 23296511 : return list1;
363 : : }
364 : :
365 : : static GSList*
366 : 252613 : _g_slist_remove_data (GSList *list,
367 : : gconstpointer data,
368 : : gboolean all)
369 : : {
370 : 252613 : GSList *tmp = NULL;
371 : 252613 : GSList **previous_ptr = &list;
372 : :
373 : 1175535 : while (*previous_ptr)
374 : : {
375 : 1175524 : tmp = *previous_ptr;
376 : 1175524 : if (tmp->data == data)
377 : : {
378 : 252622 : *previous_ptr = tmp->next;
379 : 252622 : g_slist_free_1 (tmp);
380 : 252622 : if (!all)
381 : 252602 : break;
382 : : }
383 : : else
384 : : {
385 : 922902 : previous_ptr = &tmp->next;
386 : : }
387 : : }
388 : :
389 : 252613 : return list;
390 : : }
391 : : /**
392 : : * g_slist_remove:
393 : : * @list: a #GSList
394 : : * @data: the data of the element to remove
395 : : *
396 : : * Removes an element from a #GSList.
397 : : * If two elements contain the same data, only the first is removed.
398 : : * If none of the elements contain the data, the #GSList is unchanged.
399 : : *
400 : : * Returns: the new start of the #GSList
401 : : */
402 : : GSList*
403 : 252603 : g_slist_remove (GSList *list,
404 : : gconstpointer data)
405 : : {
406 : 252603 : return _g_slist_remove_data (list, data, FALSE);
407 : : }
408 : :
409 : : /**
410 : : * g_slist_remove_all:
411 : : * @list: a #GSList
412 : : * @data: data to remove
413 : : *
414 : : * Removes all list nodes with data equal to @data.
415 : : * Returns the new head of the list. Contrast with
416 : : * g_slist_remove() which removes only the first node
417 : : * matching the given data.
418 : : *
419 : : * Returns: new head of @list
420 : : */
421 : : GSList*
422 : 10 : g_slist_remove_all (GSList *list,
423 : : gconstpointer data)
424 : : {
425 : 10 : return _g_slist_remove_data (list, data, TRUE);
426 : : }
427 : :
428 : : static inline GSList*
429 : 24308872 : _g_slist_remove_link (GSList *list,
430 : : GSList *link)
431 : : {
432 : 24308872 : GSList *tmp = NULL;
433 : 24308872 : GSList **previous_ptr = &list;
434 : :
435 : 24309551 : while (*previous_ptr)
436 : : {
437 : 24309551 : tmp = *previous_ptr;
438 : 24309551 : if (tmp == link)
439 : : {
440 : 24308872 : *previous_ptr = tmp->next;
441 : 24308872 : tmp->next = NULL;
442 : 24308872 : break;
443 : : }
444 : :
445 : 679 : previous_ptr = &tmp->next;
446 : : }
447 : :
448 : 24308872 : return list;
449 : : }
450 : :
451 : : /**
452 : : * g_slist_remove_link:
453 : : * @list: a #GSList
454 : : * @link_: an element in the #GSList
455 : : *
456 : : * Removes an element from a #GSList, without
457 : : * freeing the element. The removed element's next
458 : : * link is set to %NULL, so that it becomes a
459 : : * self-contained list with one element.
460 : : *
461 : : * Removing arbitrary nodes from a singly-linked list
462 : : * requires time that is proportional to the length of the list
463 : : * (ie. O(n)). If you find yourself using g_slist_remove_link()
464 : : * frequently, you should consider a different data structure,
465 : : * such as the doubly-linked #GList.
466 : : *
467 : : * Returns: the new start of the #GSList, without the element
468 : : */
469 : : GSList*
470 : 23272617 : g_slist_remove_link (GSList *list,
471 : : GSList *link_)
472 : : {
473 : 23272617 : return _g_slist_remove_link (list, link_);
474 : : }
475 : :
476 : : /**
477 : : * g_slist_delete_link:
478 : : * @list: a #GSList
479 : : * @link_: node to delete
480 : : *
481 : : * Removes the node link_ from the list and frees it.
482 : : * Compare this to g_slist_remove_link() which removes the node
483 : : * without freeing it.
484 : : *
485 : : * Removing arbitrary nodes from a singly-linked list requires time
486 : : * that is proportional to the length of the list (ie. O(n)). If you
487 : : * find yourself using g_slist_delete_link() frequently, you should
488 : : * consider a different data structure, such as the doubly-linked
489 : : * #GList.
490 : : *
491 : : * Returns: the new head of @list
492 : : */
493 : : GSList*
494 : 1036255 : g_slist_delete_link (GSList *list,
495 : : GSList *link_)
496 : : {
497 : 1036255 : list = _g_slist_remove_link (list, link_);
498 : 1036255 : _g_slist_free1 (link_);
499 : :
500 : 1036255 : return list;
501 : : }
502 : :
503 : : /**
504 : : * g_slist_copy:
505 : : * @list: a #GSList
506 : : *
507 : : * Copies a #GSList.
508 : : *
509 : : * Note that this is a "shallow" copy. If the list elements
510 : : * consist of pointers to data, the pointers are copied but
511 : : * the actual data isn't. See g_slist_copy_deep() if you need
512 : : * to copy the data as well.
513 : : *
514 : : * Returns: a copy of @list
515 : : */
516 : : GSList*
517 : 5360 : g_slist_copy (GSList *list)
518 : : {
519 : 5360 : return g_slist_copy_deep (list, NULL, NULL);
520 : : }
521 : :
522 : : /**
523 : : * g_slist_copy_deep:
524 : : * @list: a #GSList
525 : : * @func: (scope call): a copy function used to copy every element in the list
526 : : * @user_data: user data passed to the copy function @func, or #NULL
527 : : *
528 : : * Makes a full (deep) copy of a #GSList.
529 : : *
530 : : * In contrast with g_slist_copy(), this function uses @func to make a copy of
531 : : * each list element, in addition to copying the list container itself.
532 : : *
533 : : * @func, as a #GCopyFunc, takes two arguments, the data to be copied
534 : : * and a @user_data pointer. On common processor architectures, it's safe to
535 : : * pass %NULL as @user_data if the copy function takes only one argument. You
536 : : * may get compiler warnings from this though if compiling with GCC’s
537 : : * `-Wcast-function-type` warning.
538 : : *
539 : : * For instance, if @list holds a list of GObjects, you can do:
540 : : * |[<!-- language="C" -->
541 : : * another_list = g_slist_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
542 : : * ]|
543 : : *
544 : : * And, to entirely free the new list, you could do:
545 : : * |[<!-- language="C" -->
546 : : * g_slist_free_full (another_list, g_object_unref);
547 : : * ]|
548 : : *
549 : : * Returns: a full copy of @list, use g_slist_free_full() to free it
550 : : *
551 : : * Since: 2.34
552 : : */
553 : : GSList*
554 : 5362 : g_slist_copy_deep (GSList *list, GCopyFunc func, gpointer user_data)
555 : : {
556 : 5362 : GSList *new_list = NULL;
557 : :
558 : 5362 : if (list)
559 : : {
560 : : GSList *last;
561 : :
562 : 828 : new_list = _g_slist_alloc ();
563 : 828 : if (func)
564 : 1 : new_list->data = func (list->data, user_data);
565 : : else
566 : 827 : new_list->data = list->data;
567 : 828 : last = new_list;
568 : 828 : list = list->next;
569 : 1812 : while (list)
570 : : {
571 : 984 : last->next = _g_slist_alloc ();
572 : 984 : last = last->next;
573 : 984 : if (func)
574 : 2 : last->data = func (list->data, user_data);
575 : : else
576 : 982 : last->data = list->data;
577 : 984 : list = list->next;
578 : : }
579 : 828 : last->next = NULL;
580 : : }
581 : :
582 : 5362 : return new_list;
583 : : }
584 : :
585 : : /**
586 : : * g_slist_reverse:
587 : : * @list: a #GSList
588 : : *
589 : : * Reverses a #GSList.
590 : : *
591 : : * Returns: the start of the reversed #GSList
592 : : */
593 : : GSList*
594 : 15535 : g_slist_reverse (GSList *list)
595 : : {
596 : 15535 : GSList *prev = NULL;
597 : :
598 : 33340 : while (list)
599 : : {
600 : 17805 : GSList *next = list->next;
601 : :
602 : 17805 : list->next = prev;
603 : :
604 : 17805 : prev = list;
605 : 17805 : list = next;
606 : : }
607 : :
608 : 15535 : return prev;
609 : : }
610 : :
611 : : /**
612 : : * g_slist_nth:
613 : : * @list: a #GSList
614 : : * @n: the position of the element, counting from 0
615 : : *
616 : : * Gets the element at the given position in a #GSList.
617 : : *
618 : : * Returns: the element, or %NULL if the position is off
619 : : * the end of the #GSList
620 : : */
621 : : GSList*
622 : 40 : g_slist_nth (GSList *list,
623 : : guint n)
624 : : {
625 : 220 : while (n-- > 0 && list)
626 : 180 : list = list->next;
627 : :
628 : 40 : return list;
629 : : }
630 : :
631 : : /**
632 : : * g_slist_nth_data:
633 : : * @list: a #GSList
634 : : * @n: the position of the element
635 : : *
636 : : * Gets the data of the element at the given position.
637 : : *
638 : : * Returns: the element's data, or %NULL if the position
639 : : * is off the end of the #GSList
640 : : */
641 : : gpointer
642 : 492 : g_slist_nth_data (GSList *list,
643 : : guint n)
644 : : {
645 : 12546 : while (n-- > 0 && list)
646 : 12054 : list = list->next;
647 : :
648 : 492 : return list ? list->data : NULL;
649 : : }
650 : :
651 : : /**
652 : : * g_slist_find:
653 : : * @list: a #GSList
654 : : * @data: the element data to find
655 : : *
656 : : * Finds the element in a #GSList which
657 : : * contains the given data.
658 : : *
659 : : * Returns: the found #GSList element,
660 : : * or %NULL if it is not found
661 : : */
662 : : GSList*
663 : 309011 : g_slist_find (GSList *list,
664 : : gconstpointer data)
665 : : {
666 : 329360 : while (list)
667 : : {
668 : 302001 : if (list->data == data)
669 : 281652 : break;
670 : 20349 : list = list->next;
671 : : }
672 : :
673 : 309011 : return list;
674 : : }
675 : :
676 : :
677 : : /**
678 : : * g_slist_find_custom:
679 : : * @list: a #GSList
680 : : * @data: user data passed to the function
681 : : * @func: (scope call): the function to call for each element.
682 : : * It should return 0 when the desired element is found
683 : : *
684 : : * Finds an element in a #GSList, using a supplied function to
685 : : * find the desired element. It iterates over the list, calling
686 : : * the given function which should return 0 when the desired
687 : : * element is found. The function takes two #gconstpointer arguments,
688 : : * the #GSList element's data as the first argument and the
689 : : * given user data.
690 : : *
691 : : * Returns: the found #GSList element, or %NULL if it is not found
692 : : */
693 : : GSList*
694 : 96931 : g_slist_find_custom (GSList *list,
695 : : gconstpointer data,
696 : : GCompareFunc func)
697 : : {
698 : 96931 : g_return_val_if_fail (func != NULL, list);
699 : :
700 : 5652985 : while (list)
701 : : {
702 : 5604539 : if (! func (list->data, data))
703 : 48485 : return list;
704 : 5556054 : list = list->next;
705 : : }
706 : :
707 : 48446 : return NULL;
708 : : }
709 : :
710 : : /**
711 : : * g_slist_position:
712 : : * @list: a #GSList
713 : : * @llink: an element in the #GSList
714 : : *
715 : : * Gets the position of the given element
716 : : * in the #GSList (starting from 0).
717 : : *
718 : : * Returns: the position of the element in the #GSList,
719 : : * or -1 if the element is not found
720 : : */
721 : : gint
722 : 11 : g_slist_position (GSList *list,
723 : : GSList *llink)
724 : : {
725 : : gint i;
726 : :
727 : 11 : i = 0;
728 : 66 : while (list)
729 : : {
730 : 65 : if (list == llink)
731 : 10 : return i;
732 : 55 : i++;
733 : 55 : list = list->next;
734 : : }
735 : :
736 : 1 : return -1;
737 : : }
738 : :
739 : : /**
740 : : * g_slist_index:
741 : : * @list: a #GSList
742 : : * @data: the data to find
743 : : *
744 : : * Gets the position of the element containing
745 : : * the given data (starting from 0).
746 : : *
747 : : * Returns: the index of the element containing the data,
748 : : * or -1 if the data is not found
749 : : */
750 : : gint
751 : 11 : g_slist_index (GSList *list,
752 : : gconstpointer data)
753 : : {
754 : : gint i;
755 : :
756 : 11 : i = 0;
757 : 66 : while (list)
758 : : {
759 : 65 : if (list->data == data)
760 : 10 : return i;
761 : 55 : i++;
762 : 55 : list = list->next;
763 : : }
764 : :
765 : 1 : return -1;
766 : : }
767 : :
768 : : /**
769 : : * g_slist_last:
770 : : * @list: a #GSList
771 : : *
772 : : * Gets the last element in a #GSList.
773 : : *
774 : : * This function iterates over the whole list.
775 : : *
776 : : * Returns: the last element in the #GSList,
777 : : * or %NULL if the #GSList has no elements
778 : : */
779 : : GSList*
780 : 23217523 : g_slist_last (GSList *list)
781 : : {
782 : 23217523 : if (list)
783 : : {
784 : 62229533 : while (list->next)
785 : 39012010 : list = list->next;
786 : : }
787 : :
788 : 23217523 : return list;
789 : : }
790 : :
791 : : /**
792 : : * g_slist_length:
793 : : * @list: a #GSList
794 : : *
795 : : * Gets the number of elements in a #GSList.
796 : : *
797 : : * This function iterates over the whole list to
798 : : * count its elements. To check whether the list is non-empty, it is faster to
799 : : * check @list against %NULL.
800 : : *
801 : : * Returns: the number of elements in the #GSList
802 : : */
803 : : guint
804 : 25508 : g_slist_length (GSList *list)
805 : : {
806 : : guint length;
807 : :
808 : 25508 : length = 0;
809 : 61705 : while (list)
810 : : {
811 : 36197 : length++;
812 : 36197 : list = list->next;
813 : : }
814 : :
815 : 25508 : return length;
816 : : }
817 : :
818 : : /**
819 : : * g_slist_foreach:
820 : : * @list: a #GSList
821 : : * @func: (scope call): the function to call with each element's data
822 : : * @user_data: user data to pass to the function
823 : : *
824 : : * Calls a function for each element of a #GSList.
825 : : *
826 : : * It is safe for @func to remove the element from @list, but it must
827 : : * not modify any part of the list after that element.
828 : : */
829 : : void
830 : 768361 : g_slist_foreach (GSList *list,
831 : : GFunc func,
832 : : gpointer user_data)
833 : : {
834 : 842985 : while (list)
835 : : {
836 : 74624 : GSList *next = list->next;
837 : 74624 : (*func) (list->data, user_data);
838 : 74624 : list = next;
839 : : }
840 : 768361 : }
841 : :
842 : : static GSList*
843 : 100 : g_slist_insert_sorted_real (GSList *list,
844 : : gpointer data,
845 : : GFunc func,
846 : : gpointer user_data)
847 : : {
848 : 100 : GSList *tmp_list = list;
849 : 100 : GSList *prev_list = NULL;
850 : : GSList *new_list;
851 : : gint cmp;
852 : :
853 : 100 : g_return_val_if_fail (func != NULL, list);
854 : :
855 : 100 : if (!list)
856 : : {
857 : 2 : new_list = _g_slist_alloc ();
858 : 2 : new_list->data = data;
859 : 2 : new_list->next = NULL;
860 : 2 : return new_list;
861 : : }
862 : :
863 : 98 : cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
864 : :
865 : 1226 : while ((tmp_list->next) && (cmp > 0))
866 : : {
867 : 1128 : prev_list = tmp_list;
868 : 1128 : tmp_list = tmp_list->next;
869 : :
870 : 1128 : cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
871 : : }
872 : :
873 : 98 : new_list = _g_slist_alloc ();
874 : 98 : new_list->data = data;
875 : :
876 : 98 : if ((!tmp_list->next) && (cmp > 0))
877 : : {
878 : 2 : tmp_list->next = new_list;
879 : 2 : new_list->next = NULL;
880 : 2 : return list;
881 : : }
882 : :
883 : 96 : if (prev_list)
884 : : {
885 : 88 : prev_list->next = new_list;
886 : 88 : new_list->next = tmp_list;
887 : 88 : return list;
888 : : }
889 : : else
890 : : {
891 : 8 : new_list->next = list;
892 : 8 : return new_list;
893 : : }
894 : : }
895 : :
896 : : /**
897 : : * g_slist_insert_sorted:
898 : : * @list: a #GSList
899 : : * @data: the data for the new element
900 : : * @func: (scope call): the function to compare elements in the list.
901 : : * It should return a number > 0 if the first parameter
902 : : * comes after the second parameter in the sort order.
903 : : *
904 : : * Inserts a new element into the list, using the given
905 : : * comparison function to determine its position.
906 : : *
907 : : * Returns: the new start of the #GSList
908 : : */
909 : : GSList*
910 : 50 : g_slist_insert_sorted (GSList *list,
911 : : gpointer data,
912 : : GCompareFunc func)
913 : : {
914 : 50 : return g_slist_insert_sorted_real (list, data, (GFunc) func, NULL);
915 : : }
916 : :
917 : : /**
918 : : * g_slist_insert_sorted_with_data:
919 : : * @list: a #GSList
920 : : * @data: the data for the new element
921 : : * @func: (scope call): the function to compare elements in the list.
922 : : * It should return a number > 0 if the first parameter
923 : : * comes after the second parameter in the sort order.
924 : : * @user_data: data to pass to comparison function
925 : : *
926 : : * Inserts a new element into the list, using the given
927 : : * comparison function to determine its position.
928 : : *
929 : : * Returns: the new start of the #GSList
930 : : *
931 : : * Since: 2.10
932 : : */
933 : : GSList*
934 : 50 : g_slist_insert_sorted_with_data (GSList *list,
935 : : gpointer data,
936 : : GCompareDataFunc func,
937 : : gpointer user_data)
938 : : {
939 : 50 : return g_slist_insert_sorted_real (list, data, (GFunc) func, user_data);
940 : : }
941 : :
942 : : static GSList *
943 : 992 : g_slist_sort_merge (GSList *l1,
944 : : GSList *l2,
945 : : GFunc compare_func,
946 : : gpointer user_data)
947 : : {
948 : : GSList list, *l;
949 : : gint cmp;
950 : :
951 : 992 : l=&list;
952 : :
953 : 3602 : while (l1 && l2)
954 : : {
955 : 2610 : cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
956 : :
957 : 2610 : if (cmp <= 0)
958 : : {
959 : 1303 : l=l->next=l1;
960 : 1303 : l1=l1->next;
961 : : }
962 : : else
963 : : {
964 : 1307 : l=l->next=l2;
965 : 1307 : l2=l2->next;
966 : : }
967 : : }
968 : 992 : l->next= l1 ? l1 : l2;
969 : :
970 : 992 : return list.next;
971 : : }
972 : :
973 : : static GSList *
974 : 8745 : g_slist_sort_real (GSList *list,
975 : : GFunc compare_func,
976 : : gpointer user_data)
977 : : {
978 : : GSList *l1, *l2;
979 : :
980 : 8745 : if (!list)
981 : 6457 : return NULL;
982 : 2288 : if (!list->next)
983 : 1296 : return list;
984 : :
985 : 992 : l1 = list;
986 : 992 : l2 = list->next;
987 : :
988 : 1810 : while ((l2 = l2->next) != NULL)
989 : : {
990 : 1109 : if ((l2 = l2->next) == NULL)
991 : 291 : break;
992 : 818 : l1=l1->next;
993 : : }
994 : 992 : l2 = l1->next;
995 : 992 : l1->next = NULL;
996 : :
997 : 992 : return g_slist_sort_merge (g_slist_sort_real (list, compare_func, user_data),
998 : : g_slist_sort_real (l2, compare_func, user_data),
999 : : compare_func,
1000 : : user_data);
1001 : : }
1002 : :
1003 : : /**
1004 : : * g_slist_sort:
1005 : : * @list: a #GSList
1006 : : * @compare_func: (scope call): the comparison function used to sort the #GSList.
1007 : : * This function is passed the data from 2 elements of the #GSList
1008 : : * and should return 0 if they are equal, a negative value if the
1009 : : * first element comes before the second, or a positive value if
1010 : : * the first element comes after the second.
1011 : : *
1012 : : * Sorts a #GSList using the given comparison function. The algorithm
1013 : : * used is a stable sort.
1014 : : *
1015 : : * Returns: the start of the sorted #GSList
1016 : : */
1017 : : GSList *
1018 : 6760 : g_slist_sort (GSList *list,
1019 : : GCompareFunc compare_func)
1020 : : {
1021 : 6760 : return g_slist_sort_real (list, (GFunc) compare_func, NULL);
1022 : : }
1023 : :
1024 : : /**
1025 : : * g_slist_sort_with_data:
1026 : : * @list: a #GSList
1027 : : * @compare_func: (scope call): comparison function
1028 : : * @user_data: data to pass to comparison function
1029 : : *
1030 : : * Like g_slist_sort(), but the sort function accepts a user data argument.
1031 : : *
1032 : : * Returns: new head of the list
1033 : : */
1034 : : GSList *
1035 : 1 : g_slist_sort_with_data (GSList *list,
1036 : : GCompareDataFunc compare_func,
1037 : : gpointer user_data)
1038 : : {
1039 : 1 : return g_slist_sort_real (list, (GFunc) compare_func, user_data);
1040 : : }
1041 : :
1042 : : /**
1043 : : * g_clear_slist: (skip)
1044 : : * @slist_ptr: (not nullable): a #GSList return location
1045 : : * @destroy: (nullable): the function to pass to g_slist_free_full() or %NULL to not free elements
1046 : : *
1047 : : * Clears a pointer to a #GSList, freeing it and, optionally, freeing its elements using @destroy.
1048 : : *
1049 : : * @slist_ptr must be a valid pointer. If @slist_ptr points to a null #GSList, this does nothing.
1050 : : *
1051 : : * Since: 2.64
1052 : : */
1053 : : void
1054 : 0 : (g_clear_slist) (GSList **slist_ptr,
1055 : : GDestroyNotify destroy)
1056 : : {
1057 : : GSList *slist;
1058 : :
1059 : 0 : slist = *slist_ptr;
1060 : 0 : if (slist)
1061 : : {
1062 : 0 : *slist_ptr = NULL;
1063 : :
1064 : 0 : if (destroy)
1065 : 0 : g_slist_free_full (slist, destroy);
1066 : : else
1067 : 0 : g_slist_free (slist);
1068 : : }
1069 : 0 : }
|
