glib/glist.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   GList         *free_lists; /* implementation specific */
  43 };
  44
  45 static GAllocator       *current_allocator = NULL;
  46 G_LOCK_DEFINE_STATIC (current_allocator);
  47
  48 /* HOLDS: current_allocator_lock */
  49 static void
  50 g_list_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_LIST)
  56     {
  57       allocator->type = G_ALLOCATOR_LIST;
  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 (GList),
  69                                               sizeof (GList) * 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_list_push_allocator(GAllocator *allocator)
  79 {
  80   G_LOCK (current_allocator);
  81   g_list_validate_allocator ( allocator );
  82   allocator->last = current_allocator;
  83   current_allocator = allocator;
  84   G_UNLOCK (current_allocator);
  85 }
  86
  87 void
  88 g_list_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 GList*
 104 g_list_alloc (void)
 105 {
 106   GList *list;
 107
 108   G_LOCK (current_allocator);
 109   if (!current_allocator)
 110     {
 111       GAllocator *allocator = g_allocator_new ("GLib default GList allocator",
 112                                                128);
 113       g_list_validate_allocator (allocator);
 114       allocator->last = NULL;
 115       current_allocator = allocator;
 116     }
 117   if (!current_allocator->free_lists)
 118     {
 119       list = g_chunk_new (GList, 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   list->next = NULL;
 138   list->prev = NULL;
 139
 140   return list;
 141 }
 142
 143 void
 144 g_list_free (GList *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_list_free_1 (GList *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 GList*
 170 g_list_append (GList    *list,
 171                gpointer  data)
 172 {
 173   GList *new_list;
 174   GList *last;
 175
 176   new_list = g_list_alloc ();
 177   new_list->data = data;
 178
 179   if (list)
 180     {
 181       last = g_list_last (list);
 182       /* g_assert (last != NULL); */
 183       last->next = new_list;
 184       new_list->prev = last;
 185
 186       return list;
 187     }
 188   else
 189     return new_list;
 190 }
 191
 192 GList*
 193 g_list_prepend (GList    *list,
 194                 gpointer  data)
 195 {
 196   GList *new_list;
 197
 198   new_list = g_list_alloc ();
 199   new_list->data = data;
 200
 201   if (list)
 202     {
 203       if (list->prev)
 204         {
 205           list->prev->next = new_list;
 206           new_list->prev = list->prev;
 207         }
 208       list->prev = new_list;
 209       new_list->next = list;
 210     }
 211
 212   return new_list;
 213 }
 214
 215 GList*
 216 g_list_insert (GList    *list,
 217                gpointer  data,
 218                gint      position)
 219 {
 220   GList *new_list;
 221   GList *tmp_list;
 222
 223   if (position < 0)
 224     return g_list_append (list, data);
 225   else if (position == 0)
 226     return g_list_prepend (list, data);
 227
 228   tmp_list = g_list_nth (list, position);
 229   if (!tmp_list)
 230     return g_list_append (list, data);
 231
 232   new_list = g_list_alloc ();
 233   new_list->data = data;
 234
 235   if (tmp_list->prev)
 236     {
 237       tmp_list->prev->next = new_list;
 238       new_list->prev = tmp_list->prev;
 239     }
 240   new_list->next = tmp_list;
 241   tmp_list->prev = new_list;
 242
 243   if (tmp_list == list)
 244     return new_list;
 245   else
 246     return list;
 247 }
 248
 249 GList *
 250 g_list_concat (GList *list1, GList *list2)
 251 {
 252   GList *tmp_list;
 253
 254   if (list2)
 255     {
 256       tmp_list = g_list_last (list1);
 257       if (tmp_list)
 258         tmp_list->next = list2;
 259       else
 260         list1 = list2;
 261       list2->prev = tmp_list;
 262     }
 263
 264   return list1;
 265 }
 266
 267 GList*
 268 g_list_remove (GList    *list,
 269                gpointer  data)
 270 {
 271   GList *tmp;
 272
 273   tmp = list;
 274   while (tmp)
 275     {
 276       if (tmp->data != data)
 277         tmp = tmp->next;
 278       else
 279         {
 280           if (tmp->prev)
 281             tmp->prev->next = tmp->next;
 282           if (tmp->next)
 283             tmp->next->prev = tmp->prev;
 284
 285           if (list == tmp)
 286             list = list->next;
 287
 288           g_list_free_1 (tmp);
 289
 290           break;
 291         }
 292     }
 293   return list;
 294 }
 295
 296 inline GList*
 297 g_list_remove_link (GList *list,
 298                     GList *link)
 299 {
 300   if (link)
 301     {
 302       if (link->prev)
 303         link->prev->next = link->next;
 304       if (link->next)
 305         link->next->prev = link->prev;
 306
 307       if (link == list)
 308         list = list->next;
 309
 310       link->next = NULL;
 311       link->prev = NULL;
 312     }
 313
 314   return list;
 315 }
 316
 317 GList*
 318 g_list_delete_link (GList *list,
 319                     GList *link)
 320 {
 321   list = g_list_remove_link (list, link);
 322   g_list_free_1 (link);
 323
 324   return list;
 325 }
 326
 327 GList*
 328 g_list_copy (GList *list)
 329 {
 330   GList *new_list = NULL;
 331
 332   if (list)
 333     {
 334       GList *last;
 335
 336       new_list = g_list_alloc ();
 337       new_list->data = list->data;
 338       last = new_list;
 339       list = list->next;
 340       while (list)
 341         {
 342           last->next = g_list_alloc ();
 343           last->next->prev = last;
 344           last = last->next;
 345           last->data = list->data;
 346           list = list->next;
 347         }
 348     }
 349
 350   return new_list;
 351 }
 352
 353 GList*
 354 g_list_reverse (GList *list)
 355 {
 356   GList *last;
 357
 358   last = NULL;
 359   while (list)
 360     {
 361       last = list;
 362       list = last->next;
 363       last->next = last->prev;
 364       last->prev = list;
 365     }
 366
 367   return last;
 368 }
 369
 370 GList*
 371 g_list_nth (GList *list,
 372             guint  n)
 373 {
 374   while ((n-- > 0) && list)
 375     list = list->next;
 376
 377   return list;
 378 }
 379
 380 gpointer
 381 g_list_nth_data (GList     *list,
 382                  guint      n)
 383 {
 384   while ((n-- > 0) && list)
 385     list = list->next;
 386
 387   return list ? list->data : NULL;
 388 }
 389
 390 GList*
 391 g_list_find (GList    *list,
 392              gpointer  data)
 393 {
 394   while (list)
 395     {
 396       if (list->data == data)
 397         break;
 398       list = list->next;
 399     }
 400
 401   return list;
 402 }
 403
 404 GList*
 405 g_list_find_custom (GList       *list,
 406                     gpointer     data,
 407                     GCompareFunc func)
 408 {
 409   g_return_val_if_fail (func != NULL, list);
 410
 411   while (list)
 412     {
 413       if (! func (list->data, data))
 414         return list;
 415       list = list->next;
 416     }
 417
 418   return NULL;
 419 }
 420
 421
 422 gint
 423 g_list_position (GList *list,
 424                  GList *link)
 425 {
 426   gint i;
 427
 428   i = 0;
 429   while (list)
 430     {
 431       if (list == link)
 432         return i;
 433       i++;
 434       list = list->next;
 435     }
 436
 437   return -1;
 438 }
 439
 440 gint
 441 g_list_index (GList   *list,
 442               gpointer data)
 443 {
 444   gint i;
 445
 446   i = 0;
 447   while (list)
 448     {
 449       if (list->data == data)
 450         return i;
 451       i++;
 452       list = list->next;
 453     }
 454
 455   return -1;
 456 }
 457
 458 GList*
 459 g_list_last (GList *list)
 460 {
 461   if (list)
 462     {
 463       while (list->next)
 464         list = list->next;
 465     }
 466
 467   return list;
 468 }
 469
 470 GList*
 471 g_list_first (GList *list)
 472 {
 473   if (list)
 474     {
 475       while (list->prev)
 476         list = list->prev;
 477     }
 478
 479   return list;
 480 }
 481
 482 guint
 483 g_list_length (GList *list)
 484 {
 485   guint length;
 486
 487   length = 0;
 488   while (list)
 489     {
 490       length++;
 491       list = list->next;
 492     }
 493
 494   return length;
 495 }
 496
 497 void
 498 g_list_foreach (GList    *list,
 499                 GFunc     func,
 500                 gpointer  user_data)
 501 {
 502   while (list)
 503     {
 504       (*func) (list->data, user_data);
 505       list = list->next;
 506     }
 507 }
 508
 509
 510 GList*
 511 g_list_insert_sorted (GList        *list,
 512                       gpointer      data,
 513                       GCompareFunc  func)
 514 {
 515   GList *tmp_list = list;
 516   GList *new_list;
 517   gint cmp;
 518
 519   g_return_val_if_fail (func != NULL, list);
 520
 521   if (!list)
 522     {
 523       new_list = g_list_alloc();
 524       new_list->data = data;
 525       return new_list;
 526     }
 527
 528   cmp = (*func) (data, tmp_list->data);
 529
 530   while ((tmp_list->next) && (cmp > 0))
 531     {
 532       tmp_list = tmp_list->next;
 533       cmp = (*func) (data, tmp_list->data);
 534     }
 535
 536   new_list = g_list_alloc();
 537   new_list->data = data;
 538
 539   if ((!tmp_list->next) && (cmp > 0))
 540     {
 541       tmp_list->next = new_list;
 542       new_list->prev = tmp_list;
 543       return list;
 544     }
 545
 546   if (tmp_list->prev)
 547     {
 548       tmp_list->prev->next = new_list;
 549       new_list->prev = tmp_list->prev;
 550     }
 551   new_list->next = tmp_list;
 552   tmp_list->prev = new_list;
 553
 554   if (tmp_list == list)
 555     return new_list;
 556   else
 557     return list;
 558 }
 559
 560 static GList *
 561 g_list_sort_merge (GList       *l1,
 562                    GList       *l2,
 563                    GCompareFunc compare_func)
 564 {
 565   GList list, *l, *lprev;
 566
 567   l = &list;
 568   lprev = NULL;
 569
 570   while (l1 && l2)
 571     {
 572       if (compare_func (l1->data, l2->data) < 0)
 573         {
 574           l->next = l1;
 575           l = l->next;
 576           l->prev = lprev;
 577           lprev = l;
 578           l1 = l1->next;
 579         }
 580       else
 581         {
 582           l->next = l2;
 583           l = l->next;
 584           l->prev = lprev;
 585           lprev = l;
 586           l2 = l2->next;
 587         }
 588     }
 589   l->next = l1 ? l1 : l2;
 590   l->next->prev = l;
 591
 592   return list.next;
 593 }
 594
 595 GList*
 596 g_list_sort (GList       *list,
 597              GCompareFunc compare_func)
 598 {
 599   GList *l1, *l2;
 600
 601   if (!list)
 602     return NULL;
 603   if (!list->next)
 604     return list;
 605
 606   l1 = list;
 607   l2 = list->next;
 608
 609   while ((l2 = l2->next) != NULL)
 610     {
 611       if ((l2 = l2->next) == NULL)
 612         break;
 613       l1 = l1->next;
 614     }
 615   l2 = l1->next;
 616   l1->next = NULL;
 617
 618   return g_list_sort_merge (g_list_sort (list, compare_func),
 619                             g_list_sort (l2,   compare_func),
 620                             compare_func);
 621 }
 622
 623 GList*
 624 g_list_sort2 (GList       *list,
 625               GCompareFunc compare_func)
 626 {
 627   GSList *runs = NULL;
 628   GList *tmp;
 629
 630   /* Degenerate case.  */
 631   if (!list) return NULL;
 632
 633   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
 634   for (tmp = list; tmp; )
 635     {
 636       GList *tmp2;
 637       for (tmp2 = tmp;
 638            tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
 639            tmp2 = tmp2->next)
 640         /* Nothing */;
 641       runs = g_slist_append (runs, tmp);
 642       tmp = tmp2->next;
 643       tmp2->next = NULL;
 644     }
 645   /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]].  */
 646
 647   while (runs->next)
 648     {
 649       /* We have more than one run.  Merge pairwise.  */
 650       GSList *dst, *src, *dstprev = NULL;
 651       dst = src = runs;
 652       while (src && src->next)
 653         {
 654           dst->data = g_list_sort_merge (src->data,
 655                                          src->next->data,
 656                                          compare_func);
 657           dstprev = dst;
 658           dst = dst->next;
 659           src = src->next->next;
 660         }
 661
 662       /* If number of runs was odd, just keep the last.  */
 663       if (src)
 664         {
 665           dst->data = src->data;
 666           dstprev = dst;
 667           dst = dst->next;
 668         }
 669
 670       dstprev->next = NULL;
 671       g_slist_free (dst);
 672     }
 673
 674   /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]].  */
 675   /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]].  */
 676
 677   list = runs->data;
 678   g_slist_free (runs);
 679   return list;
 680 }