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