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