[glib/wip/gdesktopappinfo] desktopappinfo: Support search on unindexed directories
- From: Ryan Lortie <desrt src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [glib/wip/gdesktopappinfo] desktopappinfo: Support search on unindexed directories
- Date: Thu, 26 Sep 2013 03:40:48 +0000 (UTC)
commit e9cdac332e314a9380dff58b9b782d0687081d13
Author: Ryan Lortie <desrt desrt ca>
Date: Wed Sep 25 23:39:19 2013 -0400
desktopappinfo: Support search on unindexed directories
A hashtable is _so_ wrong here, but it's good enough for now...
gio/gdesktopappinfo.c | 517 ++++++++++++++++++++++++++++++++++---------------
1 files changed, 362 insertions(+), 155 deletions(-)
---
diff --git a/gio/gdesktopappinfo.c b/gio/gdesktopappinfo.c
index 049f08d..4eb490c 100644
--- a/gio/gdesktopappinfo.c
+++ b/gio/gdesktopappinfo.c
@@ -300,6 +300,7 @@ typedef struct
guint16 key_id_map_length;
guint16 *locale_ids;
guint16 desktop_entry_id;
+ GHashTable *memory_index;
} DesktopFileDir;
static DesktopFileDir *desktop_file_dirs;
@@ -395,6 +396,168 @@ add_to_table_if_appropriate (GHashTable *apps,
g_hash_table_insert (apps, g_strdup (info->filename), info);
}
+
+enum
+{
+ DESKTOP_KEY_nil,
+
+ /* NB: must keep this list sorted */
+ DESKTOP_KEY_Actions,
+ DESKTOP_KEY_Categories,
+ DESKTOP_KEY_Comment,
+ DESKTOP_KEY_DBusActivatable,
+ DESKTOP_KEY_Exec,
+ DESKTOP_KEY_GenericName,
+ DESKTOP_KEY_Hidden,
+ DESKTOP_KEY_Icon,
+ DESKTOP_KEY_Keywords,
+ DESKTOP_KEY_MimeType,
+ DESKTOP_KEY_Name,
+ DESKTOP_KEY_NoDisplay,
+ DESKTOP_KEY_NotShowIn,
+ DESKTOP_KEY_OnlyShowIn,
+ DESKTOP_KEY_Path,
+ DESKTOP_KEY_StartupNotify,
+ DESKTOP_KEY_StartupWMClass,
+ DESKTOP_KEY_Terminal,
+ DESKTOP_KEY_TryExec,
+ DESKTOP_KEY_Type,
+ DESKTOP_KEY_Version,
+ DESKTOP_KEY_X_GNOME_FullName,
+
+ N_DESKTOP_KEYS
+};
+
+const gchar *desktop_key_names[N_DESKTOP_KEYS];
+
+const gchar desktop_key_match_category[N_DESKTOP_KEYS] = {
+ /* NB: no harm in repeating numbers in case of a tie */
+ [DESKTOP_KEY_Name] = 1,
+ [DESKTOP_KEY_GenericName] = 2,
+ [DESKTOP_KEY_Keywords] = 3,
+ [DESKTOP_KEY_X_GNOME_FullName] = 4,
+ [DESKTOP_KEY_Comment] = 5
+};
+
+#define DESKTOP_KEY_NUM_MATCH_CATEGORIES 5
+
+static void
+desktop_key_init (void)
+{
+ if G_LIKELY (desktop_key_names[1])
+ return;
+
+ desktop_key_names[DESKTOP_KEY_Actions] = g_intern_static_string ("Actions");
+ desktop_key_names[DESKTOP_KEY_Categories] = g_intern_static_string ("Categories");
+ desktop_key_names[DESKTOP_KEY_Comment] = g_intern_static_string ("Comment");
+ desktop_key_names[DESKTOP_KEY_DBusActivatable] = g_intern_static_string ("DBusActivatable");
+ desktop_key_names[DESKTOP_KEY_Exec] = g_intern_static_string ("Exec");
+ desktop_key_names[DESKTOP_KEY_GenericName] = g_intern_static_string ("GenericName");
+ desktop_key_names[DESKTOP_KEY_Hidden] = g_intern_static_string ("Hidden");
+ desktop_key_names[DESKTOP_KEY_Icon] = g_intern_static_string ("Icon");
+ desktop_key_names[DESKTOP_KEY_Keywords] = g_intern_static_string ("Keywords");
+ desktop_key_names[DESKTOP_KEY_MimeType] = g_intern_static_string ("MimeType");
+ desktop_key_names[DESKTOP_KEY_Name] = g_intern_static_string ("Name");
+ desktop_key_names[DESKTOP_KEY_NoDisplay] = g_intern_static_string ("NoDisplay");
+ desktop_key_names[DESKTOP_KEY_NotShowIn] = g_intern_static_string ("NotShowIn");
+ desktop_key_names[DESKTOP_KEY_OnlyShowIn] = g_intern_static_string ("OnlyShowIn");
+ desktop_key_names[DESKTOP_KEY_Path] = g_intern_static_string ("Path");
+ desktop_key_names[DESKTOP_KEY_StartupNotify] = g_intern_static_string ("StartupNotify");
+ desktop_key_names[DESKTOP_KEY_StartupWMClass] = g_intern_static_string ("StartupWMClass");
+ desktop_key_names[DESKTOP_KEY_Terminal] = g_intern_static_string ("Terminal");
+ desktop_key_names[DESKTOP_KEY_TryExec] = g_intern_static_string ("TryExec");
+ desktop_key_names[DESKTOP_KEY_Type] = g_intern_static_string ("Type");
+ desktop_key_names[DESKTOP_KEY_Version] = g_intern_static_string ("Version");
+ desktop_key_names[DESKTOP_KEY_X_GNOME_FullName] = g_intern_static_string ("X-GNOME-FullName");
+}
+
+static void
+insert_into_list (GSList **categories,
+ const gchar *item,
+ gint into_bucket,
+ gint max_hits)
+{
+ gint n_hits = 0;
+ gint i;
+
+ for (i = 0; i <= into_bucket; i++)
+ {
+ GSList *node;
+
+ /* If we have enough hits from previous categories, stop.
+ *
+ * Note. This check will not be applied after counting up the
+ * hits in categories[into_bucket] and that's intentional: we
+ * don't want to toss out our new item if it has the same score as
+ * items we're already returning.
+ *
+ * That might mean that we get more than max_hits items, but
+ * that's the desired behaviour.
+ */
+ if (max_hits >= 0 && n_hits >= max_hits)
+ return;
+
+ /* We want to do the dup-checking in all cases, though */
+ for (node = categories[i]; node; node = node->next)
+ {
+ /* Pointer comparison is good enough because we're using the
+ * name from the desktop index (where it is unique) and
+ * because we'll never see the same desktop file name across
+ * multiple indexes due to our use of masking.
+ */
+ if (node->data == item)
+ return;
+
+ n_hits++;
+ }
+ }
+
+ /* No duplicate found at this level or any before, and not too many
+ * items in earlier buckets, so add our item.
+ */
+ categories[into_bucket] = g_slist_prepend (categories[into_bucket], (gchar *) item);
+ n_hits++;
+
+ /* We may need to remove ourselves from a later category if we already
+ * had a weaker hit for this item.
+ *
+ * We may also need to blow away an entire category if n_hits is big
+ * enough.
+ */
+ for (i = into_bucket + 1; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
+ {
+ if (!categories[i])
+ continue;
+
+ if (max_hits >= 0 && n_hits >= max_hits)
+ {
+ g_slist_free (categories[i]);
+ categories[i] = NULL;
+ }
+ else
+ {
+ GSList **ptr;
+
+ for (ptr = &categories[i]; *ptr; ptr = &(*ptr)->next)
+ if ((*ptr)->data == item)
+ {
+ /* Found us! */
+ *ptr = g_slist_delete_link (*ptr, *ptr);
+ n_hits--;
+
+ /* Since we effectively didn't add any items this time
+ * around, we know we will not need to blow away later
+ * categories. We also know that we will not appear in
+ * a later category, since we appeared here.
+ *
+ * So, we're done.
+ */
+ return;
+ }
+ }
+ }
+}
+
/* Support for unindexed DesktopFileDirs {{{2 */
static void
get_apps_from_dir (GHashTable **apps,
@@ -482,92 +645,217 @@ desktop_file_dir_unindexed_get_all (DesktopFileDir *dir,
}
}
+typedef struct _MemoryIndexEntry MemoryIndexEntry;
+typedef GHashTable MemoryIndex;
+
+struct _MemoryIndexEntry
+{
+ const gchar *app_name; /* pointer to the hashtable key */
+ gint match_category;
+ MemoryIndexEntry *next;
+};
+
static void
-desktop_file_dir_unindexed_search (DesktopFileDir *dir,
- GSList **categories,
- const gchar *term,
- gint max_hits)
+memory_index_entry_free (gpointer data)
{
- /* TODO */
-}
+ MemoryIndexEntry *mie = data;
-/* Support for indexed DesktopFileDirs {{{2 */
+ while (mie)
+ {
+ MemoryIndexEntry *next = mie->next;
-enum
+ g_slice_free (MemoryIndexEntry, mie);
+ mie = next;
+ }
+}
+
+static void
+memory_index_add_token (MemoryIndex *mi,
+ const gchar *token_start,
+ const gchar *token_end,
+ gint match_category,
+ const gchar *app_name)
{
- DESKTOP_KEY_nil,
+ MemoryIndexEntry *mie, *first;
+ gchar *normal;
+ gchar *folded;
- /* NB: must keep this list sorted */
- DESKTOP_KEY_Actions,
- DESKTOP_KEY_Categories,
- DESKTOP_KEY_Comment,
- DESKTOP_KEY_DBusActivatable,
- DESKTOP_KEY_Exec,
- DESKTOP_KEY_GenericName,
- DESKTOP_KEY_Hidden,
- DESKTOP_KEY_Icon,
- DESKTOP_KEY_Keywords,
- DESKTOP_KEY_MimeType,
- DESKTOP_KEY_Name,
- DESKTOP_KEY_NoDisplay,
- DESKTOP_KEY_NotShowIn,
- DESKTOP_KEY_OnlyShowIn,
- DESKTOP_KEY_Path,
- DESKTOP_KEY_StartupNotify,
- DESKTOP_KEY_StartupWMClass,
- DESKTOP_KEY_Terminal,
- DESKTOP_KEY_TryExec,
- DESKTOP_KEY_Type,
- DESKTOP_KEY_Version,
- DESKTOP_KEY_X_GNOME_FullName,
+ normal = g_utf8_normalize (token_start, token_end - token_start, G_NORMALIZE_ALL_COMPOSE);
- N_DESKTOP_KEYS
-};
+ /* TODO: Invent time machine. Converse with Mustafa Ataturk... */
+ if (strstr (normal, "ı") || strstr (normal, "İ"))
+ {
+ gchar *s = normal;
+ GString *tmp;
-const gchar *desktop_key_names[N_DESKTOP_KEYS];
+ tmp = g_string_new (NULL);
-const gchar desktop_key_match_category[N_DESKTOP_KEYS] = {
- /* NB: no harm in repeating numbers in case of a tie */
- [DESKTOP_KEY_Name] = 1,
- [DESKTOP_KEY_GenericName] = 2,
- [DESKTOP_KEY_Keywords] = 3,
- [DESKTOP_KEY_X_GNOME_FullName] = 4,
- [DESKTOP_KEY_Comment] = 5
-};
+ while (*s)
+ {
+ gchar *i, *I, *e;
-#define DESKTOP_KEY_NUM_MATCH_CATEGORIES 5
+ 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);
+ }
+
+ folded = g_utf8_casefold (normal, -1);
+
+ mie = g_slice_new (MemoryIndexEntry);
+ mie->app_name = app_name;
+ mie->match_category = match_category;
+
+ first = g_hash_table_lookup (mi, folded);
+
+ if (first)
+ {
+ mie->next = first->next;
+ first->next = mie;
+ g_free (folded); /* not using this... */
+ }
+ else
+ {
+ mie->next = NULL;
+ g_hash_table_insert (mi, folded, mie);
+ }
+
+ g_free (normal);
+}
static void
-desktop_key_init (void)
+memory_index_add_string (MemoryIndex *mi,
+ const gchar *string,
+ gint match_category,
+ const gchar *app_name)
{
- if G_LIKELY (desktop_key_names[1])
+ const gchar *start = NULL;
+ const gchar *s;
+
+ for (s = string; *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))
+ {
+ memory_index_add_token (mi, start, s, match_category, app_name);
+ start = NULL;
+ }
+ }
+ }
+
+ if (start)
+ memory_index_add_token (mi, start, s, match_category, app_name);
+}
+
+static MemoryIndex *
+memory_index_new (void)
+{
+ return g_hash_table_new_full (g_str_hash, g_str_equal, g_free, memory_index_entry_free);
+}
+
+static void
+desktop_file_dir_unindexed_setup_search (DesktopFileDir *dir)
+{
+ GHashTableIter iter;
+ gpointer app, path;
+
+ desktop_key_init ();
+
+ dir->memory_index = memory_index_new ();
+
+ /* Nothing to search? */
+ if (dir->app_names == NULL)
return;
- desktop_key_names[DESKTOP_KEY_Actions] = g_intern_static_string ("Actions");
- desktop_key_names[DESKTOP_KEY_Categories] = g_intern_static_string ("Categories");
- desktop_key_names[DESKTOP_KEY_Comment] = g_intern_static_string ("Comment");
- desktop_key_names[DESKTOP_KEY_DBusActivatable] = g_intern_static_string ("DBusActivatable");
- desktop_key_names[DESKTOP_KEY_Exec] = g_intern_static_string ("Exec");
- desktop_key_names[DESKTOP_KEY_GenericName] = g_intern_static_string ("GenericName");
- desktop_key_names[DESKTOP_KEY_Hidden] = g_intern_static_string ("Hidden");
- desktop_key_names[DESKTOP_KEY_Icon] = g_intern_static_string ("Icon");
- desktop_key_names[DESKTOP_KEY_Keywords] = g_intern_static_string ("Keywords");
- desktop_key_names[DESKTOP_KEY_MimeType] = g_intern_static_string ("MimeType");
- desktop_key_names[DESKTOP_KEY_Name] = g_intern_static_string ("Name");
- desktop_key_names[DESKTOP_KEY_NoDisplay] = g_intern_static_string ("NoDisplay");
- desktop_key_names[DESKTOP_KEY_NotShowIn] = g_intern_static_string ("NotShowIn");
- desktop_key_names[DESKTOP_KEY_OnlyShowIn] = g_intern_static_string ("OnlyShowIn");
- desktop_key_names[DESKTOP_KEY_Path] = g_intern_static_string ("Path");
- desktop_key_names[DESKTOP_KEY_StartupNotify] = g_intern_static_string ("StartupNotify");
- desktop_key_names[DESKTOP_KEY_StartupWMClass] = g_intern_static_string ("StartupWMClass");
- desktop_key_names[DESKTOP_KEY_Terminal] = g_intern_static_string ("Terminal");
- desktop_key_names[DESKTOP_KEY_TryExec] = g_intern_static_string ("TryExec");
- desktop_key_names[DESKTOP_KEY_Type] = g_intern_static_string ("Type");
- desktop_key_names[DESKTOP_KEY_Version] = g_intern_static_string ("Version");
- desktop_key_names[DESKTOP_KEY_X_GNOME_FullName] = g_intern_static_string ("X-GNOME-FullName");
+ g_hash_table_iter_init (&iter, dir->app_names);
+ while (g_hash_table_iter_next (&iter, &app, &path))
+ {
+ GKeyFile *key_file;
+
+ key_file = g_key_file_new ();
+
+ if (g_key_file_load_from_file (key_file, path, G_KEY_FILE_NONE, NULL))
+ {
+ /* Index the interesting keys... */
+ gint i;
+
+ for (i = 0; i < G_N_ELEMENTS (desktop_key_match_category); i++)
+ {
+ gchar *value;
+
+ if (!desktop_key_match_category[i])
+ continue;
+
+ value = g_key_file_get_locale_string (key_file, "Desktop Entry", desktop_key_names[i], NULL,
NULL);
+
+ if (value)
+ memory_index_add_string (dir->memory_index, value, desktop_key_match_category[i], app);
+
+ g_free (value);
+ }
+ }
+
+ g_key_file_free (key_file);
+ }
}
static void
+desktop_file_dir_unindexed_search (DesktopFileDir *dir,
+ GSList **categories,
+ const gchar *term,
+ gint max_hits)
+{
+ GHashTableIter iter;
+ gpointer key, value;
+
+ if (!dir->memory_index)
+ desktop_file_dir_unindexed_setup_search (dir);
+
+ g_hash_table_iter_init (&iter, dir->memory_index);
+ while (g_hash_table_iter_next (&iter, &key, &value))
+ {
+ MemoryIndexEntry *mie = value;
+
+ if (!g_str_has_prefix (key, term))
+ continue;
+
+ while (mie)
+ {
+ insert_into_list (categories, mie->app_name, mie->match_category - 1, max_hits);
+ mie = mie->next;
+ }
+ }
+}
+
+/* Support for indexed DesktopFileDirs {{{2 */
+
+static void
desktop_file_dir_indexed_init (DesktopFileDir *dir)
{
desktop_key_init ();
@@ -739,93 +1027,6 @@ desktop_file_dir_indexed_get_all (DesktopFileDir *dir,
}
static void
-insert_into_list (GSList **categories,
- const gchar *item,
- gint into_bucket,
- gint max_hits)
-{
- gint n_hits = 0;
- gint i;
-
- for (i = 0; i <= into_bucket; i++)
- {
- GSList *node;
-
- /* If we have enough hits from previous categories, stop.
- *
- * Note. This check will not be applied after counting up the
- * hits in categories[into_bucket] and that's intentional: we
- * don't want to toss out our new item if it has the same score as
- * items we're already returning.
- *
- * That might mean that we get more than max_hits items, but
- * that's the desired behaviour.
- */
- if (max_hits >= 0 && n_hits >= max_hits)
- return;
-
- /* We want to do the dup-checking in all cases, though */
- for (node = categories[i]; node; node = node->next)
- {
- /* Pointer comparison is good enough because we're using the
- * name from the desktop index (where it is unique) and
- * because we'll never see the same desktop file name across
- * multiple indexes due to our use of masking.
- */
- if (node->data == item)
- return;
-
- n_hits++;
- }
- }
-
- /* No duplicate found at this level or any before, and not too many
- * items in earlier buckets, so add our item.
- */
- categories[into_bucket] = g_slist_prepend (categories[into_bucket], (gchar *) item);
- n_hits++;
-
- /* We may need to remove ourselves from a later category if we already
- * had a weaker hit for this item.
- *
- * We may also need to blow away an entire category if n_hits is big
- * enough.
- */
- for (i = into_bucket + 1; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
- {
- if (!categories[i])
- continue;
-
- if (max_hits >= 0 && n_hits >= max_hits)
- {
- g_slist_free (categories[i]);
- categories[i] = NULL;
- }
- else
- {
- GSList **ptr;
-
- for (ptr = &categories[i]; *ptr; ptr = &(*ptr)->next)
- if ((*ptr)->data == item)
- {
- /* Found us! */
- *ptr = g_slist_delete_link (*ptr, *ptr);
- n_hits--;
-
- /* Since we effectively didn't add any items this time
- * around, we know we will not need to blow away later
- * categories. We also know that we will not appear in
- * a later category, since we appeared here.
- *
- * So, we're done.
- */
- return;
- }
- }
- }
-}
-
-static void
desktop_file_dir_indexed_search (DesktopFileDir *dir,
GSList **categories,
const gchar *term,
@@ -976,6 +1177,12 @@ desktop_file_dir_reset (DesktopFileDir *dir)
dir->locale_ids = NULL;
}
+ if (dir->memory_index)
+ {
+ g_hash_table_unref (dir->memory_index);
+ dir->memory_index = NULL;
+ }
+
dir->key_id_map_length = 0;
dir->desktop_entry_id = 0;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
