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