[gvfs] metadata: Use sequences instead of lists

[Ondrej Holy <oholy src gnome org>]

commit 0e001c9ced0dc6c6891f588e9c683308b46c9001
Author: Razvan Chitu <razvan ch95 gmail com>
Date:   Fri Sep 23 23:10:34 2016 +0300

    metadata: Use sequences instead of lists
    
    The metabuilder stores files and data in sorted lists. An insertion into a sorted
    list is done in linear time, which highly affects efficiency. In order to fix
    this, use GSequence instead which does insertion and deletion in logarithmic
    time.
    
    Modified by Ondrej Holy <oholy redhat com>.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=757747

 metadata/metabuilder.c |  195 +++++++++++++++++++++++++++++------------------
 metadata/metabuilder.h |    4 +-
 2 files changed, 122 insertions(+), 77 deletions(-)
---
diff --git a/metadata/metabuilder.c b/metadata/metabuilder.c
index 7c419b8..d7643f8 100644
--- a/metadata/metabuilder.c
+++ b/metadata/metabuilder.c
@@ -78,8 +78,9 @@ meta_builder_free (MetaBuilder *builder)
 }
 
 static gint
-compare_metafile (gconstpointer  a,
-                 gconstpointer  b)
+compare_metafile (gconstpointer a,
+                  gconstpointer b,
+                  gpointer      user_data)
 {
   const MetaFile *aa, *bb;
 
@@ -89,8 +90,9 @@ compare_metafile (gconstpointer  a,
 }
 
 static gint
-compare_metadata (gconstpointer  a,
-                 gconstpointer  b)
+compare_metadata (gconstpointer a,
+                  gconstpointer b,
+                  gpointer      user_data)
 {
   const MetaData *aa, *bb;
 
@@ -99,6 +101,18 @@ compare_metadata (gconstpointer  a,
   return strcmp (aa->key, bb->key);
 }
 
+static void
+metadata_free (MetaData *data)
+{
+  g_free (data->key);
+  if (data->is_list)
+    g_list_free_full (data->values, g_free);
+  else
+    g_free (data->value);
+
+  g_free (data);
+}
+
 MetaFile *
 metafile_new (const char *name,
              MetaFile *parent)
@@ -107,9 +121,10 @@ metafile_new (const char *name,
 
   f = g_new0 (MetaFile, 1);
   f->name = g_strdup (name);
+  f->children = g_sequence_new ((GDestroyNotify)metafile_free);
+  f->data = g_sequence_new ((GDestroyNotify)metadata_free);
   if (parent)
-    parent->children = g_list_insert_sorted (parent->children, f,
-                                            compare_metafile);
+    g_sequence_insert_sorted (parent->children, f, compare_metafile, NULL);
 
   return f;
 }
@@ -124,7 +139,7 @@ metadata_new (const char *key,
   data->key = g_strdup (key);
 
   if (file)
-    file->data = g_list_insert_sorted (file->data, data, compare_metadata);
+    g_sequence_insert_sorted (file->data, data, compare_metadata, NULL);
 
   return data;
 }
@@ -152,24 +167,12 @@ metadata_dup (MetaFile *file,
   return new_data;
 }
 
-static void
-metadata_free (MetaData *data)
-{
-  g_free (data->key);
-  if (data->is_list)
-    g_list_free_full (data->values, g_free);
-  else
-    g_free (data->value);
-
-  g_free (data);
-}
-
 void
 metafile_free (MetaFile *file)
 {
   g_free (file->name);
-  g_list_free_full (file->children, (GDestroyNotify)metafile_free);
-  g_list_free_full (file->data, (GDestroyNotify)metadata_free);
+  g_sequence_free (file->children);
+  g_sequence_free (file->data);
   g_free (file);
 }
 
@@ -178,15 +181,20 @@ metafile_lookup_child (MetaFile *metafile,
                       const char *name,
                       gboolean create)
 {
-  GList *l;
   MetaFile *child;
+  MetaFile lookup_file;
+  GSequenceIter *lookup_file_iter;
+
+  lookup_file.name = (char *)name;
+
+  lookup_file_iter = g_sequence_lookup (metafile->children,
+                                        &lookup_file,
+                                        compare_metafile,
+                                        NULL);
+
+  if (lookup_file_iter)
+    return g_sequence_get (lookup_file_iter);
 
-  for (l = metafile->children; l != NULL; l = l->next)
-    {
-      child = l->data;
-      if (strcmp (child->name, name) == 0)
-       return child;
-    }
   child = NULL;
   if (create)
     child = metafile_new (name, metafile);
@@ -252,16 +260,22 @@ meta_builder_remove (MetaBuilder *builder,
 
   if (parent != NULL)
     {
-      parent->children = g_list_remove (parent->children, f);
-      metafile_free (f);
+      GSequenceIter *iter;
+
+      iter = g_sequence_lookup (parent->children,
+                                f,
+                                compare_metafile,
+                                NULL);
+      g_sequence_remove (iter);
+
       if (mtime)
        parent->last_changed = mtime;
     }
   else
     {
       /* Removing root not allowed, just remove children */
-      g_list_free_full (f->children, (GDestroyNotify)metafile_free);
-      f->children = NULL;
+      g_sequence_remove_range (g_sequence_get_begin_iter (f->children),
+                               g_sequence_get_end_iter (f->children));
       if (mtime)
        f->last_changed = mtime;
     }
@@ -274,19 +288,23 @@ meta_file_copy_into (MetaFile *src,
                     guint64 mtime)
 {
   MetaFile *src_child, *dest_child;
-  GList *l;
+  GSequenceIter *iter;
 
   if (mtime)
     dest->last_changed = mtime;
   else
     dest->last_changed = src->last_changed;
 
-  for (l = src->data; l != NULL; l = l->next)
-    metadata_dup (dest, l->data);
+  for (iter = g_sequence_get_begin_iter (src->data);
+       iter != g_sequence_get_end_iter (src->data);
+       iter = g_sequence_iter_next (iter))
+    metadata_dup (dest, g_sequence_get (iter));
 
-  for (l = src->children; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (src->children);
+       iter != g_sequence_get_end_iter (src->children);
+       iter = g_sequence_iter_next (iter))
     {
-      src_child = l->data;
+      src_child = g_sequence_get (iter);
       dest_child = metafile_new (src_child->name, dest);
       meta_file_copy_into (src_child, dest_child, mtime);
     }
@@ -310,6 +328,8 @@ meta_builder_copy (MetaBuilder *builder,
   meta_file_copy_into (src, temp, mtime);
 
   dest = meta_builder_lookup (builder, dest_path, TRUE);
+  g_sequence_free (dest->data);
+  g_sequence_free (dest->children);
   dest->data = temp->data;
   dest->children = temp->children;
   dest->last_changed = temp->last_changed;
@@ -324,20 +344,31 @@ metafile_set_mtime (MetaFile    *file,
   file->last_changed = mtime;
 }
 
+GSequenceIter *
+metafile_key_lookup_iter (MetaFile *file,
+                          const char *key)
+{
+  MetaData lookup_data;
+
+  lookup_data.key = (char *)key;
+
+  return g_sequence_lookup (file->data,
+                            &lookup_data,
+                            compare_metadata,
+                            NULL);
+}
+
 MetaData *
 metafile_key_lookup (MetaFile *file,
                     const char *key,
                     gboolean create)
 {
-  GList *l;
   MetaData *data;
+  GSequenceIter *iter;
 
-  for (l = file->data; l != NULL; l = l->next)
-    {
-      data = l->data;
-      if (strcmp (data->key, key) == 0)
-       return data;
-    }
+  iter = metafile_key_lookup_iter (file, key);
+  if (iter)
+    return g_sequence_get (iter);
 
   data = NULL;
   if (create)
@@ -364,14 +395,11 @@ void
 metafile_key_unset (MetaFile *metafile,
                    const char *key)
 {
-  MetaData *data;
+  GSequenceIter *iter;
 
-  data = metafile_key_lookup (metafile, key, FALSE);
-  if (data)
-    {
-      metafile->data = g_list_remove (metafile->data, data);
-      metadata_free (data);
-    }
+  iter = metafile_key_lookup_iter (metafile, key);
+  if (iter)
+    g_sequence_remove (iter);
 }
 
 void
@@ -423,7 +451,8 @@ metafile_key_list_add (MetaFile *metafile,
 static void
 metafile_print (MetaFile *file, int indent, char *parent)
 {
-  GList *l, *v;
+  GSequenceIter *iter;
+  GList *v;
   MetaData *data;
   char *dir;
 
@@ -438,9 +467,11 @@ metafile_print (MetaFile *file, int indent, char *parent)
       indent += 3;
     }
 
-  for (l = file->data; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->data);
+       iter != g_sequence_get_end_iter (file->data);
+       iter = g_sequence_iter_next (iter))
     {
-      data = l->data;
+      data = g_sequence_get (iter);
       g_print ("%*s%s=", indent, "", data->key);
       if (data->is_list)
        {
@@ -455,9 +486,11 @@ metafile_print (MetaFile *file, int indent, char *parent)
        g_print ("%s", data->value);
       g_print ("\n");
     }
-  for (l = file->children; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->children);
+       iter != g_sequence_get_end_iter (file->children);
+       iter = g_sequence_iter_next (iter))
     {
-      metafile_print (l->data, indent, dir);
+      metafile_print (g_sequence_get (iter), indent, dir);
     }
 
   g_free (dir);
@@ -534,7 +567,7 @@ metafile_collect_times (MetaFile *file,
                        gint64 *time_t_min,
                        gint64 *time_t_max)
 {
-  GList *l;
+  GSequenceIter *iter;
   MetaFile *child;
 
   if (*time_t_min == 0)
@@ -545,9 +578,11 @@ metafile_collect_times (MetaFile *file,
   if (file->last_changed > *time_t_max)
     *time_t_max = file->last_changed;
 
-  for (l = file->children; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->children);
+       iter != g_sequence_get_end_iter (file->children);
+       iter = g_sequence_iter_next (iter))
     {
-      child = l->data;
+      child = g_sequence_get (iter);
       metafile_collect_times (child, time_t_min, time_t_max);
     }
 }
@@ -556,22 +591,26 @@ static void
 metafile_collect_keywords (MetaFile *file,
                           GHashTable *hash)
 {
-  GList *l;
+  GSequenceIter *iter;
   MetaData *data;
   MetaFile *child;
 
   file->metadata_pointer = 0;
   file->children_pointer = 0;
 
-  for (l = file->data; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->data);
+       iter != g_sequence_get_end_iter (file->data);
+       iter = g_sequence_iter_next (iter))
     {
-      data = l->data;
+      data = g_sequence_get (iter);
       g_hash_table_insert (hash, data->key, GINT_TO_POINTER (1));
     }
 
-  for (l = file->children; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->children);
+       iter != g_sequence_get_end_iter (file->children);
+       iter = g_sequence_iter_next (iter))
     {
-      child = l->data;
+      child = g_sequence_get (iter);
       metafile_collect_keywords (child, hash);
     }
 }
@@ -705,7 +744,7 @@ write_children (GString *out,
 {
   GHashTable *strings;
   MetaFile *child, *file;
-  GList *l;
+  GSequenceIter *iter;
   GList *files;
 
   files = g_list_prepend (NULL, builder->root);
@@ -723,11 +762,13 @@ write_children (GString *out,
       if (file->children_pointer != 0)
        set_uint32 (out, file->children_pointer, out->len);
 
-      append_uint32 (out, g_list_length (file->children), NULL);
+      append_uint32 (out, g_sequence_get_length (file->children), NULL);
 
-      for (l = file->children; l != NULL; l = l->next)
+      for (iter = g_sequence_get_begin_iter (file->children);
+           iter != g_sequence_get_end_iter (file->children);
+           iter = g_sequence_iter_next (iter))
        {
-         child = l->data;
+         child = g_sequence_get (iter);
 
          /* No mtime, children or metadata, no need for this
             to be in the file */
@@ -756,18 +797,20 @@ write_metadata_for_file (GString *out,
                         GHashTable *strings,
                         GHashTable *key_hash)
 {
-  GList *l;
+  GSequenceIter *iter;
   MetaData *data;
   guint32 key;
 
   g_assert (file->metadata_pointer != 0);
   set_uint32 (out, file->metadata_pointer, out->len);
 
-  append_uint32 (out, g_list_length (file->data), NULL);
+  append_uint32 (out, g_sequence_get_length (file->data), NULL);
 
-  for (l = file->data; l != NULL; l = l->next)
+  for (iter = g_sequence_get_begin_iter (file->data);
+       iter != g_sequence_get_end_iter (file->data);
+       iter = g_sequence_iter_next (iter))
     {
-      data = l->data;
+      data = g_sequence_get (iter);
 
       key = GPOINTER_TO_UINT (g_hash_table_lookup (key_hash, data->key));
       if (data->is_list)
@@ -788,7 +831,7 @@ write_metadata (GString *out,
   GHashTable *strings;
   GList *stringvs;
   MetaFile *child, *file;
-  GList *l;
+  GSequenceIter *iter;
   GList *files;
 
   /* Root metadata */
@@ -816,9 +859,11 @@ write_metadata (GString *out,
       strings = string_block_begin ();
       stringvs = stringv_block_begin ();
 
-      for (l = file->children; l != NULL; l = l->next)
+      for (iter = g_sequence_get_begin_iter (file->children);
+           iter != g_sequence_get_end_iter (file->children);
+           iter = g_sequence_iter_next (iter))
        {
-         child = l->data;
+         child = g_sequence_get (iter);
 
          if (child->data != NULL)
            write_metadata_for_file (out, child,
diff --git a/metadata/metabuilder.h b/metadata/metabuilder.h
index aa173c5..abfd4df 100644
--- a/metadata/metabuilder.h
+++ b/metadata/metabuilder.h
@@ -38,9 +38,9 @@ struct _MetaBuilder {
 
 struct _MetaFile {
   char *name;
-  GList *children;
+  GSequence *children;
   gint64 last_changed;
-  GList *data;
+  GSequence *data;
 
   guint32 metadata_pointer;
   guint32 children_pointer;