Re: g_strjoinv() is very slow

[David Odin <David Odin bigfoot com>]

On Sun, Sep 24, 2000 at 04:58:15PM +0200, David Odin wrote:
> On Sat, Sep 23, 2000 at 10:45:41PM -0400, Havoc Pennington wrote:
> > 
> > David Odin <David Odin bigfoot com> writes: 
> > >   Actually, it is a very good idea, but I think isn't very portable on
> > > non-GNU platforms. 
> > > 
> > >   I didn't know this function, and I saw this from the man page:
> > > CONFORMING TO
> > >        This function is not part of the ANSI or POSIX  standards,
> > >        and  is  not  customary  on Unix systems, but is not a GNU
> > >        invention either.  Perhaps it comes from MS-DOS.
> > >     
> > >   Havoc, what do you think? Should I re-write my patch to use stpcpy() and
> > > adding a test to configure.in?
> > > 
> > 
> > If you did, you'd just write a g_stpcpy(), which would be implemented
> > depending on a configure.in test, then use that.
> > 
> > I don't have any opinion though whether it's better to use
> > it. Probably only if we want g_stpcpy() in GLib anyway, and I don't
> > know whether we do or not.
> > 
>   OK. Here is what I've done.
> 
>   I've added a g_stpcpy() function to the glib, and use this function in
> g_strjoin(), g_strjoinv() and g_strconcat(). Thus, the algorithms complexity
> of these functions is reduced from O(n*n) to O(n), n being the length of the
> resulting string.
> 
>   If the g_stpcpy() isn't usefull, I'll rewrite my patch in order not to use
> it (and the three functions would become even faster by avoiding a function
> call...).
> 
>      Tell me if the patch is applied.
> 
       Hmmm. I'm very sorry, I've sent you the wrong patch...

   Here's a new one.

              Best regards,

                      DindinX
 
-- 
David Odin bigfoot com

diff -Nrudb glib.orig/CVS/Entries.Log glib/CVS/Entries.Log
--- glib.orig/CVS/Entries.Log	Sun Sep 24 17:05:42 2000
+++ glib/CVS/Entries.Log	Thu Jan  1 01:00:00 1970
@@ -1,2 +0,0 @@
-A D/gmemres////
-R D/gmemres////
diff -Nrudb glib.orig/config.h.win32.in glib/config.h.win32.in
--- glib.orig/config.h.win32.in	Thu Sep 21 18:17:31 2000
+++ glib/config.h.win32.in	Sun Sep 24 16:19:04 2000
@@ -102,6 +102,9 @@
 /* Define if you have the on_exit function.  */
 /* #undef HAVE_ON_EXIT */
 
+/* Define if you have the stpcpy function. */
+/* #undef HAVE_STPCPY */
+
 /* Define if you have the strcasecmp function.  */
 /* #undef HAVE_STRCASECMP */
 
diff -Nrudb glib.orig/configure.in glib/configure.in
--- glib.orig/configure.in	Thu Sep 21 14:49:10 2000
+++ glib/configure.in	Sun Sep 24 16:19:29 2000
@@ -357,7 +357,7 @@
 GLIB_SIZEOF([$size_includes], intmax_t, intmax_t)
 
 # Check for some functions
-AC_CHECK_FUNCS(lstat strerror strsignal memmove vsnprintf strcasecmp strncasecmp poll getcwd)
+AC_CHECK_FUNCS(lstat strerror strsignal memmove vsnprintf stpcpy strcasecmp strncasecmp poll getcwd)
 
 # Check if bcopy can be used for overlapping copies, if memmove isn't found.
 # The check is borrowed from the PERL Configure script.
diff -Nrudb glib.orig/glib.def glib/glib.def
--- glib.orig/glib.def	Thu Sep 21 18:17:31 2000
+++ glib/glib.def	Sun Sep 24 16:20:07 2000
@@ -391,6 +391,7 @@
 	g_static_rw_lock_writer_lock
 	g_static_rw_lock_writer_trylock
 	g_static_rw_lock_writer_unlock
