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