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