gvdb: introduce GvdbPath

2 files changed, 98 insertions, 1 deletions

diff --git a/gvdb/gvdb-reader.c b/gvdb/gvdb-reader.c
index 08b5bc8..4749ebf 100644
--- a/gvdb/gvdb-reader.c
+++ b/gvdb/gvdb-reader.c
@@ -14,7 +14,7 @@
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  *
- * Author: Ryan Lortie <desrt@desrt.ca>
+ * Author: Allison Lortie <desrt@desrt.ca>
  */
 
 #include "gvdb-reader.h"
@@ -42,6 +42,85 @@ struct _GvdbTable {
   guint32 n_hash_items;
 };
 
+static void
+gvdb_path_append_component (GvdbPath    *path,
+                            guint32      hash_value,
+                            guint        length)
+{
+  guint this_component = path->components++;
+
+  if G_UNLIKELY (path->components % G_N_ELEMENTS (path->my_hashes) == 0)
+    {
+      guint next_size;
+
+      G_STATIC_ASSERT (sizeof path->my_hashes == sizeof path->my_lengths);
+
+      if (path->hashes == path->my_hashes)
+        {
+          /* It's slightly inefficient to do it this way, but
+           * we're already on the slow path, and this simplifies
+           * the code below.
+           */
+          path->hashes = g_memdup (path->hashes, sizeof path->my_hashes);
+          path->lengths = g_memdup (path->lengths, sizeof path->my_lengths);
+        }
+
+      /* 16 → 32 → etc. */
+      next_size = path->components + G_N_ELEMENTS (path->my_hashes);
+      path->hashes = g_renew (guint32, path->hashes, next_size);
+      path->lengths = g_renew (guint, path->lengths, next_size);
+    }
+
+  path->hashes[this_component] = hash_value;
+  path->lengths[this_component] = length;
+}
+
+void
+gvdb_path_init (GvdbPath    *path,
+                const gchar *string,
+                gchar        separator)
+{
+  guint32 hash_value = 5381;
+  gboolean more = TRUE;
+  guint i;
+
+  path->string = string;
+  path->components = 0;
+  path->hashes = path->my_hashes;
+  path->lengths = path->my_lengths;
+
+  /* Find all of the separators, creating components, up to including
+   * each one.
+   */
+  for (i = 0; string[i]; i++)
+    {
+      hash_value = (hash_value * 33) + ((signed char) string[i]);
+      more = TRUE;
+
+      if (string[i] == separator)
+        {
+          gvdb_path_append_component (path, hash_value, i + 1);
+          more = FALSE;
+        }
+    }
+
+  /* If there was some extra characters past the last separator, this
+   * becomes our last component.
+   */
+  if (more)
+    gvdb_path_append_component (path, hash_value, i);
+}
+
+void
+gvdb_path_clear (GvdbPath *path)
+{
+  if (path->hashes != path->my_hashes)
+    g_free (path->hashes);
+
+  if (path->lengths != path->my_lengths)
+    g_free (path->my_lengths);
+}
+
 static const gchar *
 gvdb_table_item_get_key (GvdbTable                   *file,
                          const struct gvdb_hash_item *item,
diff --git a/gvdb/gvdb-reader.h b/gvdb/gvdb-reader.h
index 241b41a..1e5f270 100644
--- a/gvdb/gvdb-reader.h
+++ b/gvdb/gvdb-reader.h
@@ -24,9 +24,27 @@
 
 typedef struct _GvdbTable GvdbTable;
 
+typedef struct
+{
+  const gchar *string;
+  guint        components;
+  guint32     *hashes;
+  guint       *lengths;
+  guint32      my_hashes[16];
+  guint        my_lengths[16];
+} GvdbPath;
+
 G_BEGIN_DECLS
 
 G_GNUC_INTERNAL
+void                    gvdb_path_init                                  (GvdbPath     *path,
+                                                                         const gchar  *string,
+                                                                         gchar         separator);
+
+G_GNUC_INTERNAL
+void                    gvdb_path_clear                                 (GvdbPath     *path);
+
+G_GNUC_INTERNAL
 GvdbTable *             gvdb_table_new_from_bytes                       (GBytes       *bytes,
                                                                          gboolean      trusted,
                                                                          GError      **error);