pidgin/pidgin

Add testsuite for PurpleTrie and fix found bugs

2014-03-26, Tomasz Wasilczyk
6527214c491e
Parents 33bfffdb9e63
Children 4a2cf3314f4b
Add testsuite for PurpleTrie and fix found bugs
6 files changed, 180 insertions(+), 27 deletions(-)
  • +1 -0
    .hgignore
  • +1 -0
    libpurple/tests/Makefile.am
  • +1 -0
    libpurple/tests/check_libpurple.c
  • +128 -0
    libpurple/tests/test_trie.c
  • +1 -0
    libpurple/tests/tests.h
  • +48 -27
    libpurple/trie.c
    • --- 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);