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 Lesser 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  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser 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  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 /*
  28  * MT safe
  29  */
  30
  31 #include "config.h"
  32
  33 #include "glib.h"
  34 #include "galias.h"
  35
  36
  37 void g_slist_push_allocator (gpointer dummy) { /* present for binary compat only */ }
  38 void g_slist_pop_allocator  (void)           { /* present for binary compat only */ }
  39
  40 #define _g_slist_alloc0()       g_slice_new0 (GSList)
  41 #define _g_slist_free1(slist)   g_slice_free (GSList, slist)
  42
  43 GSList*
  44 g_slist_alloc (void)
  45 {
  46   return _g_slist_alloc0 ();
  47 }
  48
  49 void
  50 g_slist_free (GSList *slist)
  51 {
  52   g_slice_free_chain (sizeof (GSList), slist, G_STRUCT_OFFSET (GSList, next));
  53 }
  54
  55 void
  56 g_slist_free_1 (GSList *slist)
  57 {
  58   _g_slist_free1 (slist);
  59 }
  60
  61 GSList*
  62 g_slist_append (GSList   *list,
  63                 gpointer  data)
  64 {
  65   GSList *new_list;
  66   GSList *last;
  67
  68   new_list = _g_slist_alloc0 ();
  69   new_list->data = data;
  70
  71   if (list)
  72     {
  73       last = g_slist_last (list);
  74       /* g_assert (last != NULL); */
  75       last->next = new_list;
  76
  77       return list;
  78     }
  79   else
  80       return new_list;
  81 }
  82
  83 GSList*
  84 g_slist_prepend (GSList   *list,
  85                  gpointer  data)
  86 {
  87   GSList *new_list;
  88
  89   new_list = _g_slist_alloc0 ();
  90   new_list->data = data;
  91   new_list->next = list;
  92
  93   return new_list;
  94 }
  95
  96 GSList*
  97 g_slist_insert (GSList   *list,
  98                 gpointer  data,
  99                 gint      position)
 100 {
 101   GSList *prev_list;
 102   GSList *tmp_list;
 103   GSList *new_list;
 104
 105   if (position < 0)
 106     return g_slist_append (list, data);
 107   else if (position == 0)
 108     return g_slist_prepend (list, data);
 109
 110   new_list = _g_slist_alloc0 ();
 111   new_list->data = data;
 112
 113   if (!list)
 114     return new_list;
 115
 116   prev_list = NULL;
 117   tmp_list = list;
 118
 119   while ((position-- > 0) && tmp_list)
 120     {
 121       prev_list = tmp_list;
 122       tmp_list = tmp_list->next;
 123     }
 124
 125   if (prev_list)
 126     {
 127       new_list->next = prev_list->next;
 128       prev_list->next = new_list;
 129     }
 130   else
 131     {
 132       new_list->next = list;
 133       list = new_list;
 134     }
 135
 136   return list;
 137 }
 138
 139 GSList*
 140 g_slist_insert_before (GSList  *slist,
 141                        GSList  *sibling,
 142                        gpointer data)
 143 {
 144   if (!slist)
 145     {
 146       slist = g_slist_alloc ();
 147       slist->data = data;
 148       g_return_val_if_fail (sibling == NULL, slist);
 149       return slist;
 150     }
 151   else
 152     {
 153       GSList *node, *last = NULL;
 154
 155       for (node = slist; node; last = node, node = last->next)
 156         if (node == sibling)
 157           break;
 158       if (!last)
 159         {
 160           node = g_slist_alloc ();
 161           node->data = data;
 162           node->next = slist;
 163
 164           return node;
 165         }
 166       else
 167         {
 168           node = g_slist_alloc ();
 169           node->data = data;
 170           node->next = last->next;
 171           last->next = node;
 172
 173           return slist;
 174         }
 175     }
 176 }
 177
 178 GSList *
 179 g_slist_concat (GSList *list1, GSList *list2)
 180 {
 181   if (list2)
 182     {
 183       if (list1)
 184         g_slist_last (list1)->next = list2;
 185       else
 186         list1 = list2;
 187     }
 188
 189   return list1;
 190 }
 191
 192 GSList*
 193 g_slist_remove (GSList        *list,
 194                 gconstpointer  data)
 195 {
 196   GSList *tmp, *prev = NULL;
 197
 198   tmp = list;
 199   while (tmp)
 200     {
 201       if (tmp->data == data)
 202         {
 203           if (prev)
 204             prev->next = tmp->next;
 205           else
 206             list = tmp->next;
 207
 208           g_slist_free_1 (tmp);
 209           break;
 210         }
 211       prev = tmp;
 212       tmp = prev->next;
 213     }
 214
 215   return list;
 216 }
 217
 218 GSList*
 219 g_slist_remove_all (GSList        *list,
 220                     gconstpointer  data)
 221 {
 222   GSList *tmp, *prev = NULL;
 223
 224   tmp = list;
 225   while (tmp)
 226     {
 227       if (tmp->data == data)
 228         {
 229           GSList *next = tmp->next;
 230
 231           if (prev)
 232             prev->next = next;
 233           else
 234             list = next;
 235
 236           g_slist_free_1 (tmp);
 237           tmp = next;
 238         }
 239       else
 240         {
 241           prev = tmp;
 242           tmp = prev->next;
 243         }
 244     }
 245
 246   return list;
 247 }
 248
 249 static inline GSList*
 250 _g_slist_remove_link (GSList *list,
 251                       GSList *link)
 252 {
 253   GSList *tmp;
 254   GSList *prev;
 255
 256   prev = NULL;
 257   tmp = list;
 258
 259   while (tmp)
 260     {
 261       if (tmp == link)
 262         {
 263           if (prev)
 264             prev->next = tmp->next;
 265           if (list == tmp)
 266             list = list->next;
 267
 268           tmp->next = NULL;
 269           break;
 270         }
 271
 272       prev = tmp;
 273       tmp = tmp->next;
 274     }
 275
 276   return list;
 277 }
 278
 279 GSList*
 280 g_slist_remove_link (GSList *list,
 281                      GSList *link)
 282 {
 283   return _g_slist_remove_link (list, link);
 284 }
 285
 286 GSList*
 287 g_slist_delete_link (GSList *list,
 288                      GSList *link)
 289 {
 290   list = _g_slist_remove_link (list, link);
 291   _g_slist_free1 (link);
 292
 293   return list;
 294 }
 295
 296 GSList*
 297 g_slist_copy (GSList *list)
 298 {
 299   GSList *new_list = NULL;
 300
 301   if (list)
 302     {
 303       GSList *last;
 304
 305       new_list = _g_slist_alloc0 ();
 306       new_list->data = list->data;
 307       last = new_list;
 308       list = list->next;
 309       while (list)
 310         {
 311           last->next = _g_slist_alloc0 ();
 312           last = last->next;
 313           last->data = list->data;
 314           list = list->next;
 315         }
 316     }
 317
 318   return new_list;
 319 }
 320
 321 GSList*
 322 g_slist_reverse (GSList *list)
 323 {
 324   GSList *prev = NULL;
 325
 326   while (list)
 327     {
 328       GSList *next = list->next;
 329
 330       list->next = prev;
 331
 332       prev = list;
 333       list = next;
 334     }
 335
 336   return prev;
 337 }
 338
 339 GSList*
 340 g_slist_nth (GSList *list,
 341              guint   n)
 342 {
 343   while (n-- > 0 && list)
 344     list = list->next;
 345
 346   return list;
 347 }
 348
 349 gpointer
 350 g_slist_nth_data (GSList   *list,
 351                   guint     n)
 352 {
 353   while (n-- > 0 && list)
 354     list = list->next;
 355
 356   return list ? list->data : NULL;
 357 }
 358
 359 GSList*
 360 g_slist_find (GSList        *list,
 361               gconstpointer  data)
 362 {
 363   while (list)
 364     {
 365       if (list->data == data)
 366         break;
 367       list = list->next;
 368     }
 369
 370   return list;
 371 }
 372
 373 GSList*
 374 g_slist_find_custom (GSList        *list,
 375                      gconstpointer  data,
 376                      GCompareFunc   func)
 377 {
 378   g_return_val_if_fail (func != NULL, list);
 379
 380   while (list)
 381     {
 382       if (! func (list->data, data))
 383         return list;
 384       list = list->next;
 385     }
 386
 387   return NULL;
 388 }
 389
 390 gint
 391 g_slist_position (GSList *list,
 392                   GSList *link)
 393 {
 394   gint i;
 395
 396   i = 0;
 397   while (list)
 398     {
 399       if (list == link)
 400         return i;
 401       i++;
 402       list = list->next;
 403     }
 404
 405   return -1;
 406 }
 407
 408 gint
 409 g_slist_index (GSList        *list,
 410                gconstpointer  data)
 411 {
 412   gint i;
 413
 414   i = 0;
 415   while (list)
 416     {
 417       if (list->data == data)
 418         return i;
 419       i++;
 420       list = list->next;
 421     }
 422
 423   return -1;
 424 }
 425
 426 GSList*
 427 g_slist_last (GSList *list)
 428 {
 429   if (list)
 430     {
 431       while (list->next)
 432         list = list->next;
 433     }
 434
 435   return list;
 436 }
 437
 438 guint
 439 g_slist_length (GSList *list)
 440 {
 441   guint length;
 442
 443   length = 0;
 444   while (list)
 445     {
 446       length++;
 447       list = list->next;
 448     }
 449
 450   return length;
 451 }
 452
 453 void
 454 g_slist_foreach (GSList   *list,
 455                  GFunc     func,
 456                  gpointer  user_data)
 457 {
 458   while (list)
 459     {
 460       GSList *next = list->next;
 461       (*func) (list->data, user_data);
 462       list = next;
 463     }
 464 }
 465
 466 GSList*
 467 g_slist_insert_sorted (GSList       *list,
 468                        gpointer      data,
 469                        GCompareFunc  func)
 470 {
 471   GSList *tmp_list = list;
 472   GSList *prev_list = NULL;
 473   GSList *new_list;
 474   gint cmp;
 475
 476   g_return_val_if_fail (func != NULL, list);
 477
 478   if (!list)
 479     {
 480       new_list = _g_slist_alloc0 ();
 481       new_list->data = data;
 482       return new_list;
 483     }
 484
 485   cmp = (*func) (data, tmp_list->data);
 486
 487   while ((tmp_list->next) && (cmp > 0))
 488     {
 489       prev_list = tmp_list;
 490       tmp_list = tmp_list->next;
 491       cmp = (*func) (data, tmp_list->data);
 492     }
 493
 494   new_list = _g_slist_alloc0 ();
 495   new_list->data = data;
 496
 497   if ((!tmp_list->next) && (cmp > 0))
 498     {
 499       tmp_list->next = new_list;
 500       return list;
 501     }
 502
 503   if (prev_list)
 504     {
 505       prev_list->next = new_list;
 506       new_list->next = tmp_list;
 507       return list;
 508     }
 509   else
 510     {
 511       new_list->next = list;
 512       return new_list;
 513     }
 514 }
 515
 516 static GSList *
 517 g_slist_sort_merge (GSList   *l1,
 518                     GSList   *l2,
 519                     GFunc     compare_func,
 520                     gboolean  use_data,
 521                     gpointer  user_data)
 522 {
 523   GSList list, *l;
 524   gint cmp;
 525
 526   l=&list;
 527
 528   while (l1 && l2)
 529     {
 530       if (use_data)
 531         cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 532       else
 533         cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
 534
 535       if (cmp <= 0)
 536         {
 537           l=l->next=l1;
 538           l1=l1->next;
 539         }
 540       else
 541         {
 542           l=l->next=l2;
 543           l2=l2->next;
 544         }
 545     }
 546   l->next= l1 ? l1 : l2;
 547
 548   return list.next;
 549 }
 550
 551 static GSList *
 552 g_slist_sort_real (GSList   *list,
 553                    GFunc     compare_func,
 554                    gboolean  use_data,
 555                    gpointer  user_data)
 556 {
 557   GSList *l1, *l2;
 558
 559   if (!list)
 560     return NULL;
 561   if (!list->next)
 562     return list;
 563
 564   l1 = list;
 565   l2 = list->next;
 566
 567   while ((l2 = l2->next) != NULL)
 568     {
 569       if ((l2 = l2->next) == NULL)
 570         break;
 571       l1=l1->next;
 572     }
 573   l2 = l1->next;
 574   l1->next = NULL;
 575
 576   return g_slist_sort_merge (g_slist_sort_real (list, compare_func, use_data, user_data),
 577                              g_slist_sort_real (l2, compare_func, use_data, user_data),
 578                              compare_func,
 579                              use_data,
 580                              user_data);
 581 }
 582
 583 GSList *
 584 g_slist_sort (GSList       *list,
 585               GCompareFunc  compare_func)
 586 {
 587   return g_slist_sort_real (list, (GFunc) compare_func, FALSE, NULL);
 588 }
 589
 590 GSList *
 591 g_slist_sort_with_data (GSList           *list,
 592                         GCompareDataFunc  compare_func,
 593                         gpointer          user_data)
 594 {
 595   return g_slist_sort_real (list, (GFunc) compare_func, TRUE, user_data);
 596 }
 597
 598 #define __G_SLIST_C__
 599 #include "galiasdef.c"