Mercurial > pidgin3 / changeset

--- a/.hgignore	Wed Mar 26 13:12:16 2014 +0100
+++ b/.hgignore	Wed Mar 26 14:24:19 2014 +0100
@@ -83,6 +83,7 @@
 libpurple/purple-client-bindings.[ch]
 libpurple/purple-client-example
 libpurple/purple.h$
+libpurple/tests/core
 libpurple/tests/check_libpurple
 libpurple/tests/libpurple..
 ^libpurple/tests/test-suite\.log$

--- a/libpurple/tests/Makefile.am	Wed Mar 26 13:12:16 2014 +0100
+++ b/libpurple/tests/Makefile.am	Wed Mar 26 14:24:19 2014 +0100
@@ -15,6 +15,7 @@
 		test_jabber_jutil.c \
 		test_jabber_scram.c \
 		test_oscar_util.c \
+		test_trie.c \
 		test_yahoo_util.c \
 		test_util.c \
 		test_xmlnode.c \

--- a/libpurple/tests/check_libpurple.c	Wed Mar 26 13:12:16 2014 +0100
+++ b/libpurple/tests/check_libpurple.c	Wed Mar 26 14:24:19 2014 +0100
@@ -92,6 +92,7 @@
 	srunner_add_suite(sr, yahoo_util_suite());
 	srunner_add_suite(sr, util_suite());
 	srunner_add_suite(sr, purple_xmlnode_suite());
+	srunner_add_suite(sr, purple_trie_suite());
 
 	/* make this a libpurple "ui" */
 	purple_check_init();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/libpurple/tests/test_trie.c	Wed Mar 26 14:24:19 2014 +0100
@@ -0,0 +1,128 @@
+#include <string.h>
+
+#include "tests.h"
+#include "../trie.h"
+
+static gboolean
+test_trie_replace_cb(GString *out, const gchar *word, gpointer word_data,
+	gpointer user_data)
+{
+	/* the "test" word */
+	if ((int)word_data == 0x1001)
+		return FALSE;
+
+	g_string_append_printf(out, "[%d:%x]", (int)user_data, (int)word_data);
+
+	return TRUE;
+}
+
+START_TEST(test_trie_replace)
+{
+	PurpleTrie *trie;
+	const gchar *in;
+	gchar *out;
+
+	trie = purple_trie_new();
+
+	purple_trie_add(trie, "test", (gpointer)0x1001);
+	purple_trie_add(trie, "testing", (gpointer)0x1002);
+	purple_trie_add(trie, "overtested", (gpointer)0x1003);
+	purple_trie_add(trie, "trie", (gpointer)0x1004);
+	purple_trie_add(trie, "tree", (gpointer)0x1005);
+	purple_trie_add(trie, "implement", (gpointer)0x1006);
+	purple_trie_add(trie, "implementation", (gpointer)0x1007);
+
+	in = "Alice is testing her trie implementation, "
+		"but she's far away from making test tree overtested";
+
+	out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)7);
+
+	assert_string_equal("Alice is [7:1002] her [7:1004] [7:1006]ation,"
+		" but she's far away from making test [7:1005] [7:1003]", out);
+
+	g_object_unref(trie);
+	g_free(out);
+}
+END_TEST
+
+START_TEST(test_trie_replace_whole)
+{
+	PurpleTrie *trie;
+	const gchar *in;
+	gchar *out;
+
+	trie = purple_trie_new();
+
+	purple_trie_add(trie, "test", (gpointer)0x2002);
+
+	in = "test";
+
+	out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)5);
+
+	assert_string_equal("[5:2002]", out);
+
+	g_object_unref(trie);
+	g_free(out);
+}
+END_TEST
+
+START_TEST(test_trie_replace_inner)
+{
+	PurpleTrie *trie;
+	const gchar *in;
+	gchar *out;
+
+	trie = purple_trie_new();
+
+	purple_trie_add(trie, "est", (gpointer)0x3001);
+	purple_trie_add(trie, "tester", (gpointer)0x3002);
+
+	in = "the test!";
+
+	out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)3);
+
+	assert_string_equal("the t[3:3001]!", out);
+
+	g_object_unref(trie);
+	g_free(out);
+}
+END_TEST
+
+START_TEST(test_trie_replace_empty)
+{
+	PurpleTrie *trie;
+	const gchar *in;
+	gchar *out;
+
+	trie = purple_trie_new();
+
+	purple_trie_add(trie, "", (gpointer)0x4001);
+	purple_trie_add(trie, "test", (gpointer)0x4002);
+
+	in = "the test!";
+
+	out = purple_trie_replace(trie, in, test_trie_replace_cb, (gpointer)2);
+
+	assert_string_equal("[2:4001][2:4001][2:4001][2:4001][2:4001][2:4001]"
+		"[2:4001][2:4001][2:4001]", out);
+
+	g_object_unref(trie);
+	g_free(out);
+}
+END_TEST
+
+Suite *
+purple_trie_suite(void)
+{
+	Suite *s = suite_create("PurpleTrie class");
+
+	TCase *tc = tcase_create("trie");
+	tcase_add_test(tc, test_trie_replace);
+	tcase_add_test(tc, test_trie_replace_whole);
+	tcase_add_test(tc, test_trie_replace_inner);
+	tcase_add_test(tc, test_trie_replace_empty);
+
+	suite_add_tcase(s, tc);
+
+	return s;
+}

