Performance improvement: O(n^2) -> O(n).

5 files changed, 137 insertions, 24 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 600e74f..740082c 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,22 @@
+2001-05-01  Bruno Haible  <haible@clisp.cons.org>
+
+	Reduce running time for very long msgstrs from O(n^2) to O(n) where
+	n is the number of string pieces.
+	* str-list.h (string_list_init, string_list_destroy,
+	string_list_concat, string_list_concat_destroy): New declarations.
+	* str-list.c (string_list_init, string_list_destroy,
+	string_list_concat, string_list_concat_destroy): New functions.
+	* po-gram-gen.y Include str-list.h.
+	(%union): Add new alternative of type string_list_ty.
+	(string_list): Change type to stringlist.
+	(message): Use string_list_concat_destroy to convert a stringlist to
+	a single string. Use string_list_destroy instead of free.
+	(msgid_pluralform): Likewise.
+	(pluralform): Likewise.
+	(string_list): Return a stringlist. Don't concatenate the strings one
+	by one.
+	* po-lex.c: Include str-list.h.
+
 2001-04-30  Bruno Haible  <haible@clisp.cons.org>
 
 	* message.h (message_alloc): Add const to prototype.
diff --git a/src/po-gram-gen.y b/src/po-gram-gen.y
index 1b576aa..fdee486 100644
--- a/src/po-gram-gen.y
+++ b/src/po-gram-gen.y
@@ -24,6 +24,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
 #include <stdio.h>
 
+#include "str-list.h"
 #include "po-lex.h"
 #include "po-gram.h"
 #include "error.h"
@@ -102,12 +103,14 @@ static long plural_counter;
 %union
 {
   struct { char *string; lex_pos_ty pos; int obsolete; } string;
+  struct { string_list_ty stringlist; lex_pos_ty pos; int obsolete; } stringlist;
   struct { long number; lex_pos_ty pos; int obsolete; } number;
   struct { lex_pos_ty pos; int obsolete; } pos;
   struct { struct msgstr_def rhs; lex_pos_ty pos; int obsolete; } rhs;
 }
 
-%type <string> STRING COMMENT NAME string_list msgid_pluralform
+%type <string> STRING COMMENT NAME msgid_pluralform
+%type <stringlist> string_list
 %type <number> NUMBER
 %type <pos> DOMAIN MSGID MSGID_PLURAL MSGSTR '[' ']'
 %type <rhs> pluralform pluralform_list
@@ -134,29 +137,34 @@ domain
 message
 	: MSGID string_list MSGSTR string_list
 		{
+		  char *string2 = string_list_concat_destroy (&$2.stringlist);
+		  char *string4 = string_list_concat_destroy (&$4.stringlist);
+
 		  check_obsolete ($1, $2);
 		  check_obsolete ($1, $3);
 		  check_obsolete ($1, $4);
 		  if (!$1.obsolete || pass_obsolete_entries)
-		    po_callback_message ($2.string, &$1.pos, NULL,
-					 $4.string, strlen ($4.string) + 1, &$3.pos);
+		    po_callback_message (string2, &$1.pos, NULL,
+					 string4, strlen (string4) + 1, &$3.pos);
 		  else
 		    {
-		      free ($2.string);
-		      free ($4.string);
+		      free (string2);
+		      free (string4);
 		    }
 		}
 	| MSGID string_list msgid_pluralform pluralform_list
 		{
+		  char *string2 = string_list_concat_destroy (&$2.stringlist);
+
 		  check_obsolete ($1, $2);
 		  check_obsolete ($1, $3);
 		  check_obsolete ($1, $4);
 		  if (!$1.obsolete || pass_obsolete_entries)
-		    po_callback_message ($2.string, &$1.pos, $3.string,
+		    po_callback_message (string2, &$1.pos, $3.string,
 					 $4.rhs.msgstr, $4.rhs.msgstr_len, &$4.pos);
 		  else
 		    {
-		      free ($2.string);
+		      free (string2);
 		      free ($3.string);
 		      free ($4.rhs.msgstr);
 		    }
@@ -166,7 +174,7 @@ message
 		  check_obsolete ($1, $2);
 		  check_obsolete ($1, $3);
 		  po_gram_error_at_line (&$1.pos, _("missing `msgstr[]' section"));
-		  free ($2.string);
+		  string_list_destroy (&$2.stringlist);
 		  free ($3.string);
 		}
 	| MSGID string_list pluralform_list
@@ -174,14 +182,14 @@ message
 		  check_obsolete ($1, $2);
 		  check_obsolete ($1, $3);
 		  po_gram_error_at_line (&$1.pos, _("missing `msgid_plural' section"));
-		  free ($2.string);
+		  string_list_destroy (&$2.stringlist);
 		  free ($3.rhs.msgstr);
 		}
 	| MSGID string_list
 		{
 		  check_obsolete ($1, $2);
 		  po_gram_error_at_line (&$1.pos, _("missing `msgstr' section"));
-		  free ($2.string);
+		  string_list_destroy (&$2.stringlist);
 		}
 	;
 
