Re: GList changes

[Karl Nelson <kenelson ece ucdavis edu>]

> On Tue, 10 Aug 1999, Karl Nelson wrote:
> 
> > 
> > These functions simplify the 3 cases of insert to 2, and 
> > allow the user to not need to deal with head and iter at
> > the same time.
> > 
> > New functions 
> >   g_list_insert_link(GList *head,gpointer data,GList* iter); 
> >   g_list_insert_after_link(GList *head,gpointer data,GList* iter); 
> > 
> > The other functions are converted to use these.
> 
> hi karl.
> 
> first off, i couldn't apply your patch to either glib-1-2 nor HEAD,
> some hunks failed both trees.

Hmm.  They ere both taken from head.  It seems most likely that
my mailer killed something when I tried to include it in the 
message.  

> for further patches, could you please tell what version your patch
> exactly applies to and provide unified diffs? 

I will use "cvs -z9 diff -u" if that is okay.  (from the head.)

>also it'd be nice if
> you could adhere to the normal glib coding style (here, put spaces
> around "=", after commas, etc). also, additions to GList should also
> come with a GSList counterpart where appropriate.

Okay, I do not have the corresponding to gslist yet.  However,
I can complete it within the next day assuming that you want
this patch.

> on actuall matters, i'm not exactly sure what functionality you want
> to provide, especially why you proposed addition of two functions.
> if we want to provide an interface for random insertion, relative
> to specific list nodes, we should probably follow the GNode example:

I was just trying to make seperate the head of the list argument
from the iterator to which the insertion should occur.  It makes
some code much more understandable if the head and iterator are
not the same.  Especially the case of a tail insertion where
the tail must be kept.  (C++ iterators)


> 
> GNode*   g_node_insert_before   (GNode            *parent,
>                                  GNode            *sibling,
>                                  GNode            *node);
> 
> for GList and GSList this would pretty much be:
> 
> GSList* g_slist_insert_before        (GSList        *slist,
>                                       GSList        *sibling,
>                                       gpointer       data);
> GList*  g_list_insert_before         (GList         *list,
>                                       GList         *sibling,
>                                       gpointer       data);
> GSList* g_slist_insert_link_before   (GSList        *slist,
>                                       GSList        *sibling,
>                                       GSList        *new_node);
> GList*  g_list_insert_link_before    (GList         *list,
>                                       GList         *sibling,
>                                       GList         *new_node);

Renamed as such.  The name _link was added because of the 
function named remove_link.  STL uses seperate words for the 
concepts (erase and remove) so I was trying to follow the convention
of glib as I read it.

> also, changing the implementation of the existing insertion functions
> in terms of the new sibling-relative-insertion variants is not neccessary,
> this just imposes an extra function indirection (performance impact)
> and the existing implementation are probably better optimized for the
> specific cases (i did actually go through the implementations in Dec 97
> to optimize them as much as possible).

Well, I am not sure that is the impact of the changes.  The
code certianly became cleaner and cases folded on top, but I
will let you judge for yourself.  It is certianly not necessary
to fold the other cases in.

> FYI, i have appended implementations of g_slist_insert_before() and
> g_list_insert_before() to this mail, they can easily be adapted for the
> insert_link case. you can also find them in the beast module in
> beast/bse/glib-extra.c, i intend to merge most of that stuff after more
> thorough testing and optimization into glib HEAD.

Mine was exactly the same as what you included below optimized
for code size. (differed only on case of tail insertion where
tracing through list dominates over checks.)

Since you were already adding the functionality that I was
feel free to use either version.  I would also
pefer having both a before and after version as it 
simplifies list wrapping.  

