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