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 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 "config.h"
  32
  33 #include "glib.h"
  34 #include "galias.h"
  35
  36
  37 #ifndef DISABLE_MEM_POOLS
  38 struct _GAllocator /* from gmem.c */
  39 {
  40   gchar         *name;
  41   guint16        n_preallocs;
  42   guint          is_unused : 1;
  43   guint          type : 4;
  44   GAllocator    *last;
  45   GMemChunk     *mem_chunk;
  46   GList         *free_lists; /* implementation specific */
  47 };
  48
  49 static GAllocator       *current_allocator = NULL;
  50 G_LOCK_DEFINE_STATIC (current_allocator);
  51
  52 /* HOLDS: current_allocator_lock */
  53 static void
  54 g_list_validate_allocator (GAllocator *allocator)
  55 {
  56   g_return_if_fail (allocator != NULL);
  57   g_return_if_fail (allocator->is_unused == TRUE);
  58
  59   if (allocator->type != G_ALLOCATOR_LIST)
  60     {
  61       allocator->type = G_ALLOCATOR_LIST;
  62       if (allocator->mem_chunk)
  63         {
  64           g_mem_chunk_destroy (allocator->mem_chunk);
  65           allocator->mem_chunk = NULL;
  66         }
  67     }
  68
  69   if (!allocator->mem_chunk)
  70     {
  71       allocator->mem_chunk = g_mem_chunk_new (allocator->name,
  72                                               sizeof (GList),
  73                                               sizeof (GList) * allocator->n_preallocs,
  74                                               G_ALLOC_ONLY);
  75       allocator->free_lists = NULL;
  76     }
  77
  78   allocator->is_unused = FALSE;
  79 }
  80
  81 void
  82 g_list_push_allocator(GAllocator *allocator)
  83 {
  84   G_LOCK (current_allocator);
  85   g_list_validate_allocator (allocator);
  86   allocator->last = current_allocator;
  87   current_allocator = allocator;
  88   G_UNLOCK (current_allocator);
  89 }
  90
  91 void
  92 g_list_pop_allocator (void)
  93 {
  94   G_LOCK (current_allocator);
  95   if (current_allocator)
  96     {
  97       GAllocator *allocator;
  98
  99       allocator = current_allocator;
 100       current_allocator = allocator->last;
 101       allocator->last = NULL;
 102       allocator->is_unused = TRUE;
 103     }
 104   G_UNLOCK (current_allocator);
 105 }
 106
 107 static inline GList*
 108 _g_list_alloc (void)
 109 {
 110   GList *list;
 111
 112   G_LOCK (current_allocator);
 113   if (!current_allocator)
 114     {
 115       GAllocator *allocator = g_allocator_new ("GLib default GList allocator",
 116                                                128);
 117       g_list_validate_allocator (allocator);
 118       allocator->last = NULL;
 119       current_allocator = allocator;
 120     }
 121   if (!current_allocator->free_lists)
 122     {
 123       list = g_chunk_new (GList, current_allocator->mem_chunk);
 124       list->data = NULL;
 125     }
 126   else
 127     {
 128       if (current_allocator->free_lists->data)
 129         {
 130           list = current_allocator->free_lists->data;
 131           current_allocator->free_lists->data = list->next;
 132           list->data = NULL;
 133         }
 134       else
 135         {
 136           list = current_allocator->free_lists;
 137           current_allocator->free_lists = list->next;
 138         }
 139     }
 140   G_UNLOCK (current_allocator);
 141   list->next = NULL;
 142   list->prev = NULL;
 143
 144   return list;
 145 }
 146
 147 GList*
 148 g_list_alloc (void)
 149 {
 150   return _g_list_alloc ();
 151 }
 152
 153 void
 154 g_list_free (GList *list)
 155 {
 156   if (list)
 157     {
 158       GList *last_node = list;
 159
 160 #ifdef ENABLE_GC_FRIENDLY
 161       while (last_node->next)
 162         {
 163           last_node->data = NULL;
 164           last_node->prev = NULL;
 165           last_node = last_node->next;
 166         }
 167       last_node->data = NULL;
 168       last_node->prev = NULL;
 169 #else /* !ENABLE_GC_FRIENDLY */
 170       list->data = list->next;
 171 #endif /* ENABLE_GC_FRIENDLY */
 172
 173       G_LOCK (current_allocator);
 174       last_node->next = current_allocator->free_lists;
 175       current_allocator->free_lists = list;
 176       G_UNLOCK (current_allocator);
 177     }
 178 }
 179
 180 static inline void
 181 _g_list_free_1 (GList *list)
 182 {
 183   if (list)
 184     {
 185       list->data = NULL;
 186
 187 #ifdef ENABLE_GC_FRIENDLY
 188       list->prev = NULL;
 189 #endif /* ENABLE_GC_FRIENDLY */
 190
 191       G_LOCK (current_allocator);
 192       list->next = current_allocator->free_lists;
 193       current_allocator->free_lists = list;
 194       G_UNLOCK (current_allocator);
 195     }
 196 }
 197
 198 void
 199 g_list_free_1 (GList *list)
 200 {
 201   _g_list_free_1 (list);
 202 }
 203
 204 #else /* DISABLE_MEM_POOLS */
 205
 206 #define _g_list_alloc g_list_alloc
 207 GList*
 208 g_list_alloc (void)
 209 {
 210   GList *list;
 211
 212   list = g_new0 (GList, 1);
 213
 214   return list;
 215 }
 216
 217 void
 218 g_list_free (GList *list)
 219 {
 220   GList *last;
 221
 222   while (list)
 223     {
 224       last = list;
 225       list = list->next;
 226       g_free (last);
 227     }
 228 }
 229
 230 #define _g_list_free_1 g_list_free_1
 231 void
 232 g_list_free_1 (GList *list)
 233 {
 234   g_free (list);
 235 }
 236
 237 #endif
 238
 239 GList*
 240 g_list_append (GList    *list,
 241                gpointer  data)
 242 {
 243   GList *new_list;
 244   GList *last;
 245
 246   new_list = _g_list_alloc ();
 247   new_list->data = data;
 248
 249   if (list)
 250     {
 251       last = g_list_last (list);
 252       /* g_assert (last != NULL); */
 253       last->next = new_list;
 254       new_list->prev = last;
 255
 256       return list;
 257     }
 258   else
 259     return new_list;
 260 }
 261
 262 GList*
 263 g_list_prepend (GList    *list,
 264                 gpointer  data)
 265 {
 266   GList *new_list;
 267
 268   new_list = _g_list_alloc ();
 269   new_list->data = data;
 270
 271   if (list)
 272     {
 273       if (list->prev)
 274         {
 275           list->prev->next = new_list;
 276           new_list->prev = list->prev;
 277         }
 278       list->prev = new_list;
 279       new_list->next = list;
 280     }
 281
 282   return new_list;
 283 }
 284
 285 GList*
 286 g_list_insert (GList    *list,
 287                gpointer  data,
 288                gint      position)
 289 {
 290   GList *new_list;
 291   GList *tmp_list;
 292
 293   if (position < 0)
 294     return g_list_append (list, data);
 295   else if (position == 0)
 296     return g_list_prepend (list, data);
 297
 298   tmp_list = g_list_nth (list, position);
 299   if (!tmp_list)
 300     return g_list_append (list, data);
 301
 302   new_list = _g_list_alloc ();
 303   new_list->data = data;
 304
 305   if (tmp_list->prev)
 306     {
 307       tmp_list->prev->next = new_list;
 308       new_list->prev = tmp_list->prev;
 309     }
 310   new_list->next = tmp_list;
 311   tmp_list->prev = new_list;
 312
 313   if (tmp_list == list)
 314     return new_list;
 315   else
 316     return list;
 317 }
 318
 319 GList*
 320 g_list_insert_before (GList   *list,
 321                       GList   *sibling,
 322                       gpointer data)
 323 {
 324   if (!list)
 325     {
 326       list = g_list_alloc ();
 327       list->data = data;
 328       g_return_val_if_fail (sibling == NULL, list);
 329       return list;
 330     }
 331   else if (sibling)
 332     {
 333       GList *node;
 334
 335       node = g_list_alloc ();
 336       node->data = data;
 337       if (sibling->prev)
 338         {
 339           node->prev = sibling->prev;
 340           node->prev->next = node;
 341           node->next = sibling;
 342           sibling->prev = node;
 343           return list;
 344         }
 345       else
 346         {
 347           node->next = sibling;
 348           sibling->prev = node;
 349           g_return_val_if_fail (sibling == list, node);
 350           return node;
 351         }
 352     }
 353   else
 354     {
 355       GList *last;
 356
 357       last = list;
 358       while (last->next)
 359         last = last->next;
 360
 361       last->next = g_list_alloc ();
 362       last->next->data = data;
 363       last->next->prev = last;
 364
 365       return list;
 366     }
 367 }
 368
 369 GList *
 370 g_list_concat (GList *list1, GList *list2)
 371 {
 372   GList *tmp_list;
 373
 374   if (list2)
 375     {
 376       tmp_list = g_list_last (list1);
 377       if (tmp_list)
 378         tmp_list->next = list2;
 379       else
 380         list1 = list2;
 381       list2->prev = tmp_list;
 382     }
 383
 384   return list1;
 385 }
 386
 387 GList*
 388 g_list_remove (GList         *list,
 389                gconstpointer  data)
 390 {
 391   GList *tmp;
 392
 393   tmp = list;
 394   while (tmp)
 395     {
 396       if (tmp->data != data)
 397         tmp = tmp->next;
 398       else
 399         {
 400           if (tmp->prev)
 401             tmp->prev->next = tmp->next;
 402           if (tmp->next)
 403             tmp->next->prev = tmp->prev;
 404
 405           if (list == tmp)
 406             list = list->next;
 407
 408           _g_list_free_1 (tmp);
 409
 410           break;
 411         }
 412     }
 413   return list;
 414 }
 415
 416 GList*
 417 g_list_remove_all (GList        *list,
 418                    gconstpointer data)
 419 {
 420   GList *tmp = list;
 421
 422   while (tmp)
 423     {
 424       if (tmp->data != data)
 425         tmp = tmp->next;
 426       else
 427         {
 428           GList *next = tmp->next;
 429
 430           if (tmp->prev)
 431             tmp->prev->next = next;
 432           else
 433             list = next;
 434           if (next)
 435             next->prev = tmp->prev;
 436
 437           _g_list_free_1 (tmp);
 438           tmp = next;
 439         }
 440     }
 441   return list;
 442 }
 443
 444 static inline GList*
 445 _g_list_remove_link (GList *list,
 446                      GList *link)
 447 {
 448   if (link)
 449     {
 450       if (link->prev)
 451         link->prev->next = link->next;
 452       if (link->next)
 453         link->next->prev = link->prev;
 454
 455       if (link == list)
 456         list = list->next;
 457
 458       link->next = NULL;
 459       link->prev = NULL;
 460     }
 461
 462   return list;
 463 }
 464
 465 GList*
 466 g_list_remove_link (GList *list,
 467                     GList *link)
 468 {
 469   return _g_list_remove_link (list, link);
 470 }
 471
 472 GList*
 473 g_list_delete_link (GList *list,
 474                     GList *link)
 475 {
 476   list = _g_list_remove_link (list, link);
 477   _g_list_free_1 (link);
 478
 479   return list;
 480 }
 481
 482 GList*
 483 g_list_copy (GList *list)
 484 {
 485   GList *new_list = NULL;
 486
 487   if (list)
 488     {
 489       GList *last;
 490
 491       new_list = _g_list_alloc ();
 492       new_list->data = list->data;
 493       last = new_list;
 494       list = list->next;
 495       while (list)
 496         {
 497           last->next = _g_list_alloc ();
 498           last->next->prev = last;
 499           last = last->next;
 500           last->data = list->data;
 501           list = list->next;
 502         }
 503     }
 504
 505   return new_list;
 506 }
 507
 508 GList*
 509 g_list_reverse (GList *list)
 510 {
 511   GList *last;
 512
 513   last = NULL;
 514   while (list)
 515     {
 516       last = list;
 517       list = last->next;
 518       last->next = last->prev;
 519       last->prev = list;
 520     }
 521
 522   return last;
 523 }
 524
 525 GList*
 526 g_list_nth (GList *list,
 527             guint  n)
 528 {
 529   while ((n-- > 0) && list)
 530     list = list->next;
 531
 532   return list;
 533 }
 534
 535 GList*
 536 g_list_nth_prev (GList *list,
 537                  guint  n)
 538 {
 539   while ((n-- > 0) && list)
 540     list = list->prev;
 541
 542   return list;
 543 }
 544
 545 gpointer
 546 g_list_nth_data (GList     *list,
 547                  guint      n)
 548 {
 549   while ((n-- > 0) && list)
 550     list = list->next;
 551
 552   return list ? list->data : NULL;
 553 }
 554
 555 GList*
 556 g_list_find (GList         *list,
 557              gconstpointer  data)
 558 {
 559   while (list)
 560     {
 561       if (list->data == data)
 562         break;
 563       list = list->next;
 564     }
 565
 566   return list;
 567 }
 568
 569 GList*
 570 g_list_find_custom (GList         *list,
 571                     gconstpointer  data,
 572                     GCompareFunc   func)
 573 {
 574   g_return_val_if_fail (func != NULL, list);
 575
 576   while (list)
 577     {
 578       if (! func (list->data, data))
 579         return list;
 580       list = list->next;
 581     }
 582
 583   return NULL;
 584 }
 585
 586
 587 gint
 588 g_list_position (GList *list,
 589                  GList *link)
 590 {
 591   gint i;
 592
 593   i = 0;
 594   while (list)
 595     {
 596       if (list == link)
 597         return i;
 598       i++;
 599       list = list->next;
 600     }
 601
 602   return -1;
 603 }
 604
 605 gint
 606 g_list_index (GList         *list,
 607               gconstpointer  data)
 608 {
 609   gint i;
 610
 611   i = 0;
 612   while (list)
 613     {
 614       if (list->data == data)
 615         return i;
 616       i++;
 617       list = list->next;
 618     }
 619
 620   return -1;
 621 }
 622
 623 GList*
 624 g_list_last (GList *list)
 625 {
 626   if (list)
 627     {
 628       while (list->next)
 629         list = list->next;
 630     }
 631
 632   return list;
 633 }
 634
 635 GList*
 636 g_list_first (GList *list)
 637 {
 638   if (list)
 639     {
 640       while (list->prev)
 641         list = list->prev;
 642     }
 643
 644   return list;
 645 }
 646
 647 guint
 648 g_list_length (GList *list)
 649 {
 650   guint length;
 651
 652   length = 0;
 653   while (list)
 654     {
 655       length++;
 656       list = list->next;
 657     }
 658
 659   return length;
 660 }
 661
 662 void
 663 g_list_foreach (GList    *list,
 664                 GFunc     func,
 665                 gpointer  user_data)
 666 {
 667   while (list)
 668     {
 669       GList *next = list->next;
 670       (*func) (list->data, user_data);
 671       list = next;
 672     }
 673 }
 674
 675
 676 GList*
 677 g_list_insert_sorted (GList        *list,
 678                       gpointer      data,
 679                       GCompareFunc  func)
 680 {
 681   GList *tmp_list = list;
 682   GList *new_list;
 683   gint cmp;
 684
 685   g_return_val_if_fail (func != NULL, list);
 686
 687   if (!list)
 688     {
 689       new_list = _g_list_alloc ();
 690       new_list->data = data;
 691       return new_list;
 692     }
 693
 694   cmp = (*func) (data, tmp_list->data);
 695
 696   while ((tmp_list->next) && (cmp > 0))
 697     {
 698       tmp_list = tmp_list->next;
 699       cmp = (*func) (data, tmp_list->data);
 700     }
 701
 702   new_list = _g_list_alloc ();
 703   new_list->data = data;
 704
 705   if ((!tmp_list->next) && (cmp > 0))
 706     {
 707       tmp_list->next = new_list;
 708       new_list->prev = tmp_list;
 709       return list;
 710     }
 711
 712   if (tmp_list->prev)
 713     {
 714       tmp_list->prev->next = new_list;
 715       new_list->prev = tmp_list->prev;
 716     }
 717   new_list->next = tmp_list;
 718   tmp_list->prev = new_list;
 719
 720   if (tmp_list == list)
 721     return new_list;
 722   else
 723     return list;
 724 }
 725
 726 static GList *
 727 g_list_sort_merge (GList     *l1,
 728                    GList     *l2,
 729                    GFunc     compare_func,
 730                    gboolean  use_data,
 731                    gpointer  user_data)
 732 {
 733   GList list, *l, *lprev;
 734   gint cmp;
 735
 736   l = &list;
 737   lprev = NULL;
 738
 739   while (l1 && l2)
 740     {
 741       if (use_data)
 742         cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 743       else
 744         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 745
 746       if (cmp <= 0)
 747         {
 748           l->next = l1;
 749           l = l->next;
 750           l->prev = lprev;
 751           lprev = l;
 752           l1 = l1->next;
 753         }
 754       else
 755         {
 756           l->next = l2;
 757           l = l->next;
 758           l->prev = lprev;
 759           lprev = l;
 760           l2 = l2->next;
 761         }
 762     }
 763   l->next = l1 ? l1 : l2;
 764   l->next->prev = l;
 765
 766   return list.next;
 767 }
 768
 769 static GList*
 770 g_list_sort_real (GList    *list,
 771                   GFunc     compare_func,
 772                   gboolean  use_data,
 773                   gpointer  user_data)
 774 {
 775   GList *l1, *l2;
 776
 777   if (!list)
 778     return NULL;
 779   if (!list->next)
 780     return list;
 781
 782   l1 = list;
 783   l2 = list->next;
 784
 785   while ((l2 = l2->next) != NULL)
 786     {
 787       if ((l2 = l2->next) == NULL)
 788         break;
 789       l1 = l1->next;
 790     }
 791   l2 = l1->next;
 792   l1->next = NULL;
 793
 794   return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
 795                             g_list_sort_real (l2, compare_func, use_data, user_data),
 796                             compare_func,
 797                             use_data,
 798                             user_data);
 799 }
 800
 801 GList *
 802 g_list_sort (GList        *list,
 803              GCompareFunc  compare_func)
 804 {
 805   return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 806
 807 }
 808
 809 GList *
 810 g_list_sort_with_data (GList            *list,
 811                        GCompareDataFunc  compare_func,
 812                        gpointer          user_data)
 813 {
 814   return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 815 }
 816
 817 #define __G_LIST_C__
 818 #include "galiasdef.c"