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