@@ -190,7 +198,7 @@ msgid_pluralform
 		{
 		  check_obsolete ($1, $2);
 		  plural_counter = 0;
-		  $$.string = $2.string;
+		  $$.string = string_list_concat_destroy (&$2.stringlist);
 		  $$.pos = $1.pos;
 		  $$.obsolete = $1.obsolete;
 		}
@@ -230,8 +238,8 @@ pluralform
 			po_gram_error_at_line (&$1.pos, _("plural form has wrong index"));
 		    }
 		  plural_counter++;
-		  $$.rhs.msgstr = $5.string;
-		  $$.rhs.msgstr_len = strlen ($5.string) + 1;
+		  $$.rhs.msgstr = string_list_concat_destroy (&$5.stringlist);
+		  $$.rhs.msgstr_len = strlen ($$.rhs.msgstr) + 1;
 		  $$.pos = $1.pos;
 		  $$.obsolete = $1.obsolete;
 		}
@@ -240,20 +248,16 @@ pluralform
 string_list
 	: STRING
 		{
-		  $$ = $1;
+		  string_list_init (&$$.stringlist);
+		  string_list_append (&$$.stringlist, $1.string);
+		  $$.pos = $1.pos;
+		  $$.obsolete = $1.obsolete;
 		}
 	| string_list STRING
 		{
-		  size_t len1;
-		  size_t len2;
-
 		  check_obsolete ($1, $2);
-		  len1 = strlen ($1.string);
-		  len2 = strlen ($2.string);
-		  $$.string = (char *) xmalloc (len1 + len2 + 1);
-		  stpcpy (stpcpy ($$.string, $1.string), $2.string);
-		  free ($1.string);
-		  free ($2.string);
+		  $$.stringlist = $1.stringlist;
+		  string_list_append (&$$.stringlist, $2.string);
 		  $$.pos = $1.pos;
 		  $$.obsolete = $1.obsolete;
 		}
diff --git a/src/po-lex.c b/src/po-lex.c
index e1a2dab..d46c666 100644
--- a/src/po-lex.c
+++ b/src/po-lex.c
@@ -43,6 +43,7 @@
 # define va_dcl char *a1, *a2, *a3, *a4, *a5, *a6, *a7, *a8;
 #endif
 
+#include "str-list.h"
 #include "po-charset.h"
 #include "po-lex.h"
 #include "system.h"
