dfi

14 files changed, 1941 insertions, 9 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 3177660..c711cd9 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -29,6 +29,18 @@ desktop_file_install_SOURCES =			\
 	install.c
 
 update_desktop_database_SOURCES =		\
+	dfi-builder.c				\
+	dfi-builder.h				\
+	dfi-id-list.c				\
+	dfi-id-list.h				\
+	dfi-keyfile.c				\
+	dfi-keyfile.h				\
+	dfi-string-list.c			\
+	dfi-string-list.h			\
+	dfi-string-table.c			\
+	dfi-string-table.h			\
+	dfi-text-index.c			\
+	dfi-text-index.h			\
 	mimeutils.c				\
 	mimeutils.h				\
 	mime-cache.c				\
diff --git a/src/dfi-builder.c b/src/dfi-builder.c
new file mode 100644
index 0000000..f3f2591
--- /dev/null
+++ b/src/dfi-builder.c
@@ -0,0 +1,656 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-builder.h"
+
+#include "dfi-string-table.h"
+#include "dfi-keyfile.h"
+#include "dfi-text-index.h"
+#include "dfi-string-list.h"
+#include "dfi-id-list.h"
+
+#include <string.h>
+#include <unistd.h>
+#include <locale.h>
+
+typedef struct
+{
+  GHashTable *locale_string_tables;  /* string tables */
+
+  DfiStringList *app_names;
+  DfiStringList *key_names;
+  DfiStringList *locale_names;
+  DfiStringList *group_names;
+
+  DfiTextIndex  *c_text_index;
+  DfiTextIndex  *mime_types;
+
+  GHashTable *locale_text_indexes;   /* str -> DfiTextIndex */
+  GHashTable *implementations;       /* str -> DfiIdList */
+  GHashTable *desktop_files;         /* str -> DfiKeyfile */
+
+  GString    *string;                /* file contents */
+} DfiBuilder;
+
+#define foreach_sequence_item_and_position(iter, sequence, counter) \
+  for (counter = 0, iter = g_sequence_get_begin_iter (sequence);        \
+       !g_sequence_iter_is_end (iter);                                  \
+       iter = g_sequence_iter_next (iter), counter++)
+
+static GHashTable *
+dfi_builder_get_string_table (DfiBuilder  *builder,
+                              const gchar *locale)
+{
+  return dfi_string_tables_get_table (builder->locale_string_tables, locale);
+}
+
+static guint
+dfi_builder_get_offset (DfiBuilder *builder)
+{
+  return builder->string->len;
+}
+
+static void
+dfi_builder_align (DfiBuilder *builder,
+                   guint       size)
+{
+  while (builder->string->len & (size - 1))
+    g_string_append_c (builder->string, '\0');
+}
+
+static guint
+dfi_builder_get_aligned (DfiBuilder *builder,
+                         guint       size)
+{
+  dfi_builder_align (builder, size);
+
+  return dfi_builder_get_offset (builder);
+}
+
+static void
+dfi_builder_check_alignment (DfiBuilder *builder,
+                             guint       size)
+{
+  g_assert (~builder->string->len & (size - 1));
+}
+
+static guint
+dfi_builder_write_uint16 (DfiBuilder *builder,
+                          guint16     value)
+{
+  guint offset = dfi_builder_get_offset (builder);
+
+  dfi_builder_check_alignment (builder, sizeof (guint16));
+
+  value = GUINT16_TO_LE (value);
+
+  g_string_append_len (builder->string, (gpointer) &value, sizeof value);
+
+  return offset;
+}
+
+static guint
+dfi_builder_write_uint32 (DfiBuilder *builder,
+                          guint32     value)
+{
+  guint offset = dfi_builder_get_offset (builder);
+
+  dfi_builder_check_alignment (builder, sizeof (guint32));
+
+  value = GUINT32_TO_LE (value);
+
+  g_string_append_len (builder->string, (gpointer) &value, sizeof value);
+
+  return offset;
+}
+
+#if 0
+static guint
+dfi_builder_write_raw_string (DfiBuilder *builder,
+                                             const gchar             *string)
+{
+  guint offset = dfi_builder_get_offset (builder);
+
+  g_string_append (builder->string, string);
+  g_string_append_c (builder->string, '\0');
+
+  return offset;
+}
+XXX
+#endif
+
+static guint
+dfi_builder_write_string (DfiBuilder  *builder,
+                          const gchar *from_locale,
+                          const gchar *string)
+{
+  guint offset;
+
+  offset = dfi_string_tables_get_offset (builder->locale_string_tables, from_locale, string);
+
+  return dfi_builder_write_uint32 (builder, offset);
+}
+
+static guint
+dfi_builder_write_string_list (DfiBuilder    *builder,
+                               DfiStringList *string_list)
+{
+  guint offset = dfi_builder_get_aligned (builder, sizeof (guint32));
+  const gchar * const *strings;
+  guint n, i;
+
+  strings = dfi_string_list_get_strings (string_list, &n);
+
+  dfi_builder_write_uint16 (builder, n);
+  dfi_builder_write_uint16 (builder, 0xffff); /* padding */
+
+  for (i = 0; i < n; i++)
+    dfi_builder_write_string (builder, "", strings[i]);
+
+  return offset;
+}
+
+static guint
+dfi_builder_write_id (DfiBuilder    *builder,
+                      DfiStringList *string_list,
+                      const gchar   *string)
+{
+  guint value;
+
+  if (string == NULL)
+    return dfi_builder_write_uint16 (builder, G_MAXUINT16);
+
+  value = dfi_string_list_get_id (string_list, string);
+
+  return dfi_builder_write_uint16 (builder, (gsize) value);
+}
+
+static guint
+dfi_builder_write_keyfile (DfiBuilder  *builder,
+                           const gchar *app,
+                           gpointer     data)
+{
+  guint offset = dfi_builder_get_aligned (builder, sizeof (guint16));
+  DfiKeyfile *keyfile = data;
+  gint n_groups, n_items;
+  gint i;
+
+  n_groups = dfi_keyfile_get_n_groups (keyfile);
+  n_items = dfi_keyfile_get_n_items (keyfile);
+
+  dfi_builder_write_uint16 (builder, n_groups);
+  dfi_builder_write_uint16 (builder, n_items);
+
+  for (i = 0; i < n_groups; i++)
+    {
+      const gchar *group_name;
+      guint start;
+
+      group_name = dfi_keyfile_get_group_name (keyfile, i);
+      dfi_keyfile_get_group_range (keyfile, i, &start, NULL);
+
+      dfi_builder_write_id (builder, builder->group_names, group_name);
+      dfi_builder_write_uint16 (builder, start);
+    }
+
+  for (i = 0; i < n_items; i++)
+    {
+      const gchar *key, *locale, *value;
+
+      dfi_keyfile_get_item (keyfile, i, &key, &locale, &value);
+
+      dfi_builder_write_id (builder, builder->key_names, key);
+      dfi_builder_write_id (builder, builder->locale_names, locale);
+      dfi_builder_write_string (builder, locale, value);
+    }
+
+  return offset;
+}
+
+typedef guint (* DfiBuilderFunc) (DfiBuilder  *builder,
+                                  const gchar *key,
+                                  gpointer     data);
+
+static guint
+dfi_builder_write_pointer_array (DfiBuilder     *builder,
+                                 DfiStringList  *key_list,
+                                 guint           key_list_offset,
+                                 GHashTable     *data_table,
+                                 DfiBuilderFunc  func)
+{
+  const gchar * const *strings;
+  guint *offsets;
+  guint offset;
+  guint n, i;
+
+  strings = dfi_string_list_get_strings (key_list, &n);
+  offsets = g_new0 (guint, n);
+
+  for (i = 0; i < n; i++)
+    {
+      gpointer data;
+
+      data = g_hash_table_lookup (data_table, strings[i]);
+      offsets[i] = (* func) (builder, strings[i], data);
+    }
+
+  offset = dfi_builder_get_aligned (builder, sizeof (guint32));
+  dfi_builder_write_uint32 (builder, key_list_offset);
+
+  for (i = 0; i < n; i++)
+    dfi_builder_write_uint32 (builder, offsets[i]);
+
+  g_free (offsets);
+
+  return offset;
+}
+
+static guint
+dfi_builder_write_id_list (DfiBuilder  *builder,
+                           const gchar *key,
+                           gpointer     data)
+{
+  GArray *id_list = data;
+  const guint16 *ids;
+  guint offset;
+  guint n_ids;
+  guint i;
+
+  ids = dfi_id_list_get_ids (id_list, &n_ids);
+
+  offset = dfi_builder_write_uint16 (builder, n_ids);
+
+  for (i = 0; i < n_ids; i++)
+    dfi_builder_write_uint16 (builder, ids[i]);
+
+  return offset;
+}
+
+static guint
+dfi_builder_write_text_index (DfiBuilder  *builder,
+                              const gchar *key,
+                              gpointer     data)
+{
+  GSequence *text_index = data;
+  const gchar *locale = key;
+  GHashTable *string_table;
+  GSequenceIter *iter;
+  const gchar **strings;
+  guint *id_lists;
+  guint offset;
+  guint n_items;
+  guint i;
+
+  string_table = dfi_builder_get_string_table (builder, locale);
+  if (!dfi_string_table_is_written (string_table))
+    {
+      GHashTable *c_string_table;
+
+      c_string_table = dfi_string_tables_get_table (builder->locale_string_tables, "");
+      dfi_string_table_write (string_table, c_string_table, builder->string);
+    }
+
+  n_items = g_sequence_get_length (text_index);
+
+  strings = g_new (const gchar *, n_items);
+  id_lists = g_new (guint, n_items);
+
+  dfi_builder_align (builder, sizeof (guint16));
+
+  foreach_sequence_item_and_position (iter, text_index, i)
+    {
+      GArray *id_list;
+
+      dfi_text_index_get_item (iter, &strings[i], &id_list);
+      id_lists[i] = dfi_builder_write_id_list (builder, NULL, id_list);
+    }
+
+  dfi_builder_align (builder, sizeof (guint32));
+
+  offset = dfi_builder_get_offset (builder);
+
+  dfi_builder_write_uint32 (builder, n_items);
+
+  for (i = 0; i < n_items; i++)
+    {
+      dfi_builder_write_string (builder, locale, strings[i]);
+      dfi_builder_write_uint32 (builder, id_lists[i]);
+    }
+
+  g_free (strings);
+  g_free (id_lists);
+
+  return offset;
+}
+
+static void
+dfi_builder_serialise (DfiBuilder *builder)
+{
+  guint32 header_fields[8] = { 0, };
+
+  builder->string = g_string_new (NULL);
+
+  /* Make room for the header */
+  g_string_append_len (builder->string, (char *) header_fields, sizeof header_fields);
+
+  /* Write out the C string table, filling in the offsets
+   *
+   * We have to do this first because all of the string lists (apps,
+   * keys, locales, groups) are stored as strings in the C locale.
+   */
+  {
+    GHashTable *c_table;
+
+    c_table = dfi_builder_get_string_table (builder, "");
+    dfi_string_table_write (c_table, NULL, builder->string);
+  }
+
+  /* Write out the string lists.  This will work because they only
+   * refer to strings in the C locale.
+   */
+  {
+    header_fields[0] = dfi_builder_write_string_list (builder, builder->app_names);
+    header_fields[1] = dfi_builder_write_string_list (builder, builder->key_names);
+    header_fields[2] = dfi_builder_write_string_list (builder, builder->locale_names);
+    header_fields[3] = dfi_builder_write_string_list (builder, builder->group_names);
+  }
+
+  /* Write out the group implementors */
+  {
+    /*
+    header_fields[4] = dfi_builder_write_pointer_array (builder,
+                                                                       builder->group_names,
+                                                                       header_fields[3],
+                                                                       builder->group_implementors,
+                                                                       dfi_builder_write_id_list);
+                                                                       */
+  }
+
+  /* Write out the text indexes for the actual locales.
+   *
+   * Note: we do this by visiting each item in the locale string list,
+   * which doesn't include the C locale, so we won't end up emitting the
+   * C locale again here.
+   *
+   * Note: this function will write out the locale-specific string
+   * tables alongside the table for each locale in order to improve
+   * locality.
+   */
+  {
+    header_fields[5] = dfi_builder_write_pointer_array (builder,
+                                                                       builder->locale_names,
+                                                                       header_fields[2],
+                                                                       builder->locale_text_indexes,
+                                                                       dfi_builder_write_text_index);
+  }
+
+  /* Write out the desktop file contents.
+   *
+   * We have to do this last because the desktop files refer to strings
+   * from all the locales and those are only actually written in the
+   * last step.
+   *
+   * TODO: we could improve things a bit by storing the desktop files at
+   * the front of the cache, but this would require a two-pass
+   * approach...
+   */
+  {
+    header_fields[6] = dfi_builder_write_pointer_array (builder,
+                                                                       builder->app_names,
+                                                                       header_fields[0],
+                                                                       builder->desktop_files,
+                                                                       dfi_builder_write_keyfile);
+  }
+
+  /* Write out the mime types index */
+  {
+    //header_fields[7] = dfi_builder_write_text_index (builder, NULL, builder->mime_types);
+  }
+
+  /* Replace the header */
+  {
+    guint32 *file = (guint32 *) builder->string->str;
+    guint i;
+
+    for (i = 0; i < G_N_ELEMENTS (header_fields); i++)
+      file[i] = GUINT32_TO_LE (header_fields[i]);
+  }
+}
+
+static void
+dfi_builder_add_strings_for_keyfile (DfiBuilder              *builder,
+                                     DfiKeyfile *keyfile)
+{
+  guint n_groups;
+  guint i;
+
+  n_groups = dfi_keyfile_get_n_groups (keyfile);
+
+  for (i = 0; i < n_groups; i++)
+    {
+      const gchar *group_name;
+      guint start, end;
+      guint j;
+
+      group_name = dfi_keyfile_get_group_name (keyfile, i);
+      dfi_keyfile_get_group_range (keyfile, i, &start, &end);
+
+      dfi_string_list_ensure (builder->group_names, group_name);
+
+      for (j = start; j < end; j++)
+        {
+          const gchar *key, *locale, *value;
+
+          dfi_keyfile_get_item (keyfile, j, &key, &locale, &value);
+
+          dfi_string_list_ensure (builder->key_names, key);
+
+          if (locale)
+            dfi_string_list_ensure (builder->locale_names, locale);
+
+          dfi_string_tables_add_string (builder->locale_string_tables, locale, value);
+        }
+    }
+}
+
+static void
+dfi_builder_add_strings (DfiBuilder *builder)
+{
+  GHashTableIter keyfile_iter;
+  gpointer key, value;
+
+  builder->locale_string_tables = dfi_string_tables_create ();
+  builder->app_names = dfi_string_list_new ();
+  builder->key_names = dfi_string_list_new ();
+  builder->locale_names = dfi_string_list_new ();
+  builder->group_names = dfi_string_list_new ();
+
+  g_hash_table_iter_init (&keyfile_iter, builder->desktop_files);
+  while (g_hash_table_iter_next (&keyfile_iter, &key, &value))
+    {
+      DfiKeyfile *keyfile = value;
+      const gchar *app = key;
+
+      dfi_string_list_ensure (builder->app_names, app);
+      dfi_builder_add_strings_for_keyfile (builder, keyfile);
+    }
+
+  dfi_string_list_convert (builder->app_names);
+  dfi_string_list_convert (builder->group_names);
+  dfi_string_list_convert (builder->key_names);
+  dfi_string_list_convert (builder->locale_names);
+
+  {
+    GHashTable *c_string_table;
+
+    c_string_table = dfi_string_tables_get_table (builder->locale_string_tables, "");
+
+    dfi_string_list_populate_strings (builder->app_names, c_string_table);
+    dfi_string_list_populate_strings (builder->group_names, c_string_table);
+    dfi_string_list_populate_strings (builder->key_names, c_string_table);
+    dfi_string_list_populate_strings (builder->locale_names, c_string_table);
+  }
+}
+
+static GSequence *
+dfi_builder_index_one_locale (DfiBuilder  *builder,
+                              const gchar *locale)
+{
+  const gchar *fields[] = { "Name", "GenericName", "X-GNOME-FullName", "Comment", "Keywords" };
+  gchar **locale_variants;
+  GHashTableIter keyfile_iter;
+  gpointer key, val;
+  GSequence *text_index;
+
+  if (locale)
+    locale_variants = g_get_locale_variants (locale);
+  else
+    locale_variants = g_new0 (gchar *, 0 + 1);
+
+  text_index = dfi_text_index_new ();
+
+  g_hash_table_iter_init (&keyfile_iter, builder->desktop_files);
+  while (g_hash_table_iter_next (&keyfile_iter, &key, &val))
+    {
+      DfiKeyfile *kf = val;
+      const gchar *app = key;
+      guint i;
+
+      for (i = 0; i < G_N_ELEMENTS (fields); i++)
+        {
+          const gchar *value;
+
+          value = dfi_keyfile_get_value (kf, (const gchar **) locale_variants, "Desktop Entry", fields[i]);
+
+          if (value)
+            {
+              guint16 ids[3];
+
+              ids[0] = dfi_string_list_get_id (builder->app_names, app);
+              ids[1] = dfi_string_list_get_id (builder->group_names, "Desktop Entry");
+              ids[2] = dfi_string_list_get_id (builder->key_names, fields[i]);
+
+              dfi_text_index_add_ids_tokenised (text_index, value, ids, 3);
+            }
+        }
+    }
+
+  g_free (locale_variants);
+
+  return text_index;
+}
+
+static void
+dfi_builder_index_strings (DfiBuilder *builder)
+{
+  const gchar * const *locale_names;
+  GHashTable *c_string_table;
+  guint i;
+
+  c_string_table = dfi_string_tables_get_table (builder->locale_string_tables, "");
+  builder->c_text_index = dfi_builder_index_one_locale (builder, "");
+  dfi_text_index_populate_strings (builder->c_text_index, c_string_table);
+
+  locale_names = dfi_string_list_get_strings (builder->locale_names, NULL);
+
+  builder->locale_text_indexes = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, dfi_text_index_free);
+
+  for (i = 0; locale_names[i]; i++)
+    {
+      const gchar *locale = locale_names[i];
+      GHashTable *string_table;
+      GSequence *text_index;
+
+      text_index = dfi_builder_index_one_locale (builder, locale);
+      g_hash_table_insert (builder->locale_text_indexes, g_strdup (locale), text_index);
+      string_table = dfi_string_tables_get_table (builder->locale_string_tables, locale);
+      dfi_text_index_populate_strings (text_index, string_table);
+    }
+}
+
+static DfiBuilder *
+dfi_builder_new (void)
+{
+  DfiBuilder *builder;
+
+  builder = g_slice_new0 (DfiBuilder);
+  builder->desktop_files = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, (GDestroyNotify) dfi_keyfile_free);
+  builder->string = NULL;
+
+  return builder;
+}
+
+static gboolean
+dfi_builder_add_desktop_file (DfiBuilder   *builder,
+                              const gchar  *desktop_id,
+                              const gchar  *filename,
+                              GError      **error)
+{
+  DfiKeyfile *kf;
+
+  kf = dfi_keyfile_new (filename, error);
+  if (!kf)
+    return FALSE;
+
+  g_hash_table_insert (builder->desktop_files, g_strdup (desktop_id), kf);
+
+  return TRUE;
+}
+
+GBytes *
+dfi_builder_build (const gchar  *desktop_dir,
+                   GError      **error)
+{
+  DfiBuilder *builder;
+  const gchar *name;
+  GDir *dir;
+
+  builder = dfi_builder_new ();
+
+  dir = g_dir_open (desktop_dir, 0, error);
+  if (!dir)
+    return NULL;
+
+  while ((name = g_dir_read_name (dir)))
+    {
+      gboolean success;
+      gchar *fullname;
+
+      if (!g_str_has_suffix (name, ".desktop"))
+        continue;
+
+      fullname = g_build_filename (desktop_dir, name, NULL);
+      success = dfi_builder_add_desktop_file (builder, name, fullname, error);
+      g_free (fullname);
+
+      if (!success)
+        return NULL;
+    }
+  g_dir_close (dir);
+
+  dfi_builder_add_strings (builder);
+
+  dfi_builder_index_strings (builder);
+
+  dfi_builder_serialise (builder);
+
+  return g_bytes_new (builder->string->str, builder->string->len);
+}
diff --git a/src/dfi-builder.h b/src/dfi-builder.h
new file mode 100644
index 0000000..f5dae1f
--- /dev/null
+++ b/src/dfi-builder.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_builder_h__
+#define __dfi_builder_h__
+
+#include <glib.h>
+
+GBytes *                        dfi_builder_build                       (const gchar  *desktop_dir,
+                                                                         GError      **error);
+
+#endif /* __dfi_builder_h__ */
diff --git a/src/dfi-id-list.c b/src/dfi-id-list.c
new file mode 100644
index 0000000..22813d4
--- /dev/null
+++ b/src/dfi-id-list.c
@@ -0,0 +1,55 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-id-list.h"
+
+#include "dfi-text-index.h"
+
+#include <string.h>
+
+GArray *
+dfi_id_list_new (void)
+{
+  return g_array_new (FALSE, FALSE, sizeof (guint16));
+}
+
+void
+dfi_id_list_free (GArray *id_list)
+{
+  g_array_free (id_list, TRUE);
+}
+
+void
+dfi_id_list_add_ids (GArray        *id_list,
+                     const guint16 *ids,
+                     gint           n_ids)
+{
+  g_array_append_vals (id_list, ids, n_ids);
+}
+
+const guint16 *
+dfi_id_list_get_ids (GArray *id_list,
+                     guint  *n_ids)
+{
+  *n_ids = id_list->len;
+
+  return (guint16 *) id_list->data;
+}
diff --git a/src/dfi-id-list.h b/src/dfi-id-list.h
new file mode 100644
index 0000000..f2fe6b0
--- /dev/null
+++ b/src/dfi-id-list.h
@@ -0,0 +1,39 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_id_list_h__
+#define __dfi_id_list_h__
+
+#include <glib.h>
+
+typedef GArray DfiIdList;
+
+DfiIdList *             dfi_id_list_new                                 (void);
+
+void                    dfi_id_list_free                                (DfiIdList     *id_list);
+
+void                    dfi_id_list_add_ids                             (DfiIdList     *id_list,
+                                                                         const guint16 *ids,
+                                                                         gint           n_ids);
+
+const guint16 *         dfi_id_list_get_ids                             (DfiIdList      *id_list,
+                                                                         guint          *n_ids);
+#endif /* __dfi_id_list_h__ */
diff --git a/src/dfi-keyfile.c b/src/dfi-keyfile.c
new file mode 100644
index 0000000..87c7725
--- /dev/null
+++ b/src/dfi-keyfile.c
@@ -0,0 +1,308 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-keyfile.h"
+
+#include <string.h>
+
+typedef struct
+{
+  gchar *key;
+  gchar *locale;
+  gchar *value;
+} DfiKeyfileItem;
+
+typedef struct
+{
+  gchar *name;
+  guint  start;
+} DfiKeyfileGroup;
+
+struct _DfiKeyfile
+{
+  GPtrArray *groups;
+  GPtrArray *items;
+};
+
+static void
+dfi_keyfile_group_free (gpointer data)
+{
+  DfiKeyfileGroup *group = data;
+
+  g_free (group->name);
+
+  g_slice_free (DfiKeyfileGroup, group);
+}
+
+static void
+dfi_keyfile_item_free (gpointer data)
+{
+  DfiKeyfileItem *item = data;
+
+  g_free (item->key);
+  g_free (item->locale);
+  g_free (item->value);
+
+  g_slice_free (DfiKeyfileItem, item);
+}
+
+void
+dfi_keyfile_free (DfiKeyfile *keyfile)
+{
+  g_ptr_array_free (keyfile->groups, TRUE);
+  g_ptr_array_free (keyfile->items, TRUE);
+
+  g_slice_free (DfiKeyfile, keyfile);
+}
+
+guint
+dfi_keyfile_get_n_groups (DfiKeyfile *keyfile)
+{
+  return keyfile->groups->len;
+}
+
+guint
+dfi_keyfile_get_n_items (DfiKeyfile *keyfile)
+{
+  return keyfile->items->len;
+}
+
+const gchar *
+dfi_keyfile_get_group_name (DfiKeyfile *keyfile,
+                            guint       group)
+{
+  DfiKeyfileGroup *kfg;
+
+  kfg = keyfile->groups->pdata[group];
+
+  return kfg->name;
+}
+
+void
+dfi_keyfile_get_group_range (DfiKeyfile *keyfile,
+                             guint       group,
+                             guint      *start,
+                             guint      *end)
+{
+  DfiKeyfileGroup *kfg;
+
+  kfg = keyfile->groups->pdata[group];
+  *start = kfg->start;
+
+  if (end)
+    {
+      if (group == keyfile->groups->len - 1)
+        *end = keyfile->items->len;
+      else
+        {
+          kfg = keyfile->groups->pdata[group + 1];
+          *end = kfg->start;
+        }
+    }
+}
+
+void
+dfi_keyfile_get_item (DfiKeyfile   *keyfile,
+                      guint         item,
+                      const gchar **key,
+                      const gchar **locale,
+                      const gchar **value)
+{
+  DfiKeyfileItem *kfi;
+
+  kfi = keyfile->items->pdata[item];
+
+  *key = kfi->key;
+  *locale = kfi->locale;
+  *value = kfi->value;
+}
+
+const gchar *
+dfi_keyfile_get_value (DfiKeyfile          *keyfile,
+                       const gchar * const *locale_variants,
+                       const gchar         *group_name,
+                       const gchar         *key)
+{
+  guint start = 0, end = 0;
+  guint i;
+
+  /* Find group... */
+  for (i = 0; i < keyfile->groups->len; i++)
+    {
+      DfiKeyfileGroup *group = keyfile->groups->pdata[i];
+
+      if (g_str_equal (group->name, group_name))
+        {
+          start = group->start;
+
+          if (i < keyfile->groups->len - 1)
+            {
+              DfiKeyfileGroup *next_group;
+
+              next_group = keyfile->groups->pdata[i + 1];
+              end = next_group->start;
+            }
+          else
+            end = keyfile->items->len;
+        }
+    }
+
+  /* For each locale variant... */
+  for (i = 0; locale_variants[i]; i++)
+    {
+      guint j;
+
+      for (j = start; j < end; j++)
+        {
+          DfiKeyfileItem *item = keyfile->items->pdata[j];
+
+          /* There are more unique locales than there are keys, so check
+           * those first.
+           */
+          if (item->locale && g_str_equal (item->locale, locale_variants[i]) && g_str_equal (item->key, key))
+            return item->value;
+        }
+    }
+
+  /* Try the NULL locale as a fallback */
+  for (i = start; i < end; i++)
+    {
+      DfiKeyfileItem *item = keyfile->items->pdata[i];
+
+      if (item->locale[0] == '\0' && g_str_equal (item->key, key))
+        return item->value;
+    }
+
+  return NULL;
+}
+
+DfiKeyfile *
+dfi_keyfile_new (const gchar  *filename,
+                 GError      **error)
+{
+  DfiKeyfile *kf;
+  gchar *contents;
+  const gchar *c;
+  gsize length;
+  gint line = 1;
+
+  if (!g_file_get_contents (filename, &contents, &length, error))
+    return NULL;
+
+  kf = g_slice_new (DfiKeyfile);
+  kf->groups = g_ptr_array_new_with_free_func (dfi_keyfile_group_free);
+  kf->items = g_ptr_array_new_with_free_func (dfi_keyfile_item_free);
+
+  c = contents;
+  while (*c)
+    {
+      gint line_length;
+
+      line_length = strcspn (c, "\n");
+
+      if (line_length == 0 || c[0] == '#')
+        /* looks like a comment */
+        ;
+
+      else if (c[0] == '[')
+        {
+          DfiKeyfileGroup *kfg;
+          gint group_size;
+
+          group_size = strcspn (c + 1, "]");
+          if (group_size != line_length - 2)
+            {
+              g_set_error (error, G_KEY_FILE_ERROR, G_KEY_FILE_ERROR_PARSE,
+                           "%s:%d: Invalid group line: ']' must be last character on line", filename, line);
+              goto err;
+            }
+
+          kfg = g_slice_new (DfiKeyfileGroup);
+
+          kfg->name = g_strndup (c + 1, group_size);
+          kfg->start = kf->items->len;
+
+          g_ptr_array_add (kf->groups, kfg);
+        }
+
+      else
+        {
+          DfiKeyfileItem *kfi;
+          gsize key_size;
+          const gchar *locale;
+          gsize locale_size;
+          const gchar *value;
+          gsize value_size;
+
+          key_size = strspn (c, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-");
+
+          if (key_size && c[key_size] == '[')
+            {
+              locale = c + key_size + 1;
+              locale_size = strspn (locale, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789@._");
+              if (locale_size == 0 || locale[locale_size] != ']' || locale[locale_size + 1] != '=')
+                {
+                  g_set_error (error, G_KEY_FILE_ERROR, G_KEY_FILE_ERROR_PARSE,
+                               "%s:%d: Keys containing '[' must then have a locale name, then ']='", filename, line);
+                  goto err;
+                }
+              value = locale + locale_size + 2;
+              value_size = line_length - locale_size - key_size - 3; /* [ ] = */
+            }
+          else if (key_size && c[key_size] == '=')
+            {
+              locale = "";
+              locale_size = 0;
+              value = c + key_size + 1;
+              value_size = line_length - key_size - 1; /* = */
+            }
+          else
+            {
+              g_set_error (error, G_KEY_FILE_ERROR, G_KEY_FILE_ERROR_PARSE,
+                           "%s:%d: Lines must either be empty, comments, groups or assignments", filename, line);
+              goto err;
+            }
+
+          kfi = g_slice_new (DfiKeyfileItem);
+          kfi->key = g_strndup (c, key_size);
+          kfi->locale = g_strndup (locale, locale_size);
+          kfi->value = g_strndup (value, value_size);
+
+          g_ptr_array_add (kf->items, kfi);
+        }
+
+      c += line_length;
+
+      /* May have unterminated lines... */
+      if (*c == '\n')
+        c++;
+
+      line++;
+    }
+
+  return kf;
+
+err:
+  g_ptr_array_free (kf->groups, TRUE);
+  g_ptr_array_free (kf->items, TRUE);
+
+  return NULL;
+}
diff --git a/src/dfi-keyfile.h b/src/dfi-keyfile.h
new file mode 100644
index 0000000..5683320
--- /dev/null
+++ b/src/dfi-keyfile.h
@@ -0,0 +1,57 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_keyfile_h__
+#define __dfi_keyfile_h__
+
+#include <glib.h>
+
+typedef struct _DfiKeyfile                                  DfiKeyfile;
+
+DfiKeyfile *            dfi_keyfile_new                                 (const gchar          *filename,
+                                                                         GError              **error);
+
+void                    dfi_keyfile_free                                (DfiKeyfile           *keyfile);
+
+const gchar *           dfi_keyfile_get_value                           (DfiKeyfile           *keyfile,
+                                                                         const gchar * const  *locale_variants,
+                                                                         const gchar          *group_name,
+                                                                         const gchar          *key);
+
+guint                   dfi_keyfile_get_n_groups                        (DfiKeyfile           *keyfile);
+
+guint                   dfi_keyfile_get_n_items                         (DfiKeyfile           *keyfile);
+
+const gchar *           dfi_keyfile_get_group_name                      (DfiKeyfile           *keyfile,
+                                                                         guint                 group);
+
+void                    dfi_keyfile_get_group_range                     (DfiKeyfile           *keyfile,
+                                                                         guint                 group,
+                                                                         guint                *start,
+                                                                         guint                *end);
+
+void                    dfi_keyfile_get_item                            (DfiKeyfile           *keyfile,
+                                                                         guint                 item,
+                                                                         const gchar         **key,
+                                                                         const gchar         **locale,
+                                                                         const gchar         **value);
+
+#endif /* __dfi_keyfile_h__ */
diff --git a/src/dfi-string-list.c b/src/dfi-string-list.c
new file mode 100644
index 0000000..a4926dc
--- /dev/null
+++ b/src/dfi-string-list.c
@@ -0,0 +1,138 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-string-list.h"
+
+#include "dfi-string-table.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+struct _DfiStringList
+{
+  GHashTable *table;
+  gchar **strings;
+};
+
+DfiStringList *
+dfi_string_list_new (void)
+{
+  DfiStringList *string_list;
+
+  string_list = g_slice_new0 (DfiStringList);
+  string_list->table = g_hash_table_new (g_str_hash, g_str_equal);
+
+  return string_list;
+}
+
+void
+dfi_string_list_free (DfiStringList *string_list)
+{
+  /* This will call g_free() on each key */
+  g_hash_table_foreach (string_list->table, (GHFunc) g_free, NULL);
+  g_free (string_list->strings);
+
+  g_slice_free (DfiStringList, string_list);
+}
+
+void
+dfi_string_list_ensure (DfiStringList *string_list,
+                        const gchar   *string)
+{
+  /* Ensure we're not already converted */
+  g_assert (string_list->strings == NULL);
+
+  if (!g_hash_table_contains (string_list->table, string))
+    g_hash_table_add (string_list->table, g_strdup (string));
+}
+
+void
+dfi_string_list_convert (DfiStringList *string_list)
+{
+  GHashTableIter iter;
+  gpointer key;
+  guint n, i;
+
+  /* Ensure we're not already converted */
+  g_assert (string_list->strings == NULL);
+
+  n = g_hash_table_size (string_list->table);
+  string_list->strings = g_new (gchar *, n + 1);
+  i = 0;
+
+  g_hash_table_iter_init (&iter, string_list->table);
+  while (g_hash_table_iter_next (&iter, &key, NULL))
+    string_list->strings[i++] = key;
+  g_assert_cmpint (i, ==, n);
+  string_list->strings[n] = NULL;
+
+  qsort (string_list->strings, n, sizeof (char *), (GCompareFunc) strcmp);
+
+  /* Store the id of each string back into the table for fast lookup.
+   *
+   * Note: no free func on the hash table, so we can just reuse the same
+   * string as the key without worrying that it will be freed.
+   */
+  for (i = 0; i < n; i++)
+    g_hash_table_insert (string_list->table, (gchar *) string_list->strings[i], GUINT_TO_POINTER (i));
+}
+
+void
+dfi_string_list_populate_strings (DfiStringList *string_list,
+                                  GHashTable    *string_table)
+{
+  GHashTableIter iter;
+  gpointer string;
+
+  /* Ensure that we've been converted */
+  g_assert (string_list->strings);
+
+  g_hash_table_iter_init (&iter, string_list->table);
+  while (g_hash_table_iter_next (&iter, &string, NULL))
+    dfi_string_table_add_string (string_table, string);
+}
+
+guint
+dfi_string_list_get_id (DfiStringList *string_list,
+                        const gchar   *string)
+{
+  gpointer value;
+
+  /* Ensure that we've been converted */
+  g_assert (string_list->strings);
+
+  value = g_hash_table_lookup (string_list->table, string);
+
+  return GPOINTER_TO_UINT (value);
+}
+
+const gchar * const *
+dfi_string_list_get_strings (DfiStringList *string_list,
+                             guint         *n_strings)
+{
+  /* Ensure that we've been converted */
+  g_assert (string_list->strings);
+
+  if (n_strings)
+    *n_strings = g_hash_table_size (string_list->table);
+
+  return (const gchar **) string_list->strings;
+}
diff --git a/src/dfi-string-list.h b/src/dfi-string-list.h
new file mode 100644
index 0000000..ca7900b
--- /dev/null
+++ b/src/dfi-string-list.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_string_list_h__
+#define __dfi_string_list_h__
+
+#include "dfi-string-table.h"
+
+typedef struct _DfiStringList                               DfiStringList;
+
+DfiStringList *         dfi_string_list_new                             (void);
+
+void                    dfi_string_list_free                            (DfiStringList  *string_list);
+
+void                    dfi_string_list_ensure                          (DfiStringList  *string_list,
+                                                                         const gchar    *string);
+
+void                    dfi_string_list_convert                         (DfiStringList  *string_list);
+
+void                    dfi_string_list_populate_strings                (DfiStringList  *string_list,
+                                                                         DfiStringTable *string_table);
+
+const gchar * const *   dfi_string_list_get_strings                     (DfiStringList  *string_list,
+                                                                         guint          *n_strings);
+
+guint                   dfi_string_list_get_id                          (DfiStringList  *string_list,
+                                                                         const gchar    *string);
+
+#endif /* __dfi_string_list_h__ */
diff --git a/src/dfi-string-table.c b/src/dfi-string-table.c
new file mode 100644
index 0000000..9d97d37
--- /dev/null
+++ b/src/dfi-string-table.c
@@ -0,0 +1,198 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-string-table.h"
+
+#include <string.h>
+
+static guint
+str_hash0 (gconstpointer a)
+{
+  return a ? g_str_hash (a) : 0;
+}
+
+static gboolean
+str_equal0 (gconstpointer a,
+            gconstpointer b)
+{
+  return g_strcmp0 (a, b) == 0;
+}
+
+GHashTable *
+dfi_string_tables_create (void)
+{
+  return g_hash_table_new_full (str_hash0, str_equal0, g_free, (GDestroyNotify) g_hash_table_unref);
+}
+
+static gchar *
+get_locale_group (const gchar *for_locale)
+{
+  /* This function decides how to group the string tables of locales in
+   * order to improve sharing of strings between similar locales while
+   * preventing too much overlap between unrelated ones (thus improving
+   * locality of access).
+   *
+   * This function doesn't need to be "correct" in any sense (beyond
+   * being deterministic); this grouping is merely an optimisation.
+   */
+
+  /* Untranslated strings... */
+  g_assert (for_locale);
+  if (!for_locale)
+    return NULL;
+
+  /* English translations will share 99% of strings with the C locale,
+   * so avoid duplicating them.  Note: careful to avoid en@shaw.
+   */
+  if (g_str_equal (for_locale, "en") || g_str_has_prefix (for_locale, "en_"))
+    return g_strdup ("");
+
+  /* Valencian is just a dialect of Catalan, so make sure they get
+   * grouped together.
+   */
+  if (g_str_equal (for_locale, "ca@valencia"))
+    return g_strdup ("ca");
+
+  /* Other uses of '@' indicate different character sets.  Not much will
+   * be gained by grouping them, so keep them separate.
+   */
+  if (for_locale[0] && for_locale[1] && for_locale[2] == '@')
+    return g_strdup (for_locale);
+
+  /* Otherwise, we have cases like pt_BR and fr_CH.  Group these by
+   * language code for hope that they will be similar.
+   */
+  if (for_locale[0] && for_locale[1] && for_locale[2] == '_')
+    return g_strndup (for_locale, 2);
+
+  /* Otherwise, it's something else.  Return it, I guess... */
+  return g_strdup (for_locale);
+}
+
+GHashTable *
+dfi_string_tables_get_table (GHashTable  *string_tables,
+                             const gchar *locale)
+{
+  GHashTable *string_table;
+
+  string_table = g_hash_table_lookup (string_tables, locale);
+
+  if (!string_table)
+    {
+      gchar *locale_group = get_locale_group (locale);
+
+      string_table = g_hash_table_lookup (string_tables, locale_group);
+
+      if (!string_table)
+        {
+          string_table = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
+          g_hash_table_insert (string_tables, g_strdup (locale_group), string_table);
+        }
+
+      g_free (locale_group);
+
+      g_hash_table_insert (string_tables, g_strdup (locale), g_hash_table_ref (string_table));
+    }
+
+  return string_table;
+}
+
+void
+dfi_string_tables_add_string (GHashTable  *string_tables,
+                              const gchar *locale,
+                              const gchar *string)
+{
+  GHashTable *string_table;
+
+  string_table = dfi_string_tables_get_table (string_tables, locale);
+
+  dfi_string_table_add_string (string_table, string);
+}
+
+void
+dfi_string_table_add_string (GHashTable  *string_table,
+                             const gchar *string)
+{
+  g_hash_table_insert (string_table, g_strdup (string), NULL);
+}
+
+guint
+dfi_string_tables_get_offset (GHashTable  *string_tables,
+                              const gchar *locale,
+                              const gchar *string)
+{
+  GHashTable *string_table;
+
+  string_table = dfi_string_tables_get_table (string_tables, locale);
+
+  return dfi_string_table_get_offset (string_table, string);
+}
+
+guint
+dfi_string_table_get_offset (GHashTable  *string_table,
+                             const gchar *string)
+{
+  gpointer offset;
+
+  offset = g_hash_table_lookup (string_table, string);
+  g_assert (offset);
+
+  return GPOINTER_TO_UINT (offset);
+}
+
+gboolean
+dfi_string_table_is_written (GHashTable *string_table)
+{
+  GHashTableIter iter;
+  gpointer val;
+
+  g_hash_table_iter_init (&iter, string_table);
+  if (!g_hash_table_iter_next (&iter, NULL, &val))
+    g_error ("mysterious empty string table...");
+
+  return val != NULL;
+}
+
+void
+dfi_string_table_write (GHashTable *string_table,
+                        GHashTable *shared_table,
+                        GString    *file)
+{
+  GHashTableIter iter;
+  gpointer key, val;
+
+  g_hash_table_iter_init (&iter, string_table);
+  while (g_hash_table_iter_next (&iter, &key, &val))
+    {
+      g_assert (val == NULL);
+
+      if (shared_table)
+        val = g_hash_table_lookup (shared_table, key);
+
+      if (val == NULL)
+        {
+          g_hash_table_iter_replace (&iter, GUINT_TO_POINTER (file->len));
+          g_string_append_len (file, key, strlen (key) + 1);
+        }
+      else
+        g_hash_table_iter_replace (&iter, val);
+    }
+}
diff --git a/src/dfi-string-table.h b/src/dfi-string-table.h
new file mode 100644
index 0000000..0cc555e
--- /dev/null
+++ b/src/dfi-string-table.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_string_table_h__
+#define __dfi_string_table_h__
+
+#include <glib.h>
+
+typedef GHashTable DfiStringTables;
+typedef GHashTable DfiStringTable;
+
+DfiStringTables *       dfi_string_tables_create                        (void);
+
+DfiStringTable *        dfi_string_tables_get_table                     (DfiStringTables *string_tables,
+                                                                         const gchar     *locale);
+
+void                    dfi_string_tables_add_string                    (DfiStringTables *string_tables,
+                                                                         const gchar     *locale,
+                                                                         const gchar     *string);
+
+void                    dfi_string_table_add_string                     (DfiStringTable  *string_table,
+                                                                         const gchar     *string);
+
+guint                   dfi_string_tables_get_offset                    (DfiStringTable  *string_table,
+                                                                         const gchar     *locale,
+                                                                         const gchar     *string);
+
+guint                   dfi_string_table_get_offset                     (DfiStringTable  *string_table,
+                                                                         const gchar     *string);
+
+gboolean                dfi_string_table_is_written                     (DfiStringTable  *string_table);
+
+void                    dfi_string_table_write                          (DfiStringTable  *string_table,
+                                                                         DfiStringTable  *shared_table,
+                                                                         GString         *file);
+
+#endif /* __dfi_string_table_h__ */
diff --git a/src/dfi-text-index.c b/src/dfi-text-index.c
new file mode 100644
index 0000000..19811ff
--- /dev/null
+++ b/src/dfi-text-index.c
@@ -0,0 +1,253 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#include "dfi-text-index.h"
+
+#include "dfi-string-table.h"
+#include "dfi-id-list.h"
+
+#include <string.h>
+
+typedef struct
+{
+  /* Our GSequence compare function treats DesktopFileIndexTextIndexItem
+   * as a subclass of 'string' for purposes of comparison.
+   *
+   * The string, therefore, must come first.
+   */
+  gchar *token;
+
+  GArray *id_list;
+} DesktopFileIndexTextIndexItem;
+
+static gint
+dfi_text_index_string_compare (gconstpointer a,
+                               gconstpointer b,
+                               gpointer      user_data)
+{
+  /* As mentioned above: the pointers can equivalently be pointers to a
+   * 'DesktopFileIndexTextIndexItem' or to a 'gchar *'.
+   */
+  const gchar * const *str_a = a;
+  const gchar * const *str_b = b;
+
+  return strcmp (*str_a, *str_b);
+}
+
+static DesktopFileIndexTextIndexItem *
+dfi_text_index_item_new (const gchar *token)
+{
+  DesktopFileIndexTextIndexItem *item;
+
+  item = g_slice_new (DesktopFileIndexTextIndexItem);
+  item->token = g_strdup (token);
+  item->id_list = dfi_id_list_new ();
+
+  return item;
+}
+
+static void
+dfi_text_index_item_free (gpointer data)
+{
+  DesktopFileIndexTextIndexItem *item = data;
+
+  dfi_id_list_free (item->id_list);
+  g_free (item->token);
+
+  g_slice_free (DesktopFileIndexTextIndexItem, item);
+}
+
+GSequence *
+dfi_text_index_new (void)
+{
+  return g_sequence_new (dfi_text_index_item_free);
+}
+
+void
+dfi_text_index_free (gpointer data)
+{
+  g_sequence_free (data);
+}
+
+void
+dfi_text_index_add_ids (GSequence     *text_index,
+                        const gchar   *token,
+                        const guint16 *ids,
+                        gint           n_ids)
+{
+  DesktopFileIndexTextIndexItem *item;
+  GSequenceIter *iter;
+
+  iter = g_sequence_lookup (text_index, &token, dfi_text_index_string_compare, NULL);
+  if (iter)
+    {
+      item = g_sequence_get (iter);
+    }
+  else
+    {
+      item = dfi_text_index_item_new (token);
+      g_sequence_insert_sorted (text_index, item, dfi_text_index_string_compare, NULL);
+    }
+
+  dfi_id_list_add_ids (item->id_list, ids, n_ids);
+}
+
+static void
+dfi_text_index_add_folded (GPtrArray   *array,
+                           const gchar *start,
+                           const gchar *end)
+{
+  gchar *normal;
+
+  normal = g_utf8_normalize (start, end - start, G_NORMALIZE_ALL_COMPOSE);
+
+  /* TODO: Invent time machine.  Converse with Mustafa Ataturk... */
+  if (strstr (normal, "ı") || strstr (normal, "İ"))
+    {
+      gchar *s = normal;
+      GString *tmp;
+
+      tmp = g_string_new (NULL);
+
+      while (*s)
+        {
+          gchar *i, *I, *e;
+
+          i = strstr (s, "ı");
+          I = strstr (s, "İ");
+
+          if (!i && !I)
+            break;
+          else if (i && !I)
+            e = i;
+          else if (I && !i)
+            e = I;
+          else if (i < I)
+            e = i;
+          else
+            e = I;
+
+          g_string_append_len (tmp, s, e - s);
+          g_string_append_c (tmp, 'i');
+          s = g_utf8_next_char (e);
+        }
+
+      g_string_append (tmp, s);
+      g_free (normal);
+      normal = g_string_free (tmp, FALSE);
+    }
+
+  g_ptr_array_add (array, g_utf8_casefold (normal, -1));
+  g_free (normal);
+}
+
+static gchar **
+dfi_text_index_split_words (const gchar *value)
+{
+  const gchar *start = NULL;
+  GPtrArray *result;
+  const gchar *s;
+
+  result = g_ptr_array_new ();
+
+  for (s = value; *s; s = g_utf8_next_char (s))
+    {
+      gunichar c = g_utf8_get_char (s);
+
+      if (start == NULL)
+        {
+          if (g_unichar_isalnum (c))
+            start = s;
+        }
+      else
+        {
+          if (!g_unichar_isalnum (c))
+            {
+              dfi_text_index_add_folded (result, start, s);
+              start = NULL;
+            }
+        }
+    }
+
+  if (start)
+    dfi_text_index_add_folded (result, start, s);
+
+  g_ptr_array_add (result, NULL);
+
+  return (gchar **) g_ptr_array_free (result, FALSE);
+}
+
+void
+dfi_text_index_add_ids_tokenised (GSequence     *text_index,
+                                  const gchar   *string_to_tokenise,
+                                  const guint16 *ids,
+                                  gint           n_ids)
+{
+  gchar **tokens;
+  gint i;
+
+  tokens = dfi_text_index_split_words (string_to_tokenise);
+  for (i = 0; tokens[i]; i++)
+    {
+      gint j;
+
+      for (j = 0; j < i; j++)
+        if (g_str_equal (tokens[i], tokens[j]))
+          break;
+
+      if (j < i)
+        continue;
+
+      dfi_text_index_add_ids (text_index, tokens[i], ids, n_ids);
+    }
+
+}
+
+void
+dfi_text_index_get_item (GSequenceIter  *iter,
+                         const gchar   **token,
+                         GArray        **id_list)
+{
+  DesktopFileIndexTextIndexItem *item;
+
+  item = g_sequence_get (iter);
+
+  *token = item->token;
+  *id_list = item->id_list;
+}
+
+void
+dfi_text_index_populate_strings (GSequence      *text_index,
+                                 DfiStringTable *string_table)
+{
+  GSequenceIter *iter;
+
+  iter = g_sequence_get_begin_iter (text_index);
+
+  while (!g_sequence_iter_is_end (iter))
+    {
+      DesktopFileIndexTextIndexItem *item = g_sequence_get (iter);
+
+      dfi_string_table_add_string (string_table, item->token);
+
+      iter = g_sequence_iter_next (iter);
+    }
+}
diff --git a/src/dfi-text-index.h b/src/dfi-text-index.h
new file mode 100644
index 0000000..5e53dd8
--- /dev/null
+++ b/src/dfi-text-index.h
@@ -0,0 +1,50 @@
+/*
+ * Copyright © 2013 Canonical Limited
+ *
+ * update-desktop-database is free software; you can redistribute it
+ * and/or modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * update-desktop-database is distributed in the hope that it will be
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with update-desktop-database; see the file COPYING.  If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite
+ * 330, Boston, MA 02111-1307, USA.
+ *
+ * Author: Ryan Lortie <desrt@desrt.ca>
+ */
+
+#ifndef __dfi_text_index_h__
+#define __dfi_text_index_h__
+
+#include "dfi-string-table.h"
+
+typedef GSequence DfiTextIndex;
+
+DfiTextIndex *          dfi_text_index_new                              (void);
+
+void                    dfi_text_index_free                             (gpointer         text_index);
+
+void                    dfi_text_index_add_ids                          (DfiTextIndex    *text_index,
+                                                                         const gchar     *token,
+                                                                         const guint16   *ids,
+                                                                         gint             n_ids);
+
+void                    dfi_text_index_add_ids_tokenised                (DfiTextIndex    *text_index,
+                                                                         const gchar     *string_to_tokenise,
+                                                                         const guint16   *ids,
+                                                                         gint             n_ids);
+
+void                    dfi_text_index_get_item                         (GSequenceIter   *iter,
+                                                                         const gchar    **token,
+                                                                         GArray         **id_list);
+
+void                    dfi_text_index_populate_strings                 (DfiTextIndex    *text_index,
+                                                                         DfiStringTable  *string_table);
+
+#endif /* __dfi_text_index_h__ */
diff --git a/src/update-desktop-database.c b/src/update-desktop-database.c
index 260d79a..106aa10 100644
--- a/src/update-desktop-database.c
+++ b/src/update-desktop-database.c
@@ -28,9 +28,14 @@
 #include <glib.h>
 #include <glib/gi18n.h>
 
+#include <sys/types.h>
+#include <sys/time.h>
+
 #include "mime-cache.h"
+#include "dfi-builder.h"
 
 #define CACHE_FILENAME "mimeinfo.cache"
+#define INDEX_FILENAME "desktop-file-index"
 
 static gboolean verbose = FALSE, quiet = FALSE;
 
@@ -53,21 +58,50 @@ static gboolean
 update_database (const char  *desktop_dir,
                  GError     **error)
 {
-  gboolean success;
-  char *cache_file;
+  gboolean success = FALSE;
+  gchar *cache_file;
+  gchar *index_file;
   GBytes *cache;
+  GBytes *dfi;
+
+  cache_file = g_build_filename (desktop_dir, CACHE_FILENAME, NULL);
+  index_file = g_build_filename (desktop_dir, INDEX_FILENAME, NULL);
+  dfi = NULL;
 
   cache = mime_cache_build (desktop_dir, error);
   if (!cache)
-    return FALSE;
-
-  cache_file = g_build_filename (desktop_dir, CACHE_FILENAME, NULL);
-  success = g_file_set_contents (cache_file,
-                                 g_bytes_get_data (cache, NULL),
-                                 g_bytes_get_size (cache),
-                                 error);
+    goto out;
+
+  dfi = dfi_builder_build (desktop_dir, error);
+  if (!dfi)
+    goto out;
+
+  if (!g_file_set_contents (cache_file,
+                            g_bytes_get_data (cache, NULL),
+                            g_bytes_get_size (cache),
+                            error))
+    goto out;
+
+  if (!g_file_set_contents (index_file,
+                            g_bytes_get_data (dfi, NULL),
+                            g_bytes_get_size (dfi),
+                            error))
+    goto out;
+
+  /* Touch the timestamp after we have written both files in order to
+   * ensure that each file has a timestamp newer than the directory
+   * itself.
+   */
+  utimes (cache_file, NULL);
+  utimes (index_file, NULL);
+
+  success = TRUE;
+
+out:
   g_bytes_unref (cache);
+  g_bytes_unref (dfi);
   g_free (cache_file);
+  g_free (index_file);
 
   return success;
 }