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