# HG changeset patch # User Tomasz Wasilczyk # Date 1395792167 -3600 # Node ID 799b62769bd36315f00d50b01f2eef18ba580d79 # Parent 94f0de42866dd8995e129f3a4cbdd1ad85fbcdb3 Trie: implement search-and-replace (not yet tested) diff -r 94f0de42866d -r 799b62769bd3 libpurple/trie.c --- a/libpurple/trie.c Tue Mar 25 22:52:25 2014 +0100 +++ b/libpurple/trie.c Wed Mar 26 01:02:47 2014 +0100 @@ -22,6 +22,8 @@ #include "trie.h" +#include + #include "debug.h" #include "memorypool.h" @@ -49,6 +51,7 @@ struct _PurpleTrieRecord { const gchar *word; + guint word_len; gpointer data; }; @@ -171,7 +174,7 @@ /* Allocates a state and binds it to the parent. */ static PurpleTrieState * -purple_trie_state_new(PurpleTrie *trie, PurpleTrieState *parent, guchar letter) +purple_trie_state_new(PurpleTrie *trie, PurpleTrieState *parent, guchar character) { PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie); PurpleTrieState *state; @@ -200,7 +203,7 @@ return NULL; } - parent->children[letter] = state; + parent->children[character] = state; return state; } @@ -241,12 +244,12 @@ for (cur_len = 0; reclist != NULL; cur_len++) { for (it = reclist; it; it = it->next) { PurpleTrieRecord *rec = it->rec; - guchar letter = rec->word[cur_len]; + guchar character = rec->word[cur_len]; PurpleTrieState *prefix = it->extra_data; PurpleTrieState *lon_suf_parent; /* the whole word is already added to the trie */ - if (letter == '\0') { + if (character == '\0') { if (prefix->found_word == NULL) prefix->found_word = rec; else { @@ -263,15 +266,15 @@ /* word's prefix is already in the trie, added by the * other word */ - if (prefix->children && prefix->children[letter]) { - it->extra_data = prefix->children[letter]; + 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 letter. + * prefix is now of length increased by one character. */ - prefix = purple_trie_state_new(trie, prefix, letter); + prefix = purple_trie_state_new(trie, prefix, character); if (!prefix) { g_warn_if_reached(); g_object_unref(reclist_mpool); @@ -287,12 +290,13 @@ lon_suf_parent = prefix->parent->longest_suffix; while (lon_suf_parent) { if (lon_suf_parent->children && - lon_suf_parent->children[letter]) + lon_suf_parent->children[character]) { - prefix->longest_suffix = - lon_suf_parent->children[letter]; + prefix->longest_suffix = lon_suf_parent-> + children[character]; break; } + lon_suf_parent = lon_suf_parent->longest_suffix; } if (prefix->longest_suffix == NULL) prefix->longest_suffix = root; @@ -305,6 +309,66 @@ } /******************************************************************************* + * Searching + ******************************************************************************/ + +gchar * +purple_trie_replace(PurpleTrie *trie, const gchar *src, + PurpleTrieReplaceCb replace_cb, gpointer user_data) +{ + PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie); + PurpleTrieState *state; + gsize i = 0; + GString *out; + + if (src == NULL) + return NULL; + + g_return_val_if_fail(replace_cb != NULL, g_strdup(src)); + g_return_val_if_fail(priv != NULL, NULL); + + out = g_string_new(NULL); + state = priv->root_state; + while (src[i] != '\0') { + guchar character = src[i]; + + /* change state after processing a character */ + while (TRUE) { + /* Perfect fit - next character is the same, as the + * child of the prefix we reached so far. */ + if (state->children && state->children[character]) { + state = state->children[character]; + break; + } + + /* We reached root, that's a pity. */ + if (state == priv->root_state) + break; + + state = state->longest_suffix; + } + + /* if we reached a "found" state, let's process it */ + if (state->found_word) { + gboolean was_replaced; + + was_replaced = replace_cb(out, state->found_word->word, + state->found_word->data, user_data); + + if (was_replaced || priv->reset_on_match) { + i += state->found_word->word_len; + state = priv->root_state; + } else + i++; + } else + i++; + } + + return g_string_free(out, FALSE); +} + + +/******************************************************************************* * Records ******************************************************************************/ @@ -325,6 +389,7 @@ rec = purple_memory_pool_alloc(priv->records_obj_mempool, sizeof(PurpleTrieRecord), sizeof(gpointer)); rec->word = purple_memory_pool_strdup(priv->records_str_mempool, word); + rec->word_len = strlen(word); rec->data = data; priv->records = purple_record_list_prepend(priv->records_obj_mempool, diff -r 94f0de42866d -r 799b62769bd3 libpurple/trie.h --- a/libpurple/trie.h Tue Mar 25 22:52:25 2014 +0100 +++ b/libpurple/trie.h Wed Mar 26 01:02:47 2014 +0100 @@ -57,6 +57,22 @@ void (*purple_reserved4)(void); }; +/** + * PurpleTrieReplaceCb: + * @out: Currently built output string, append replacement to it. + * @word: Found word. + * @word_data: A user data bound with this word, when added with + * purple_trie_add(). + * @user_data: A user supplied data passed when calling purple_trie_replace(). + * + * A funtion called after every found matching substring to be replaced. + * + * Returns: %TRUE, if the word was replaced, %FALSE otherwise. In the second + * case you might possibly want to leave @out untouched. + */ +typedef gboolean (*PurpleTrieReplaceCb)(GString *out, const gchar *word, + gpointer word_data, gpointer user_data); + G_BEGIN_DECLS GType @@ -105,6 +121,22 @@ void purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data); +/** + * purple_trie_replace: + * @trie: The trie. + * @src: The source string. + * @replace_cb: The replacement function. + * @user_data: Custom data to be passed to @replace_cb. + * + * Looks for all occuriences of words added to @trie, in @src string. + * It's O(strlen(src)), if replace_cb runs in O(strlen(word)). + * + * Returns: resulting string. Must be g_free'd when you are done using it. + */ +gchar * +purple_trie_replace(PurpleTrie *trie, const gchar *src, + PurpleTrieReplaceCb replace_cb, gpointer user_data); + G_END_DECLS #endif /* PURPLE_MEMORY_POOL_H */