Re: [PATCH] savedir: optionally produce ordered directory list

[Sergey Poznyakoff]

Hi Paul,

> It simplifies things by removing the obsolescent function
> fdsavedir, and omitting the static variable that stores internal
> state.

Great, thank you.  It passed the test successfully.  While at it,
it appeared to me that we can also avoid some memory reallocations
and one iteration over the entries array.  The attached patch
implements that idea and shows a slight improvement in the speed.

Regards,
Sergey

diff --git a/ChangeLog b/ChangeLog
index 96c544e..5aba801 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+2014-02-11  Sergey Poznyakoff  <address@hidden>
+           Paul Eggert  <address@hidden>
+
+       savedir: add sorting arg to savedir, streamsavedir; remove fdsavedir
+       Patch based on an idea by Dick Streefland in
+       <ttps://savannah.gnu.org/patch/?7892>.
+       * NEWS: Document this.
+       * lib/savedir.c (NAME_SIZE_DEFAULT): Remove.
+       (direntry_t, comparison_function): New types.
+       (direntry_cmp_name): New function.
+       (direntry_cmp_inode) [D_INO_IN_DIRENT]: New function.
+       (streamsavedir, savedir): New arg OPTION.
+       (streamsavedir): Simplify memory allocation.
+       (fdsavedir): Remove.
+       * lib/savedir.h (enum savedir_option): New type.
+       (streamsavedir, savedir): New arg OPTION.
+       (fdsavedir): Remove.
+
 2014-02-05  Paul Eggert  <address@hidden>

        file-type: add support for doors and other less-common file types
diff --git a/NEWS b/NEWS
index 2e7a518..4b02a5a 100644
--- a/NEWS
+++ b/NEWS
@@ -3,6 +3,10 @@ Important notes

 Date        Modules         Changes

+2014-02-11  savedir         The savedir and streamsavedir functions have a
+                            new argument specifying how to sort the result.
+                            The fdsavedir function is removed.
+
 2013-04-24  gettext         If your project uses 'gettextize --intl' it is now
                             your responsibility to put -I$(top_builddir)/intl
                             into the Makefile.am for gnulib.
diff --git a/lib/savedir.c b/lib/savedir.c
index 6e9c66c..badf602 100644
--- a/lib/savedir.c
+++ b/lib/savedir.c
@@ -37,29 +37,72 @@

 #include "xalloc.h"

-#ifndef NAME_SIZE_DEFAULT
-# define NAME_SIZE_DEFAULT 512
+typedef struct
+{
+  char *name;
+  size_t size;
+#if D_INO_IN_DIRENT
+  ino_t ino;
+#endif
+} direntry_t;
+
+/* Compare the names of two directory entries */
+
+static int
+direntry_cmp_name (void const *a, void const *b)
+{
+  direntry_t const *dea = a;
+  direntry_t const *deb = b;
+
+  return strcmp (dea->name, deb->name);
+}
+
+#if D_INO_IN_DIRENT
+/* Compare the inode numbers of two directory entries */
+
+static int
+direntry_cmp_inode (void const *a, void const *b)
+{
+  direntry_t const *dea = a;
+  direntry_t const *deb = b;
+
+  return dea->ino < deb->ino ? -1 : dea->ino > deb->ino;
+}
+#endif
+
+typedef int (*comparison_function) (void const *, void const *);
+
+static comparison_function const comparison_function_table[] =
+  {
+    0,
+    direntry_cmp_name
+#if D_INO_IN_DIRENT
+    , direntry_cmp_inode
 #endif
+  };

 /* Return a freshly allocated string containing the file names
    in directory DIRP, separated by '\0' characters;
    the end is marked by two '\0' characters in a row.
+   Returned values are sorted according to OPTION.
    Return NULL (setting errno) if DIRP cannot be read.
    If DIRP is NULL, return NULL without affecting errno.  */

 char *
