/src/glib-2.80.0/glib/gslist.c
Line | Count | Source |
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 | 0 | #define _g_slist_alloc0() g_slice_new0 (GSList) |
61 | 363 | #define _g_slist_alloc() g_slice_new (GSList) |
62 | 89 | #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 | | g_slist_alloc (void) |
75 | 0 | { |
76 | 0 | return _g_slist_alloc0 (); |
77 | 0 | } |
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 | | g_slist_free (GSList *list) |
99 | 36.7k | { |
100 | 36.7k | g_slice_free_chain (GSList, list, next); |
101 | 36.7k | } |
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 | | g_slist_free_1 (GSList *list) |
119 | 89 | { |
120 | 89 | _g_slist_free1 (list); |
121 | 89 | } |
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 | | g_slist_free_full (GSList *list, |
147 | | GDestroyNotify free_func) |
148 | 0 | { |
149 | 0 | g_slist_foreach (list, (GFunc) free_func, NULL); |
150 | 0 | g_slist_free (list); |
151 | 0 | } |
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 | | g_slist_append (GSList *list, |
185 | | gpointer data) |
186 | 0 | { |
187 | 0 | GSList *new_list; |
188 | 0 | GSList *last; |
189 | |
|
190 | 0 | new_list = _g_slist_alloc (); |
191 | 0 | new_list->data = data; |
192 | 0 | new_list->next = NULL; |
193 | |
|
194 | 0 | if (list) |
195 | 0 | { |
196 | 0 | last = g_slist_last (list); |
197 | | /* g_assert (last != NULL); */ |
198 | 0 | last->next = new_list; |
199 | |
|
200 | 0 | return list; |
201 | 0 | } |
202 | 0 | else |
203 | 0 | return new_list; |
204 | 0 | } |
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 | | g_slist_prepend (GSList *list, |
227 | | gpointer data) |
228 | 363 | { |
229 | 363 | GSList *new_list; |
230 | | |
231 | 363 | new_list = _g_slist_alloc (); |
232 | 363 | new_list->data = data; |
233 | 363 | new_list->next = list; |
234 | | |
235 | 363 | return new_list; |
236 | 363 | } |
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 | | g_slist_insert (GSList *list, |
253 | | gpointer data, |
254 | | gint position) |
255 | 0 | { |
256 | 0 | GSList *prev_list; |
257 | 0 | GSList *tmp_list; |
258 | 0 | GSList *new_list; |
259 | |
|
260 | 0 | if (position < 0) |
261 | 0 | return g_slist_append (list, data); |
262 | 0 | else if (position == 0) |
263 | 0 | return g_slist_prepend (list, data); |
264 | | |
265 | 0 | new_list = _g_slist_alloc (); |
266 | 0 | new_list->data = data; |
267 | |
|
268 | 0 | if (!list) |
269 | 0 | { |
270 | 0 | new_list->next = NULL; |
271 | 0 | return new_list; |
272 | 0 | } |
273 | | |
274 | 0 | prev_list = NULL; |
275 | 0 | tmp_list = list; |
276 | |
|
277 | 0 | while ((position-- > 0) && tmp_list) |
278 | 0 | { |
279 | 0 | prev_list = tmp_list; |
280 | 0 | tmp_list = tmp_list->next; |
281 | 0 | } |
282 | |
|
283 | 0 | new_list->next = prev_list->next; |
284 | 0 | prev_list->next = new_list; |
285 | |
|
286 | 0 | return list; |
287 | 0 | } |
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 | | g_slist_insert_before (GSList *slist, |
301 | | GSList *sibling, |
302 | | gpointer data) |
303 | 0 | { |
304 | 0 | if (!slist) |
305 | 0 | { |
306 | 0 | slist = _g_slist_alloc (); |
307 | 0 | slist->data = data; |
308 | 0 | slist->next = NULL; |
309 | 0 | g_return_val_if_fail (sibling == NULL, slist); |
310 | 0 | return slist; |
311 | 0 | } |
312 | 0 | else |
313 | 0 | { |
314 | 0 | GSList *node, *last = NULL; |
315 | |
|
316 | 0 | for (node = slist; node; last = node, node = last->next) |
317 | 0 | if (node == sibling) |
318 | 0 | break; |
319 | 0 | if (!last) |
320 | 0 | { |
321 | 0 | node = _g_slist_alloc (); |
322 | 0 | node->data = data; |
323 | 0 | node->next = slist; |
324 | |
|
325 | 0 | return node; |
326 | 0 | } |
327 | 0 | else |
328 | 0 | { |
329 | 0 | node = _g_slist_alloc (); |
330 | 0 | node->data = data; |
331 | 0 | node->next = last->next; |
332 | 0 | last->next = node; |
333 | |
|
334 | 0 | return slist; |
335 | 0 | } |
336 | 0 | } |
337 | 0 | } |
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 | | g_slist_concat (GSList *list1, GSList *list2) |
352 | 0 | { |
353 | 0 | if (list2) |
354 | 0 | { |
355 | 0 | if (list1) |
356 | 0 | g_slist_last (list1)->next = list2; |
357 | 0 | else |
358 | 0 | list1 = list2; |
359 | 0 | } |
360 | |
|
361 | 0 | return list1; |
362 | 0 | } |
363 | | |
364 | | static GSList* |
365 | | _g_slist_remove_data (GSList *list, |
366 | | gconstpointer data, |
367 | | gboolean all) |
368 | 89 | { |
369 | 89 | GSList *tmp = NULL; |
370 | 89 | GSList **previous_ptr = &list; |
371 | | |
372 | 89 | while (*previous_ptr) |
373 | 89 | { |
374 | 89 | tmp = *previous_ptr; |
375 | 89 | if (tmp->data == data) |
376 | 89 | { |
377 | 89 | *previous_ptr = tmp->next; |
378 | 89 | g_slist_free_1 (tmp); |
379 | 89 | if (!all) |
380 | 89 | break; |
381 | 89 | } |
382 | 0 | else |
383 | 0 | { |
384 | 0 | previous_ptr = &tmp->next; |
385 | 0 | } |
386 | 89 | } |
387 | | |
388 | 89 | return list; |
389 | 89 | } |
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 | | g_slist_remove (GSList *list, |
403 | | gconstpointer data) |
404 | 89 | { |
405 | 89 | return _g_slist_remove_data (list, data, FALSE); |
406 | 89 | } |
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 | | g_slist_remove_all (GSList *list, |
422 | | gconstpointer data) |
423 | 0 | { |
424 | 0 | return _g_slist_remove_data (list, data, TRUE); |
425 | 0 | } |
426 | | |
427 | | static inline GSList* |
428 | | _g_slist_remove_link (GSList *list, |
429 | | GSList *link) |
430 | 0 | { |
431 | 0 | GSList *tmp = NULL; |
432 | 0 | GSList **previous_ptr = &list; |
433 | |
|
434 | 0 | while (*previous_ptr) |
435 | 0 | { |
436 | 0 | tmp = *previous_ptr; |
437 | 0 | if (tmp == link) |
438 | 0 | { |
439 | 0 | *previous_ptr = tmp->next; |
440 | 0 | tmp->next = NULL; |
441 | 0 | break; |
442 | 0 | } |
443 | | |
444 | 0 | previous_ptr = &tmp->next; |
445 | 0 | } |
446 | |
|
447 | 0 | return list; |
448 | 0 | } |
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 | | g_slist_remove_link (GSList *list, |
470 | | GSList *link_) |
471 | 0 | { |
472 | 0 | return _g_slist_remove_link (list, link_); |
473 | 0 | } |
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 | | g_slist_delete_link (GSList *list, |
494 | | GSList *link_) |
495 | 0 | { |
496 | 0 | list = _g_slist_remove_link (list, link_); |
497 | 0 | _g_slist_free1 (link_); |
498 | |
|
499 | 0 | return list; |
500 | 0 | } |
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 | | g_slist_copy (GSList *list) |
517 | 12 | { |
518 | 12 | return g_slist_copy_deep (list, NULL, NULL); |
519 | 12 | } |
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 | | g_slist_copy_deep (GSList *list, GCopyFunc func, gpointer user_data) |
554 | 12 | { |
555 | 12 | GSList *new_list = NULL; |
556 | | |
557 | 12 | if (list) |
558 | 0 | { |
559 | 0 | GSList *last; |
560 | |
|
561 | 0 | new_list = _g_slist_alloc (); |
562 | 0 | if (func) |
563 | 0 | new_list->data = func (list->data, user_data); |
564 | 0 | else |
565 | 0 | new_list->data = list->data; |
566 | 0 | last = new_list; |
567 | 0 | list = list->next; |
568 | 0 | while (list) |
569 | 0 | { |
570 | 0 | last->next = _g_slist_alloc (); |
571 | 0 | last = last->next; |
572 | 0 | if (func) |
573 | 0 | last->data = func (list->data, user_data); |
574 | 0 | else |
575 | 0 | last->data = list->data; |
576 | 0 | list = list->next; |
577 | 0 | } |
578 | 0 | last->next = NULL; |
579 | 0 | } |
580 | | |
581 | 12 | return new_list; |
582 | 12 | } |
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 | | g_slist_reverse (GSList *list) |
594 | 0 | { |
595 | 0 | GSList *prev = NULL; |
596 | |
|
597 | 0 | while (list) |
598 | 0 | { |
599 | 0 | GSList *next = list->next; |
600 | |
|
601 | 0 | list->next = prev; |
602 | |
|
603 | 0 | prev = list; |
604 | 0 | list = next; |
605 | 0 | } |
606 | |
|
607 | 0 | return prev; |
608 | 0 | } |
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 | | g_slist_nth (GSList *list, |
622 | | guint n) |
623 | 0 | { |
624 | 0 | while (n-- > 0 && list) |
625 | 0 | list = list->next; |
626 | |
|
627 | 0 | return list; |
628 | 0 | } |
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 | | g_slist_nth_data (GSList *list, |
642 | | guint n) |
643 | 0 | { |
644 | 0 | while (n-- > 0 && list) |
645 | 0 | list = list->next; |
646 | |
|
647 | 0 | return list ? list->data : NULL; |
648 | 0 | } |
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 | | g_slist_find (GSList *list, |
663 | | gconstpointer data) |
664 | 89 | { |
665 | 92 | while (list) |
666 | 3 | { |
667 | 3 | if (list->data == data) |
668 | 0 | break; |
669 | 3 | list = list->next; |
670 | 3 | } |
671 | | |
672 | 89 | return list; |
673 | 89 | } |
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 | | g_slist_find_custom (GSList *list, |
694 | | gconstpointer data, |
695 | | GCompareFunc func) |
696 | 0 | { |
697 | 0 | g_return_val_if_fail (func != NULL, list); |
698 | | |
699 | 0 | while (list) |
700 | 0 | { |
701 | 0 | if (! func (list->data, data)) |
702 | 0 | return list; |
703 | 0 | list = list->next; |
704 | 0 | } |
705 | | |
706 | 0 | return NULL; |
707 | 0 | } |
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 | | g_slist_position (GSList *list, |
722 | | GSList *llink) |
723 | 0 | { |
724 | 0 | gint i; |
725 | |
|
726 | 0 | i = 0; |
727 | 0 | while (list) |
728 | 0 | { |
729 | 0 | if (list == llink) |
730 | 0 | return i; |
731 | 0 | i++; |
732 | 0 | list = list->next; |
733 | 0 | } |
734 | | |
735 | 0 | return -1; |
736 | 0 | } |
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 | | g_slist_index (GSList *list, |
751 | | gconstpointer data) |
752 | 0 | { |
753 | 0 | gint i; |
754 | |
|
755 | 0 | i = 0; |
756 | 0 | while (list) |
757 | 0 | { |
758 | 0 | if (list->data == data) |
759 | 0 | return i; |
760 | 0 | i++; |
761 | 0 | list = list->next; |
762 | 0 | } |
763 | | |
764 | 0 | return -1; |
765 | 0 | } |
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 | | g_slist_last (GSList *list) |
780 | 0 | { |
781 | 0 | if (list) |
782 | 0 | { |
783 | 0 | while (list->next) |
784 | 0 | list = list->next; |
785 | 0 | } |
786 | |
|
787 | 0 | return list; |
788 | 0 | } |
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 | | g_slist_length (GSList *list) |
804 | 17 | { |
805 | 17 | guint length; |
806 | | |
807 | 17 | length = 0; |
808 | 17 | while (list) |
809 | 0 | { |
810 | 0 | length++; |
811 | 0 | list = list->next; |
812 | 0 | } |
813 | | |
814 | 17 | return length; |
815 | 17 | } |
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 | | g_slist_foreach (GSList *list, |
830 | | GFunc func, |
831 | | gpointer user_data) |
832 | 0 | { |
833 | 0 | while (list) |
834 | 0 | { |
835 | 0 | GSList *next = list->next; |
836 | 0 | (*func) (list->data, user_data); |
837 | 0 | list = next; |
838 | 0 | } |
839 | 0 | } |
840 | | |
841 | | static GSList* |
842 | | g_slist_insert_sorted_real (GSList *list, |
843 | | gpointer data, |
844 | | GFunc func, |
845 | | gpointer user_data) |
846 | 0 | { |
847 | 0 | GSList *tmp_list = list; |
848 | 0 | GSList *prev_list = NULL; |
849 | 0 | GSList *new_list; |
850 | 0 | gint cmp; |
851 | |
|
852 | 0 | g_return_val_if_fail (func != NULL, list); |
853 | | |
854 | 0 | if (!list) |
855 | 0 | { |
856 | 0 | new_list = _g_slist_alloc (); |
857 | 0 | new_list->data = data; |
858 | 0 | new_list->next = NULL; |
859 | 0 | return new_list; |
860 | 0 | } |
861 | | |
862 | 0 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
863 | |
|
864 | 0 | while ((tmp_list->next) && (cmp > 0)) |
865 | 0 | { |
866 | 0 | prev_list = tmp_list; |
867 | 0 | tmp_list = tmp_list->next; |
868 | |
|
869 | 0 | cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); |
870 | 0 | } |
871 | |
|
872 | 0 | new_list = _g_slist_alloc (); |
873 | 0 | new_list->data = data; |
874 | |
|
875 | 0 | if ((!tmp_list->next) && (cmp > 0)) |
876 | 0 | { |
877 | 0 | tmp_list->next = new_list; |
878 | 0 | new_list->next = NULL; |
879 | 0 | return list; |
880 | 0 | } |
881 | | |
882 | 0 | if (prev_list) |
883 | 0 | { |
884 | 0 | prev_list->next = new_list; |
885 | 0 | new_list->next = tmp_list; |
886 | 0 | return list; |
887 | 0 | } |
888 | 0 | else |
889 | 0 | { |
890 | 0 | new_list->next = list; |
891 | 0 | return new_list; |
892 | 0 | } |
893 | 0 | } |
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 | | g_slist_insert_sorted (GSList *list, |
910 | | gpointer data, |
911 | | GCompareFunc func) |
912 | 0 | { |
913 | 0 | return g_slist_insert_sorted_real (list, data, (GFunc) func, NULL); |
914 | 0 | } |
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 | | g_slist_insert_sorted_with_data (GSList *list, |
934 | | gpointer data, |
935 | | GCompareDataFunc func, |
936 | | gpointer user_data) |
937 | 0 | { |
938 | 0 | return g_slist_insert_sorted_real (list, data, (GFunc) func, user_data); |
939 | 0 | } |
940 | | |
941 | | static GSList * |
942 | | g_slist_sort_merge (GSList *l1, |
943 | | GSList *l2, |
944 | | GFunc compare_func, |
945 | | gpointer user_data) |
946 | 0 | { |
947 | 0 | GSList list, *l; |
948 | 0 | gint cmp; |
949 | |
|
950 | 0 | l=&list; |
951 | |
|
952 | 0 | while (l1 && l2) |
953 | 0 | { |
954 | 0 | cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data); |
955 | |
|
956 | 0 | if (cmp <= 0) |
957 | 0 | { |
958 | 0 | l=l->next=l1; |
959 | 0 | l1=l1->next; |
960 | 0 | } |
961 | 0 | else |
962 | 0 | { |
963 | 0 | l=l->next=l2; |
964 | 0 | l2=l2->next; |
965 | 0 | } |
966 | 0 | } |
967 | 0 | l->next= l1 ? l1 : l2; |
968 | |
|
969 | 0 | return list.next; |
970 | 0 | } |
971 | | |
972 | | static GSList * |
973 | | g_slist_sort_real (GSList *list, |
974 | | GFunc compare_func, |
975 | | gpointer user_data) |
976 | 0 | { |
977 | 0 | GSList *l1, *l2; |
978 | |
|
979 | 0 | if (!list) |
980 | 0 | return NULL; |
981 | 0 | if (!list->next) |
982 | 0 | return list; |
983 | | |
984 | 0 | l1 = list; |
985 | 0 | l2 = list->next; |
986 | |
|
987 | 0 | while ((l2 = l2->next) != NULL) |
988 | 0 | { |
989 | 0 | if ((l2 = l2->next) == NULL) |
990 | 0 | break; |
991 | 0 | l1=l1->next; |
992 | 0 | } |
993 | 0 | l2 = l1->next; |
994 | 0 | l1->next = NULL; |
995 | |
|
996 | 0 | return g_slist_sort_merge (g_slist_sort_real (list, compare_func, user_data), |
997 | 0 | g_slist_sort_real (l2, compare_func, user_data), |
998 | 0 | compare_func, |
999 | 0 | user_data); |
1000 | 0 | } |
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 | | g_slist_sort (GSList *list, |
1018 | | GCompareFunc compare_func) |
1019 | 0 | { |
1020 | 0 | return g_slist_sort_real (list, (GFunc) compare_func, NULL); |
1021 | 0 | } |
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 | | g_slist_sort_with_data (GSList *list, |
1035 | | GCompareDataFunc compare_func, |
1036 | | gpointer user_data) |
1037 | 0 | { |
1038 | 0 | return g_slist_sort_real (list, (GFunc) compare_func, user_data); |
1039 | 0 | } |
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 | | (g_clear_slist) (GSList **slist_ptr, |
1054 | | GDestroyNotify destroy) |
1055 | 0 | { |
1056 | 0 | GSList *slist; |
1057 | |
|
1058 | 0 | slist = *slist_ptr; |
1059 | 0 | if (slist) |
1060 | 0 | { |
1061 | 0 | *slist_ptr = NULL; |
1062 | |
|
1063 | 0 | if (destroy) |
1064 | 0 | g_slist_free_full (slist, destroy); |
1065 | 0 | else |
1066 | 0 | g_slist_free (slist); |
1067 | 0 | } |
1068 | 0 | } |