gslist.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   GSList        *free_lists; /* implementation specific */
  31 };
  32
  33 static GAllocator       *current_allocator = NULL;
  34
  35 void
  36 g_slist_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_SLIST)
  42     {
  43       allocator->type = G_ALLOCATOR_SLIST;
  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 (GSList),
  55                                               sizeof (GSList) * 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_slist_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 GSList*
  80 g_slist_alloc (void)
  81 {
  82   GSList *list;
  83
  84   if (!current_allocator)
  85     g_slist_push_allocator (g_allocator_new ("GLib default GSList allocator", 1024));
  86
  87   if (!current_allocator->free_lists)
  88     {
  89       list = g_chunk_new (GSList, 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
 108   return list;
 109 }
 110
 111 void
 112 g_slist_free (GSList *list)
 113 {
 114   if (list)
 115     {
 116       list->data = list->next;
 117       list->next = current_allocator->free_lists;
 118       current_allocator->free_lists = list;
 119     }
 120 }
 121
 122 void
 123 g_slist_free_1 (GSList *list)
 124 {
 125   if (list)
 126     {
 127       list->data = NULL;
 128       list->next = current_allocator->free_lists;
 129       current_allocator->free_lists = list;
 130     }
 131 }
 132
 133 GSList*
 134 g_slist_append (GSList   *list,
 135                 gpointer  data)
 136 {
 137   GSList *new_list;
 138   GSList *last;
 139
 140   new_list = g_slist_alloc ();
 141   new_list->data = data;
 142
 143   if (list)
 144     {
 145       last = g_slist_last (list);
 146       /* g_assert (last != NULL); */
 147       last->next = new_list;
 148
 149       return list;
 150     }
 151   else
 152       return new_list;
 153 }
 154
 155 GSList*
 156 g_slist_prepend (GSList   *list,
 157                  gpointer  data)
 158 {
 159   GSList *new_list;
 160
 161   new_list = g_slist_alloc ();
 162   new_list->data = data;
 163   new_list->next = list;
 164
 165   return new_list;
 166 }
 167
 168 GSList*
 169 g_slist_insert (GSList   *list,
 170                 gpointer  data,
 171                 gint      position)
 172 {
 173   GSList *prev_list;
 174   GSList *tmp_list;
 175   GSList *new_list;
 176
 177   if (position < 0)
 178     return g_slist_append (list, data);
 179   else if (position == 0)
 180     return g_slist_prepend (list, data);
 181
 182   new_list = g_slist_alloc ();
 183   new_list->data = data;
 184
 185   if (!list)
 186     return new_list;
 187
 188   prev_list = NULL;
 189   tmp_list = list;
 190
 191   while ((position-- > 0) && tmp_list)
 192     {
 193       prev_list = tmp_list;
 194       tmp_list = tmp_list->next;
 195     }
 196
 197   if (prev_list)
 198     {
 199       new_list->next = prev_list->next;
 200       prev_list->next = new_list;
 201     }
 202   else
 203     {
 204       new_list->next = list;
 205       list = new_list;
 206     }
 207
 208   return list;
 209 }
 210
 211 GSList *
 212 g_slist_concat (GSList *list1, GSList *list2)
 213 {
 214   if (list2)
 215     {
 216       if (list1)
 217         g_slist_last (list1)->next = list2;
 218       else
 219         list1 = list2;
 220     }
 221
 222   return list1;
 223 }
 224
 225 GSList*
 226 g_slist_remove (GSList   *list,
 227                 gpointer  data)
 228 {
 229   GSList *tmp;
 230   GSList *prev;
 231
 232   prev = NULL;
 233   tmp = list;
 234
 235   while (tmp)
 236     {
 237       if (tmp->data == data)
 238         {
 239           if (prev)
 240             prev->next = tmp->next;
 241           if (list == tmp)
 242             list = list->next;
 243
 244           tmp->next = NULL;
 245           g_slist_free (tmp);
 246
 247           break;
 248         }
 249
 250       prev = tmp;
 251       tmp = tmp->next;
 252     }
 253
 254   return list;
 255 }
 256
 257 GSList*
 258 g_slist_remove_link (GSList *list,
 259                      GSList *link)
 260 {
 261   GSList *tmp;
 262   GSList *prev;
 263
 264   prev = NULL;
 265   tmp = list;
 266
 267   while (tmp)
 268     {
 269       if (tmp == link)
 270         {
 271           if (prev)
 272             prev->next = tmp->next;
 273           if (list == tmp)
 274             list = list->next;
 275
 276           tmp->next = NULL;
 277           break;
 278         }
 279
 280       prev = tmp;
 281       tmp = tmp->next;
 282     }
 283
 284   return list;
 285 }
 286
 287 GSList*
 288 g_slist_copy (GSList *list)
 289 {
 290   GSList *new_list = NULL;
 291
 292   if (list)
 293     {
 294       GSList *last;
 295
 296       new_list = g_slist_alloc ();
 297       new_list->data = list->data;
 298       last = new_list;
 299       list = list->next;
 300       while (list)
 301         {
 302           last->next = g_slist_alloc ();
 303           last = last->next;
 304           last->data = list->data;
 305           list = list->next;
 306         }
 307     }
 308
 309   return new_list;
 310 }
 311
 312 GSList*
 313 g_slist_reverse (GSList *list)
 314 {
 315   GSList *tmp;
 316   GSList *prev;
 317   GSList *last;
 318
 319   last = NULL;
 320   prev = NULL;
 321
 322   while (list)
 323     {
 324       last = list;
 325
 326       tmp = list->next;
 327       list->next = prev;
 328
 329       prev = list;
 330       list = tmp;
 331     }
 332
 333   return last;
 334 }
 335
 336 GSList*
 337 g_slist_nth (GSList *list,
 338              guint   n)
 339 {
 340   while ((n-- > 0) && list)
 341     list = list->next;
 342
 343   return list;
 344 }
 345
 346 gpointer
 347 g_slist_nth_data (GSList   *list,
 348                   guint     n)
 349 {
 350   while ((n-- > 0) && list)
 351     list = list->next;
 352
 353   return list ? list->data : NULL;
 354 }
 355
 356 GSList*
 357 g_slist_find (GSList   *list,
 358               gpointer  data)
 359 {
 360   while (list)
 361     {
 362       if (list->data == data)
 363         break;
 364       list = list->next;
 365     }
 366
 367   return list;
 368 }
 369
 370 GSList*
 371 g_slist_find_custom (GSList      *list,
 372                      gpointer     data,
 373                      GCompareFunc func)
 374 {
 375   g_return_val_if_fail (func != NULL, list);
 376
 377   while (list)
 378     {
 379       if (! func (list->data, data))
 380         return list;
 381       list = list->next;
 382     }
 383
 384   return NULL;
 385 }
 386
 387 gint
 388 g_slist_position (GSList *list,
 389                   GSList *link)
 390 {
 391   gint i;
 392
 393   i = 0;
 394   while (list)
 395     {
 396       if (list == link)
 397         return i;
 398       i++;
 399       list = list->next;
 400     }
 401
 402   return -1;
 403 }
 404
 405 gint
 406 g_slist_index (GSList   *list,
 407                gpointer data)
 408 {
 409   gint i;
 410
 411   i = 0;
 412   while (list)
 413     {
 414       if (list->data == data)
 415         return i;
 416       i++;
 417       list = list->next;
 418     }
 419
 420   return -1;
 421 }
 422
 423 GSList*
 424 g_slist_last (GSList *list)
 425 {
 426   if (list)
 427     {
 428       while (list->next)
 429         list = list->next;
 430     }
 431
 432   return list;
 433 }
 434
 435 guint
 436 g_slist_length (GSList *list)
 437 {
 438   guint length;
 439
 440   length = 0;
 441   while (list)
 442     {
 443       length++;
 444       list = list->next;
 445     }
 446
 447   return length;
 448 }
 449
 450 void
 451 g_slist_foreach (GSList   *list,
 452                  GFunc     func,
 453                  gpointer  user_data)
 454 {
 455   while (list)
 456     {
 457       (*func) (list->data, user_data);
 458       list = list->next;
 459     }
 460 }
 461
 462 GSList*
 463 g_slist_insert_sorted (GSList       *list,
 464                        gpointer      data,
 465                        GCompareFunc  func)
 466 {
 467   GSList *tmp_list = list;
 468   GSList *prev_list = NULL;
 469   GSList *new_list;
 470   gint cmp;
 471
 472   g_return_val_if_fail (func != NULL, list);
 473
 474   if (!list)
 475     {
 476       new_list = g_slist_alloc();
 477       new_list->data = data;
 478       return new_list;
 479     }
 480
 481   cmp = (*func) (data, tmp_list->data);
 482
 483   while ((tmp_list->next) && (cmp > 0))
 484     {
 485       prev_list = tmp_list;
 486       tmp_list = tmp_list->next;
 487       cmp = (*func) (data, tmp_list->data);
 488     }
 489
 490   new_list = g_slist_alloc();
 491   new_list->data = data;
 492
 493   if ((!tmp_list->next) && (cmp > 0))
 494     {
 495       tmp_list->next = new_list;
 496       return list;
 497     }
 498
 499   if (prev_list)
 500     {
 501       prev_list->next = new_list;
 502       new_list->next = tmp_list;
 503       return list;
 504     }
 505   else
 506     {
 507       new_list->next = list;
 508       return new_list;
 509     }
 510 }
 511
 512 static GSList*
 513 g_slist_sort_merge  (GSList      *l1,
 514                      GSList      *l2,
 515                      GCompareFunc compare_func)
 516 {
 517   GSList list, *l;
 518
 519   l=&list;
 520
 521   while (l1 && l2)
 522     {
 523       if (compare_func(l1->data,l2->data) < 0)
 524         {
 525           l=l->next=l1;
 526           l1=l1->next;
 527         }
 528       else
 529         {
 530           l=l->next=l2;
 531           l2=l2->next;
 532         }
 533     }
 534   l->next= l1 ? l1 : l2;
 535
 536   return list.next;
 537 }
 538
 539 GSList*
 540 g_slist_sort (GSList       *list,
 541               GCompareFunc compare_func)
 542 {
 543   GSList *l1, *l2;
 544
 545   if (!list)
 546     return NULL;
 547   if (!list->next)
 548     return list;
 549
 550   l1 = list;
 551   l2 = list->next;
 552
 553   while ((l2 = l2->next) != NULL)
 554     {
 555       if ((l2 = l2->next) == NULL)
 556         break;
 557       l1=l1->next;
 558     }
 559   l2 = l1->next;
 560   l1->next = NULL;
 561
 562   return g_slist_sort_merge (g_slist_sort (list, compare_func),
 563                              g_slist_sort (l2,   compare_func),
 564                              compare_func);
 565 }