1 /* GLIB - Library of useful routines for C programming

     2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

     3  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Lesser General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Lesser General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Lesser General Public

    16  * License along with this library; if not, write to the

    17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

    18  * Boston, MA 02111-1307, USA.

    19  */

    20 

    21 /*

    22  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

    23  * file for a list of people on the GLib Team.  See the ChangeLog

    24  * files for a list of changes.  These files are distributed with

    25  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

    26  */

    27 

    28 /* 

    29  * MT safe

    30  */

    31 

    32 #include "config.h"

    33 

    34 #include "glib.h"

    35 #include "galias.h"

    36 

    37 

    38 EXPORT_C void g_slist_push_allocator (gpointer dummy) { /* present for binary compat only */ }

    39 EXPORT_C void g_slist_pop_allocator  (void)           { /* present for binary compat only */ }

    40 

    41 #define _g_slist_alloc0()       g_slice_new0 (GSList)

    42 #define _g_slist_alloc()        g_slice_new (GSList)

    43 #define _g_slist_free1(slist)   g_slice_free (GSList, slist)

    44 

    45 EXPORT_C GSList*

    46 g_slist_alloc (void)

    47 {

    48   return _g_slist_alloc0 ();

    49 }

    50 

    51 EXPORT_C void

    52 g_slist_free (GSList *slist)

    53 {

    54   g_slice_free_chain (GSList, slist, next);

    55 }

    56 

    57 EXPORT_C void

    58 g_slist_free_1 (GSList *slist)

    59 {

    60   _g_slist_free1 (slist);

    61 }

    62 

    63 EXPORT_C GSList*

    64 g_slist_append (GSList   *list,

    65 		gpointer  data)

    66 {

    67   GSList *new_list;

    68   GSList *last;

    69 

    70   new_list = _g_slist_alloc ();

    71   new_list->data = data;

    72   new_list->next = NULL;

    73 

    74   if (list)

    75     {

    76       last = g_slist_last (list);

    77       /* g_assert (last != NULL); */

    78       last->next = new_list;

    79 

    80       return list;

    81     }

    82   else

    83     return new_list;

    84 }

    85 

    86 EXPORT_C GSList*

    87 g_slist_prepend (GSList   *list,

    88 		 gpointer  data)

    89 {

    90   GSList *new_list;

    91 

    92   new_list = _g_slist_alloc ();

    93   new_list->data = data;

    94   new_list->next = list;

    95 

    96   return new_list;

    97 }

    98 

    99 EXPORT_C GSList*

   100 g_slist_insert (GSList   *list,

   101 		gpointer  data,

   102 		gint      position)

   103 {

   104   GSList *prev_list;

   105   GSList *tmp_list;

   106   GSList *new_list;

   107 

   108   if (position < 0)

   109     return g_slist_append (list, data);

   110   else if (position == 0)

   111     return g_slist_prepend (list, data);

   112 

   113   new_list = _g_slist_alloc ();

   114   

   115   new_list->data = data;

   116 

   117   if (!list)

   118     {

   119       new_list->next = NULL;

   120       return new_list;

   121     }

   122 

   123   prev_list = NULL;

   124   tmp_list = list;

   125 

   126   while ((position-- > 0) && tmp_list)

   127     {

   128       prev_list = tmp_list;

   129       tmp_list = tmp_list->next;

   130     }

   131 

   132   if (prev_list)

   133     {

   134       new_list->next = prev_list->next;

   135       prev_list->next = new_list;

   136     }

   137   else

   138     {

   139       new_list->next = list;

   140       list = new_list;

   141     }

   142 

   143   return list;

   144 }

   145 

   146 EXPORT_C GSList*

   147 g_slist_insert_before (GSList  *slist,

   148 		       GSList  *sibling,

   149 		       gpointer data)

   150 {

   151   if (!slist)

   152     {

   153       slist = _g_slist_alloc ();

   154       slist->data = data;

   155       slist->next = NULL;

   156       g_return_val_if_fail (sibling == NULL, slist);

   157       return slist;

   158     }

   159   else

   160     {

   161       GSList *node, *last = NULL;

   162 

   163       for (node = slist; node; last = node, node = last->next)

   164 	if (node == sibling)

   165 	  break;

   166       if (!last)

   167 	{

   168 	  node = _g_slist_alloc ();

   169 	  

   170 	  node->data = data;

   171 	  node->next = slist;

   172 

   173 	  return node;

   174 	}

   175       else

   176 	{

   177 	  node = _g_slist_alloc ();

   178 	  node->data = data;

   179 	  node->next = last->next;

   180 	  last->next = node;

   181 

   182 	  return slist;

   183 	}

   184     }

   185 }

   186 

   187 EXPORT_C GSList *

   188 g_slist_concat (GSList *list1, GSList *list2)

   189 {

   190   if (list2)

   191     {

   192       if (list1)

   193 	g_slist_last (list1)->next = list2;

   194       else

   195 	list1 = list2;

   196     }

   197 

   198   return list1;

   199 }

   200 

   201 EXPORT_C GSList*

   202 g_slist_remove (GSList        *list,

   203 		gconstpointer  data)

   204 {

   205   GSList *tmp, *prev = NULL;

   206 

   207   tmp = list;

   208   while (tmp)

   209     {

   210       if (tmp->data == data)

   211 	{

   212 	  if (prev)

   213 	    prev->next = tmp->next;

   214 	  else

   215 	    list = tmp->next;

   216 

   217 	  g_slist_free_1 (tmp);

   218 	  break;

   219 	}

   220       prev = tmp;

   221       tmp = prev->next;

   222     }

   223 

   224   return list;

   225 }

   226 

   227 EXPORT_C GSList*

   228 g_slist_remove_all (GSList        *list,

   229 		    gconstpointer  data)

   230 {

   231   GSList *tmp, *prev = NULL;

   232 

   233   tmp = list;

   234   while (tmp)

   235     {

   236       if (tmp->data == data)

   237 	{

   238 	  GSList *next = tmp->next;

   239 

   240 	  if (prev)

   241 	    prev->next = next;

   242 	  else

   243 	    list = next;

   244 	  

   245 	  g_slist_free_1 (tmp);

   246 	  tmp = next;

   247 	}

   248       else

   249 	{

   250 	  prev = tmp;

   251 	  tmp = prev->next;

   252 	}

   253     }

   254 

   255   return list;

   256 }

   257 

   258 static inline GSList*

   259 _g_slist_remove_link (GSList *list,

   260 		      GSList *link)

   261 {

   262   GSList *tmp;

   263   GSList *prev;

   264 

   265   prev = NULL;

   266   tmp = list;

   267 

   268   while (tmp)

   269     {

   270       if (tmp == link)

   271 	{

   272 	  if (prev)

   273 	    prev->next = tmp->next;

   274 	  if (list == tmp)

   275 	    list = list->next;

   276 

   277 	  tmp->next = NULL;

   278 	  break;

   279 	}

   280 

   281       prev = tmp;

   282       tmp = tmp->next;

   283     }

   284 

   285   return list;

   286 }

   287 

   288 EXPORT_C GSList* 

   289 g_slist_remove_link (GSList *list,

   290 		     GSList *link)

   291 {

   292   return _g_slist_remove_link (list, link);

   293 }

   294 

   295 EXPORT_C GSList*

   296 g_slist_delete_link (GSList *list,

   297 		     GSList *link)

   298 {

   299   list = _g_slist_remove_link (list, link);

   300   _g_slist_free1 (link);

   301 

   302   return list;

   303 }

   304 

   305 EXPORT_C GSList*

   306 g_slist_copy (GSList *list)

   307 {

   308   GSList *new_list = NULL;

   309 

   310   if (list)

   311     {

   312       GSList *last;

   313 

   314       new_list = _g_slist_alloc ();

   315       new_list->data = list->data;

   316       last = new_list;

   317       list = list->next;

   318       while (list)

   319 	{

   320 	  last->next = _g_slist_alloc ();

   321 	  last = last->next;

   322 	  last->data = list->data;

   323 	  list = list->next;

   324 	}

   325       last->next = NULL;

   326     }

   327 

   328   return new_list;

   329 }

   330 

   331 EXPORT_C GSList*

   332 g_slist_reverse (GSList *list)

   333 {

   334   GSList *prev = NULL;

   335   

   336   while (list)

   337     {

   338       GSList *next = list->next;

   339 

   340       list->next = prev;

   341       

   342       prev = list;

   343       list = next;

   344     }

   345   

   346   return prev;

   347 }

   348 

   349 EXPORT_C GSList*

   350 g_slist_nth (GSList *list,

   351 	     guint   n)

   352 {

   353   while (n-- > 0 && list)

   354     list = list->next;

   355 

   356   return list;

   357 }

   358 

   359 EXPORT_C gpointer

   360 g_slist_nth_data (GSList   *list,

   361 		  guint     n)

   362 {

   363   while (n-- > 0 && list)

   364     list = list->next;

   365 

   366   return list ? list->data : NULL;

   367 }

   368 

   369 EXPORT_C GSList*

   370 g_slist_find (GSList        *list,

   371 	      gconstpointer  data)

   372 {

   373   while (list)

   374     {

   375       if (list->data == data)

   376 	break;

   377       list = list->next;

   378     }

   379 

   380   return list;

   381 }

   382 

   383 EXPORT_C GSList*

   384 g_slist_find_custom (GSList        *list,

   385 		     gconstpointer  data,

   386 		     GCompareFunc   func)

   387 {

   388   g_return_val_if_fail (func != NULL, list);

   389 

   390   while (list)

   391     {

   392       if (! func (list->data, data))

   393 	return list;

   394       list = list->next;

   395     }

   396 

   397   return NULL;

   398 }

   399 

   400 EXPORT_C gint

   401 g_slist_position (GSList *list,

   402 		  GSList *link)

   403 {

   404   gint i;

   405 

   406   i = 0;

   407   while (list)

   408     {

   409       if (list == link)

   410 	return i;

   411       i++;

   412       list = list->next;

   413     }

   414 

   415   return -1;

   416 }

   417 

   418 EXPORT_C gint

   419 g_slist_index (GSList        *list,

   420 	       gconstpointer  data)

   421 {

   422   gint i;

   423 

   424   i = 0;

   425   while (list)

   426     {

   427       if (list->data == data)

   428 	return i;

   429       i++;

   430       list = list->next;

   431     }

   432 

   433   return -1;

   434 }

   435 

   436 EXPORT_C GSList*

   437 g_slist_last (GSList *list)

   438 {

   439   if (list)

   440     {

   441       while (list->next)

   442 	list = list->next;

   443     }

   444 

   445   return list;

   446 }

   447 

   448 EXPORT_C guint

   449 g_slist_length (GSList *list)

   450 {

   451   guint length;

   452 

   453   length = 0;

   454   while (list)

   455     {

   456       length++;

   457       list = list->next;

   458     }

   459 

   460   return length;

   461 }

   462 

   463 EXPORT_C void

   464 g_slist_foreach (GSList   *list,

   465 		 GFunc     func,

   466 		 gpointer  user_data)

   467 {

   468   while (list)

   469     {

   470       GSList *next = list->next;

   471       (*func) (list->data, user_data);

   472       list = next;

   473     }

   474 }

   475 

   476 static GSList*

   477 g_slist_insert_sorted_real (GSList   *list,

   478 			    gpointer  data,

   479 			    GFunc     func,

   480 			    gpointer  user_data)

   481 {

   482   GSList *tmp_list = list;

   483   GSList *prev_list = NULL;

   484   GSList *new_list;

   485   gint cmp;

   486  

   487   g_return_val_if_fail (func != NULL, list);

   488 

   489   if (!list)

   490     {

   491       new_list = _g_slist_alloc ();

   492       new_list->data = data;

   493       new_list->next = NULL;

   494       return new_list;

   495     }

   496  

   497   cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);

   498  

   499   while ((tmp_list->next) && (cmp > 0))

   500     {

   501       prev_list = tmp_list;

   502       tmp_list = tmp_list->next;

   503 

   504       cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);

   505     }

   506 

   507   new_list = _g_slist_alloc ();

   508   new_list->data = data;

   509 

   510   if ((!tmp_list->next) && (cmp > 0))

   511     {

   512       tmp_list->next = new_list;

   513       new_list->next = NULL;

   514       return list;

   515     }

   516   

   517   if (prev_list)

   518     {

   519       prev_list->next = new_list;

   520       new_list->next = tmp_list;

   521       return list;

   522     }

   523   else

   524     {

   525       new_list->next = list;

   526       return new_list;

   527     }

   528 }

   529 

   530 EXPORT_C GSList*

   531 g_slist_insert_sorted (GSList       *list,

   532                        gpointer      data,

   533                        GCompareFunc  func)

   534 {

   535   return g_slist_insert_sorted_real (list, data, (GFunc) func, NULL);

   536 }

   537 

   538 EXPORT_C GSList*

   539 g_slist_insert_sorted_with_data (GSList           *list,

   540 				 gpointer          data,

   541 				 GCompareDataFunc  func,

   542 				 gpointer          user_data)

   543 {

   544   return g_slist_insert_sorted_real (list, data, (GFunc) func, user_data);

   545 }

   546 

   547 static GSList *

   548 g_slist_sort_merge (GSList   *l1, 

   549 		    GSList   *l2,

   550 		    GFunc     compare_func,

   551 		    gpointer  user_data)

   552 {

   553   GSList list, *l;

   554   gint cmp;

   555 

   556   l=&list;

   557 

   558   while (l1 && l2)

   559     {

   560       cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);

   561 

   562       if (cmp <= 0)

   563         {

   564 	  l=l->next=l1;

   565 	  l1=l1->next;

   566         } 

   567       else 

   568 	{

   569 	  l=l->next=l2;

   570 	  l2=l2->next;

   571         }

   572     }

   573   l->next= l1 ? l1 : l2;

   574   

   575   return list.next;

   576 }

   577 

   578 static GSList *

   579 g_slist_sort_real (GSList   *list,

   580 		   GFunc     compare_func,

   581 		   gpointer  user_data)

   582 {

   583   GSList *l1, *l2;

   584 

   585   if (!list) 

   586     return NULL;

   587   if (!list->next) 

   588     return list;

   589 

   590   l1 = list; 

   591   l2 = list->next;

   592 

   593   while ((l2 = l2->next) != NULL)

   594     {

   595       if ((l2 = l2->next) == NULL) 

   596 	break;

   597       l1=l1->next;

   598     }

   599   l2 = l1->next; 

   600   l1->next = NULL;

   601 

   602   return g_slist_sort_merge (g_slist_sort_real (list, compare_func, user_data),

   603 			     g_slist_sort_real (l2, compare_func, user_data),

   604 			     compare_func,

   605 			     user_data);

   606 }

   607 

   608 EXPORT_C GSList *

   609 g_slist_sort (GSList       *list,

   610 	      GCompareFunc  compare_func)

   611 {

   612   return g_slist_sort_real (list, (GFunc) compare_func, NULL);

   613 }

   614 

   615 EXPORT_C GSList *

   616 g_slist_sort_with_data (GSList           *list,

   617 			GCompareDataFunc  compare_func,

   618 			gpointer          user_data)

   619 {

   620   return g_slist_sort_real (list, (GFunc) compare_func, user_data);

   621 }

   622 

   623 #define __G_SLIST_C__

   624 #include "galiasdef.c"