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, write to the 16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 * Boston, MA 02111-1307, USA. 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 "glib.h" 34#include "galias.h" 35 36 37void g_list_push_allocator (gpointer dummy) { /* present for binary compat only */ } 38void g_list_pop_allocator (void) { /* present for binary compat only */ } 39 40#define _g_list_alloc() g_slice_new (GList) 41#define _g_list_alloc0() g_slice_new0 (GList) 42#define _g_list_free1(list) g_slice_free (GList, list) 43 44GList* 45g_list_alloc (void) 46{ 47 return _g_list_alloc0 (); 48} 49 50/** 51 * g_list_free: 52 * @list: a #GList 53 * 54 * Frees all of the memory used by a #GList. 55 * The freed elements are returned to the slice allocator. 56 * 57 * <note><para> 58 * If list elements contain dynamically-allocated memory, 59 * they should be freed first. 60 * </para></note> 61 */ 62void 63g_list_free (GList *list) 64{ 65 g_slice_free_chain (GList, list, next); 66} 67 68/** 69 * g_list_free_1: 70 * @list: a #GList element 71 * 72 * Frees one #GList element. 73 * It is usually used after g_list_remove_link(). 74 */ 75void 76g_list_free_1 (GList *list) 77{ 78 _g_list_free1 (list); 79} 80 81/** 82 * g_list_append: 83 * @list: a pointer to a #GList 84 * @data: the data for the new element 85 * 86 * Adds a new element on to the end of the list. 87 * 88 * <note><para> 89 * The return value is the new start of the list, which 90 * may have changed, so make sure you store the new value. 91 * </para></note> 92 * 93 * <note><para> 94 * Note that g_list_append() has to traverse the entire list 95 * to find the end, which is inefficient when adding multiple 96 * elements. A common idiom to avoid the inefficiency is to prepend 97 * the elements and reverse the list when all elements have been added. 98 * </para></note> 99 * 100 * |[ 101 * /* Notice that these are initialized to the empty list. */ 102 * GList *list = NULL, *number_list = NULL; 103 * 104 * /* This is a list of strings. */ 105 * list = g_list_append (list, "first"); 106 * list = g_list_append (list, "second"); 107 * 108 * /* This is a list of integers. */ 109 * number_list = g_list_append (number_list, GINT_TO_POINTER (27)); 110 * number_list = g_list_append (number_list, GINT_TO_POINTER (14)); 111 * ]| 112 * 113 * Returns: the new start of the #GList 114 */ 115GList* 116g_list_append (GList *list, 117 gpointer data) 118{ 119 GList *new_list; 120 GList *last; 121 122 new_list = _g_list_alloc (); 123 new_list->data = data; 124 new_list->next = NULL; 125 126 if (list) 127 { 128 last = g_list_last (list); 129 /* g_assert (last != NULL); */ 130 last->next = new_list; 131 new_list->prev = last; 132 133 return list; 134 } 135 else 136 { 137 new_list->prev = NULL; 138 return new_list; 139 } 140} 141 142/** 143 * g_list_prepend: 144 * @list: a pointer to a #GList 145 * @data: the data for the new element 146 * 147 * Adds a new element on to the start of the list. 148 * 149 * <note><para> 150 * The return value is the new start of the list, which 151 * may have changed, so make sure you store the new value. 152 * </para></note> 153 * 154 * |[ 155 * /* Notice that it is initialized to the empty list. */ 156 * GList *list = NULL; 157 * list = g_list_prepend (list, "last"); 158 * list = g_list_prepend (list, "first"); 159 * ]| 160 * 161 * Returns: the new start of the #GList 162 */ 163GList* 164g_list_prepend (GList *list, 165 gpointer data) 166{ 167 GList *new_list; 168 169 new_list = _g_list_alloc (); 170 new_list->data = data; 171 new_list->next = list; 172 173 if (list) 174 { 175 new_list->prev = list->prev; 176 if (list->prev) 177 list->prev->next = new_list; 178 list->prev = new_list; 179 } 180 else 181 new_list->prev = NULL; 182 183 return new_list; 184} 185 186/** 187 * g_list_insert: 188 * @list: a pointer to a #GList 189 * @data: the data for the new element 190 * @position: the position to insert the element. If this is 191 * negative, or is larger than the number of elements in the 192 * list, the new element is added on to the end of the list. 193 * 194 * Inserts a new element into the list at the given position. 195 * 196 * Returns: the new start of the #GList 197 */ 198GList* 199g_list_insert (GList *list, 200 gpointer data, 201 gint position) 202{ 203 GList *new_list; 204 GList *tmp_list; 205 206 if (position < 0) 207 return g_list_append (list, data); 208 else if (position == 0) 209 return g_list_prepend (list, data); 210 211 tmp_list = g_list_nth (list, position); 212 if (!tmp_list) 213 return g_list_append (list, data); 214 215 new_list = _g_list_alloc (); 216 new_list->data = data; 217 new_list->prev = tmp_list->prev; 218 if (tmp_list->prev) 219 tmp_list->prev->next = new_list; 220 new_list->next = tmp_list; 221 tmp_list->prev = new_list; 222 223 if (tmp_list == list) 224 return new_list; 225 else 226 return list; 227} 228 229/** 230 * g_list_insert_before: 231 * @list: a pointer to a #GList 232 * @sibling: the list element before which the new element 233 * is inserted or %NULL to insert at the end of the list 234 * @data: the data for the new element 235 * 236 * Inserts a new element into the list before the given position. 237 * 238 * Returns: the new start of the #GList 239 */ 240GList* 241g_list_insert_before (GList *list, 242 GList *sibling, 243 gpointer data) 244{ 245 if (!list) 246 { 247 list = g_list_alloc (); 248 list->data = data; 249 g_return_val_if_fail (sibling == NULL, list); 250 return list; 251 } 252 else if (sibling) 253 { 254 GList *node; 255 256 node = _g_list_alloc (); 257 node->data = data; 258 node->prev = sibling->prev; 259 node->next = sibling; 260 sibling->prev = node; 261 if (node->prev) 262 { 263 node->prev->next = node; 264 return list; 265 } 266 else 267 { 268 g_return_val_if_fail (sibling == list, node); 269 return node; 270 } 271 } 272 else 273 { 274 GList *last; 275 276 last = list; 277 while (last->next) 278 last = last->next; 279 280 last->next = _g_list_alloc (); 281 last->next->data = data; 282 last->next->prev = last; 283 last->next->next = NULL; 284 285 return list; 286 } 287} 288 289/** 290 * g_list_concat: 291 * @list1: a #GList 292 * @list2: the #GList to add to the end of the first #GList 293 * 294 * Adds the second #GList onto the end of the first #GList. 295 * Note that the elements of the second #GList are not copied. 296 * They are used directly. 297 * 298 * Returns: the start of the new #GList 299 */ 300GList * 301g_list_concat (GList *list1, GList *list2) 302{ 303 GList *tmp_list; 304 305 if (list2) 306 { 307 tmp_list = g_list_last (list1); 308 if (tmp_list) 309 tmp_list->next = list2; 310 else 311 list1 = list2; 312 list2->prev = tmp_list; 313 } 314 315 return list1; 316} 317 318/** 319 * g_list_remove: 320 * @list: a #GList 321 * @data: the data of the element to remove 322 * 323 * Removes an element from a #GList. 324 * If two elements contain the same data, only the first is removed. 325 * If none of the elements contain the data, the #GList is unchanged. 326 * 327 * Returns: the new start of the #GList 328 */ 329GList* 330g_list_remove (GList *list, 331 gconstpointer data) 332{ 333 GList *tmp; 334 335 tmp = list; 336 while (tmp) 337 { 338 if (tmp->data != data) 339 tmp = tmp->next; 340 else 341 { 342 if (tmp->prev) 343 tmp->prev->next = tmp->next; 344 if (tmp->next) 345 tmp->next->prev = tmp->prev; 346 347 if (list == tmp) 348 list = list->next; 349 350 _g_list_free1 (tmp); 351 352 break; 353 } 354 } 355 return list; 356} 357 358/** 359 * g_list_remove_all: 360 * @list: a #GList 361 * @data: data to remove 362 * 363 * Removes all list nodes with data equal to @data. 364 * Returns the new head of the list. Contrast with 365 * g_list_remove() which removes only the first node 366 * matching the given data. 367 * 368 * Returns: new head of @list 369 */ 370GList* 371g_list_remove_all (GList *list, 372 gconstpointer data) 373{ 374 GList *tmp = list; 375 376 while (tmp) 377 { 378 if (tmp->data != data) 379 tmp = tmp->next; 380 else 381 { 382 GList *next = tmp->next; 383 384 if (tmp->prev) 385 tmp->prev->next = next; 386 else 387 list = next; 388 if (next) 389 next->prev = tmp->prev; 390 391 _g_list_free1 (tmp); 392 tmp = next; 393 } 394 } 395 return list; 396} 397 398static inline GList* 399_g_list_remove_link (GList *list, 400 GList *link) 401{ 402 if (link) 403 { 404 if (link->prev) 405 link->prev->next = link->next; 406 if (link->next) 407 link->next->prev = link->prev; 408 409 if (link == list) 410 list = list->next; 411 412 link->next = NULL; 413 link->prev = NULL; 414 } 415 416 return list; 417} 418 419/** 420 * g_list_remove_link: 421 * @list: a #GList 422 * @llink: an element in the #GList 423 * 424 * Removes an element from a #GList, without freeing the element. 425 * The removed element's prev and next links are set to %NULL, so 426 * that it becomes a self-contained list with one element. 427 * 428 * Returns: the new start of the #GList, without the element 429 */ 430GList* 431g_list_remove_link (GList *list, 432 GList *llink) 433{ 434 return _g_list_remove_link (list, llink); 435} 436 437/** 438 * g_list_delete_link: 439 * @list: a #GList 440 * @link_: node to delete from @list 441 * 442 * Removes the node link_ from the list and frees it. 443 * Compare this to g_list_remove_link() which removes the node 444 * without freeing it. 445 * 446 * Returns: the new head of @list 447 */ 448GList* 449g_list_delete_link (GList *list, 450 GList *link_) 451{ 452 list = _g_list_remove_link (list, link_); 453 _g_list_free1 (link_); 454 455 return list; 456} 457 458/** 459 * g_list_copy: 460 * @list: a #GList 461 * 462 * Copies a #GList. 463 * 464 * <note><para> 465 * Note that this is a "shallow" copy. If the list elements 466 * consist of pointers to data, the pointers are copied but 467 * the actual data is not. 468 * </para></note> 469 * 470 * Returns: a copy of @list 471 */ 472GList* 473g_list_copy (GList *list) 474{ 475 GList *new_list = NULL; 476 477 if (list) 478 { 479 GList *last; 480 481 new_list = _g_list_alloc (); 482 new_list->data = list->data; 483 new_list->prev = NULL; 484 last = new_list; 485 list = list->next; 486 while (list) 487 { 488 last->next = _g_list_alloc (); 489 last->next->prev = last; 490 last = last->next; 491 last->data = list->data; 492 list = list->next; 493 } 494 last->next = NULL; 495 } 496 497 return new_list; 498} 499 500/** 501 * g_list_reverse: 502 * @list: a #GList 503 * 504 * Reverses a #GList. 505 * It simply switches the next and prev pointers of each element. 506 * 507 * Returns: the start of the reversed #GList 508 */ 509GList* 510g_list_reverse (GList *list) 511{ 512 GList *last; 513 514 last = NULL; 515 while (list) 516 { 517 last = list; 518 list = last->next; 519 last->next = last->prev; 520 last->prev = list; 521 } 522 523 return last; 524} 525 526/** 527 * g_list_nth: 528 * @list: a #GList 529 * @n: the position of the element, counting from 0 530 * 531 * Gets the element at the given position in a #GList. 532 * 533 * Returns: the element, or %NULL if the position is off 534 * the end of the #GList 535 */ 536GList* 537g_list_nth (GList *list, 538 guint n) 539{ 540 while ((n-- > 0) && list) 541 list = list->next; 542 543 return list; 544} 545 546/** 547 * g_list_nth_prev: 548 * @list: a #GList 549 * @n: the position of the element, counting from 0 550 * 551 * Gets the element @n places before @list. 552 * 553 * Returns: the element, or %NULL if the position is 554 * off the end of the #GList 555 */ 556GList* 557g_list_nth_prev (GList *list, 558 guint n) 559{ 560 while ((n-- > 0) && list) 561 list = list->prev; 562 563 return list; 564} 565 566/** 567 * g_list_nth_data: 568 * @list: a #GList 569 * @n: the position of the element 570 * 571 * Gets the data of the element at the given position. 572 * 573 * Returns: the element's data, or %NULL if the position 574 * is off the end of the #GList 575 */ 576gpointer 577g_list_nth_data (GList *list, 578 guint n) 579{ 580 while ((n-- > 0) && list) 581 list = list->next; 582 583 return list ? list->data : NULL; 584} 585 586/** 587 * g_list_find: 588 * @list: a #GList 589 * @data: the element data to find 590 * 591 * Finds the element in a #GList which 592 * contains the given data. 593 * 594 * Returns: the found #GList element, 595 * or %NULL if it is not found 596 */ 597GList* 598g_list_find (GList *list, 599 gconstpointer data) 600{ 601 while (list) 602 { 603 if (list->data == data) 604 break; 605 list = list->next; 606 } 607 608 return list; 609} 610 611/** 612 * g_list_find_custom: 613 * @list: a #GList 614 * @data: user data passed to the function 615 * @func: the function to call for each element. 616 * It should return 0 when the desired element is found 617 * 618 * Finds an element in a #GList, using a supplied function to 619 * find the desired element. It iterates over the list, calling 620 * the given function which should return 0 when the desired 621 * element is found. The function takes two #gconstpointer arguments, 622 * the #GList element's data as the first argument and the 623 * given user data. 624 * 625 * Returns: the found #GList element, or %NULL if it is not found 626 */ 627GList* 628g_list_find_custom (GList *list, 629 gconstpointer data, 630 GCompareFunc func) 631{ 632 g_return_val_if_fail (func != NULL, list); 633 634 while (list) 635 { 636 if (! func (list->data, data)) 637 return list; 638 list = list->next; 639 } 640 641 return NULL; 642} 643 644 645/** 646 * g_list_position: 647 * @list: a #GList 648 * @llink: an element in the #GList 649 * 650 * Gets the position of the given element 651 * in the #GList (starting from 0). 652 * 653 * Returns: the position of the element in the #GList, 654 * or -1 if the element is not found 655 */ 656gint 657g_list_position (GList *list, 658 GList *llink) 659{ 660 gint i; 661 662 i = 0; 663 while (list) 664 { 665 if (list == llink) 666 return i; 667 i++; 668 list = list->next; 669 } 670 671 return -1; 672} 673 674/** 675 * g_list_index: 676 * @list: a #GList 677 * @data: the data to find 678 * 679 * Gets the position of the element containing 680 * the given data (starting from 0). 681 * 682 * Returns: the index of the element containing the data, 683 * or -1 if the data is not found 684 */ 685gint 686g_list_index (GList *list, 687 gconstpointer data) 688{ 689 gint i; 690 691 i = 0; 692 while (list) 693 { 694 if (list->data == data) 695 return i; 696 i++; 697 list = list->next; 698 } 699 700 return -1; 701} 702 703/** 704 * g_list_last: 705 * @list: a #GList 706 * 707 * Gets the last element in a #GList. 708 * 709 * Returns: the last element in the #GList, 710 * or %NULL if the #GList has no elements 711 */ 712GList* 713g_list_last (GList *list) 714{ 715 if (list) 716 { 717 while (list->next) 718 list = list->next; 719 } 720 721 return list; 722} 723 724/** 725 * g_list_first: 726 * @list: a #GList 727 * 728 * Gets the first element in a #GList. 729 * 730 * Returns: the first element in the #GList, 731 * or %NULL if the #GList has no elements 732 */ 733GList* 734g_list_first (GList *list) 735{ 736 if (list) 737 { 738 while (list->prev) 739 list = list->prev; 740 } 741 742 return list; 743} 744 745/** 746 * g_list_length: 747 * @list: a #GList 748 * 749 * Gets the number of elements in a #GList. 750 * 751 * <note><para> 752 * This function iterates over the whole list to 753 * count its elements. 754 * </para></note> 755 * 756 * Returns: the number of elements in the #GList 757 */ 758guint 759g_list_length (GList *list) 760{ 761 guint length; 762 763 length = 0; 764 while (list) 765 { 766 length++; 767 list = list->next; 768 } 769 770 return length; 771} 772 773/** 774 * g_list_foreach: 775 * @list: a #GList 776 * @func: the function to call with each element's data 777 * @user_data: user data to pass to the function 778 * 779 * Calls a function for each element of a #GList. 780 */ 781void 782g_list_foreach (GList *list, 783 GFunc func, 784 gpointer user_data) 785{ 786 while (list) 787 { 788 GList *next = list->next; 789 (*func) (list->data, user_data); 790 list = next; 791 } 792} 793 794static GList* 795g_list_insert_sorted_real (GList *list, 796 gpointer data, 797 GFunc func, 798 gpointer user_data) 799{ 800 GList *tmp_list = list; 801 GList *new_list; 802 gint cmp; 803 804 g_return_val_if_fail (func != NULL, list); 805 806 if (!list) 807 { 808 new_list = _g_list_alloc0 (); 809 new_list->data = data; 810 return new_list; 811 } 812 813 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); 814 815 while ((tmp_list->next) && (cmp > 0)) 816 { 817 tmp_list = tmp_list->next; 818 819 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); 820 } 821 822 new_list = _g_list_alloc0 (); 823 new_list->data = data; 824 825 if ((!tmp_list->next) && (cmp > 0)) 826 { 827 tmp_list->next = new_list; 828 new_list->prev = tmp_list; 829 return list; 830 } 831 832 if (tmp_list->prev) 833 { 834 tmp_list->prev->next = new_list; 835 new_list->prev = tmp_list->prev; 836 } 837 new_list->next = tmp_list; 838 tmp_list->prev = new_list; 839 840 if (tmp_list == list) 841 return new_list; 842 else 843 return list; 844} 845 846/** 847 * g_list_insert_sorted: 848 * @list: a pointer to a #GList 849 * @data: the data for the new element 850 * @func: the function to compare elements in the list. It should 851 * return a number > 0 if the first parameter comes after the 852 * second parameter in the sort order. 853 * 854 * Inserts a new element into the list, using the given comparison 855 * function to determine its position. 856 * 857 * Returns: the new start of the #GList 858 */ 859GList* 860g_list_insert_sorted (GList *list, 861 gpointer data, 862 GCompareFunc func) 863{ 864 return g_list_insert_sorted_real (list, data, (GFunc) func, NULL); 865} 866 867/** 868 * g_list_insert_sorted_with_data: 869 * @list: a pointer to a #GList 870 * @data: the data for the new element 871 * @func: the function to compare elements in the list. 872 * It should return a number > 0 if the first parameter 873 * comes after the second parameter in the sort order. 874 * @user_data: user data to pass to comparison function. 875 * 876 * Inserts a new element into the list, using the given comparison 877 * function to determine its position. 878 * 879 * Returns: the new start of the #GList 880 * 881 * Since: 2.10 882 */ 883GList* 884g_list_insert_sorted_with_data (GList *list, 885 gpointer data, 886 GCompareDataFunc func, 887 gpointer user_data) 888{ 889 return g_list_insert_sorted_real (list, data, (GFunc) func, user_data); 890} 891 892static GList * 893g_list_sort_merge (GList *l1, 894 GList *l2, 895 GFunc compare_func, 896 gpointer user_data) 897{ 898 GList list, *l, *lprev; 899 gint cmp; 900 901 l = &list; 902 lprev = NULL; 903 904 while (l1 && l2) 905 { 906 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data); 907 908 if (cmp <= 0) 909 { 910 l->next = l1; 911 l1 = l1->next; 912 } 913 else 914 { 915 l->next = l2; 916 l2 = l2->next; 917 } 918 l = l->next; 919 l->prev = lprev; 920 lprev = l; 921 } 922 l->next = l1 ? l1 : l2; 923 l->next->prev = l; 924 925 return list.next; 926} 927 928static GList* 929g_list_sort_real (GList *list, 930 GFunc compare_func, 931 gpointer user_data) 932{ 933 GList *l1, *l2; 934 935 if (!list) 936 return NULL; 937 if (!list->next) 938 return list; 939 940 l1 = list; 941 l2 = list->next; 942 943 while ((l2 = l2->next) != NULL) 944 { 945 if ((l2 = l2->next) == NULL) 946 break; 947 l1 = l1->next; 948 } 949 l2 = l1->next; 950 l1->next = NULL; 951 952 return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data), 953 g_list_sort_real (l2, compare_func, user_data), 954 compare_func, 955 user_data); 956} 957 958/** 959 * g_list_sort: 960 * @list: a #GList 961 * @compare_func: the comparison function used to sort the #GList. 962 * This function is passed the data from 2 elements of the #GList 963 * and should return 0 if they are equal, a negative value if the 964 * first element comes before the second, or a positive value if 965 * the first element comes after the second. 966 * 967 * Sorts a #GList using the given comparison function. 968 * 969 * Returns: the start of the sorted #GList 970 */ 971GList * 972g_list_sort (GList *list, 973 GCompareFunc compare_func) 974{ 975 return g_list_sort_real (list, (GFunc) compare_func, NULL); 976 977} 978 979/** 980 * g_list_sort_with_data: 981 * @list: a #GList 982 * @compare_func: comparison function 983 * @user_data: user data to pass to comparison function 984 * 985 * Like g_list_sort(), but the comparison function accepts 986 * a user data argument. 987 * 988 * Returns: the new head of @list 989 */ 990GList * 991g_list_sort_with_data (GList *list, 992 GCompareDataFunc compare_func, 993 gpointer user_data) 994{ 995 return g_list_sort_real (list, (GFunc) compare_func, user_data); 996} 997 998#define __G_LIST_C__ 999#include "galiasdef.c" 1000