-streamsavedir (DIR *dirp)
+streamsavedir (DIR *dirp, enum savedir_option option)
 {
-  char *name_space;
-  size_t allocated = NAME_SIZE_DEFAULT;
+  char *name_space = NULL;
+  size_t allocated = 0;
+  direntry_t *entries = NULL;
+  size_t entries_allocated = 0;
+  size_t entries_used = 0;
   size_t used = 0;
-  int save_errno;
+  int readdir_errno;
+  comparison_function cmp = comparison_function_table[option];

   if (dirp == NULL)
     return NULL;

-  name_space = xmalloc (allocated);
-
   for (;;)
     {
       struct dirent const *dp;
@@ -76,48 +119,65 @@ streamsavedir (DIR *dirp)
       if (entry[entry[0] != '.' ? 0 : entry[1] != '.' ? 1 : 2] != '\0')
         {
           size_t entry_size = _D_EXACT_NAMLEN (dp) + 1;
-          if (used + entry_size < used)
-            xalloc_die ();
-          if (allocated <= used + entry_size)
+          if (cmp)
             {
-              do
+              if (entries_allocated == entries_used)
                 {
-                  if (2 * allocated < allocated)
-                    xalloc_die ();
-                  allocated *= 2;
+                  size_t n = entries_allocated;
+                  entries = x2nrealloc (entries, &n, sizeof *entries);
+                  entries_allocated = n;
                 }
-              while (allocated <= used + entry_size);
-
-              name_space = xrealloc (name_space, allocated);
+              entries[entries_used].name = xstrdup (entry);
+             entries[entries_used].size = entry_size;
+#if D_INO_IN_DIRENT
+              entries[entries_used].ino = dp->d_ino;
+#endif
+              entries_used++;
             }
-          memcpy (name_space + used, entry, entry_size);
-          used += entry_size;
+         else
+           {
+             if (allocated - used <= entry_size)
+               {
+                 size_t n = used + entry_size;
+                 if (n < used)
+                   xalloc_die ();
+                 name_space = x2nrealloc (name_space, &n, 1);
+                 allocated = n;
+               }
+             memcpy (name_space + used, entry, entry_size);
+           }
+         used += entry_size;
         }
     }
-  name_space[used] = '\0';
-  save_errno = errno;
-  if (save_errno != 0)
+
+  readdir_errno = errno;
+  if (readdir_errno != 0)
     {
+      free (entries);
       free (name_space);
-      errno = save_errno;
+      errno = readdir_errno;
       return NULL;
     }
-  return name_space;
-}

-/* Like streamsavedir (DIRP), except also close DIRP.  */
-
-static char *
-savedirstream (DIR *dirp)
-{
-  char *name_space = streamsavedir (dirp);
-  if (dirp && closedir (dirp) != 0)
+  if (cmp)
     {
-      int save_errno = errno;
-      free (name_space);
-      errno = save_errno;
-      return NULL;
+      size_t i;
+
+      qsort (entries, entries_used, sizeof *entries, cmp);
+      name_space = xmalloc (used + 1);
+      used = 0;
+      for (i = 0; i < entries_used; i++)
+        {
+          memcpy (name_space + used, entries[i].name, entries[i].size);
+          used += entries[i].size;
+         free (entries[i].name);
+        }
+      free (entries);
     }
+  else if (used == allocated)
+    name_space = xrealloc (name_space, used + 1);
+
+  name_space[used] = '\0';
   return name_space;
 }

@@ -127,19 +187,21 @@ savedirstream (DIR *dirp)
    Return NULL (setting errno) if DIR cannot be opened, read, or closed.  */

 char *
-savedir (char const *dir)
+savedir (char const *dir, enum savedir_option option)
 {
-  return savedirstream (opendir (dir));
-}
-
-/* Return a freshly allocated string containing the file names
-   in directory FD, separated by '\0' characters;
-   the end is marked by two '\0' characters in a row.
-   Return NULL (setting errno) if FD cannot be read or closed.  */
-
-/* deprecated */
-char *
-fdsavedir (int fd)
-{
-  return savedirstream (fdopendir (fd));
+  DIR *dirp = opendir (dir);
+  if (! dirp)
+    return NULL;
+  else
+    {
+      char *name_space = streamsavedir (dirp, option);
+      if (closedir (dirp) != 0)
+        {
+          int closedir_errno = errno;
+          free (name_space);
+          errno = closedir_errno;
+          return NULL;
+        }
+      return name_space;
+    }
 }
diff --git a/lib/savedir.h b/lib/savedir.h
index 0684d94..73fc98a 100644
--- a/lib/savedir.h
+++ b/lib/savedir.h
@@ -22,8 +22,17 @@
 #define _GL_SAVEDIR_H

 #include <dirent.h>
-char *streamsavedir (DIR *dirp);
-char *savedir (char const *dir);
-char *fdsavedir (int fd); /* deprecated */
+
+enum savedir_option
+  {
+    SAVEDIR_SORT_NONE,
+    SAVEDIR_SORT_NAME
+#if D_INO_IN_DIRENT
+    , SAVEDIR_SORT_INODE
+#endif
+  };
+
+char *streamsavedir (DIR *, enum savedir_option);
+char *savedir (char const *, enum savedir_option);

 #endif