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