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 GList*
 487 g_list_nth_prev (GList *list,
 488                  guint  n)
 489 {
 490   while ((n-- > 0) && list)
 491     list = list->prev;
 492
 493   return list;
 494 }
 495
 496 gpointer
 497 g_list_nth_data (GList     *list,
 498                  guint      n)
 499 {
 500   while ((n-- > 0) && list)
 501     list = list->next;
 502
 503   return list ? list->data : NULL;
 504 }
 505
 506 GList*
 507 g_list_find (GList         *list,
 508              gconstpointer  data)
 509 {
 510   while (list)
 511     {
 512       if (list->data == data)
 513         break;
 514       list = list->next;
 515     }
 516
 517   return list;
 518 }
 519
 520 GList*
 521 g_list_find_custom (GList         *list,
 522                     gconstpointer  data,
 523                     GCompareFunc   func)
 524 {
 525   g_return_val_if_fail (func != NULL, list);
 526
 527   while (list)
 528     {
 529       if (! func (list->data, data))
 530         return list;
 531       list = list->next;
 532     }
 533
 534   return NULL;
 535 }
 536
 537
 538 gint
 539 g_list_position (GList *list,
 540                  GList *link)
 541 {
 542   gint i;
 543
 544   i = 0;
 545   while (list)
 546     {
 547       if (list == link)
 548         return i;
 549       i++;
 550       list = list->next;
 551     }
 552
 553   return -1;
 554 }
 555
 556 gint
 557 g_list_index (GList         *list,
 558               gconstpointer  data)
 559 {
 560   gint i;
 561
 562   i = 0;
 563   while (list)
 564     {
 565       if (list->data == data)
 566         return i;
 567       i++;
 568       list = list->next;
 569     }
 570
 571   return -1;
 572 }
 573
 574 GList*
 575 g_list_last (GList *list)
 576 {
 577   if (list)
 578     {
 579       while (list->next)
 580         list = list->next;
 581     }
 582
 583   return list;
 584 }
 585
 586 GList*
 587 g_list_first (GList *list)
 588 {
 589   if (list)
 590     {
 591       while (list->prev)
 592         list = list->prev;
 593     }
 594
 595   return list;
 596 }
 597
 598 guint
 599 g_list_length (GList *list)
 600 {
 601   guint length;
 602
 603   length = 0;
 604   while (list)
 605     {
 606       length++;
 607       list = list->next;
 608     }
 609
 610   return length;
 611 }
 612
 613 void
 614 g_list_foreach (GList    *list,
 615                 GFunc     func,
 616                 gpointer  user_data)
 617 {
 618   while (list)
 619     {
 620       GList *next = list->next;
 621       (*func) (list->data, user_data);
 622       list = next;
 623     }
 624 }
 625
 626
 627 GList*
 628 g_list_insert_sorted (GList        *list,
 629                       gpointer      data,
 630                       GCompareFunc  func)
 631 {
 632   GList *tmp_list = list;
 633   GList *new_list;
 634   gint cmp;
 635
 636   g_return_val_if_fail (func != NULL, list);
 637
 638   if (!list)
 639     {
 640       new_list = _g_list_alloc ();
 641       new_list->data = data;
 642       return new_list;
 643     }
 644
 645   cmp = (*func) (data, tmp_list->data);
 646
 647   while ((tmp_list->next) && (cmp > 0))
 648     {
 649       tmp_list = tmp_list->next;
 650       cmp = (*func) (data, tmp_list->data);
 651     }
 652
 653   new_list = _g_list_alloc ();
 654   new_list->data = data;
 655
 656   if ((!tmp_list->next) && (cmp > 0))
 657     {
 658       tmp_list->next = new_list;
 659       new_list->prev = tmp_list;
 660       return list;
 661     }
 662
 663   if (tmp_list->prev)
 664     {
 665       tmp_list->prev->next = new_list;
 666       new_list->prev = tmp_list->prev;
 667     }
 668   new_list->next = tmp_list;
 669   tmp_list->prev = new_list;
 670
 671   if (tmp_list == list)
 672     return new_list;
 673   else
 674     return list;
 675 }
 676
 677 static GList *
 678 g_list_sort_merge (GList     *l1,
 679                    GList     *l2,
 680                    GFunc     compare_func,
 681                    gboolean  use_data,
 682                    gpointer  user_data)
 683 {
 684   GList list, *l, *lprev;
 685   gint cmp;
 686
 687   l = &list;
 688   lprev = NULL;
 689
 690   while (l1 && l2)
 691     {
 692       if (use_data)
 693         cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 694       else
 695         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 696
 697       if (cmp <= 0)
 698         {
 699           l->next = l1;
 700           l = l->next;
 701           l->prev = lprev;
 702           lprev = l;
 703           l1 = l1->next;
 704         }
 705       else
 706         {
 707           l->next = l2;
 708           l = l->next;
 709           l->prev = lprev;
 710           lprev = l;
 711           l2 = l2->next;
 712         }
 713     }
 714   l->next = l1 ? l1 : l2;
 715   l->next->prev = l;
 716
 717   return list.next;
 718 }
 719
 720 static GList*
 721 g_list_sort_real (GList    *list,
 722                   GFunc     compare_func,
 723                   gboolean  use_data,
 724                   gpointer  user_data)
 725 {
 726   GList *l1, *l2;
 727
 728   if (!list)
 729     return NULL;
 730   if (!list->next)
 731     return list;
 732
 733   l1 = list;
 734   l2 = list->next;
 735
 736   while ((l2 = l2->next) != NULL)
 737     {
 738       if ((l2 = l2->next) == NULL)
 739         break;
 740       l1 = l1->next;
 741     }
 742   l2 = l1->next;
 743   l1->next = NULL;
 744
 745   return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
 746                             g_list_sort_real (l2, compare_func, use_data, user_data),
 747                             compare_func,
 748                             use_data,
 749                             user_data);
 750 }
 751
 752 GList *
 753 g_list_sort (GList        *list,
 754              GCompareFunc  compare_func)
 755 {
 756   return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 757
 758 }
 759
 760 GList *
 761 g_list_sort_with_data (GList            *list,
 762                        GCompareDataFunc  compare_func,
 763                        gpointer          user_data)
 764 {
 765   return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 766 }
 767
 768 static GList*
 769 g_list_sort2 (GList       *list,
 770               GCompareFunc compare_func)
 771 {
 772   GSList *runs = NULL;
 773   GList *tmp;
 774
 775   /* Degenerate case.  */
 776   if (!list) return NULL;
 777
 778   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
 779   for (tmp = list; tmp; )
 780     {
 781       GList *tmp2;
 782       for (tmp2 = tmp;
 783            tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
 784            tmp2 = tmp2->next)
 785         /* Nothing */;
 786       runs = g_slist_append (runs, tmp);
 787       tmp = tmp2->next;
 788       tmp2->next = NULL;
 789     }
 790   /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]].  */
 791
 792   while (runs->next)
 793     {
 794       /* We have more than one run.  Merge pairwise.  */
 795       GSList *dst, *src, *dstprev = NULL;
 796       dst = src = runs;
 797       while (src && src->next)
 798         {
 799           dst->data = g_list_sort_merge (src->data,
 800                                          src->next->data,
 801                                          (GFunc) compare_func,
 802                                          FALSE, NULL);
 803           dstprev = dst;
 804           dst = dst->next;
 805           src = src->next->next;
 806         }
 807
 808       /* If number of runs was odd, just keep the last.  */
 809       if (src)
 810         {
 811           dst->data = src->data;
 812           dstprev = dst;
 813           dst = dst->next;
 814         }
 815
 816       dstprev->next = NULL;
 817       g_slist_free (dst);
 818     }
 819
 820   /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]].  */
 821   /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]].  */
 822
 823   list = runs->data;
 824   g_slist_free (runs);
 825   return list;
 826 }