[sysprof: 50/63] libsysprof-capture: Rewrite list_files() to avoid GHashTable/GPtrArray

[Christian Hergert <chergert src gnome org>]

commit 75b69d0a896bfd75da33681a7061e03563518c1e
Author: Philip Withnall <withnall endlessm com>
Date:   Thu Jul 2 12:38:32 2020 +0100

    libsysprof-capture: Rewrite list_files() to avoid GHashTable/GPtrArray
    
    This changes its API and ABI: it now returns an allocated array of const
    strings, rather than an allocated array of allocated strings.
    
    The call sites in the source tree have been adjusted accordingly.
    
    Signed-off-by: Philip Withnall <withnall endlessm com>
    
    Helps: #40

 src/libsysprof-capture/sysprof-capture-reader.c | 82 ++++++++++++++++++++-----
 src/libsysprof-capture/sysprof-capture-reader.h |  2 +-
 src/tests/test-capture.c                        |  2 +-
 src/tools/sysprof-dump.c                        |  4 +-
 4 files changed, 71 insertions(+), 19 deletions(-)
---
diff --git a/src/libsysprof-capture/sysprof-capture-reader.c b/src/libsysprof-capture/sysprof-capture-reader.c
index 12b3f87..1166ae5 100644
--- a/src/libsysprof-capture/sysprof-capture-reader.c
+++ b/src/libsysprof-capture/sysprof-capture-reader.c
@@ -62,6 +62,7 @@
 #include <errno.h>
 #include <fcntl.h>
 #include <limits.h>
+#include <stdlib.h>
 #include <string.h>
 #include <sys/stat.h>
 #include <sys/types.h>
@@ -1273,20 +1274,60 @@ sysprof_capture_reader_read_file (SysprofCaptureReader *self)
   return file_chunk;
 }
 
-char **
+static bool
+array_append (const char ***files,
+              size_t       *n_files,
+              size_t       *n_files_allocated,
+              const char   *new_element)
+{
+  if (*n_files == *n_files_allocated)
+    {
+      const char **new_files;
+
+      *n_files_allocated = (*n_files_allocated > 0) ? 2 * *n_files_allocated : 4;
+      new_files = reallocarray (*files, *n_files_allocated, sizeof (**files));
+      if (new_files == NULL)
+        return false;
+      *files = new_files;
+    }
+
+  (*files)[*n_files] = new_element;
+  *n_files = *n_files + 1;
+  assert (*n_files <= *n_files_allocated);
+
+  return true;
+}
+
+static void
+array_deduplicate (const char **files,
+                   size_t      *n_files)
+{
+  size_t last_written, next_to_read;
+
+  if (*n_files == 0)
+    return;
+
+  for (last_written = 0, next_to_read = 1; last_written <= next_to_read && next_to_read < *n_files;)
+    {
+      if (strcmp (files[next_to_read], files[last_written]) == 0)
+        next_to_read++;
+      else
+        files[++last_written] = files[next_to_read++];
+    }
+
+  assert (last_written + 1 <= *n_files);
+  *n_files = last_written + 1;
+}
+
+const char **
 sysprof_capture_reader_list_files (SysprofCaptureReader *self)
 {
-  g_autoptr(GHashTable) files = NULL;
-  g_autoptr(GPtrArray) ar = NULL;
+  const char **files = NULL;
+  size_t n_files = 0, n_files_allocated = 0;
   SysprofCaptureFrameType type;
-  GHashTableIter iter;
-  const gchar *key;
 
   assert (self != NULL);
 
-  ar = g_ptr_array_new_with_free_func (g_free);
-  files = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
-
   while (sysprof_capture_reader_peek_type (self, &type))
     {
       const SysprofCaptureFileChunk *file;
@@ -1300,16 +1341,27 @@ sysprof_capture_reader_list_files (SysprofCaptureReader *self)
       if (!(file = sysprof_capture_reader_read_file (self)))
         break;
 
-      if (!g_hash_table_contains (files, file->path))
-        g_hash_table_insert (files, g_strdup (file->path), NULL);
+      if (!array_append (&files, &n_files, &n_files_allocated, file->path))
+        {
+          free (files);
+          errno = ENOMEM;
+          return NULL;
+        }
     }
 
-  g_hash_table_iter_init (&iter, files);
-  while (g_hash_table_iter_next (&iter, (gpointer *)&key, NULL))
-    g_ptr_array_add (ar, g_strdup (key));
-  g_ptr_array_add (ar, NULL);
+  /* Sort and deduplicate the files array. */
+  qsort (files, n_files, sizeof (*files), (int (*)(const void *, const void *)) strcmp);
+  array_deduplicate (files, &n_files);
+
+  /* Add a null terminator */
+  if (!array_append (&files, &n_files, &n_files_allocated, NULL))
+    {
+      free (files);
+      errno = ENOMEM;
+      return NULL;
+    }
 
-  return (char **)g_ptr_array_free (sysprof_steal_pointer (&ar), FALSE);
+  return sysprof_steal_pointer (&files);
 }
 
 bool
diff --git a/src/libsysprof-capture/sysprof-capture-reader.h b/src/libsysprof-capture/sysprof-capture-reader.h
index c417f9b..0fffa6a 100644
--- a/src/libsysprof-capture/sysprof-capture-reader.h
+++ b/src/libsysprof-capture/sysprof-capture-reader.h
@@ -144,7 +144,7 @@ SYSPROF_AVAILABLE_IN_ALL
 const SysprofCaptureFileChunk      *sysprof_capture_reader_find_file           (SysprofCaptureReader      
*self,
                                                                                 const char                
*path);
 SYSPROF_AVAILABLE_IN_ALL
-char                              **sysprof_capture_reader_list_files          (SysprofCaptureReader      
*self);
+const char                        **sysprof_capture_reader_list_files          (SysprofCaptureReader      
*self);
 SYSPROF_AVAILABLE_IN_ALL
 bool                                sysprof_capture_reader_read_file_fd        (SysprofCaptureReader      
*self,
                                                                                 const char                
*path,
diff --git a/src/tests/test-capture.c b/src/tests/test-capture.c
index 895fdfc..dda2ab1 100644
--- a/src/tests/test-capture.c
+++ b/src/tests/test-capture.c
@@ -747,7 +747,7 @@ test_reader_writer_file (void)
 {
   g_autofree gchar *data = NULL;
   GByteArray *buf = g_byte_array_new ();
-  g_auto(GStrv) files = NULL;
+  g_autofree const gchar **files = NULL;
   SysprofCaptureWriter *writer;
   SysprofCaptureReader *reader;
   SysprofCaptureFrameType type;
diff --git a/src/tools/sysprof-dump.c b/src/tools/sysprof-dump.c
index 2439490..17bd3a9 100644
--- a/src/tools/sysprof-dump.c
+++ b/src/tools/sysprof-dump.c
@@ -64,9 +64,9 @@ main (gint argc,
 
   if (list_files)
     {
-      g_auto(GStrv) files = sysprof_capture_reader_list_files (reader);
+      g_autofree const gchar **files = sysprof_capture_reader_list_files (reader);
 
-      for (guint i = 0; files[i]; i++)
+      for (gsize i = 0; files[i]; i++)
         g_print ("%s\n", files[i]);
 
       return EXIT_SUCCESS;