/pidgin/main: b4a35c405e95: Trie: states allocation
Tomasz Wasilczyk
twasilczyk at pidgin.im
Tue Mar 25 10:42:06 EDT 2014
Changeset: b4a35c405e9526f9a2ea3c5c961b5f2dc83490db
Author: Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date: 2014-03-25 15:41 +0100
Branch: default
URL: https://hg.pidgin.im/pidgin/main/rev/b4a35c405e95
Description:
Trie: states allocation
diffstat:
libpurple/memorypool.c | 49 +++++++++++++---
libpurple/memorypool.h | 21 +++++++
libpurple/trie.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++--
3 files changed, 200 insertions(+), 17 deletions(-)
diffs (truncated from 321 to 300 lines):
diff --git a/libpurple/memorypool.c b/libpurple/memorypool.c
--- a/libpurple/memorypool.c
+++ b/libpurple/memorypool.c
@@ -137,6 +137,23 @@ purple_memory_pool_alloc_impl(PurpleMemo
return mem;
}
+static void
+purple_memory_pool_cleanup_impl(PurpleMemoryPool *pool)
+{
+ PurpleMemoryPoolPrivate *priv = PURPLE_MEMORY_POOL_GET_PRIVATE(pool);
+ PurpleMemoryPoolBlock *blk;
+
+ g_return_if_fail(priv != NULL);
+
+ blk = priv->first_block;
+ while (blk) {
+ PurpleMemoryPoolBlock *next = blk->next;
+ g_free(blk);
+ blk = next;
+ }
+}
+
+
/*******************************************************************************
* API implementation
******************************************************************************/
@@ -191,6 +208,19 @@ purple_memory_pool_free(PurpleMemoryPool
klass->pfree(pool, mem);
}
+void
+purple_memory_pool_cleanup(PurpleMemoryPool *pool)
+{
+ PurpleMemoryPoolClass *klass;
+
+ g_return_if_fail(PURPLE_IS_MEMORY_POOL(pool));
+
+ klass = PURPLE_MEMORY_POOL_GET_CLASS(pool);
+ g_return_if_fail(klass != NULL);
+
+ klass->cleanup(pool);
+}
+
/*******************************************************************************
* Object stuff
@@ -212,18 +242,18 @@ purple_memory_pool_new(void)
return g_object_new(PURPLE_TYPE_MEMORY_POOL, NULL);
}
+PurpleMemoryPool *
+purple_memory_pool_new_sized(gulong block_size)
+{
+ return g_object_new(PURPLE_TYPE_MEMORY_POOL,
+ "block-size", block_size,
+ NULL);
+}
+
static void
purple_memory_pool_finalize(GObject *obj)
{
- PurpleMemoryPoolPrivate *priv = PURPLE_MEMORY_POOL_GET_PRIVATE(obj);
- PurpleMemoryPoolBlock *blk;
-
- blk = priv->first_block;
- while (blk) {
- PurpleMemoryPoolBlock *next = blk->next;
- g_free(blk);
- blk = next;
- }
+ purple_memory_pool_cleanup(PURPLE_MEMORY_POOL(obj));
G_OBJECT_CLASS(parent_class)->finalize(obj);
}
@@ -274,6 +304,7 @@ purple_memory_pool_class_init(PurpleMemo
obj_class->set_property = purple_memory_pool_set_property;
klass->palloc = purple_memory_pool_alloc_impl;
+ klass->cleanup = purple_memory_pool_cleanup_impl;
properties[PROP_BLOCK_SIZE] = g_param_spec_ulong("block-size",
"Block size", "The default size of each block of pool memory.",
diff --git a/libpurple/memorypool.h b/libpurple/memorypool.h
--- a/libpurple/memorypool.h
+++ b/libpurple/memorypool.h
@@ -53,6 +53,7 @@ struct _PurpleMemoryPoolClass
gpointer (*palloc)(PurpleMemoryPool *pool, gsize size, guint alignment);
gpointer (*pfree)(PurpleMemoryPool *pool, gpointer mem);
+ void (*cleanup)(PurpleMemoryPool *pool);
void (*purple_reserved1)(void);
void (*purple_reserved2)(void);
@@ -76,6 +77,16 @@ PurpleMemoryPool *
purple_memory_pool_new(void);
/**
+ * purple_memory_pool_new_sized:
+ *
+ * Creates a new memory pool with non-default block size.
+ *
+ * Returns: The new #PurpleMemoryPool.
+ */
+PurpleMemoryPool *
+purple_memory_pool_new_sized(gulong block_size);
+
+/**
* purple_memory_pool_alloc:
* @pool: The memory pool.
* @size: The size of memory to be allocated.
@@ -116,6 +127,16 @@ void
purple_memory_pool_free(PurpleMemoryPool *pool, gpointer mem);
/**
+ * purple_memory_pool_cleanup:
+ * @pool: The memory pool.
+ *
+ * Marks all memory allocated within a memory pool as not used. It may free
+ * resources, but don't have to.
+ */
+void
+purple_memory_pool_cleanup(PurpleMemoryPool *pool);
+
+/**
* purple_memory_pool_strdup:
* @pool: The memory pool.
* @str: The string to duplicate.
diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -27,14 +27,22 @@
#define PURPLE_TRIE_GET_PRIVATE(obj) \
(G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
+#define PURPLE_TRIE_STATES_POOL_BLOCK_SIZE 102400
+
typedef struct _PurpleTrieRecord PurpleTrieRecord;
+typedef struct _PurpleTrieState PurpleTrieState;
+typedef struct _PurpleTrieRecordList PurpleTrieRecordList;
typedef struct
{
gboolean reset_on_match;
- PurpleMemoryPool *records_mempool;
- GSList *records;
+ PurpleMemoryPool *records_str_mempool;
+ PurpleMemoryPool *records_obj_mempool;
+ PurpleTrieRecordList *records;
+
+ PurpleMemoryPool *states_mempool;
+ PurpleTrieState *root_state;
} PurpleTriePrivate;
struct _PurpleTrieRecord
@@ -43,6 +51,115 @@ struct _PurpleTrieRecord
gpointer data;
};
+struct _PurpleTrieRecordList
+{
+ PurpleTrieRecord *rec;
+ PurpleTrieRecordList *next;
+ PurpleTrieRecordList *prev;
+};
+
+struct _PurpleTrieState
+{
+ PurpleTrieState *parent;
+ PurpleTrieState **children;
+
+ PurpleTrieState *longest_suffix;
+
+ PurpleTrieRecord *found_word;
+};
+
+/*******************************************************************************
+ * Records list
+ ******************************************************************************/
+
+static PurpleTrieRecordList *
+purple_record_list_prepend(PurpleMemoryPool *mpool,
+ PurpleTrieRecordList *old_head, PurpleTrieRecord *rec)
+{
+ PurpleTrieRecordList *new_head;
+
+ new_head = purple_memory_pool_alloc(mpool,
+ sizeof(PurpleTrieRecordList), sizeof(gpointer));
+ new_head->rec = rec;
+ new_head->next = old_head;
+ old_head->prev = new_head;
+ new_head->prev = NULL;
+
+ return new_head;
+}
+
+/*******************************************************************************
+ * States management
+ ******************************************************************************/
+
+static void
+purple_trie_states_cleanup(PurpleTrie *trie)
+{
+ PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+
+ g_return_if_fail(priv != NULL);
+
+ if (priv->root_state != NULL) {
+ purple_memory_pool_cleanup(priv->states_mempool);
+ priv->root_state = NULL;
+ }
+}
+
+/* Allocates a state and binds it to the parent. */
+static PurpleTrieState *
+purple_trie_state_new(PurpleTrie *trie, PurpleTrieState *parent, guchar letter)
+{
+ PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+ PurpleTrieState *state;
+
+ g_return_val_if_fail(priv != NULL, NULL);
+
+ state = purple_memory_pool_alloc0(priv->states_mempool,
+ sizeof(PurpleTrieState), sizeof(gpointer));
+ g_return_val_if_fail(state != NULL, NULL);
+
+ if (parent == NULL)
+ return state;
+
+ state->parent = parent;
+ if (parent->children == NULL) {
+ parent->children = purple_memory_pool_alloc0(
+ priv->states_mempool,
+ /* PurpleTrieState *children[sizeof(guchar)] */
+ sizeof(guchar) * sizeof(gpointer),
+ sizeof(gpointer));
+ }
+
+ if (parent->children == NULL) {
+ purple_memory_pool_free(priv->states_mempool, state);
+ g_warn_if_reached();
+ return NULL;
+ }
+
+ parent->children[letter] = state;
+
+ return state;
+}
+
+static gboolean
+purple_trie_states_build(PurpleTrie *trie)
+{
+ PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
+ PurpleTrieState *root;
+
+ g_return_val_if_fail(priv != NULL, FALSE);
+
+ if (priv->root_state != NULL)
+ return TRUE;
+
+ priv->root_state = root = purple_trie_state_new(trie, NULL, '\0');
+ g_return_val_if_fail(root != NULL, FALSE);
+
+ /* XXX: TODO */
+
+ return TRUE;
+}
+
/*******************************************************************************
* Records
******************************************************************************/
@@ -56,11 +173,21 @@ purple_trie_add(PurpleTrie *trie, const
g_return_if_fail(priv != NULL);
g_return_if_fail(word != NULL);
- rec = g_new(PurpleTrieRecord, 1);
- rec->word = purple_memory_pool_strdup(priv->records_mempool, word);
+ /* Every change in a trie invalidates longest_suffix map.
+ * These prefixes could be updated instead of cleaning the whole graph.
+ */
+ 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->data = data;
- priv->records = g_slist_prepend(priv->records, rec);
+ 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);
}
/*******************************************************************************
@@ -113,7 +240,10 @@ purple_trie_init(GTypeInstance *instance
PurpleTrie *trie = PURPLE_TRIE(instance);
PurpleTriePrivate *priv = PURPLE_TRIE_GET_PRIVATE(trie);
More information about the Commits
mailing list