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_insert_before (GList   *list,
 322                       GList   *sibling,
 323                       gpointer data)
 324 {
 325   if (!list)
 326     {
 327       list = g_list_alloc ();
 328       list->data = data;
 329       g_return_val_if_fail (sibling == NULL, list);
 330       return list;
 331     }
 332   else if (sibling)
 333     {
 334       GList *node;
 335
 336       node = g_list_alloc ();
 337       node->data = data;
 338       if (sibling->prev)
 339         {
 340           node->prev = sibling->prev;
 341           node->prev->next = node;
 342           node->next = sibling;
 343           sibling->prev = node;
 344           return list;
 345         }
 346       else
 347         {
 348           node->next = sibling;
 349           sibling->prev = node;
 350           g_return_val_if_fail (sibling == list, node);
 351           return node;
 352         }
 353     }
 354   else
 355     {
 356       GList *last;
 357
 358       last = list;
 359       while (last->next)
 360         last = last->next;
 361
 362       last->next = g_list_alloc ();
 363       last->next->data = data;
 364       last->next->prev = last;
 365
 366       return list;
 367     }
 368 }
 369
 370 GList *
 371 g_list_concat (GList *list1, GList *list2)
 372 {
 373   GList *tmp_list;
 374
 375   if (list2)
 376     {
 377       tmp_list = g_list_last (list1);
 378       if (tmp_list)
 379         tmp_list->next = list2;
 380       else
 381         list1 = list2;
 382       list2->prev = tmp_list;
 383     }
 384
 385   return list1;
 386 }
 387
 388 GList*
 389 g_list_remove (GList         *list,
 390                gconstpointer  data)
 391 {
 392   GList *tmp;
 393
 394   tmp = list;
 395   while (tmp)
 396     {
 397       if (tmp->data != data)
 398         tmp = tmp->next;
 399       else
 400         {
 401           if (tmp->prev)
 402             tmp->prev->next = tmp->next;
 403           if (tmp->next)
 404             tmp->next->prev = tmp->prev;
 405
 406           if (list == tmp)
 407             list = list->next;
 408
 409           _g_list_free_1 (tmp);
 410
 411           break;
 412         }
 413     }
 414   return list;
 415 }
 416
 417 GList*
 418 g_list_remove_all (GList        *list,
 419                    gconstpointer data)
 420 {
 421   GList *tmp = list;
 422
 423   while (tmp)
 424     {
 425       if (tmp->data != data)
 426         tmp = tmp->next;
 427       else
 428         {
 429           GList *next = tmp->next;
 430
 431           if (tmp->prev)
 432             tmp->prev->next = next;
 433           else
 434             list = next;
 435           if (next)
 436             next->prev = tmp->prev;
 437
 438           _g_list_free_1 (tmp);
 439           tmp = next;
 440         }
 441     }
 442   return list;
 443 }
 444
 445 static inline GList*
 446 _g_list_remove_link (GList *list,
 447                      GList *link)
 448 {
 449   if (link)
 450     {
 451       if (link->prev)
 452         link->prev->next = link->next;
 453       if (link->next)
 454         link->next->prev = link->prev;
 455
 456       if (link == list)
 457         list = list->next;
 458
 459       link->next = NULL;
 460       link->prev = NULL;
 461     }
 462
 463   return list;
 464 }
 465
 466 GList*
 467 g_list_remove_link (GList *list,
 468                     GList *link)
 469 {
 470   return _g_list_remove_link (list, link);
 471 }
 472
 473 GList*
 474 g_list_delete_link (GList *list,
 475                     GList *link)
 476 {
 477   list = _g_list_remove_link (list, link);
 478   _g_list_free_1 (link);
 479
 480   return list;
 481 }
 482
 483 GList*
 484 g_list_copy (GList *list)
 485 {
 486   GList *new_list = NULL;
 487
 488   if (list)
 489     {
 490       GList *last;
 491
 492       new_list = _g_list_alloc ();
 493       new_list->data = list->data;
 494       last = new_list;
 495       list = list->next;
 496       while (list)
 497         {
 498           last->next = _g_list_alloc ();
 499           last->next->prev = last;
 500           last = last->next;
 501           last->data = list->data;
 502           list = list->next;
 503         }
 504     }
 505
 506   return new_list;
 507 }
 508
 509 GList*
 510 g_list_reverse (GList *list)
 511 {
 512   GList *last;
 513
 514   last = NULL;
 515   while (list)
 516     {
 517       last = list;
 518       list = last->next;
 519       last->next = last->prev;
 520       last->prev = list;
 521     }
 522
 523   return last;
 524 }
 525
 526 GList*
 527 g_list_nth (GList *list,
 528             guint  n)
 529 {
 530   while ((n-- > 0) && list)
 531     list = list->next;
 532
 533   return list;
 534 }
 535
 536 GList*
 537 g_list_nth_prev (GList *list,
 538                  guint  n)
 539 {
 540   while ((n-- > 0) && list)
 541     list = list->prev;
 542
 543   return list;
 544 }
 545
 546 gpointer
 547 g_list_nth_data (GList     *list,
 548                  guint      n)
 549 {
 550   while ((n-- > 0) && list)
 551     list = list->next;
 552
 553   return list ? list->data : NULL;
 554 }
 555
 556 GList*
 557 g_list_find (GList         *list,
 558              gconstpointer  data)
 559 {
 560   while (list)
 561     {
 562       if (list->data == data)
 563         break;
 564       list = list->next;
 565     }
 566
 567   return list;
 568 }
 569
 570 GList*
 571 g_list_find_custom (GList         *list,
 572                     gconstpointer  data,
 573                     GCompareFunc   func)
 574 {
 575   g_return_val_if_fail (func != NULL, list);
 576
 577   while (list)
 578     {
 579       if (! func (list->data, data))
 580         return list;
 581       list = list->next;
 582     }
 583
 584   return NULL;
 585 }
 586
 587
 588 gint
 589 g_list_position (GList *list,
 590                  GList *link)
 591 {
 592   gint i;
 593
 594   i = 0;
 595   while (list)
 596     {
 597       if (list == link)
 598         return i;
 599       i++;
 600       list = list->next;
 601     }
 602
 603   return -1;
 604 }
 605
 606 gint
 607 g_list_index (GList         *list,
 608               gconstpointer  data)
 609 {
 610   gint i;
 611
 612   i = 0;
 613   while (list)
 614     {
 615       if (list->data == data)
 616         return i;
 617       i++;
 618       list = list->next;
 619     }
 620
 621   return -1;
 622 }
 623
 624 GList*
 625 g_list_last (GList *list)
 626 {
 627   if (list)
 628     {
 629       while (list->next)
 630         list = list->next;
 631     }
 632
 633   return list;
 634 }
 635
 636 GList*
 637 g_list_first (GList *list)
 638 {
 639   if (list)
 640     {
 641       while (list->prev)
 642         list = list->prev;
 643     }
 644
 645   return list;
 646 }
 647
 648 guint
 649 g_list_length (GList *list)
 650 {
 651   guint length;
 652
 653   length = 0;
 654   while (list)
 655     {
 656       length++;
 657       list = list->next;
 658     }
 659
 660   return length;
 661 }
 662
 663 void
 664 g_list_foreach (GList    *list,
 665                 GFunc     func,
 666                 gpointer  user_data)
 667 {
 668   while (list)
 669     {
 670       GList *next = list->next;
 671       (*func) (list->data, user_data);
 672       list = next;
 673     }
 674 }
 675
 676
 677 GList*
 678 g_list_insert_sorted (GList        *list,
 679                       gpointer      data,
 680                       GCompareFunc  func)
 681 {
 682   GList *tmp_list = list;
 683   GList *new_list;
 684   gint cmp;
 685
 686   g_return_val_if_fail (func != NULL, list);
 687
 688   if (!list)
 689     {
 690       new_list = _g_list_alloc ();
 691       new_list->data = data;
 692       return new_list;
 693     }
 694
 695   cmp = (*func) (data, tmp_list->data);
 696
 697   while ((tmp_list->next) && (cmp > 0))
 698     {
 699       tmp_list = tmp_list->next;
 700       cmp = (*func) (data, tmp_list->data);
 701     }
 702
 703   new_list = _g_list_alloc ();
 704   new_list->data = data;
 705
 706   if ((!tmp_list->next) && (cmp > 0))
 707     {
 708       tmp_list->next = new_list;
 709       new_list->prev = tmp_list;
 710       return list;
 711     }
 712
 713   if (tmp_list->prev)
 714     {
 715       tmp_list->prev->next = new_list;
 716       new_list->prev = tmp_list->prev;
 717     }
 718   new_list->next = tmp_list;
 719   tmp_list->prev = new_list;
 720
 721   if (tmp_list == list)
 722     return new_list;
 723   else
 724     return list;
 725 }
 726
 727 static GList *
 728 g_list_sort_merge (GList     *l1,
 729                    GList     *l2,
 730                    GFunc     compare_func,
 731                    gboolean  use_data,
 732                    gpointer  user_data)
 733 {
 734   GList list, *l, *lprev;
 735   gint cmp;
 736
 737   l = &list;
 738   lprev = NULL;
 739
 740   while (l1 && l2)
 741     {
 742       if (use_data)
 743         cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 744       else
 745         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 746
 747       if (cmp <= 0)
 748         {
 749           l->next = l1;
 750           l = l->next;
 751           l->prev = lprev;
 752           lprev = l;
 753           l1 = l1->next;
 754         }
 755       else
 756         {
 757           l->next = l2;
 758           l = l->next;
 759           l->prev = lprev;
 760           lprev = l;
 761           l2 = l2->next;
 762         }
 763     }
 764   l->next = l1 ? l1 : l2;
 765   l->next->prev = l;
 766
 767   return list.next;
 768 }
 769
 770 static GList*
 771 g_list_sort_real (GList    *list,
 772                   GFunc     compare_func,
 773                   gboolean  use_data,
 774                   gpointer  user_data)
 775 {
 776   GList *l1, *l2;
 777
 778   if (!list)
 779     return NULL;
 780   if (!list->next)
 781     return list;
 782
 783   l1 = list;
 784   l2 = list->next;
 785
 786   while ((l2 = l2->next) != NULL)
 787     {
 788       if ((l2 = l2->next) == NULL)
 789         break;
 790       l1 = l1->next;
 791     }
 792   l2 = l1->next;
 793   l1->next = NULL;
 794
 795   return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
 796                             g_list_sort_real (l2, compare_func, use_data, user_data),
 797                             compare_func,
 798                             use_data,
 799                             user_data);
 800 }
 801
 802 GList *
 803 g_list_sort (GList        *list,
 804              GCompareFunc  compare_func)
 805 {
 806   return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 807
 808 }
 809
 810 GList *
 811 g_list_sort_with_data (GList            *list,
 812                        GCompareDataFunc  compare_func,
 813                        gpointer          user_data)
 814 {
 815   return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 816 }
 817
 818 static GList*
 819 g_list_sort2 (GList       *list,
 820               GCompareFunc compare_func)
 821 {
 822   GSList *runs = NULL;
 823   GList *tmp;
 824
 825   /* Degenerate case.  */
 826   if (!list) return NULL;
 827
 828   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
 829   for (tmp = list; tmp; )
 830     {
 831       GList *tmp2;
 832       for (tmp2 = tmp;
 833            tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
 834            tmp2 = tmp2->next)
 835         /* Nothing */;
 836       runs = g_slist_append (runs, tmp);
 837       tmp = tmp2->next;
 838       tmp2->next = NULL;
 839     }
 840   /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]].  */
 841
 842   while (runs->next)
 843     {
 844       /* We have more than one run.  Merge pairwise.  */
 845       GSList *dst, *src, *dstprev = NULL;
 846       dst = src = runs;
 847       while (src && src->next)
 848         {
 849           dst->data = g_list_sort_merge (src->data,
 850                                          src->next->data,
 851                                          (GFunc) compare_func,
 852                                          FALSE, NULL);
 853           dstprev = dst;
 854           dst = dst->next;
 855           src = src->next->next;
 856         }
 857
 858       /* If number of runs was odd, just keep the last.  */
 859       if (src)
 860         {
 861           dst->data = src->data;
 862           dstprev = dst;
 863           dst = dst->next;
 864         }
 865
 866       dstprev->next = NULL;
 867       g_slist_free (dst);
 868     }
 869
 870   /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]].  */
 871   /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]].  */
 872
 873   list = runs->data;
 874   g_slist_free (runs);
 875   return list;
 876 }