--- a/libpurple/tests/tests.h	Wed Mar 26 13:12:16 2014 +0100
+++ b/libpurple/tests/tests.h	Wed Mar 26 14:24:19 2014 +0100
@@ -17,6 +17,7 @@
 Suite * yahoo_util_suite(void);
 Suite * util_suite(void);
 Suite * purple_xmlnode_suite(void);
+Suite * purple_trie_suite(void);
 
 /* helper macros */
 #define assert_int_equal(expected, actual) { \

--- a/libpurple/trie.c	Wed Mar 26 13:12:16 2014 +0100
+++ b/libpurple/trie.c	Wed Mar 26 14:24:19 2014 +0100
@@ -254,6 +254,7 @@
 	PurpleMemoryPool *reclist_mpool;
 	PurpleTrieRecordList *reclist, *it;
 	gulong cur_len;
+	PurpleTrieRecordList *empty_word = NULL;
 
 	g_return_val_if_fail(priv != NULL, FALSE);
 
@@ -262,9 +263,7 @@
 
 	priv->root_state = root = purple_trie_state_new(trie, NULL, '\0');
 	g_return_val_if_fail(root != NULL, FALSE);
-	/* I don't think we need this assignment:
-	 * root->longest_suffix = root;
-	 */
+	g_assert(root->longest_suffix == NULL);
 
 	/* reclist is a list of words not yet added to the trie. Shorter words
 	 * are removed from the list, when they are fully added to the trie. */
@@ -273,8 +272,17 @@
 
 	/* extra_data on every element of reclist will be a pointer to a trie
 	 * node -- the prefix of the word with len of cur_len */
-	for (it = reclist; it != NULL; it = it->next)
+	for (it = reclist; it != NULL; it = it->next) {
 		it->extra_data = root;
+		if (it->rec->word_len == 0)
+			empty_word = it;
+	}
+
+	/* a special case for the empty word */
+	if (empty_word) {
+		root->found_word = empty_word->rec;
+		reclist = purple_record_list_remove(reclist, empty_word);
+	}
 
 	/* Iterate over indexes of words -- every loop iteration checks certain
 	 * index of all remaining words. Loop finishes when there are no words
@@ -286,8 +294,33 @@
 			PurpleTrieState *prefix = it->extra_data;
 			PurpleTrieState *lon_suf_parent;
 
-			/* the whole word is already added to the trie */
 			if (character == '\0') {
+				purple_debug_warning("trie", "found "
+					"a collision of empty words");
+				/* it->next is still valid, see below */
+				reclist = purple_record_list_remove(reclist, it);
+				continue;
+			}
+
+			if (prefix->children && prefix->children[character]) {
+				/* Word's prefix is already in the trie, added
+				 * by the other word. */
+				prefix = prefix->children[character];
+			} else {
+				/* We need to create a new branch of trie. */
+				prefix = purple_trie_state_new(trie, prefix,
+					character);
+				if (!prefix) {
+					g_warn_if_reached();
+					g_object_unref(reclist_mpool);
+					return FALSE;
+				}
+			}
+			it->extra_data = prefix;
+			/* prefix is now of length increased by one character. */
+
+			/* The whole word is now added to the trie. */
+			if (rec->word[cur_len + 1] == '\0') {
 				if (prefix->found_word == NULL)
 					prefix->found_word = rec;
 				else {
@@ -299,32 +332,14 @@
 				/* "it" is not modified here, so it->next is
 				 * still valid */
 				reclist = purple_record_list_remove(reclist, it);
-				continue;
 			}
 
-			/* word's prefix is already in the trie, added by the
-			 * other word */
-			if (prefix->children && prefix->children[character]) {
-				it->extra_data = prefix->children[character];
-				continue;
-			}
-
-			/* We need to create a new branch of trie.
-			 * prefix is now of length increased by one character.
-			 */
-			prefix = purple_trie_state_new(trie, prefix, character);
-			if (!prefix) {
-				g_warn_if_reached();
-				g_object_unref(reclist_mpool);
-				return FALSE;
-			}
-			it->extra_data = prefix;
-
 			/* We need to fill the longest_suffix field -- a longest
 			 * complete suffix of the prefix we created. We look for
 			 * that suffix in any path starting in root and ending
 			 * in the (cur_len - 1) level of trie. */
-			g_assert(prefix->longest_suffix == NULL);
+			if (prefix->longest_suffix != NULL)
+				continue;
 			lon_suf_parent = prefix->parent->longest_suffix;
 			while (lon_suf_parent) {
 				if (lon_suf_parent->children &&
@@ -338,6 +353,10 @@
 			}
 			if (prefix->longest_suffix == NULL)
 				prefix->longest_suffix = root;
+			if (prefix->found_word == NULL) {
+				prefix->found_word =
+					prefix->longest_suffix->found_word;
+			}
 		}
 	}
 
@@ -395,9 +414,11 @@
 			gsize str_old_len;
 
 			/* let's get back to the beginning of the word */
-			g_assert(out->len >= state->found_word->word_len - 1);
 			str_old_len = out->len;
-			out->len -= state->found_word->word_len - 1;
+			if (state->found_word->word_len > 0) {
+				g_assert(out->len >= state->found_word->word_len - 1);
+				out->len -= state->found_word->word_len - 1;
+			}
 
 			was_replaced = replace_cb(out, state->found_word->word,
 				state->found_word->data, user_data);