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