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_concat (GSList *list1, GSList *list2)
 312 {
 313   if (list2)
 314     {
 315       if (list1)
 316         g_slist_last (list1)->next = list2;
 317       else
 318         list1 = list2;
 319     }
 320
 321   return list1;
 322 }
 323
 324 GSList*
 325 g_slist_remove (GSList        *list,
 326                 gconstpointer  data)
 327 {
 328   GSList *tmp, *prev = NULL;
 329
 330   tmp = list;
 331   while (tmp)
 332     {
 333       if (tmp->data == data)
 334         {
 335           if (prev)
 336             prev->next = tmp->next;
 337           else
 338             list = tmp->next;
 339
 340           g_slist_free_1 (tmp);
 341           break;
 342         }
 343       prev = tmp;
 344       tmp = prev->next;
 345     }
 346
 347   return list;
 348 }
 349
 350 GSList*
 351 g_slist_remove_all (GSList        *list,
 352                     gconstpointer  data)
 353 {
 354   GSList *tmp, *prev = NULL;
 355
 356   tmp = list;
 357   while (tmp)
 358     {
 359       if (tmp->data == data)
 360         {
 361           GSList *next = tmp->next;
 362
 363           if (prev)
 364             prev->next = next;
 365           else
 366             list = next;
 367
 368           g_slist_free_1 (tmp);
 369           tmp = next;
 370         }
 371       else
 372         {
 373           prev = tmp;
 374           tmp = prev->next;
 375         }
 376     }
 377
 378   return list;
 379 }
 380
 381 static inline GSList*
 382 _g_slist_remove_link (GSList *list,
 383                       GSList *link)
 384 {
 385   GSList *tmp;
 386   GSList *prev;
 387
 388   prev = NULL;
 389   tmp = list;
 390
 391   while (tmp)
 392     {
 393       if (tmp == link)
 394         {
 395           if (prev)
 396             prev->next = tmp->next;
 397           if (list == tmp)
 398             list = list->next;
 399
 400           tmp->next = NULL;
 401           break;
 402         }
 403
 404       prev = tmp;
 405       tmp = tmp->next;
 406     }
 407
 408   return list;
 409 }
 410
 411 GSList*
 412 g_slist_remove_link (GSList *list,
 413                      GSList *link)
 414 {
 415   return _g_slist_remove_link (list, link);
 416 }
 417
 418 GSList*
 419 g_slist_delete_link (GSList *list,
 420                      GSList *link)
 421 {
 422   list = _g_slist_remove_link (list, link);
 423   _g_slist_free_1 (link);
 424
 425   return list;
 426 }
 427
 428 GSList*
 429 g_slist_copy (GSList *list)
 430 {
 431   GSList *new_list = NULL;
 432
 433   if (list)
 434     {
 435       GSList *last;
 436
 437       new_list = _g_slist_alloc ();
 438       new_list->data = list->data;
 439       last = new_list;
 440       list = list->next;
 441       while (list)
 442         {
 443           last->next = _g_slist_alloc ();
 444           last = last->next;
 445           last->data = list->data;
 446           list = list->next;
 447         }
 448     }
 449
 450   return new_list;
 451 }
 452
 453 GSList*
 454 g_slist_reverse (GSList *list)
 455 {
 456   GSList *prev = NULL;
 457
 458   while (list)
 459     {
 460       GSList *next = list->next;
 461
 462       list->next = prev;
 463
 464       prev = list;
 465       list = next;
 466     }
 467
 468   return prev;
 469 }
 470
 471 GSList*
 472 g_slist_nth (GSList *list,
 473              guint   n)
 474 {
 475   while (n-- > 0 && list)
 476     list = list->next;
 477
 478   return list;
 479 }
 480
 481 gpointer
 482 g_slist_nth_data (GSList   *list,
 483                   guint     n)
 484 {
 485   while (n-- > 0 && list)
 486     list = list->next;
 487
 488   return list ? list->data : NULL;
 489 }
 490
 491 GSList*
 492 g_slist_find (GSList        *list,
 493               gconstpointer  data)
 494 {
 495   while (list)
 496     {
 497       if (list->data == data)
 498         break;
 499       list = list->next;
 500     }
 501
 502   return list;
 503 }
 504
 505 GSList*
 506 g_slist_find_custom (GSList        *list,
 507                      gconstpointer  data,
 508                      GCompareFunc   func)
 509 {
 510   g_return_val_if_fail (func != NULL, list);
 511
 512   while (list)
 513     {
 514       if (! func (list->data, data))
 515         return list;
 516       list = list->next;
 517     }
 518
 519   return NULL;
 520 }
 521
 522 gint
 523 g_slist_position (GSList *list,
 524                   GSList *link)
 525 {
 526   gint i;
 527
 528   i = 0;
 529   while (list)
 530     {
 531       if (list == link)
 532         return i;
 533       i++;
 534       list = list->next;
 535     }
 536
 537   return -1;
 538 }
 539
 540 gint
 541 g_slist_index (GSList        *list,
 542                gconstpointer  data)
 543 {
 544   gint i;
 545
 546   i = 0;
 547   while (list)
 548     {
 549       if (list->data == data)
 550         return i;
 551       i++;
 552       list = list->next;
 553     }
 554
 555   return -1;
 556 }
 557
 558 GSList*
 559 g_slist_last (GSList *list)
 560 {
 561   if (list)
 562     {
 563       while (list->next)
 564         list = list->next;
 565     }
 566
 567   return list;
 568 }
 569
 570 guint
 571 g_slist_length (GSList *list)
 572 {
 573   guint length;
 574
 575   length = 0;
 576   while (list)
 577     {
 578       length++;
 579       list = list->next;
 580     }
 581
 582   return length;
 583 }
 584
 585 void
 586 g_slist_foreach (GSList   *list,
 587                  GFunc     func,
 588                  gpointer  user_data)
 589 {
 590   while (list)
 591     {
 592       GSList *next = list->next;
 593       (*func) (list->data, user_data);
 594       list = next;
 595     }
 596 }
 597
 598 GSList*
 599 g_slist_insert_sorted (GSList       *list,
 600                        gpointer      data,
 601                        GCompareFunc  func)
 602 {
 603   GSList *tmp_list = list;
 604   GSList *prev_list = NULL;
 605   GSList *new_list;
 606   gint cmp;
 607
 608   g_return_val_if_fail (func != NULL, list);
 609
 610   if (!list)
 611     {
 612       new_list = _g_slist_alloc ();
 613       new_list->data = data;
 614       return new_list;
 615     }
 616
 617   cmp = (*func) (data, tmp_list->data);
 618
 619   while ((tmp_list->next) && (cmp > 0))
 620     {
 621       prev_list = tmp_list;
 622       tmp_list = tmp_list->next;
 623       cmp = (*func) (data, tmp_list->data);
 624     }
 625
 626   new_list = _g_slist_alloc ();
 627   new_list->data = data;
 628
 629   if ((!tmp_list->next) && (cmp > 0))
 630     {
 631       tmp_list->next = new_list;
 632       return list;
 633     }
 634
 635   if (prev_list)
 636     {
 637       prev_list->next = new_list;
 638       new_list->next = tmp_list;
 639       return list;
 640     }
 641   else
 642     {
 643       new_list->next = list;
 644       return new_list;
 645     }
 646 }
 647
 648 static GSList *
 649 g_slist_sort_merge (GSList   *l1,
 650                     GSList   *l2,
 651                     GFunc     compare_func,
 652                     gboolean  use_data,
 653                     gpointer  user_data)
 654 {
 655   GSList list, *l;
 656   gint cmp;
 657
 658   l=&list;
 659
 660   while (l1 && l2)
 661     {
 662       if (use_data)
 663         cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 664       else
 665         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 666
 667       if (cmp <= 0)
 668         {
 669           l=l->next=l1;
 670           l1=l1->next;
 671         }
 672       else
 673         {
 674           l=l->next=l2;
 675           l2=l2->next;
 676         }
 677     }
 678   l->next= l1 ? l1 : l2;
 679
 680   return list.next;
 681 }
 682
 683 static GSList *
 684 g_slist_sort_real (GSList   *list,
 685                    GFunc     compare_func,
 686                    gboolean  use_data,
 687                    gpointer  user_data)
 688 {
 689   GSList *l1, *l2;
 690
 691   if (!list)
 692     return NULL;
 693   if (!list->next)
 694     return list;
 695
 696   l1 = list;
 697   l2 = list->next;
 698
 699   while ((l2 = l2->next) != NULL)
 700     {
 701       if ((l2 = l2->next) == NULL)
 702         break;
 703       l1=l1->next;
 704     }
 705   l2 = l1->next;
 706   l1->next = NULL;
 707
 708   return g_slist_sort_merge (g_slist_sort_real (list, compare_func, use_data, user_data),
 709                              g_slist_sort_real (l2, compare_func, use_data, user_data),
 710                              compare_func,
 711                              use_data,
 712                              user_data);
 713 }
 714
 715 GSList *
 716 g_slist_sort (GSList       *list,
 717               GCompareFunc  compare_func)
 718 {
 719   return g_slist_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 720 }
 721
 722 GSList *
 723 g_slist_sort_with_data (GSList           *list,
 724                         GCompareDataFunc  compare_func,
 725                         gpointer          user_data)
 726 {
 727   return g_slist_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 728 }