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