(ie.  I can do this

  GList *list,*last;

  ...
 
  list = g_list_insert_after (list, last=g_list_last(list), data);
  /* do something with last like make more insertions */
  
which is what the patch was for.  Without it the same concept 
ends up written as 

  GList *list,*last;

  last=g_list_last(list);
  if (last == list) 
    list=g_list_append (list, data);
  else
    g_list_append (last, data);

Which is less clear and multicase for what should be a simple
action (insert to end of list).


Hope the patch works, and it clears up what I am trying to
do.

--Karl


Index: glib.h
===================================================================
RCS file: /cvs/gnome/glib/glib.h,v
retrieving revision 1.135
diff -u -r1.135 glib.h
--- glib.h	1999/08/02 23:16:31	1.135
+++ glib.h	1999/08/13 08:50:41
@@ -880,6 +880,12 @@
 GList* g_list_insert		(GList		*list,
 				 gpointer	 data,
 				 gint		 position);
+GList* g_list_insert_before     (GList          *list,
+                                 GList          *link,
+                                 gpointer        data);
+GList* g_list_insert_after      (GList          *list,
+                                 GList          *link,
+                                 gpointer        data);
 GList* g_list_insert_sorted	(GList		*list,
 				 gpointer	 data,
 				 GCompareFunc	 func);
Index: glist.c
===================================================================
RCS file: /cvs/gnome/glib/glist.c,v
retrieving revision 1.13
diff -u -r1.13 glist.c
--- glist.c	1999/07/24 18:50:55	1.13
+++ glist.c	1999/08/13 08:50:42
@@ -170,81 +170,90 @@
 g_list_append (GList	*list,
 	       gpointer	 data)
 {
-  GList *new_list;
-  GList *last;
-  
-  new_list = g_list_alloc ();
-  new_list->data = data;
-  
-  if (list)
-    {
-      last = g_list_last (list);
-      /* g_assert (last != NULL); */
-      last->next = new_list;
-      new_list->prev = last;
-
-      return list;
-    }
-  else
-    return new_list;
+  return g_list_insert_after (list, 0, data);
 }
 
 GList*
 g_list_prepend (GList	 *list,
 		gpointer  data)
 {
+  return g_list_insert_before (list, list, data);
+}
+
+GList*
+g_list_insert (GList	*list,
+	       gpointer	 data,
+	       gint	 position)
+{
+  if (position < 0)
+    return g_list_insert_after (list, 0, data);
+
+  return g_list_insert_before (list, g_list_nth (list, position), data);
+}
+
+GList*
+g_list_insert_before (GList	*list,
+	              GList	*link,
+	       	      gpointer	 data)
+{
   GList *new_list;
-  
+
   new_list = g_list_alloc ();
   new_list->data = data;
-  
-  if (list)
+
+  if (!list)
+    {
+      g_return_val_if_fail (link == NULL, new_list);
+      return new_list; 
+    }
+
+  if (!link) 
+    link = g_list_last (list);
+
+  new_list->next = link;
+  if (link->prev)
     {
-      if (list->prev)
-	{
-	  list->prev->next = new_list;
-	  new_list->prev = list->prev;
-	}
-      list->prev = new_list;
-      new_list->next = list;
+      link->prev->next = new_list;
+      new_list->prev = link->prev;
     }
-  
-  return new_list;
+  link->prev = new_list;
+
+  if (link == list)
+    return new_list;
+
+  return list;
 }
 
 GList*
-g_list_insert (GList	*list,
-	       gpointer	 data,
-	       gint	 position)
+g_list_insert_after (GList	*list,
+	             GList      *link,
+	       	     gpointer	 data)
 {
   GList *new_list;
-  GList *tmp_list;
-  
-  if (position < 0)
-    return g_list_append (list, data);
-  else if (position == 0)
-    return g_list_prepend (list, data);
-  
-  tmp_list = g_list_nth (list, position);
-  if (!tmp_list)
-    return g_list_append (list, data);
-  
+
   new_list = g_list_alloc ();
   new_list->data = data;
-  
-  if (tmp_list->prev)
+
+  if (!list)
     {
-      tmp_list->prev->next = new_list;
-      new_list->prev = tmp_list->prev;
+      g_return_val_if_fail (link == NULL, new_list);
+      return new_list; 
     }
-  new_list->next = tmp_list;
-  tmp_list->prev = new_list;
-  
-  if (tmp_list == list)
-    return new_list;
-  else
-    return list;
+
+  if (!link) 
+    link = g_list_last (list);
+
+  new_list->prev = link;
+  if (link->next)
+    {
+      link->next->prev = new_list;
+      new_list->next = link->next;
+    }
+  link->next = new_list;
+
+  return list;
 }
+
 
 GList *
 g_list_concat (GList *list1, GList *list2)