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