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