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