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 static inline GList*
 368 _g_list_remove_link (GList *list,
 369                      GList *link)
 370 {
 371   if (link)
 372     {
 373       if (link->prev)
 374         link->prev->next = link->next;
 375       if (link->next)
 376         link->next->prev = link->prev;
 377
 378       if (link == list)
 379         list = list->next;
 380
 381       link->next = NULL;
 382       link->prev = NULL;
 383     }
 384
 385   return list;
 386 }
 387
 388 GList*
 389 g_list_remove_link (GList *list,
 390                     GList *link)
 391 {
 392   return _g_list_remove_link (list, link);
 393 }
 394
 395 GList*
 396 g_list_delete_link (GList *list,
 397                     GList *link)
 398 {
 399   list = _g_list_remove_link (list, link);
 400   _g_list_free_1 (link);
 401
 402   return list;
 403 }
 404
 405 GList*
 406 g_list_copy (GList *list)
 407 {
 408   GList *new_list = NULL;
 409
 410   if (list)
 411     {
 412       GList *last;
 413
 414       new_list = _g_list_alloc ();
 415       new_list->data = list->data;
 416       last = new_list;
 417       list = list->next;
 418       while (list)
 419         {
 420           last->next = _g_list_alloc ();
 421           last->next->prev = last;
 422           last = last->next;
 423           last->data = list->data;
 424           list = list->next;
 425         }
 426     }
 427
 428   return new_list;
 429 }
 430
 431 GList*
 432 g_list_reverse (GList *list)
 433 {
 434   GList *last;
 435
 436   last = NULL;
 437   while (list)
 438     {
 439       last = list;
 440       list = last->next;
 441       last->next = last->prev;
 442       last->prev = list;
 443     }
 444
 445   return last;
 446 }
 447
 448 GList*
 449 g_list_nth (GList *list,
 450             guint  n)
 451 {
 452   while ((n-- > 0) && list)
 453     list = list->next;
 454
 455   return list;
 456 }
 457
 458 gpointer
 459 g_list_nth_data (GList     *list,
 460                  guint      n)
 461 {
 462   while ((n-- > 0) && list)
 463     list = list->next;
 464
 465   return list ? list->data : NULL;
 466 }
 467
 468 GList*
 469 g_list_find (GList         *list,
 470              gconstpointer  data)
 471 {
 472   while (list)
 473     {
 474       if (list->data == data)
 475         break;
 476       list = list->next;
 477     }
 478
 479   return list;
 480 }
 481
 482 GList*
 483 g_list_find_custom (GList         *list,
 484                     gconstpointer  data,
 485                     GCompareFunc   func)
 486 {
 487   g_return_val_if_fail (func != NULL, list);
 488
 489   while (list)
 490     {
 491       if (! func (list->data, data))
 492         return list;
 493       list = list->next;
 494     }
 495
 496   return NULL;
 497 }
 498
 499
 500 gint
 501 g_list_position (GList *list,
 502                  GList *link)
 503 {
 504   gint i;
 505
 506   i = 0;
 507   while (list)
 508     {
 509       if (list == link)
 510         return i;
 511       i++;
 512       list = list->next;
 513     }
 514
 515   return -1;
 516 }
 517
 518 gint
 519 g_list_index (GList         *list,
 520               gconstpointer  data)
 521 {
 522   gint i;
 523
 524   i = 0;
 525   while (list)
 526     {
 527       if (list->data == data)
 528         return i;
 529       i++;
 530       list = list->next;
 531     }
 532
 533   return -1;
 534 }
 535
 536 GList*
 537 g_list_last (GList *list)
 538 {
 539   if (list)
 540     {
 541       while (list->next)
 542         list = list->next;
 543     }
 544
 545   return list;
 546 }
 547
 548 GList*
 549 g_list_first (GList *list)
 550 {
 551   if (list)
 552     {
 553       while (list->prev)
 554         list = list->prev;
 555     }
 556
 557   return list;
 558 }
 559
 560 guint
 561 g_list_length (GList *list)
 562 {
 563   guint length;
 564
 565   length = 0;
 566   while (list)
 567     {
 568       length++;
 569       list = list->next;
 570     }
 571
 572   return length;
 573 }
 574
 575 void
 576 g_list_foreach (GList    *list,
 577                 GFunc     func,
 578                 gpointer  user_data)
 579 {
 580   while (list)
 581     {
 582       (*func) (list->data, user_data);
 583       list = list->next;
 584     }
 585 }
 586
 587
 588 GList*
 589 g_list_insert_sorted (GList        *list,
 590                       gpointer      data,
 591                       GCompareFunc  func)
 592 {
 593   GList *tmp_list = list;
 594   GList *new_list;
 595   gint cmp;
 596
 597   g_return_val_if_fail (func != NULL, list);
 598
 599   if (!list)
 600     {
 601       new_list = _g_list_alloc ();
 602       new_list->data = data;
 603       return new_list;
 604     }
 605
 606   cmp = (*func) (data, tmp_list->data);
 607
 608   while ((tmp_list->next) && (cmp > 0))
 609     {
 610       tmp_list = tmp_list->next;
 611       cmp = (*func) (data, tmp_list->data);
 612     }
 613
 614   new_list = _g_list_alloc ();
 615   new_list->data = data;
 616
 617   if ((!tmp_list->next) && (cmp > 0))
 618     {
 619       tmp_list->next = new_list;
 620       new_list->prev = tmp_list;
 621       return list;
 622     }
 623
 624   if (tmp_list->prev)
 625     {
 626       tmp_list->prev->next = new_list;
 627       new_list->prev = tmp_list->prev;
 628     }
 629   new_list->next = tmp_list;
 630   tmp_list->prev = new_list;
 631
 632   if (tmp_list == list)
 633     return new_list;
 634   else
 635     return list;
 636 }
 637
 638 static GList *
 639 g_list_sort_merge (GList     *l1,
 640                    GList     *l2,
 641                    GFunc     compare_func,
 642                    gboolean  use_data,
 643                    gpointer  user_data)
 644 {
 645   GList list, *l, *lprev;
 646   gint cmp;
 647
 648   l = &list;
 649   lprev = NULL;
 650
 651   while (l1 && l2)
 652     {
 653       if (use_data)
 654         cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
 655       else
 656         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 657
 658       if (cmp <= 0)
 659         {
 660           l->next = l1;
 661           l = l->next;
 662           l->prev = lprev;
 663           lprev = l;
 664           l1 = l1->next;
 665         }
 666       else
 667         {
 668           l->next = l2;
 669           l = l->next;
 670           l->prev = lprev;
 671           lprev = l;
 672           l2 = l2->next;
 673         }
 674     }
 675   l->next = l1 ? l1 : l2;
 676   l->next->prev = l;
 677
 678   return list.next;
 679 }
 680
 681 GList*
 682 g_list_sort_real (GList    *list,
 683                   GFunc     compare_func,
 684                   gboolean  use_data,
 685                   gpointer  user_data)
 686 {
 687   GList *l1, *l2;
 688
 689   if (!list)
 690     return NULL;
 691   if (!list->next)
 692     return list;
 693
 694   l1 = list;
 695   l2 = list->next;
 696
 697   while ((l2 = l2->next) != NULL)
 698     {
 699       if ((l2 = l2->next) == NULL)
 700         break;
 701       l1 = l1->next;
 702     }
 703   l2 = l1->next;
 704   l1->next = NULL;
 705
 706   return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
 707                             g_list_sort_real (l2, compare_func, use_data, user_data),
 708                             compare_func,
 709                             use_data,
 710                             user_data);
 711 }
 712
 713 GList *
 714 g_list_sort (GList        *list,
 715              GCompareFunc  compare_func)
 716 {
 717   return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 718
 719 }
 720
 721 GList *
 722 g_list_sort_with_data (GList            *list,
 723                        GCompareFuncData  compare_func,
 724                        gpointer          user_data)
 725 {
 726   return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 727 }
 728
 729 GList*
 730 g_list_sort2 (GList       *list,
 731               GCompareFunc compare_func)
 732 {
 733   GSList *runs = NULL;
 734   GList *tmp;
 735
 736   /* Degenerate case.  */
 737   if (!list) return NULL;
 738
 739   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
 740   for (tmp = list; tmp; )
 741     {
 742       GList *tmp2;
 743       for (tmp2 = tmp;
 744            tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
 745            tmp2 = tmp2->next)
 746         /* Nothing */;
 747       runs = g_slist_append (runs, tmp);
 748       tmp = tmp2->next;
 749       tmp2->next = NULL;
 750     }
 751   /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]].  */
 752
 753   while (runs->next)
 754     {
 755       /* We have more than one run.  Merge pairwise.  */
 756       GSList *dst, *src, *dstprev = NULL;
 757       dst = src = runs;
 758       while (src && src->next)
 759         {
 760           dst->data = g_list_sort_merge (src->data,
 761                                          src->next->data,
 762                                          (GFunc) compare_func,
 763                                          FALSE, NULL);
 764           dstprev = dst;
 765           dst = dst->next;
 766           src = src->next->next;
 767         }
 768
 769       /* If number of runs was odd, just keep the last.  */
 770       if (src)
 771         {
 772           dst->data = src->data;
 773           dstprev = dst;
 774           dst = dst->next;
 775         }
 776
 777       dstprev->next = NULL;
 778       g_slist_free (dst);
 779     }
 780
 781   /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]].  */
 782   /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]].  */
 783
 784   list = runs->data;
 785   g_slist_free (runs);
 786   return list;
 787 }