nexmon – Blame information for rev 1

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