pidgin3: comparison libpurple/trie.c

-:94f0de42866d
+:799b62769bd3
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA
 */
 #include "trie.h"
+#include <string.h>
 #include "debug.h"
 #include "memorypool.h"
 #define PURPLE_TRIE_GET_PRIVATE(obj) \
 	(G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
 } PurpleTriePrivate;
 struct _PurpleTrieRecord
 {
 	const gchar *word;
+	guint word_len;
 	gpointer data;
 };
 struct _PurpleTrieRecordList
 {
 	}
 }
 /* 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;
 	g_return_val_if_fail(priv != NULL, NULL);
 		purple_memory_pool_free(priv->states_mempool, state);
 		g_warn_if_reached();
 		return NULL;
 	}
-	parent->children[letter] = state;
+	parent->children[character] = state;
 	return state;
 }
 static gboolean
 	 * index of all remaining words. Loop finishes when there are no words
 	 * longer than cur_len. */
 	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 {
 					purple_debug_warning("trie", "found "
 						"a collision of \"%s\" words",
 				continue;
 			}
 			/* word's prefix is already in the trie, added by the
 			 * other word */
-			if (prefix->children && prefix->children[letter]) {
+			if (prefix->children && prefix->children[character]) {
-				it->extra_data = prefix->children[letter];
+				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);
 				return FALSE;
 			}
 			 * in the (cur_len - 1) level of trie. */
 			g_assert(prefix->longest_suffix == NULL);
 			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 =
+					prefix->longest_suffix = lon_suf_parent->
-						lon_suf_parent->children[letter];
+						children[character];
 					break;
 				}
+				lon_suf_parent = lon_suf_parent->longest_suffix;
 			}
 			if (prefix->longest_suffix == NULL)
 				prefix->longest_suffix = root;
 		}
 	}
 	return TRUE;
 }
 /*******************************************************************************
+* 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
 ******************************************************************************/
 void
 purple_trie_add(PurpleTrie *trie, const gchar *word, gpointer data)
 	purple_trie_states_cleanup(trie);
 	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,
 		priv->records, rec);

Mercurial > pidgin3 / file comparison

comparison: libpurple/trie.c

libpurple/trie.c