gvdb-reader.c: add gvdb_table_get_names()

This function lists off all names that appear within a particular hash.

2 files changed, 152 insertions, 1 deletions

diff --git a/gvdb-reader.c b/gvdb-reader.c
index b81aa56..a8531af 100644
--- a/gvdb-reader.c
+++ b/gvdb-reader.c
@@ -378,6 +378,155 @@ gvdb_table_list_from_item (GvdbTable                    *table,
   return TRUE;
 }
 
+/**
+ * gvdb_table_get_names:
+ * @table: a #GvdbTable
+ * @length: the number of items returned, or %NULL
+ *
+ * Gets a list of all names contained in @table.
+ *
+ * No call to gvdb_table_get_table(), gvdb_table_list() or
+ * gvdb_table_get_value() will succeed unless it is for one of the
+ * names returned by this function.
+ *
+ * Note that some names that are returned may still fail for all of the
+ * above calls in the case of the corrupted file.  Note also that the
+ * returned strings may not be utf8.
+ *
+ * Returns: a %NULL-terminated list of strings, of length @length
+ **/
+gchar **
+gvdb_table_get_names (GvdbTable *table,
+                      gint      *length)
+{
+  gchar **names;
+  gint n_names;
+  gint filled;
+  gint total;
+  gint i;
+
+  /* We generally proceed by iterating over the list of items in the
+   * hash table (in order of appearance) recording them into an array.
+   *
+   * Each item has a parent item (except root items).  The parent item
+   * forms part of the name of the item.  We could go fetching the
+   * parent item chain at the point that we encounter each item but then
+   * we would need to implement some sort of recursion along with checks
+   * for self-referential items.
+   *
+   * Instead, we do a number of passes.  Each pass will build up one
+   * level of names (starting from the root).  We continue to do passes
+   * until no more items are left.  The first pass will only add root
+   * items and each further pass will only add items whose direct parent
+   * is an item added in the immediately previous pass.  It's also
+   * possible that items get filled if they follow their parent within a
+   * particular pass.
+   *
+   * At most we will have a number of passes equal to the depth of the
+   * tree.  Self-referential items will never be filled in (since their
+   * parent will have never been filled in).  We continue until we have
+   * a pass that fills in no additional items.
+   *
+   * This takes an O(n) algorithm and turns it into O(n*m) where m is
+   * the depth of the tree, but in all sane cases the tree won't be very
+   * deep and the constant factor of this algorithm is lower (and the
+   * complexity of coding it, as well).
+   */
+
+  n_names = table->n_hash_items;
+  names = g_new0 (gchar *, n_names + 1);
+
+  /* 'names' starts out all-NULL.  On each pass we record the number
+   * of items changed from NULL to non-NULL in 'filled' so we know if we
+   * should repeat the loop.  'total' counts the total number of items
+   * filled.  If 'total' ends up equal to 'n_names' then we know that
+   * 'names' has been completely filled.
+   */
+
+  total = 0;
+  do
+    {
+      /* Loop until we have filled no more entries */
+      filled = 0;
+
+      for (i = 0; i < n_names; i++)
+        {
+          const struct gvdb_hash_item *item = &table->hash_items[i];
+          const gchar *name;
+          gsize name_length;
+          guint32 parent;
+
+          /* already got it on a previous pass */
+          if (names[i] != NULL)
+            continue;
+
+          parent = guint32_from_le (item->parent);
+
+          if (parent == 0xffffffffu)
+            {
+              /* it's a root item */
+              name = gvdb_table_item_get_key (table, item, &name_length);
+
+              if (name != NULL)
+                {
+                  names[i] = g_strndup (name, name_length);
+                  filled++;
+                }
+            }
+
+          else if (parent < n_names && names[parent] != NULL)
+            {
+              /* It's a non-root item whose parent was filled in already.
+               *
+               * Calculate the name of this item by combining it with
+               * its parent name.
+               */
+              name = gvdb_table_item_get_key (table, item, &name_length);
+
+              if (name != NULL)
+                {
+                  const gchar *parent_name = names[parent];
+                  gsize parent_length;
+                  gchar *fullname;
+
+                  parent_length = strlen (parent_name);
+                  fullname = g_malloc (parent_length + name_length + 1);
+                  memcpy (fullname, parent_name, parent_length);
+                  memcpy (fullname + parent_length, name, name_length);
+                  fullname[parent_length + name_length] = '\0';
+                  names[i] = fullname;
+                  filled++;
+                }
+            }
+        }
+
+      total += filled;
+    }
+  while (filled && total < n_names);
+
+  /* If the table was corrupted then 'names' may have holes in it.
+   * Collapse those.
+   */
+  if G_UNLIKELY (total != n_names)
+    {
+      GPtrArray *fixed_names;
+
+      fixed_names = g_ptr_array_new ();
+      for (i = 0; i < n_names; i++)
+        if (names[i] != NULL)
+          g_ptr_array_add (fixed_names, names[i]);
+
+      g_free (names);
+      n_names = fixed_names->len;
+      g_ptr_array_add (fixed_names, NULL);
+      names = (gchar **) g_ptr_array_free (fixed_names, FALSE);
+    }
+
+  if (length)
+    *length = n_names;
+
+  return names;
+}
 
 /**
  * gvdb_table_list:
diff --git a/gvdb-reader.h b/gvdb-reader.h
index 2a50c10..5c4631a 100644
--- a/gvdb-reader.h
+++ b/gvdb-reader.h
@@ -46,7 +46,9 @@ G_GNUC_INTERNAL
 GvdbTable *             gvdb_table_ref                                  (GvdbTable    *table);
 G_GNUC_INTERNAL
 void                    gvdb_table_unref                                (GvdbTable    *table);
-
+G_GNUC_INTERNAL
+gchar **                gvdb_table_get_names                            (GvdbTable    *table,
+                                                                         gint         *length);
 G_GNUC_INTERNAL
 gchar **                gvdb_table_list                                 (GvdbTable    *table,
                                                                          const gchar  *key);