/dev/tomkiewicz/new-smileys: a032063e50c7: Trie: implement purpl...

Tomasz Wasilczyk twasilczyk at pidgin.im
Sat Mar 29 12:08:03 EDT 2014


Changeset: a032063e50c7140dd6dd9e9db14567eb1cd35eef
Author:	 Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date:	 2014-03-29 17:07 +0100
Branch:	 default
URL: https://hg.pidgin.im/dev/tomkiewicz/new-smileys/rev/a032063e50c7

Description:

Trie: implement purple_trie_remove

diffstat:

 libpurple/trie.c |  48 +++++++++++++++++++++++++++++++++++++++++++-----
 libpurple/trie.h |  16 +++++++++++++++-
 2 files changed, 58 insertions(+), 6 deletions(-)

diffs (126 lines):

diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -53,6 +53,7 @@ typedef struct
 	PurpleMemoryPool *records_str_mempool;
 	PurpleMemoryPool *records_obj_mempool;
 	PurpleTrieRecordList *records;
+	GHashTable *records_map;
 	gsize records_total_size;
 
 	PurpleMemoryPool *states_mempool;
@@ -61,7 +62,7 @@ typedef struct
 
 struct _PurpleTrieRecord
 {
-	const gchar *word;
+	gchar *word;
 	guint word_len;
 	gpointer data;
 };
@@ -563,15 +564,20 @@ purple_trie_multi_replace(const GSList *
  * Records
  ******************************************************************************/
 
-void
+gboolean
 purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data)
 {
 	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
 	PurpleTrieRecord *rec;
 
-	g_return_if_fail(priv != NULL);
-	g_return_if_fail(word != NULL);
-	g_return_if_fail(word[0] != '\0');
+	g_return_val_if_fail(priv != NULL, FALSE);
+	g_return_val_if_fail(word != NULL, FALSE);
+	g_return_val_if_fail(word[0] != '\0', FALSE);
+
+	if (g_hash_table_lookup(priv->records_map, word) != NULL) {
+		purple_debug_warning("trie", "record exists: %s", word);
+		return FALSE;
+	}
 
 	/* Every change in a trie invalidates longest_suffix map.
 	 * These prefixes could be updated instead of cleaning the whole graph.
@@ -588,6 +594,35 @@ purple_trie_add(PurpleTrie *trie, const 
 	priv->records_total_size += rec->word_len;
 	priv->records = purple_record_list_prepend(priv->records_obj_mempool,
 		priv->records, rec);
+	g_hash_table_insert(priv->records_map, priv->records, rec->word);
+
+	return TRUE;
+}
+
+void
+purple_trie_remove(PurpleTrie *trie, const gchar *word)
+{
+	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+	PurpleTrieRecordList *it;
+
+	g_return_if_fail(priv != NULL);
+	g_return_if_fail(word != NULL);
+	g_return_if_fail(word[0] != '\0');
+
+	it = g_hash_table_lookup(priv->records_map, word);
+	if (it == NULL)
+		return;
+
+	/* see purple_trie_add */
+	purple_trie_states_cleanup(trie);
+
+	priv->records_total_size -= it->rec->word_len;
+	priv->records = purple_record_list_remove(priv->records, it);
+	g_hash_table_remove(priv->records_map, it->rec->word);
+
+	purple_memory_pool_free(priv->records_str_mempool, it->rec->word);
+	purple_memory_pool_free(priv->records_obj_mempool, it->rec);
+	purple_memory_pool_free(priv->records_obj_mempool, it);
 }
 
 /*******************************************************************************
@@ -636,6 +671,8 @@ purple_trie_init(GTypeInstance *instance
 	priv->states_mempool = purple_memory_pool_new();
 	purple_memory_pool_set_block_size(priv->states_mempool,
 		PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE);
+
+	priv->records_map = g_hash_table_new(g_str_hash, g_str_equal);
 }
 
 static void
@@ -643,6 +680,7 @@ purple_trie_finalize(GObject *obj)
 {
 	PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(obj);
 
+	g_hash_table_destroy(priv->records_map);
 	g_object_unref(priv->records_obj_mempool);
 	g_object_unref(priv->records_str_mempool);
 	g_object_unref(priv->states_mempool);
diff --git a/libpurple/trie.h b/libpurple/trie.h
--- a/libpurple/trie.h
+++ b/libpurple/trie.h
@@ -117,9 +117,23 @@ purple_trie_set_reset_on_match(PurpleTri
  * @data: The word-related data (may be %NULL).
  *
  * Adds a word to the trie.
+ *
+ * Returns: %TRUE if succeeded, %FALSE otherwise (possibly on duplicate)
+ */
+gboolean
+purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data);
+
+/**
+ * purple_trie_remove:
+ * @trie: The trie.
+ * @word: The word.
+ *
+ * Removes a word from the trie. Depending on used memory pool, this may not
+ * free allocated memory (that will be freed when destroying the whole
+ * collection), so use it wisely.
  */
 void
-purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data);
+purple_trie_remove(PurpleTrie *trie, const gchar *word);
 
 /**
  * purple_trie_replace:



More information about the Commits mailing list