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 * Modified by Bruno Haible for use as a gnulib module. 29 */ 30 31/* 32 * MT safe 33 */ 34 35#include "config.h" 36 37#include "glib.h" 38#if 0 39#include "galias.h" 40#endif 41 42 43#if 0 44void g_list_push_allocator (gpointer dummy) { /* present for binary compat only */ } 45void g_list_pop_allocator (void) { /* present for binary compat only */ } 46#endif 47 48#define _g_list_alloc() g_slice_new (GList) 49#define _g_list_alloc0() g_slice_new0 (GList) 50#define _g_list_free1(list) g_slice_free (GList, list) 51 52#if 0 53 54GList* 55g_list_alloc (void) 56{ 57 return _g_list_alloc0 (); 58} 59 60#endif 61 62void 63g_list_free (GList *list) 64{ 65 while (list) 66 { 67 GList *n = list->next; 68 g_slice_free (GList, list); 69 list = n; 70 } 71} 72 73#if 0 74 75void 76g_list_free_1 (GList *list) 77{ 78 _g_list_free1 (list); 79} 80 81#endif 82 83GList* 84g_list_append (GList *list, 85 gpointer data) 86{ 87 GList *new_list; 88 GList *last; 89 90 new_list = _g_list_alloc (); 91 new_list->data = data; 92 new_list->next = NULL; 93 94 if (list) 95 { 96 last = g_list_last (list); 97 /* g_assert (last != NULL); */ 98 last->next = new_list; 99 new_list->prev = last; 100 101 return list; 102 } 103 else 104 { 105 new_list->prev = NULL; 106 return new_list; 107 } 108} 109 110GList* 111g_list_prepend (GList *list, 112 gpointer data) 113{ 114 GList *new_list; 115 116 new_list = _g_list_alloc (); 117 new_list->data = data; 118 new_list->next = list; 119 120 if (list) 121 { 122 new_list->prev = list->prev; 123 if (list->prev) 124 list->prev->next = new_list; 125 list->prev = new_list; 126 } 127 else 128 new_list->prev = NULL; 129 130 return new_list; 131} 132 133#if 0 134 135GList* 136g_list_insert (GList *list, 137 gpointer data, 138 gint position) 139{ 140 GList *new_list; 141 GList *tmp_list; 142 143 if (position < 0) 144 return g_list_append (list, data); 145 else if (position == 0) 146 return g_list_prepend (list, data); 147 148 tmp_list = g_list_nth (list, position); 149 if (!tmp_list) 150 return g_list_append (list, data); 151 152 new_list = _g_list_alloc (); 153 new_list->data = data; 154 new_list->prev = tmp_list->prev; 155 if (tmp_list->prev) 156 tmp_list->prev->next = new_list; 157 new_list->next = tmp_list; 158 tmp_list->prev = new_list; 159 160 if (tmp_list == list) 161 return new_list; 162 else 163 return list; 164} 165 166GList* 167g_list_insert_before (GList *list, 168 GList *sibling, 169 gpointer data) 170{ 171 if (!list) 172 { 173 list = g_list_alloc (); 174 list->data = data; 175 g_return_val_if_fail (sibling == NULL, list); 176 return list; 177 } 178 else if (sibling) 179 { 180 GList *node; 181 182 node = _g_list_alloc (); 183 node->data = data; 184 node->prev = sibling->prev; 185 node->next = sibling; 186 sibling->prev = node; 187 if (node->prev) 188 { 189 node->prev->next = node; 190 return list; 191 } 192 else 193 { 194 g_return_val_if_fail (sibling == list, node); 195 return node; 196 } 197 } 198 else 199 { 200 GList *last; 201 202 last = list; 203 while (last->next) 204 last = last->next; 205 206 last->next = _g_list_alloc (); 207 last->next->data = data; 208 last->next->prev = last; 209 last->next->next = NULL; 210 211 return list; 212 } 213} 214 215GList * 216g_list_concat (GList *list1, GList *list2) 217{ 218 GList *tmp_list; 219 220 if (list2) 221 { 222 tmp_list = g_list_last (list1); 223 if (tmp_list) 224 tmp_list->next = list2; 225 else 226 list1 = list2; 227 list2->prev = tmp_list; 228 } 229 230 return list1; 231} 232 233GList* 234g_list_remove (GList *list, 235 gconstpointer data) 236{ 237 GList *tmp; 238 239 tmp = list; 240 while (tmp) 241 { 242 if (tmp->data != data) 243 tmp = tmp->next; 244 else 245 { 246 if (tmp->prev) 247 tmp->prev->next = tmp->next; 248 if (tmp->next) 249 tmp->next->prev = tmp->prev; 250 251 if (list == tmp) 252 list = list->next; 253 254 _g_list_free1 (tmp); 255 256 break; 257 } 258 } 259 return list; 260} 261 262GList* 263g_list_remove_all (GList *list, 264 gconstpointer data) 265{ 266 GList *tmp = list; 267 268 while (tmp) 269 { 270 if (tmp->data != data) 271 tmp = tmp->next; 272 else 273 { 274 GList *next = tmp->next; 275 276 if (tmp->prev) 277 tmp->prev->next = next; 278 else 279 list = next; 280 if (next) 281 next->prev = tmp->prev; 282 283 _g_list_free1 (tmp); 284 tmp = next; 285 } 286 } 287 return list; 288} 289 290#endif 291 292static inline GList* 293_g_list_remove_link (GList *list, 294 GList *link) 295{ 296 if (link) 297 { 298 if (link->prev) 299 link->prev->next = link->next; 300 if (link->next) 301 link->next->prev = link->prev; 302 303 if (link == list) 304 list = list->next; 305 306 link->next = NULL; 307 link->prev = NULL; 308 } 309 310 return list; 311} 312 313#if 0 314 315GList* 316g_list_remove_link (GList *list, 317 GList *link) 318{ 319 return _g_list_remove_link (list, link); 320} 321 322#endif 323 324GList* 325g_list_delete_link (GList *list, 326 GList *link) 327{ 328 list = _g_list_remove_link (list, link); 329 _g_list_free1 (link); 330 331 return list; 332} 333 334#if 0 335 336GList* 337g_list_copy (GList *list) 338{ 339 GList *new_list = NULL; 340 341 if (list) 342 { 343 GList *last; 344 345 new_list = _g_list_alloc (); 346 new_list->data = list->data; 347 new_list->prev = NULL; 348 last = new_list; 349 list = list->next; 350 while (list) 351 { 352 last->next = _g_list_alloc (); 353 last->next->prev = last; 354 last = last->next; 355 last->data = list->data; 356 list = list->next; 357 } 358 last->next = NULL; 359 } 360 361 return new_list; 362} 363 364GList* 365g_list_reverse (GList *list) 366{ 367 GList *last; 368 369 last = NULL; 370 while (list) 371 { 372 last = list; 373 list = last->next; 374 last->next = last->prev; 375 last->prev = list; 376 } 377 378 return last; 379} 380 381GList* 382g_list_nth (GList *list, 383 guint n) 384{ 385 while ((n-- > 0) && list) 386 list = list->next; 387 388 return list; 389} 390 391GList* 392g_list_nth_prev (GList *list, 393 guint n) 394{ 395 while ((n-- > 0) && list) 396 list = list->prev; 397 398 return list; 399} 400 401gpointer 402g_list_nth_data (GList *list, 403 guint n) 404{ 405 while ((n-- > 0) && list) 406 list = list->next; 407 408 return list ? list->data : NULL; 409} 410 411GList* 412g_list_find (GList *list, 413 gconstpointer data) 414{ 415 while (list) 416 { 417 if (list->data == data) 418 break; 419 list = list->next; 420 } 421 422 return list; 423} 424 425GList* 426g_list_find_custom (GList *list, 427 gconstpointer data, 428 GCompareFunc func) 429{ 430 g_return_val_if_fail (func != NULL, list); 431 432 while (list) 433 { 434 if (! func (list->data, data)) 435 return list; 436 list = list->next; 437 } 438 439 return NULL; 440} 441 442 443gint 444g_list_position (GList *list, 445 GList *link) 446{ 447 gint i; 448 449 i = 0; 450 while (list) 451 { 452 if (list == link) 453 return i; 454 i++; 455 list = list->next; 456 } 457 458 return -1; 459} 460 461gint 462g_list_index (GList *list, 463 gconstpointer data) 464{ 465 gint i; 466 467 i = 0; 468 while (list) 469 { 470 if (list->data == data) 471 return i; 472 i++; 473 list = list->next; 474 } 475 476 return -1; 477} 478 479#endif 480 481GList* 482g_list_last (GList *list) 483{ 484 if (list) 485 { 486 while (list->next) 487 list = list->next; 488 } 489 490 return list; 491} 492 493#if 0 494 495GList* 496g_list_first (GList *list) 497{ 498 if (list) 499 { 500 while (list->prev) 501 list = list->prev; 502 } 503 504 return list; 505} 506 507guint 508g_list_length (GList *list) 509{ 510 guint length; 511 512 length = 0; 513 while (list) 514 { 515 length++; 516 list = list->next; 517 } 518 519 return length; 520} 521 522void 523g_list_foreach (GList *list, 524 GFunc func, 525 gpointer user_data) 526{ 527 while (list) 528 { 529 GList *next = list->next; 530 (*func) (list->data, user_data); 531 list = next; 532 } 533} 534 535static GList* 536g_list_insert_sorted_real (GList *list, 537 gpointer data, 538 GFunc func, 539 gpointer user_data) 540{ 541 GList *tmp_list = list; 542 GList *new_list; 543 gint cmp; 544 545 g_return_val_if_fail (func != NULL, list); 546 547 if (!list) 548 { 549 new_list = _g_list_alloc0 (); 550 new_list->data = data; 551 return new_list; 552 } 553 554 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); 555 556 while ((tmp_list->next) && (cmp > 0)) 557 { 558 tmp_list = tmp_list->next; 559 560 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data); 561 } 562 563 new_list = _g_list_alloc0 (); 564 new_list->data = data; 565 566 if ((!tmp_list->next) && (cmp > 0)) 567 { 568 tmp_list->next = new_list; 569 new_list->prev = tmp_list; 570 return list; 571 } 572 573 if (tmp_list->prev) 574 { 575 tmp_list->prev->next = new_list; 576 new_list->prev = tmp_list->prev; 577 } 578 new_list->next = tmp_list; 579 tmp_list->prev = new_list; 580 581 if (tmp_list == list) 582 return new_list; 583 else 584 return list; 585} 586 587GList* 588g_list_insert_sorted (GList *list, 589 gpointer data, 590 GCompareFunc func) 591{ 592 return g_list_insert_sorted_real (list, data, (GFunc) func, NULL); 593} 594 595GList* 596g_list_insert_sorted_with_data (GList *list, 597 gpointer data, 598 GCompareDataFunc func, 599 gpointer user_data) 600{ 601 return g_list_insert_sorted_real (list, data, (GFunc) func, user_data); 602} 603 604static GList * 605g_list_sort_merge (GList *l1, 606 GList *l2, 607 GFunc compare_func, 608 gpointer user_data) 609{ 610 GList list, *l, *lprev; 611 gint cmp; 612 613 l = &list; 614 lprev = NULL; 615 616 while (l1 && l2) 617 { 618 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data); 619 620 if (cmp <= 0) 621 { 622 l->next = l1; 623 l1 = l1->next; 624 } 625 else 626 { 627 l->next = l2; 628 l2 = l2->next; 629 } 630 l = l->next; 631 l->prev = lprev; 632 lprev = l; 633 } 634 l->next = l1 ? l1 : l2; 635 l->next->prev = l; 636 637 return list.next; 638} 639 640static GList* 641g_list_sort_real (GList *list, 642 GFunc compare_func, 643 gpointer user_data) 644{ 645 GList *l1, *l2; 646 647 if (!list) 648 return NULL; 649 if (!list->next) 650 return list; 651 652 l1 = list; 653 l2 = list->next; 654 655 while ((l2 = l2->next) != NULL) 656 { 657 if ((l2 = l2->next) == NULL) 658 break; 659 l1 = l1->next; 660 } 661 l2 = l1->next; 662 l1->next = NULL; 663 664 return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data), 665 g_list_sort_real (l2, compare_func, user_data), 666 compare_func, 667 user_data); 668} 669 670GList * 671g_list_sort (GList *list, 672 GCompareFunc compare_func) 673{ 674 return g_list_sort_real (list, (GFunc) compare_func, NULL); 675 676} 677 678GList * 679g_list_sort_with_data (GList *list, 680 GCompareDataFunc compare_func, 681 gpointer user_data) 682{ 683 return g_list_sort_real (list, (GFunc) compare_func, user_data); 684} 685 686#define __G_LIST_C__ 687#include "galiasdef.c" 688#endif 689