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