memxfrm: Speed up.

[gnulib.git] / lib / memxfrm.c

diff --git a/lib/memxfrm.c b/lib/memxfrm.c
index dc6eda1..d0a3c78 100644 (file)
--- a/lib/memxfrm.c
+++ b/lib/memxfrm.c
@@ -1,5 +1,5 @@
 /* Locale dependent memory area transformation for comparison.
-   Copyright (C) 2009 Free Software Foundation, Inc.
+   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2009.
 
    This program is free software: you can redistribute it and/or modify it
@@ -45,7 +45,7 @@ memxfrm (char *s, size_t n, char *resultbuf, size_t *lengthp)
       allocated = (n > 0 ? n : 1);
       result = (char *) malloc (allocated);
       if (result == NULL)
-       goto out_of_memory_2;
+        goto out_of_memory_2;
     }
   length = 0;
 
@@ -63,54 +63,97 @@ memxfrm (char *s, size_t n, char *resultbuf, size_t *lengthp)
     p = s;
     for (;;)
       {
-       /* Search next NUL byte.  */
-       const char *q = p + strlen (p);
-
-       for (;;)
-         {
-           size_t k;
-
-           errno = 0;
-           k = strxfrm (result + length, p, allocated - length);
-           if (errno != 0)
-             goto fail;
-           if (k >= allocated - length)
-             {
-               /* Grow the result buffer.  */
-               char *new_result;
-
-               allocated = 2 * allocated;
-               if (allocated < 64)
-                 allocated = 64;
-               if (result == resultbuf)
-                 new_result = (char *) malloc (allocated);
-               else
-                 new_result = (char *) realloc (result, allocated);
-               if (new_result == NULL)
-                 goto out_of_memory_1;
-               result = new_result;
-             }
-           else
-             {
-               length += k;
-               break;
-             }
-         }
-
-       p = q + 1;
-       if (p == p_end)
-         break;
-       result[length] = '\0';
+        /* Search next NUL byte.  */
+        size_t l = strlen (p);
+
+        for (;;)
+          {
+            size_t k;
+
+            /* A call to strxfrm costs about 20 times more than a call to
+               strdup of the result.  Therefore it is worth to try to avoid
+               calling strxfrm more than once on a given string, by making
+               enough room before calling strxfrm.
+               The size of the strxfrm result, k, is likely to be between
+               l and 3 * l.  */
+            if (3 * l >= allocated - length)
+              {
+                /* Grow the result buffer.  */
+                size_t new_allocated;
+                char *new_result;
+
+                new_allocated = length + 3 * l + 1;
+                if (new_allocated < 2 * allocated)
+                  new_allocated = 2 * allocated;
+                if (new_allocated < 64)
+                  new_allocated = 64;
+                if (result == resultbuf)
+                  new_result = (char *) malloc (new_allocated);
+                else
+                  new_result = (char *) realloc (result, new_allocated);
+                if (new_result != NULL)
+                  {
+                    allocated = new_allocated;
+                    result = new_result;
+                  }
+              }
+
+            errno = 0;
+            k = strxfrm (result + length, p, allocated - length);
+            if (errno != 0)
+              goto fail;
+            if (k >= allocated - length)
+              {
+                /* Grow the result buffer.  */
+                size_t new_allocated;
+                char *new_result;
+
+                new_allocated = length + k + 1;
+                if (new_allocated < 2 * allocated)
+                  new_allocated = 2 * allocated;
+                if (new_allocated < 64)
+                  new_allocated = 64;
+                if (result == resultbuf)
+                  new_result = (char *) malloc (new_allocated);
+                else
+                  new_result = (char *) realloc (result, new_allocated);
+                if (new_result == NULL)
+                  goto out_of_memory_1;
+                allocated = new_allocated;
+                result = new_result;
+              }
+            else
+              {
+                length += k;
+                break;
+              }
+          }
+
+        p = p + l + 1;
+        if (p == p_end)
+          break;
+        result[length] = '\0';
         length++;
       }
   }
 
-  /* Shrink the allocated memory if possible.  */
-  if (result != resultbuf && (length > 0 ? length : 1) < allocated)
+  /* Shrink the allocated memory if possible.
+     It is not worth calling realloc when length + 1 == allocated; it would
+     save just one byte.  */
+  if (result != resultbuf && length + 1 < allocated)
     {
-      char *memory = (char *) realloc (result, length > 0 ? length : 1);
-      if (memory != NULL)
-       result = memory;
+      if ((length > 0 ? length : 1) <= *lengthp)
+        {
+          memcpy (resultbuf, result, length);
+          free (result);
+          result = resultbuf;
+        }
+      else
+        {
+          char *memory = (char *) realloc (result, length > 0 ? length : 1);
+          if (memory != NULL)
+            result = memory;
+        }
     }
 
   s[n] = orig_sentinel;