glist.c

   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
  34 struct _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
  45 static GAllocator       *current_allocator = NULL;
  46 G_LOCK_DEFINE_STATIC (current_allocator);
  47
  48 /* HOLDS: current_allocator_lock */
  49 static void
  50 g_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
  77 void
  78 g_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
  87 void
  88 g_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
 103 static 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
 143 GList*
 144 g_list_alloc (void)
 145 {
 146   return _g_list_alloc ();
 147 }
 148
 149 void
 150 g_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
 176 static 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
 194 void
 195 g_list_free_1 (GList *list)
 196 {
 197   _g_list_free_1 (list);
 198 }
 199
 200 GList*
 201 g_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
 223 GList*
 224 g_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
 246 GList*
 247 g_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
 280 GList *
 281 g_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
 298 GList*
 299 g_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
 327 static 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
 348 GList*
 349 g_list_remove_link (GList *list,
 350                     GList *link)
 351 {
 352   return _g_list_remove_link (list, link);
 353 }
 354
 355 GList*
 356 g_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
 365 GList*
 366 g_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
 391 GList*
 392 g_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
 408 GList*
 409 g_list_nth (GList *list,
 410             guint  n)
 411 {
 412   while ((n-- > 0) && list)
 413     list = list->next;
 414
 415   return list;
 416 }
 417
 418 gpointer
 419 g_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
 428 GList*
 429 g_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
 442 GList*
 443 g_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
 460 gint
 461 g_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
 478 gint
 479 g_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
 496 GList*
 497 g_list_last (GList *list)
 498 {
 499   if (list)
 500     {
 501       while (list->next)
 502         list = list->next;
 503     }
 504
 505   return list;
 506 }
 507
 508 GList*
 509 g_list_first (GList *list)
 510 {
 511   if (list)
 512     {
 513       while (list->prev)
 514         list = list->prev;
 515     }
 516
 517   return list;
 518 }
 519
 520 guint
 521 g_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
 535 void
 536 g_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
 548 GList*
 549 g_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
 598 static GList *
 599 g_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
 641 GList*
 642 g_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
 673 GList *
 674 g_list_sort (GList        *list,
 675              GCompareFunc  compare_func)
 676 {
 677   return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 678
 679 }
 680
 681 GList *
 682 g_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
 689 GList*
 690 g_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 }