/pidgin/main: 6527214c491e: Add testsuite for PurpleTrie and fix...
Tomasz Wasilczyk
twasilczyk at pidgin.im
Wed Mar 26 09:24:28 EDT 2014
Changeset: 6527214c491ee3c93c5a65835acbce022f3cc88d
Author: Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date: 2014-03-26 14:24 +0100
Branch: default
URL: https://hg.pidgin.im/pidgin/main/rev/6527214c491e
Description:
Add testsuite for PurpleTrie and fix found bugs
diffstat:
.hgignore | 1 +
libpurple/tests/Makefile.am | 1 +
libpurple/tests/check_libpurple.c | 1 +
libpurple/tests/test_trie.c | 128 ++++++++++++++++++++++++++++++++++++++
libpurple/tests/tests.h | 1 +
libpurple/trie.c | 75 ++++++++++++++--------
6 files changed, 180 insertions(+), 27 deletions(-)
diffs (truncated from 313 to 300 lines):
diff --git a/.hgignore b/.hgignore
--- a/.hgignore
+++ b/.hgignore
@@ -83,6 +83,7 @@ libpurple/plugins/perl/common/lib
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$
diff --git a/libpurple/tests/Makefile.am b/libpurple/tests/Makefile.am
--- a/libpurple/tests/Makefile.am
+++ b/libpurple/tests/Makefile.am
@@ -15,6 +15,7 @@ check_libpurple_SOURCES=\
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 \
diff --git a/libpurple/tests/check_libpurple.c b/libpurple/tests/check_libpurple.c
--- a/libpurple/tests/check_libpurple.c
+++ b/libpurple/tests/check_libpurple.c
@@ -92,6 +92,7 @@ int main(void)
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();
diff --git a/libpurple/tests/test_trie.c b/libpurple/tests/test_trie.c
new file mode 100644
--- /dev/null
+++ b/libpurple/tests/test_trie.c
@@ -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;
+}
diff --git a/libpurple/tests/tests.h b/libpurple/tests/tests.h
--- a/libpurple/tests/tests.h
+++ b/libpurple/tests/tests.h
@@ -17,6 +17,7 @@ Suite * oscar_util_suite(void);
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) { \
diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -254,6 +254,7 @@ purple_trie_states_build(PurpleTrie *tri
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 @@ purple_trie_states_build(PurpleTrie *tri
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 @@ purple_trie_states_build(PurpleTrie *tri
/* 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 @@ purple_trie_states_build(PurpleTrie *tri
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 @@ purple_trie_states_build(PurpleTrie *tri
/* "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 @@ purple_trie_states_build(PurpleTrie *tri
}
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 @@ purple_trie_replace(PurpleTrie *trie, co
More information about the Commits
mailing list