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