Re: [gtk-list] g_list_append is O(n^2)

[Robert Wilhelm <robert physiol med tu-muenchen de>]

On Thu, Oct 15, 1998 at 12:10:45PM +0200, Robert Wilhelm wrote:
> g_list_append() does not work in linear time as it is required for the STL
> equivalent.
> 

sorry for the confusion. STL has constant time at least for  push_back()
and push_front(), while glib has constant time for g_list_prepend()
but linear time for g_list_append(). It has to go through the whole
list in g_list_last().

Following hack  to g_list_append() makes it return the last element
and my test case has the same time complexity for STL and glib now.

BEWARE: This hack may break other applications.


Index: glist.c
===================================================================
RCS file: /cvs/gnome/glib/glist.c,v
retrieving revision 1.1.1.1
diff -u -p -r1.1.1.1 glist.c
--- glist.c     1998/06/10 23:21:13     1.1.1.1
+++ glist.c     1998/10/15 10:53:14
@@ -141,11 +141,9 @@ g_list_append (GList       *list,
       /* g_assert (last != NULL); */
       last->next = new_list;
       new_list->prev = last;
-
-      return list;
     }
-  else
-    return new_list;
+
+  return new_list;
 }
 
 GList*

-- 
Robert Wilhelm