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 #include "config.h"

    32 

    33 #include "glib.h"

    34 #include "galias.h"

    35 

    36 

    37 EXPORT_C void g_list_push_allocator (gpointer dummy) { /* present for binary compat only */ }

    38 EXPORT_C 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 

    45 EXPORT_C GList*

    46 g_list_alloc (void)

    47 {

    48   return _g_list_alloc0 ();

    49 }

    50 

    51 EXPORT_C void

    52 g_list_free (GList *list)

    53 {

    54   g_slice_free_chain (GList, list, next);

    55 }

    56 

    57 EXPORT_C void

    58 g_list_free_1 (GList *list)

    59 {

    60   _g_list_free1 (list);

    61 }

    62 

    63 EXPORT_C GList*

    64 g_list_append (GList	*list,

    65 	       gpointer	 data)

    66 {

    67   GList *new_list;

    68   GList *last;

    69   

    70   new_list = _g_list_alloc ();

    71   new_list->data = data;

    72   new_list->next = NULL;

    73   

    74   if (list)

    75     {

    76       last = g_list_last (list);

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

    78       last->next = new_list;

    79       new_list->prev = last;

    80 

    81       return list;

    82     }

    83   else

    84     {

    85       new_list->prev = NULL;

    86       return new_list;

    87     }

    88 }

    89 

    90 EXPORT_C GList*

    91 g_list_prepend (GList	 *list,

    92 		gpointer  data)

    93 {

    94   GList *new_list;

    95   

    96   new_list = _g_list_alloc ();

    97   new_list->data = data;

    98   new_list->next = list;

    99   

   100   if (list)

   101     {

   102       new_list->prev = list->prev;

   103       if (list->prev)

   104 	list->prev->next = new_list;

   105       list->prev = new_list;

   106     }

   107   else

   108     new_list->prev = NULL;

   109   

   110   return new_list;

   111 }

   112 

   113 EXPORT_C GList*

   114 g_list_insert (GList	*list,

   115 	       gpointer	 data,

   116 	       gint	 position)

   117 {

   118   GList *new_list;

   119   GList *tmp_list;

   120   

   121   if (position < 0)

   122     return g_list_append (list, data);

   123   else if (position == 0)

   124     return g_list_prepend (list, data);

   125   

   126   tmp_list = g_list_nth (list, position);

   127   if (!tmp_list)

   128     return g_list_append (list, data);

   129   

   130   new_list = _g_list_alloc ();

   131   new_list->data = data;

   132   new_list->prev = tmp_list->prev;

   133   if (tmp_list->prev)

   134     tmp_list->prev->next = new_list;

   135   new_list->next = tmp_list;

   136   tmp_list->prev = new_list;

   137   

   138   if (tmp_list == list)

   139     return new_list;

   140   else

   141     return list;

   142 }

   143 

   144 EXPORT_C GList*

   145 g_list_insert_before (GList   *list,

   146 		      GList   *sibling,

   147 		      gpointer data)

   148 {

   149   if (!list)

   150     {

   151       list = g_list_alloc ();

   152       list->data = data;

   153       g_return_val_if_fail (sibling == NULL, list);

   154       return list;

   155     }

   156   else if (sibling)

   157     {

   158       GList *node;

   159 

   160       node = _g_list_alloc ();

   161       node->data = data;

   162       node->prev = sibling->prev;

   163       node->next = sibling;

   164       sibling->prev = node;

   165       if (node->prev)

   166 	{

   167 	  node->prev->next = node;

   168 	  return list;

   169 	}

   170       else

   171 	{

   172 	  g_return_val_if_fail (sibling == list, node);

   173 	  return node;

   174 	}

   175     }

   176   else

   177     {

   178       GList *last;

   179 

   180       last = list;

   181       while (last->next)

   182 	last = last->next;

   183 

   184       last->next = _g_list_alloc ();

   185       last->next->data = data;

   186       last->next->prev = last;

   187       last->next->next = NULL;

   188 

   189       return list;

   190     }

   191 }

   192 

   193 EXPORT_C GList *

   194 g_list_concat (GList *list1, GList *list2)

   195 {

   196   GList *tmp_list;

   197   

   198   if (list2)

   199     {

   200       tmp_list = g_list_last (list1);

   201       if (tmp_list)

   202 	tmp_list->next = list2;

   203       else

   204 	list1 = list2;

   205       list2->prev = tmp_list;

   206     }

   207   

   208   return list1;

   209 }

   210 

   211 EXPORT_C GList*

   212 g_list_remove (GList	     *list,

   213 	       gconstpointer  data)

   214 {

   215   GList *tmp;

   216   

   217   tmp = list;

   218   while (tmp)

   219     {

   220       if (tmp->data != data)

   221 	tmp = tmp->next;

   222       else

   223 	{

   224 	  if (tmp->prev)

   225 	    tmp->prev->next = tmp->next;

   226 	  if (tmp->next)

   227 	    tmp->next->prev = tmp->prev;

   228 	  

   229 	  if (list == tmp)

   230 	    list = list->next;

   231 	  

   232 	  _g_list_free1 (tmp);

   233 	  

   234 	  break;

   235 	}

   236     }

   237   return list;

   238 }

   239 

   240 EXPORT_C GList*

   241 g_list_remove_all (GList	*list,

   242 		   gconstpointer data)

   243 {

   244   GList *tmp = list;

   245 

   246   while (tmp)

   247     {

   248       if (tmp->data != data)

   249 	tmp = tmp->next;

   250       else

   251 	{

   252 	  GList *next = tmp->next;

   253 

   254 	  if (tmp->prev)

   255 	    tmp->prev->next = next;

   256 	  else

   257 	    list = next;

   258 	  if (next)

   259 	    next->prev = tmp->prev;

   260 

   261 	  _g_list_free1 (tmp);

   262 	  tmp = next;

   263 	}

   264     }

   265   return list;

   266 }

   267 

   268 static inline GList*

   269 _g_list_remove_link (GList *list,

   270 		     GList *link)

   271 {

   272   if (link)

   273     {

   274       if (link->prev)

   275 	link->prev->next = link->next;

   276       if (link->next)

   277 	link->next->prev = link->prev;

   278       

   279       if (link == list)

   280 	list = list->next;

   281       

   282       link->next = NULL;

   283       link->prev = NULL;

   284     }

   285   

   286   return list;

   287 }

   288 

   289 EXPORT_C GList*

   290 g_list_remove_link (GList *list,

   291 		    GList *link)

   292 {

   293   return _g_list_remove_link (list, link);

   294 }

   295 

   296 EXPORT_C GList*

   297 g_list_delete_link (GList *list,

   298 		    GList *link)

   299 {

   300   list = _g_list_remove_link (list, link);

   301   _g_list_free1 (link);

   302 

   303   return list;

   304 }

   305 

   306 EXPORT_C GList*

   307 g_list_copy (GList *list)

   308 {

   309   GList *new_list = NULL;

   310 

   311   if (list)

   312     {

   313       GList *last;

   314 

   315       new_list = _g_list_alloc ();

   316       new_list->data = list->data;

   317       new_list->prev = NULL;

   318       last = new_list;

   319       list = list->next;

   320       while (list)

   321 	{

   322 	  last->next = _g_list_alloc ();

   323 	  last->next->prev = last;

   324 	  last = last->next;

   325 	  last->data = list->data;

   326 	  list = list->next;

   327 	}

   328       last->next = NULL;

   329     }

   330 

   331   return new_list;

   332 }

   333 

   334 EXPORT_C GList*

   335 g_list_reverse (GList *list)

   336 {

   337   GList *last;

   338   

   339   last = NULL;

   340   while (list)

   341     {

   342       last = list;

   343       list = last->next;

   344       last->next = last->prev;

   345       last->prev = list;

   346     }

   347   

   348   return last;

   349 }

   350 

   351 EXPORT_C GList*

   352 g_list_nth (GList *list,

   353 	    guint  n)

   354 {

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

   356     list = list->next;

   357   

   358   return list;

   359 }

   360 

   361 EXPORT_C GList*

   362 g_list_nth_prev (GList *list,

   363 		 guint  n)

   364 {

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

   366     list = list->prev;

   367   

   368   return list;

   369 }

   370 

   371 EXPORT_C gpointer

   372 g_list_nth_data (GList     *list,

   373 		 guint      n)

   374 {

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

   376     list = list->next;

   377   

   378   return list ? list->data : NULL;

   379 }

   380 

   381 EXPORT_C GList*

   382 g_list_find (GList         *list,

   383 	     gconstpointer  data)

   384 {

   385   while (list)

   386     {

   387       if (list->data == data)

   388 	break;

   389       list = list->next;

   390     }

   391   

   392   return list;

   393 }

   394 

   395 EXPORT_C GList*

   396 g_list_find_custom (GList         *list,

   397 		    gconstpointer  data,

   398 		    GCompareFunc   func)

   399 {

   400   g_return_val_if_fail (func != NULL, list);

   401 

   402   while (list)

   403     {

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

   405 	return list;

   406       list = list->next;

   407     }

   408 

   409   return NULL;

   410 }

   411 

   412 

   413 EXPORT_C gint

   414 g_list_position (GList *list,

   415 		 GList *link)

   416 {

   417   gint i;

   418 

   419   i = 0;

   420   while (list)

   421     {

   422       if (list == link)

   423 	return i;

   424       i++;

   425       list = list->next;

   426     }

   427 

   428   return -1;

   429 }

   430 

   431 EXPORT_C gint

   432 g_list_index (GList         *list,

   433 	      gconstpointer  data)

   434 {

   435   gint i;

   436 

   437   i = 0;

   438   while (list)

   439     {

   440       if (list->data == data)

   441 	return i;

   442       i++;

   443       list = list->next;

   444     }

   445 

   446   return -1;

   447 }

   448 

   449 EXPORT_C GList*

   450 g_list_last (GList *list)

   451 {

   452   if (list)

   453     {

   454       while (list->next)

   455 	list = list->next;

   456     }

   457   

   458   return list;

   459 }

   460 

   461 EXPORT_C GList*

   462 g_list_first (GList *list)

   463 {

   464   if (list)

   465     {

   466       while (list->prev)

   467 	list = list->prev;

   468     }

   469   

   470   return list;

   471 }

   472 

   473 EXPORT_C guint

   474 g_list_length (GList *list)

   475 {

   476   guint length;

   477   

   478   length = 0;

   479   while (list)

   480     {

   481       length++;

   482       list = list->next;

   483     }

   484   

   485   return length;

   486 }

   487 

   488 EXPORT_C void

   489 g_list_foreach (GList	 *list,

   490 		GFunc	  func,

   491 		gpointer  user_data)

   492 {

   493   while (list)

   494     {

   495       GList *next = list->next;

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

   497       list = next;

   498     }

   499 }

   500 

   501 static GList*

   502 g_list_insert_sorted_real (GList    *list,

   503 			   gpointer  data,

   504 			   GFunc     func,

   505 			   gpointer  user_data)

   506 {

   507   GList *tmp_list = list;

   508   GList *new_list;

   509   gint cmp;

   510 

   511   g_return_val_if_fail (func != NULL, list);

   512   

   513   if (!list) 

   514     {

   515       new_list = _g_list_alloc0 ();

   516       new_list->data = data;

   517       return new_list;

   518     }

   519   

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

   521 

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

   523     {

   524       tmp_list = tmp_list->next;

   525 

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

   527     }

   528 

   529   new_list = _g_list_alloc0 ();

   530   new_list->data = data;

   531 

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

   533     {

   534       tmp_list->next = new_list;

   535       new_list->prev = tmp_list;

   536       return list;

   537     }

   538    

   539   if (tmp_list->prev)

   540     {

   541       tmp_list->prev->next = new_list;

   542       new_list->prev = tmp_list->prev;

   543     }

   544   new_list->next = tmp_list;

   545   tmp_list->prev = new_list;

   546  

   547   if (tmp_list == list)

   548     return new_list;

   549   else

   550     return list;

   551 }

   552 

   553 EXPORT_C GList*

   554 g_list_insert_sorted (GList        *list,

   555 		      gpointer      data,

   556 		      GCompareFunc  func)

   557 {

   558   return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);

   559 }

   560 

   561 EXPORT_C GList*

   562 g_list_insert_sorted_with_data (GList            *list,

   563 				gpointer          data,

   564 				GCompareDataFunc  func,

   565 				gpointer          user_data)

   566 {

   567   return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);

   568 }

   569 

   570 static GList *

   571 g_list_sort_merge (GList     *l1, 

   572 		   GList     *l2,

   573 		   GFunc     compare_func,

   574 		   gpointer  user_data)

   575 {

   576   GList list, *l, *lprev;

   577   gint cmp;

   578 

   579   l = &list; 

   580   lprev = NULL;

   581 

   582   while (l1 && l2)

   583     {

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

   585 

   586       if (cmp <= 0)

   587         {

   588 	  l->next = l1;

   589 	  l1 = l1->next;

   590         } 

   591       else 

   592 	{

   593 	  l->next = l2;

   594 	  l2 = l2->next;

   595         }

   596       l = l->next;

   597       l->prev = lprev; 

   598       lprev = l;

   599     }

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

   601   l->next->prev = l;

   602 

   603   return list.next;

   604 }

   605 

   606 static GList* 

   607 g_list_sort_real (GList    *list,

   608 		  GFunc     compare_func,

   609 		  gpointer  user_data)

   610 {

   611   GList *l1, *l2;

   612   

   613   if (!list) 

   614     return NULL;

   615   if (!list->next) 

   616     return list;

   617   

   618   l1 = list; 

   619   l2 = list->next;

   620 

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

   622     {

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

   624 	break;

   625       l1 = l1->next;

   626     }

   627   l2 = l1->next; 

   628   l1->next = NULL; 

   629 

   630   return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),

   631 			    g_list_sort_real (l2, compare_func, user_data),

   632 			    compare_func,

   633 			    user_data);

   634 }

   635 

   636 EXPORT_C GList *

   637 g_list_sort (GList        *list,

   638 	     GCompareFunc  compare_func)

   639 {

   640   return g_list_sort_real (list, (GFunc) compare_func, NULL);

   641 			    

   642 }

   643 

   644 EXPORT_C GList *

   645 g_list_sort_with_data (GList            *list,

   646 		       GCompareDataFunc  compare_func,

   647 		       gpointer          user_data)

   648 {

   649   return g_list_sort_real (list, (GFunc) compare_func, user_data);

   650 }

   651 

   652 #define __G_LIST_C__

   653 #include "galiasdef.c"