+  g_stpcpy
 	g_str_equal
 	g_str_hash
 	g_strcanon
diff -Nrudb glib.orig/glib.h glib/glib.h
--- glib.orig/glib.h	Tue Sep 19 16:30:35 2000
+++ glib/glib.h	Sun Sep 24 16:21:51 2000
@@ -1761,8 +1761,8 @@
 gchar*   g_strjoinv		(const gchar  *separator,
 				 gchar       **str_array);
 void     g_strfreev		(gchar       **str_array);
-
-
+gchar*   stpcpy       (gchar *dest,
+                       const char *src);
 
 /* calculate a string size, guarranteed to fit format + args.
  */
diff -Nrudb glib.orig/gstrfuncs.c glib/gstrfuncs.c
--- glib.orig/gstrfuncs.c	Sun Sep 10 18:04:33 2000
+++ glib/gstrfuncs.c	Sun Sep 24 18:25:55 2000
@@ -118,6 +118,21 @@
   return str;
 }
 
+gchar *
+g_stpcpy (gchar *dest,
+          const gchar *src)
+{
+  g_return_val_if_fail (dest != NULL, NULL);
+  g_return_val_if_fail (src != NULL, NULL);
+
+#ifdef HAVE_STPCPY
+  return stpcpy (dest, src);
+#else
+  strcpy(dest, src);
+  return dest+strlen(src);
+#endif
+}
+
 gchar*
 g_strdup_vprintf (const gchar *format,
 		  va_list      args1)
@@ -156,6 +171,7 @@
   va_list args;
   gchar	  *s;
   gchar	  *concat;
+  gchar   *ptr;
 
   g_return_val_if_fail (string1 != NULL, NULL);
 
@@ -170,14 +186,14 @@
   va_end (args);
 
   concat = g_new (gchar, l);
-  concat[0] = 0;
+  ptr = concat;
 
-  strcat (concat, string1);
+  ptr = g_stpcpy (ptr, string1);
   va_start (args, string1);
   s = va_arg (args, gchar*);
   while (s)
     {
-      strcat (concat, s);
+      ptr = g_stpcpy (ptr, s);
       s = va_arg (args, gchar*);
     }
   va_end (args);
@@ -1554,6 +1570,7 @@
 	    gchar       **str_array)
 {
   gchar *string;
+  gchar *ptr;
 
   g_return_val_if_fail (str_array != NULL, NULL);
 
@@ -1567,16 +1584,18 @@
 
       separator_len = strlen (separator);
       len = 1 + strlen (str_array[0]);
-      for(i = 1; str_array[i] != NULL; i++)
-	len += separator_len + strlen(str_array[i]);
+      for (i = 1; str_array[i] != NULL; i++)
+        len += strlen(str_array[i]);
+      len += separator_len*i;
 
       string = g_new (gchar, len);
       *string = 0;
       strcat (string, *str_array);
+      ptr = string + strlen (*str_array);
       for (i = 1; str_array[i] != NULL; i++)
 	{
-	  strcat (string, separator);
-	  strcat (string, str_array[i]);
+          ptr = g_stpcpy (ptr, separator);
+          ptr = g_stpcpy (ptr, str_array[i]);
 	}
       }
   else
@@ -1593,6 +1612,7 @@
   va_list args;
   guint len;
   guint separator_len;
+  gchar *ptr;
 
   if (separator == NULL)
     separator = "";
@@ -1622,12 +1642,13 @@
 
       s = va_arg (args, gchar*);
       strcat (string, s);
+      ptr = string + strlen (s);
 
       s = va_arg (args, gchar*);
       while (s)
 	{
-	  strcat (string, separator);
-	  strcat (string, s);
+          ptr = g_stpcpy(ptr, separator);
+          ptr = g_stpcpy(ptr, s);
 	  s = va_arg (args, gchar*);
 	}
     }