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 Library 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  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library 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-1999.  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       list->data = list->next;
 155       G_LOCK (current_allocator);
 156       list->next = current_allocator->free_lists;
 157       current_allocator->free_lists = list;
 158       G_UNLOCK (current_allocator);
 159     }
 160 }
 161
 162 static inline void
 163 _g_slist_free_1 (GSList *list)
 164 {
 165   if (list)
 166     {
 167       list->data = NULL;
 168       G_LOCK (current_allocator);
 169       list->next = current_allocator->free_lists;
 170       current_allocator->free_lists = list;
 171       G_UNLOCK (current_allocator);
 172     }
 173 }
 174
 175 void
 176 g_slist_free_1 (GSList *list)
 177 {
 178   _g_slist_free_1 (list);
 179 }
 180
 181 GSList*
 182 g_slist_append (GSList   *list,
 183                 gpointer  data)
 184 {
 185   GSList *new_list;
 186   GSList *last;
 187
 188   new_list = _g_slist_alloc ();
 189   new_list->data = data;
 190
 191   if (list)
 192     {
 193       last = g_slist_last (list);
 194       /* g_assert (last != NULL); */
 195       last->next = new_list;
 196
 197       return list;
 198     }
 199   else
 200       return new_list;
 201 }
 202
 203 GSList*
 204 g_slist_prepend (GSList   *list,
 205                  gpointer  data)
 206 {
 207   GSList *new_list;
 208
 209   new_list = _g_slist_alloc ();
 210   new_list->data = data;
 211   new_list->next = list;
 212
 213   return new_list;
 214 }
 215
 216 GSList*
 217 g_slist_insert (GSList   *list,
 218                 gpointer  data,
 219                 gint      position)
 220 {
 221   GSList *prev_list;
 222   GSList *tmp_list;
 223   GSList *new_list;
 224
 225   if (position < 0)
 226     return g_slist_append (list, data);
 227   else if (position == 0)
 228     return g_slist_prepend (list, data);
 229
 230   new_list = _g_slist_alloc ();
 231   new_list->data = data;
 232
 233   if (!list)
 234     return new_list;
 235
 236   prev_list = NULL;
 237   tmp_list = list;
 238
 239   while ((position-- > 0) && tmp_list)
 240     {
 241       prev_list = tmp_list;
 242       tmp_list = tmp_list->next;
 243     }
 244
 245   if (prev_list)
 246     {
 247       new_list->next = prev_list->next;
 248       prev_list->next = new_list;
 249     }
 250   else
 251     {
 252       new_list->next = list;
 253       list = new_list;
 254     }
 255
 256   return list;
 257 }
 258
 259 GSList *
 260 g_slist_concat (GSList *list1, GSList *list2)
 261 {
 262   if (list2)
 263     {
 264       if (list1)
 265         g_slist_last (list1)->next = list2;
 266       else
 267         list1 = list2;
 268     }
 269
 270   return list1;
 271 }
 272
 273 GSList*
 274 g_slist_remove (GSList   *list,
 275                 gpointer  data)
 276 {
 277   GSList *tmp;
 278   GSList *prev;
 279
 280   prev = NULL;
 281   tmp = list;
 282
 283   while (tmp)
 284     {
 285       if (tmp->data == data)
 286         {
 287           if (prev)
 288             prev->next = tmp->next;
 289           if (list == tmp)
 290             list = list->next;
 291
 292           tmp->next = NULL;
 293           g_slist_free (tmp);
 294
 295           break;
 296         }
 297
 298       prev = tmp;
 299       tmp = tmp->next;
 300     }
 301
 302   return list;
 303 }
 304
 305 static inline GSList*
 306 _g_slist_remove_link (GSList *list,
 307                       GSList *link)
 308 {
 309   GSList *tmp;
 310   GSList *prev;
 311
 312   prev = NULL;
 313   tmp = list;
 314
 315   while (tmp)
 316     {
 317       if (tmp == link)
 318         {
 319           if (prev)
 320             prev->next = tmp->next;
 321           if (list == tmp)
 322             list = list->next;
 323
 324           tmp->next = NULL;
 325           break;
 326         }
 327
 328       prev = tmp;
 329       tmp = tmp->next;
 330     }
 331
 332   return list;
 333 }
 334
 335 GSList*
 336 g_slist_remove_link (GSList *list,
 337                      GSList *link)
 338 {
 339   return _g_slist_remove_link (list, link);
 340 }
 341
 342 GSList*
 343 g_slist_delete_link (GSList *list,
 344                      GSList *link)
 345 {
 346   list = _g_slist_remove_link (list, link);
 347   _g_slist_free_1 (link);
 348
 349   return list;
 350 }
 351
 352 GSList*
 353 g_slist_copy (GSList *list)
 354 {
 355   GSList *new_list = NULL;
 356
 357   if (list)
 358     {
 359       GSList *last;
 360
 361       new_list = _g_slist_alloc ();
 362       new_list->data = list->data;
 363       last = new_list;
 364       list = list->next;
 365       while (list)
 366         {
 367           last->next = _g_slist_alloc ();
 368           last = last->next;
 369           last->data = list->data;
 370           list = list->next;
 371         }
 372     }
 373
 374   return new_list;
 375 }
 376
 377 GSList*
 378 g_slist_reverse (GSList *list)
 379 {
 380   GSList *tmp;
 381   GSList *prev;
 382   GSList *last;
 383
 384   last = NULL;
 385   prev = NULL;
 386
 387   while (list)
 388     {
 389       last = list;
 390
 391       tmp = list->next;
 392       list->next = prev;
 393
 394       prev = list;
 395       list = tmp;
 396     }
 397
 398   return last;
 399 }
 400
 401 GSList*
 402 g_slist_nth (GSList *list,
 403              guint   n)
 404 {
 405   while ((n-- > 0) && list)
 406     list = list->next;
 407
 408   return list;
 409 }
 410
 411 gpointer
 412 g_slist_nth_data (GSList   *list,
 413                   guint     n)
 414 {
 415   while ((n-- > 0) && list)
 416     list = list->next;
 417
 418   return list ? list->data : NULL;
 419 }
 420
 421 GSList*
 422 g_slist_find (GSList   *list,
 423               gpointer  data)
 424 {
 425   while (list)
 426     {
 427       if (list->data == data)
 428         break;
 429       list = list->next;
 430     }
 431
 432   return list;
 433 }
 434
 435 GSList*
 436 g_slist_find_custom (GSList      *list,
 437                      gpointer     data,
 438                      GCompareFunc func)
 439 {
 440   g_return_val_if_fail (func != NULL, list);
 441
 442   while (list)
 443     {
 444       if (! func (list->data, data))
 445         return list;
 446       list = list->next;
 447     }
 448
 449   return NULL;
 450 }
 451
 452 gint
 453 g_slist_position (GSList *list,
 454                   GSList *link)
 455 {
 456   gint i;
 457
 458   i = 0;
 459   while (list)
 460     {
 461       if (list == link)
 462         return i;
 463       i++;
 464       list = list->next;
 465     }
 466
 467   return -1;
 468 }
 469
 470 gint
 471 g_slist_index (GSList   *list,
 472                gpointer data)
 473 {
 474   gint i;
 475
 476   i = 0;
 477   while (list)
 478     {
 479       if (list->data == data)
 480         return i;
 481       i++;
 482       list = list->next;
 483     }
 484
 485   return -1;
 486 }
 487
 488 GSList*
 489 g_slist_last (GSList *list)
 490 {
 491   if (list)
 492     {
 493       while (list->next)
 494         list = list->next;
 495     }
 496
 497   return list;
 498 }
 499
 500 guint
 501 g_slist_length (GSList *list)
 502 {
 503   guint length;
 504
 505   length = 0;
 506   while (list)
 507     {
 508       length++;
 509       list = list->next;
 510     }
 511
 512   return length;
 513 }
 514
 515 void
 516 g_slist_foreach (GSList   *list,
 517                  GFunc     func,
 518                  gpointer  user_data)
 519 {
 520   while (list)
 521     {
 522       (*func) (list->data, user_data);
 523       list = list->next;
 524     }
 525 }
 526
 527 GSList*
 528 g_slist_insert_sorted (GSList       *list,
 529                        gpointer      data,
 530                        GCompareFunc  func)
 531 {
 532   GSList *tmp_list = list;
 533   GSList *prev_list = NULL;
 534   GSList *new_list;
 535   gint cmp;
 536
 537   g_return_val_if_fail (func != NULL, list);
 538
 539   if (!list)
 540     {
 541       new_list = _g_slist_alloc ();
 542       new_list->data = data;
 543       return new_list;
 544     }
 545
 546   cmp = (*func) (data, tmp_list->data);
 547
 548   while ((tmp_list->next) && (cmp > 0))
 549     {
 550       prev_list = tmp_list;
 551       tmp_list = tmp_list->next;
 552       cmp = (*func) (data, tmp_list->data);
 553     }
 554
 555   new_list = _g_slist_alloc ();
 556   new_list->data = data;
 557
 558   if ((!tmp_list->next) && (cmp > 0))
 559     {
 560       tmp_list->next = new_list;
 561       return list;
 562     }
 563
 564   if (prev_list)
 565     {
 566       prev_list->next = new_list;
 567       new_list->next = tmp_list;
 568       return list;
 569     }
 570   else
 571     {
 572       new_list->next = list;
 573       return new_list;
 574     }
 575 }
 576
 577 static GSList*
 578 g_slist_sort_merge  (GSList      *l1,
 579                      GSList      *l2,
 580                      GCompareFunc compare_func)
 581 {
 582   GSList list, *l;
 583
 584   l=&list;
 585
 586   while (l1 && l2)
 587     {
 588       if (compare_func(l1->data,l2->data) < 0)
 589         {
 590           l=l->next=l1;
 591           l1=l1->next;
 592         }
 593       else
 594         {
 595           l=l->next=l2;
 596           l2=l2->next;
 597         }
 598     }
 599   l->next= l1 ? l1 : l2;
 600
 601   return list.next;
 602 }
 603
 604 GSList*
 605 g_slist_sort (GSList       *list,
 606               GCompareFunc compare_func)
 607 {
 608   GSList *l1, *l2;
 609
 610   if (!list)
 611     return NULL;
 612   if (!list->next)
 613     return list;
 614
 615   l1 = list;
 616   l2 = list->next;
 617
 618   while ((l2 = l2->next) != NULL)
 619     {
 620       if ((l2 = l2->next) == NULL)
 621         break;
 622       l1=l1->next;
 623     }
 624   l2 = l1->next;
 625   l1->next = NULL;
 626
 627   return g_slist_sort_merge (g_slist_sort (list, compare_func),
 628                              g_slist_sort (l2,   compare_func),
 629                              compare_func);
 630 }