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