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