glist.c revision c9bd7542e1a28ba9de60048361c0a97d251833e7
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 GCompareFunc compare_func) 602{ 603 GList list, *l, *lprev; 604 605 l = &list; 606 lprev = NULL; 607 608 while (l1 && l2) 609 { 610 if (compare_func (l1->data, l2->data) < 0) 611 { 612 l->next = l1; 613 l = l->next; 614 l->prev = lprev; 615 lprev = l; 616 l1 = l1->next; 617 } 618 else 619 { 620 l->next = l2; 621 l = l->next; 622 l->prev = lprev; 623 lprev = l; 624 l2 = l2->next; 625 } 626 } 627 l->next = l1 ? l1 : l2; 628 l->next->prev = l; 629 630 return list.next; 631} 632 633GList* 634g_list_sort (GList *list, 635 GCompareFunc compare_func) 636{ 637 GList *l1, *l2; 638 639 if (!list) 640 return NULL; 641 if (!list->next) 642 return list; 643 644 l1 = list; 645 l2 = list->next; 646 647 while ((l2 = l2->next) != NULL) 648 { 649 if ((l2 = l2->next) == NULL) 650 break; 651 l1 = l1->next; 652 } 653 l2 = l1->next; 654 l1->next = NULL; 655 656 return g_list_sort_merge (g_list_sort (list, compare_func), 657 g_list_sort (l2, compare_func), 658 compare_func); 659} 660 661GList* 662g_list_sort2 (GList *list, 663 GCompareFunc compare_func) 664{ 665 GSList *runs = NULL; 666 GList *tmp; 667 668 /* Degenerate case. */ 669 if (!list) return NULL; 670 671 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */ 672 for (tmp = list; tmp; ) 673 { 674 GList *tmp2; 675 for (tmp2 = tmp; 676 tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0; 677 tmp2 = tmp2->next) 678 /* Nothing */; 679 runs = g_slist_append (runs, tmp); 680 tmp = tmp2->next; 681 tmp2->next = NULL; 682 } 683 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */ 684 685 while (runs->next) 686 { 687 /* We have more than one run. Merge pairwise. */ 688 GSList *dst, *src, *dstprev = NULL; 689 dst = src = runs; 690 while (src && src->next) 691 { 692 dst->data = g_list_sort_merge (src->data, 693 src->next->data, 694 compare_func); 695 dstprev = dst; 696 dst = dst->next; 697 src = src->next->next; 698 } 699 700 /* If number of runs was odd, just keep the last. */ 701 if (src) 702 { 703 dst->data = src->data; 704 dstprev = dst; 705 dst = dst->next; 706 } 707 708 dstprev->next = NULL; 709 g_slist_free (dst); 710 } 711 712 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */ 713 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */ 714 715 list = runs->data; 716 g_slist_free (runs); 717 return list; 718} 719