diff --git a/src/str-list.c b/src/str-list.c
index 7d27020..d2c0726 100644
--- a/src/str-list.c
+++ b/src/str-list.c
@@ -1,5 +1,5 @@
 /* GNU gettext - internationalization aids
-   Copyright (C) 1995, 1998, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1995, 1998, 2000, 2001 Free Software Foundation, Inc.
 
    This file was written by Peter Miller <millerp@canb.auug.org.au>
 
@@ -27,6 +27,17 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 #include "str-list.h"
 
 
+/* Initialize an empty list of strings.  */
+void
+string_list_init (slp)
+     string_list_ty *slp;
+{
+  slp->item = NULL;
+  slp->nitems = 0;
+  slp->nitems_max = 0;
+}
+
+
 /* Return a fresh, empty list of strings.  */
 string_list_ty *
 string_list_alloc ()
@@ -91,6 +102,20 @@ string_list_append_unique (slp, s)
 }
 
 
+/* Destroy a list of strings.  */
+void
+string_list_destroy (slp)
+     string_list_ty *slp;
+{
+  size_t j;
+
+  for (j = 0; j < slp->nitems; ++j)
+    free ((char *) slp->item[j]);
+  if (slp->item != NULL)
+    free (slp->item);
+}
+
+
 /* Free a list of strings.  */
 void
 string_list_free (slp)
@@ -107,6 +132,56 @@ string_list_free (slp)
 
 
 /* Return a freshly allocated string obtained by concatenating all the
+   strings in the list.  */
+char *
+string_list_concat (slp)
+     const string_list_ty *slp;
+{
+  size_t len;
+  size_t j;
+  char *result;
+  size_t pos;
+
+  len = 1;
+  for (j = 0; j < slp->nitems; ++j)
+    len += strlen (slp->item[j]);
+  result = xmalloc (len);
+  pos = 0;
+  for (j = 0; j < slp->nitems; ++j)
+    {
+      len = strlen (slp->item[j]);
+      memcpy (result + pos, slp->item[j], len);
+      pos += len;
+    }
+  result[pos] = '\0';
+  return result;
+}
+
+
+/* Return a freshly allocated string obtained by concatenating all the
+   strings in the list, and destroy the list.  */
+char *
+string_list_concat_destroy (slp)
+     string_list_ty *slp;
+{
+  char *result;
+
+  /* Optimize the most frequent case.  */
+  if (slp->nitems == 1)
+    {
+      result = (char *) slp->item[0];
+      free (slp->item);
+    }
+  else
+    {
+      result = string_list_concat (slp);
+      string_list_destroy (slp);
+    }
+  return result;
+}
+
+
+/* Return a freshly allocated string obtained by concatenating all the
    strings in the list, separated by spaces.  */
 char *
 string_list_join (slp)
diff --git a/src/str-list.h b/src/str-list.h
index def4f52..4a60b0f 100644
--- a/src/str-list.h
+++ b/src/str-list.h
@@ -33,6 +33,9 @@ struct string_list_ty
   size_t nitems_max;
 };
 
+/* Initialize an empty list of strings.  */
+extern void string_list_init PARAMS ((string_list_ty *__slp));
+
 /* Return a fresh, empty list of strings.  */
 extern string_list_ty *string_list_alloc PARAMS ((void));
 
@@ -45,10 +48,21 @@ extern void string_list_append PARAMS ((string_list_ty *__slp,
 extern void string_list_append_unique PARAMS ((string_list_ty *__slp,
 					       const char *__s));
 
+/* Destroy a list of strings.  */
+extern void string_list_destroy PARAMS ((string_list_ty *__slp));
+
 /* Free a list of strings.  */
 extern void string_list_free PARAMS ((string_list_ty *__slp));
 
 /* Return a freshly allocated string obtained by concatenating all the
+   strings in the list.  */
+extern char *string_list_concat PARAMS ((const string_list_ty *__slp));
+
+/* Return a freshly allocated string obtained by concatenating all the
+   strings in the list, and destroy the list.  */
+extern char *string_list_concat_destroy PARAMS ((string_list_ty *__slp));
+
+/* Return a freshly allocated string obtained by concatenating all the
    strings in the list, separated by spaces.  */
 extern char *string_list_join PARAMS ((const string_list_ty *__slp));