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