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