[gnome-builder] fuzzy: use tombstone records to support removal from fuzzy index

[Christian Hergert <chergert src gnome org>]

commit a649294b3ad290a7c0c79fb3c9192404f041a018
Author: Christian Hergert <chergert redhat com>
Date:   Thu Oct 15 11:08:44 2015 -0700

    fuzzy: use tombstone records to support removal from fuzzy index

 contrib/search/fuzzy.c |   44 ++++++++++++++++++++++++++++++++++++++++++--
 contrib/search/fuzzy.h |    3 +++
 tests/test-fuzzy.c     |   15 ++++++++++++++-
 3 files changed, 59 insertions(+), 3 deletions(-)
---
diff --git a/contrib/search/fuzzy.c b/contrib/search/fuzzy.c
index 302b251..4238155 100644
--- a/contrib/search/fuzzy.c
+++ b/contrib/search/fuzzy.c
@@ -40,6 +40,7 @@ struct _Fuzzy
   GArray         *id_to_text_offset;
   GPtrArray      *id_to_value;
   GHashTable     *char_tables;
+  GHashTable     *removed;
   guint           in_bulk_insert : 1;
   guint           case_sensitive : 1;
 };
@@ -127,6 +128,7 @@ fuzzy_new (gboolean case_sensitive)
   fuzzy->id_to_text_offset = g_array_new (FALSE, FALSE, sizeof (gsize));
   fuzzy->char_tables = g_hash_table_new_full (NULL, NULL, NULL, (GDestroyNotify)g_array_unref);
   fuzzy->case_sensitive = case_sensitive;
+  fuzzy->removed = g_hash_table_new (g_direct_hash, g_direct_equal);
 
   return fuzzy;
 }
@@ -309,6 +311,9 @@ fuzzy_unref (Fuzzy *fuzzy)
       g_hash_table_unref (fuzzy->char_tables);
       fuzzy->char_tables = NULL;
 
+      g_hash_table_unref (fuzzy->removed);
+      fuzzy->removed = NULL;
+
       g_slice_free (Fuzzy, fuzzy);
     }
 }
@@ -471,9 +476,15 @@ fuzzy_match (Fuzzy       *fuzzy,
 
   while (g_hash_table_iter_next (&iter, &key, &value))
     {
-      match.key = fuzzy_get_string (fuzzy, GPOINTER_TO_INT (key));
+      /* Ignore keys that have a tombstone record. */
+      if (g_hash_table_contains (fuzzy->removed, key))
+        continue;
+
+      match.id = GPOINTER_TO_INT (key);
+      match.key = fuzzy_get_string (fuzzy, match.id);
       match.score = 1.0 / (strlen (match.key) + GPOINTER_TO_INT (value));
-      match.value = g_ptr_array_index (fuzzy->id_to_value, GPOINTER_TO_INT (key));
+      match.value = g_ptr_array_index (fuzzy->id_to_value, match.id);
+
       g_array_append_val (matches, match);
     }
 
@@ -514,3 +525,32 @@ fuzzy_contains (Fuzzy       *fuzzy,
 
   return ret;
 }
+
+void
+fuzzy_remove (Fuzzy       *fuzzy,
+              const gchar *key)
+{
+  GArray *ar;
+
+  g_return_if_fail (fuzzy != NULL);
+
+  if (!key || !*key)
+    return;
+
+  ar = fuzzy_match (fuzzy, key, 1);
+
+  if (ar != NULL && ar->len > 0)
+    {
+      guint i;
+
+      for (i = 0; i < ar->len; i++)
+        {
+          FuzzyMatch *match = &g_array_index (ar, FuzzyMatch, i);
+
+          if (g_strcmp0 (match->key, key) == 0)
+            g_hash_table_insert (fuzzy->removed, GINT_TO_POINTER (match->id), NULL);
+        }
+    }
+
+  g_clear_pointer (&ar, g_array_unref);
+}
diff --git a/contrib/search/fuzzy.h b/contrib/search/fuzzy.h
index 8b45691..cc6330c 100644
--- a/contrib/search/fuzzy.h
+++ b/contrib/search/fuzzy.h
@@ -31,6 +31,7 @@ struct _FuzzyMatch
    const gchar *key;
    gpointer     value;
    gfloat       score;
+   guint        id;
 };
 
 Fuzzy     *fuzzy_new                (gboolean        case_sensitive);
@@ -48,6 +49,8 @@ void       fuzzy_insert             (Fuzzy          *fuzzy,
 GArray    *fuzzy_match              (Fuzzy          *fuzzy,
                                      const gchar    *needle,
                                      gsize           max_matches);
+void       fuzzy_remove             (Fuzzy          *fuzzy,
+                                     const gchar    *key);
 Fuzzy     *fuzzy_ref                (Fuzzy          *fuzzy);
 void       fuzzy_unref              (Fuzzy          *fuzzy);
 
diff --git a/tests/test-fuzzy.c b/tests/test-fuzzy.c
index cf96e88..1e21884 100644
--- a/tests/test-fuzzy.c
+++ b/tests/test-fuzzy.c
@@ -63,13 +63,26 @@ main (int argc,
     {
       FuzzyMatch *m = &g_array_index (ar, FuzzyMatch, i);
 
-      g_print ("%0.3lf: %s\n", m->score, m->key);
+      g_print ("%0.3lf: (%d): %s\n", m->score, m->id, m->key);
     }
 
   g_print ("%d matches\n", ar->len);
 
+  g_print ("Testing removal\n");
+
+  for (guint i = 0; i < ar->len; i++)
+    {
+      FuzzyMatch *m = &g_array_index (ar, FuzzyMatch, i);
+      fuzzy_remove (fuzzy, m->key);
+    }
+
   g_array_unref (ar);
 
+  ar = fuzzy_match (fuzzy, param, 0);
+  g_assert (ar == NULL || ar->len == 0);
+  g_clear_pointer (&ar, g_array_unref);
+  g_print ("success.\n");
+
   fuzzy_unref (fuzzy);
 
   return 0;