diff options
author | Razvan Chitu <razvan.ch95@gmail.com> | 2016-09-23 23:10:34 +0300 |
---|---|---|
committer | Ondrej Holy <oholy@redhat.com> | 2016-11-24 16:15:11 +0100 |
commit | 0e001c9ced0dc6c6891f588e9c683308b46c9001 (patch) | |
tree | 5c8a46b5919e4c2c98ce7e9430415e63f0f45a4b /metadata | |
parent | bec55901afa6cf1166d77b2b542e4556e7b19e57 (diff) | |
download | gvfs-0e001c9ced0dc6c6891f588e9c683308b46c9001.tar.gz |
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
Diffstat (limited to 'metadata')
-rw-r--r-- | metadata/metabuilder.c | 195 | ||||
-rw-r--r-- | metadata/metabuilder.h | 4 |
2 files changed, 122 insertions, 77 deletions
diff --git a/metadata/metabuilder.c b/metadata/metabuilder.c index 7c419b83..d7643f87 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 aa173c53..abfd4dfb 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; |