/pidgin/main: 33bfffdb9e63: Trie, memory pool: fix and make them...
Tomasz Wasilczyk
twasilczyk at pidgin.im
Wed Mar 26 08:12:26 EDT 2014
Changeset: 33bfffdb9e632be83353759023524dc86cad2188
Author: Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date: 2014-03-26 13:12 +0100
Branch: default
URL: https://hg.pidgin.im/pidgin/main/rev/33bfffdb9e63
Description:
Trie, memory pool: fix and make them actually working
diffstat:
libpurple/memorypool.c | 6 +-
libpurple/trie.c | 88 ++++++++++++++++++++++++++++++++++---------------
libpurple/trie.h | 2 +-
3 files changed, 64 insertions(+), 32 deletions(-)
diffs (196 lines):
diff --git a/libpurple/memorypool.c b/libpurple/memorypool.c
--- a/libpurple/memorypool.c
+++ b/libpurple/memorypool.c
@@ -30,7 +30,7 @@
#define PURPLE_MEMORY_POINTER_SHIFT(pointer, value) \
(gpointer)((guintptr)(pointer) + (value))
#define PURPLE_MEMORY_PADDED(pointer, padding) \
- (gpointer)(((guintptr)(pointer) - 1) % (padding) + 1)
+ (gpointer)((((guintptr)(pointer) - 1) / (padding) + 1) * padding)
#define PURPLE_MEMORY_POOL_DEFAULT_BLOCK_SIZE 1024
@@ -77,8 +77,7 @@ purple_memory_pool_block_new(gulong bloc
block->available_ptr = PURPLE_MEMORY_POINTER_SHIFT(block_raw,
sizeof(PurpleMemoryPoolBlock));
block->end_ptr = PURPLE_MEMORY_POINTER_SHIFT(block_raw, total_size);
-
- memset(block, 0, sizeof(PurpleMemoryPoolBlock));
+ block->next = NULL;
return block;
}
@@ -92,6 +91,7 @@ purple_memory_pool_alloc_impl(PurpleMemo
g_return_val_if_fail(priv != NULL, NULL);
+ g_return_val_if_fail(alignment <= PURPLE_MEMORY_POOL_BLOCK_PADDING, NULL);
g_warn_if_fail(alignment >= 1);
if (alignment < 1)
alignment = 1;
diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -83,7 +83,7 @@ purple_record_list_new(PurpleMemoryPool
{
PurpleTrieRecordList *node;
- node = purple_memory_pool_alloc(mpool,
+ node = purple_memory_pool_alloc0(mpool,
sizeof(PurpleTrieRecordList), sizeof(gpointer));
g_return_val_if_fail(node != NULL, NULL);
@@ -102,8 +102,8 @@ purple_record_list_prepend(PurpleMemoryP
g_return_val_if_fail(new_head != NULL, NULL);
new_head->next = old_head;
- old_head->prev = new_head;
- new_head->prev = NULL;
+ if (old_head)
+ old_head->prev = new_head;
return new_head;
}
@@ -192,8 +192,8 @@ purple_trie_state_new(PurpleTrie *trie,
if (parent->children == NULL) {
parent->children = purple_memory_pool_alloc0(
priv->states_mempool,
- /* PurpleTrieState *children[sizeof(guchar)] */
- sizeof(guchar) * sizeof(gpointer),
+ /* PurpleTrieState *children[G_MAXUCHAR + 1] */
+ 256 * sizeof(gpointer),
sizeof(gpointer));
}
@@ -208,6 +208,44 @@ purple_trie_state_new(PurpleTrie *trie,
return state;
}
+#if 0
+static gchar *
+purple_trie_print(PurpleTrieState *state, int limit)
+{
+ GString *str = g_string_new(NULL);
+ int i;
+
+ if (limit < 0)
+ return g_strdup("{ LIMIT }");
+
+ if (state->found_word)
+ g_string_append(str, "*");
+ g_string_append(str, "{ ");
+ for (i = 0; i < 256; i++) {
+ gchar *chp;
+ if (!state->children)
+ continue;
+ if (!state->children[i])
+ continue;
+ if (i == 0)
+ g_string_append(str, "(null)->");
+ else
+ g_string_append_printf(str, "%c->", i);
+ if (state->children[i] == state)
+ g_string_append(str, "loop");
+ else {
+ chp = purple_trie_print(state->children[i], limit - 1);
+ g_string_append(str, chp);
+ g_string_append_c(str, ' ');
+ g_free(chp);
+ }
+ }
+ g_string_append(str, "}");
+
+ return g_string_free(str, FALSE);
+}
+#endif
+
static gboolean
purple_trie_states_build(PurpleTrie *trie)
{
@@ -327,11 +365,13 @@ purple_trie_replace(PurpleTrie *trie, co
g_return_val_if_fail(replace_cb != NULL, g_strdup(src));
g_return_val_if_fail(priv != NULL, NULL);
+ purple_trie_states_build(trie);
+
out = g_string_new(NULL);
state = priv->root_state;
while (src[i] != '\0') {
- guchar character = src[i];
- gboolean copy_char;
+ guchar character = src[i++];
+ gboolean was_replaced = FALSE;
/* change state after processing a character */
while (TRUE) {
@@ -351,35 +391,30 @@ purple_trie_replace(PurpleTrie *trie, co
}
/* if we reached a "found" state, let's process it */
- copy_char = FALSE;
if (state->found_word) {
- gboolean was_replaced;
+ 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;
was_replaced = replace_cb(out, state->found_word->word,
state->found_word->data, user_data);
- if (was_replaced || priv->reset_on_match) {
- if (!was_replaced) {
- g_string_append_len(out,
- state->found_word->word,
- state->found_word->word_len);
- }
+ /* output string was untouched, rollback to the
+ * previous position*/
+ if (!was_replaced)
+ out->len = str_old_len;
- /* skip a whole word, not a character */
- i += state->found_word->word_len;
-
+ if (was_replaced || priv->reset_on_match)
state = priv->root_state;
- } else
- copy_char = TRUE;
- } else
- copy_char = TRUE;
+ }
/* We skipped a character without finding any records,
* let's just copy it to the output. */
- if (copy_char) {
+ if (!was_replaced)
g_string_append_c(out, character);
- i++;
- }
}
return g_string_free(out, FALSE);
@@ -412,9 +447,6 @@ purple_trie_add(PurpleTrie *trie, const
priv->records = purple_record_list_prepend(priv->records_obj_mempool,
priv->records, rec);
-
- /* XXX: it won't be called here (it's inefficient), but in search function */
- purple_trie_states_build(trie);
}
/*******************************************************************************
diff --git a/libpurple/trie.h b/libpurple/trie.h
--- a/libpurple/trie.h
+++ b/libpurple/trie.h
@@ -68,7 +68,7 @@ struct _PurpleTrieClass
* 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.
+ * case you must not modify @out.
*/
typedef gboolean (*PurpleTrieReplaceCb)(GString *out, const gchar *word,
gpointer word_data, gpointer user_data);
More information about the Commits
mailing list